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

Главная  

О кафедре  

Программы  

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

Публикации  

Гранты  

Экзамены  

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

:: Программы

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

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

3 семестр

Лекции

ЛЕКЦИЯ 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.