Математическая логика и теория алгоритмов.

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ.

КУРС ЛЕКЦИЙ (34 ЧАСА, 17 ЛЕКЦИЙ).

I. Исчисление высказываний. (10 часов, 5 лекций).

1. Высказывания. Логические связки. Простые и составные высказывания. Формулы. Истинностные таблицы и совершенные нормальные формы (сложных) высказываний. Равносильные высказывания. Основные тождества с высказываниями. Тавтологии. Противоречия. Логическое следование.

2. Аксиомы ИВ. Вывод, теорема, правила вывода в ИВ. Теоремы и тавтологии, непротиворечивость ИВ. Теоремы и метатеоремы. Примеры доказательств теорем в ИВ.

3. Гипотезы, следствие из гипотез, вывод следствия. Теорема дедукции для ИВ. Примеры доказательств теорем ИВ и выводов следствий из гипотез с помощью Теоремы дедукции для.

4. Теорема о полноте ИВ.

5. Метод резолюций в ИВ. Метод резолюций для хорновских дизъюнктов.

II. Исчисление предикатов и аксиоматические теории 1-ого порядка. (14 часов, 7 лекций).

6. Язык логики предикатов. Правильные подстановки термов в формулы.

7. Интерпретации, выполнимость формул логики предикатов, истинность, модели. Общезначимость.

8. Предваренная форма. Введение новых функциональных букв и констант.

9. Аксиомы ИП. Вывод, теорема, правила вывода в ИП. Теорема дедукции для ИП.

10. Теории первого порядка, их свойства. Примеры теорий первого порядка. Метаматематика. Предметный язык и метаязык. Метатеоремы. Понятия непротиворечивости и полноты формальной аксиоматической теории.

11. Метод резолюций для ИП.

12. Теорема о существовании модели. Теорема Геделя о полноте.

III. Разрешимость, вычислимость, алгоритмы. (4 часа, 2 лекции).

13. Разрешимость и вычислимость. Тезис Черча. Рекурсивные функции. Машины Тьюринга.

14. Теорема Черча. Теорема Геделя о неполноте. Вторая теорема Геделя.

IV. Сложность алгоритмов и NP – полные задачи. (6 часов, 3 лекции).

15. Временная оценка сложности алгоритма. Размер индивидуальной задачи и скорость роста сложности алгоритма. Асимптотические оценки. Полиномиальные и экспоненциальные алгоритмы. Понятие эффективности алгоритма. Задачи распознавания. Классы (задач) Р и NP.

16. Полиномиальное сведение. NP – полные задачи. Дополнения задач. Предполагаемая структура класса NP. NP – трудные задачи.

17. Приближенное решение NP – полных задач. Метод ветвей и границ. Динамическое программирование. Алгоритмы локального поиска. Стохастические алгоритмы. Использование эвристик.

Дата добавления: 2015-08-28