МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)

Главная  

О кафедре  

Программы  

Учебные пособия  

Публикации  

Гранты  

Экзамены  

Труды семинара  

:: Программы

Математика » 2 факультет » КТ(ИВТ) Мат. лог. и теор. алг. » Полная программа

» Версия для печати

5 семестр

Лекции

ЛЕКЦИЯ 1-2. Логика высказываний (ЛВ). Операции над высказываниями. Таблица истинности. Алгебра высказываний. Формулы ЛВ. Тождественная истинность (ложность) формул ЛВ. Основные равносильные формулы ЛВ. Проблема разрешимости в ЛВ. Специальные виды формул ЛВ — ДНФ, КНФ, СДНФ, СКНФ. Построение семантического дерева формулы ЛВ. Применение ЛВ к решению логических задач. Семантическое дерево.

ЛЕКЦИЯ 3-4. Схемы из функциональных элементов. Контактные схемы. Исчисление высказываний (ИВ). Формулы ИВ. Секвенции. Правила вывода ИВ. Связь между формулами ЛВ и ИВ. Метод резолюций.

ЛЕКЦИЯ 5. Логика предикатов (ЛП). Операции над предикатами и кванторами. Область истинности. Формулы логики предикатов. Равносильные формулы ЛП. Нормальная и предваренная нормальная форма формулы ЛП. Общезначимость и выполнимость формул ЛП. Проблема разрешимости ЛП. Применение языка ЛП в математике.

ЛЕКЦИЯ 6. Нечеткая логика. Нечеткие высказывания, нечеткие предикаты.

ЛЕКЦИЯ 7-8. Понятие алгоритма. Машины Тьюринга и операции над ними. Вычислимые функции. Простейшие функции. Частично рекурсивные функции. Операции суперпозиции и примитивной рекурсии. Рекурсивные функции. Операция минимизации. Алгоритмически неразрешимые проблемы. Тезис Черча.

Практика

ЗАНЯТИЕ 1. Операции над высказываниями (отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность, неравнозначность). Таблица истинности.

ЗАНЯТИЕ 2. Нахождение ДНФ, КНФ, СДНФ, СКНФ формул логики высказываний. Построение семантического дерева.

ЗАНЯТИЕ 3. Схемы из функциональных элементов. Контактные схемы.

ЗАНЯТИЕ 4. Решение логических задач. Метод резолюций.

ЗАНЯТИЕ 5. Нахождение области истинности предикатов. Нахождение предваренной нормальной формы предикатных формул.

ЗАНЯТИЕ 6. Нечеткие высказывания, нечеткие предикаты.

ЗАНЯТИЕ 7. Построение программ для машины Тьюринга.

ЗАНЯТИЕ 8. Операции суперпозиции, примитивной рекурсии и минимизации.

Лабораторные

ЗАНЯТИЕ 1-2. Построение таблиц истинности, нахождение СДНФ, СКНФ. Приведение формул логики высказываний к ДНФ, КНФ. Построение семантического дерева.

ЗАНЯТИЕ 3-4. Решение логических задач. Метод резолюций.

ЗАНЯТИЕ 5-6. Нахождение области истинности предикатов. Нахождение предваренной нормальной формы предикатных формул.

ЗАНЯТИЕ 7-8. Написание программы машины Тьюринга, правильно вычисляющей заданную функцию. Построение функции с помощью операций примитивной рекурсии и минимизации.

Курсовые работы

Курсовых работ нет.

Рекомендуемая литература

1. Агарева О. Ю., Селиванов Ю. В. Математическая логика и теория алгоритмов. Учебное пособие. М., МАТИ, 2011, 1–80.

2. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М., Физматлит, 2009.

3. Гуц А. К. Математическая логика и теория алгоритмов. М, Либроком, 2009.

4. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., Физматлит, 2009.

5. Шапорев С. Д. Математическая логика. Курс лекций и практических занятий. СПб., БХВ-Петербург, 2009.

Дополнительная литература:

1. Агарева О. Ю., Выск Н. Д. Математическая логика и теория алгоритмов. Методические указания и варианты курсовых заданий, М., МАТИ, Каф. "Высш. мат.", 2011, 1–48.

2. Зюзьков В. М., Шелупанов А. А. Математическая логика и теория алгоритмов. М., Горячая линия — Телеком, 2007.

3. Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов. М., Академия, 2008.

4. Колмогоров А. Н., Драгалин А. Г. Математическая логика. М., Физматлит, 2006.

5. Москинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях. М., Логос, 2007.

6. Тишин В. В. Дискретная математика в примерах и задачах. СПб., БХВ-Петербург, 2008.