Категория: Другое

Глава 1. Математическая логика (18 часов).

1.1. Что изучает логика и математическая логика? Компоненты формальных теорий. Что такое высказывание? Логические операции (связки: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция).

1.2. Формулы логики высказываний (подформулы). Интерпретация формул. Таблицы истинности для формул.

1.3. Выполнимые и опровержимые формулы. Тождественно-истинные и тождественно-ложные формулы (тавтологии и противоречия). Теоремы 1 и 2 «о тавтологиях». Наиболее важные тавтологии. Примеры тавтологий и противоречий.

1.4. Логическая эквивалентность – равносильность формул. Основные равносильности (правила равносильных преобразований). Правило подстановки. Теоремы 1,2,3 «о равносильностях».

1.5. Формальные теории (ФТ). Состав формальной теории Γ. Выводимость формул: определения «выводимой формулы», «вывода», «теоремы», свойства «сохранения выводимости при добавлении лишних гипотез», интерпретации и «модели множества формул», «модели ФТ».

1.6. Общезначимость, непротиворечивость, полнота, независимость и разрешимость теории Г: определения общезначимой (тавтологии) и противоречивой формул, формулы «логического следствия» множества формул Г, определения «семантически и формально непротиворечивых» теории Г. Формулировки «метатеорем» о «семантически и формально непротиворечивых» теориях Г (без доказательства). Определения «полной» теории Г, «аксиоматизируемого» множества формул F, «независимой» системы аксиом, «разрешимой и полуразрешимой» теории Г.

1.7. Исчисление высказываний – формальная теория L: определение ИВ (ее состав). Определения: «формула В - частный случай формулы А», унификатор, «формула С - совместный частный случай формул А и В», унифицируемые формулы и наиболее общий унификатор, частный случай набора формул и совместный частный случай набора формул.

1.8. Различные аксиоматизации ИВ: Аксиомы Клини. Доказательство Теоремы 1: . Доказательство Теоремы 2:  и ее смысл (производное правило – правило «введения импликации»).

1.9. Доказательство Теоремы «дедукции»: если , то   и обратно.

1.10. Применимость правила дедукции для более широкого класса ФТ. Следствие 1: если , то и обратно (доказательство). Следствие 2: правило «транзитивности» . Следствие 3: правило «сечения» . Доказательство следствий.

1.11. Некоторые важные теоремы ИВ: ТЕОРЕМЫ (а, б, в, г, д, е, ж): их доказательство.

1.12. Множество теорем ИВ: доказательство леммы .

1.13. Множество теорем ИВ: доказательство теоремы   и Следствия: Теория L – формально непротиворечива.

1.14. Исчисление предикатов (ИП) – формальная теория К: определение и состав ИП. Свободное и связанное вхождение переменных в формулы. Контрарные литералы. Определение «свободного терма» в формуле, «чистого и прикладного ИП»

1.15. Интерпретация ИП: определение, свойства интерпретации (11 свойств, в том числе определения истинной и открытой формул, модели множества формул).

1.16. Общезначимость: определение и две теоремы (без доказательства). Метатеоремы 1, 2 о полноте ЧИП (без доказательства).

1.17. Определения «логического следования» и «логической эквивалентности». Некоторые следствия и эквивалентности (9 случаев).

1.18. Теория равенства: определение и 3 теоремы. Вывод.

1.19. Формальная арифметика (аксиоматика).

1.20. Теория абелевых групп (АГ): определения АГ конечного порядка, полной АГ, периодической АГ. Формулировки 2-х Метатеорем Геделя о «неполноте» ПИП 1-го порядка. Вывод из теорем.

1.21. Автоматическое доказательство теорем (АДТ): постановка задачи, теорема «доказательство от противного» (как основа метода «резолюции»): если , где F- противоречие, то .

1.22. Сведение формул ИП к предложениям. Теорема «о невыполнимости множества предложений, полученных из противоречия».

1.23. Правило резолюции (ПР) для ИВ. Теорема (с док-вом): «ПР логично, т.е. резольвента – логическое следствие резольвируемых предложений».

1.24. Правило резолюции для ИП.

1.25. Алгоритм АДТ: «опровержение методом резолюций» (3 возможных случая). Вывод в отношении ИП на основании 3-го случая. Пример доказательства (из семинарского занятия) теорем ИВ по алгоритму АДТ «опровержение методом резолюций».

ГЛАВА 2. ТЕОРИЯ АЛГОРИТМОВ (8 часов).

2.1. Понятие алгоритма и неформальной вычислимости: определения и основные особенности алгоритма.

2.2. Подход Геделя-Клини к формализации понятия алгоритма: Частично-рекурсивные функции (ЧРФ): операторы суперпозиции, примитивной рекурсии, минимизации для построения ЧРФ.

2.3. Примеры рекурсивности (примитивно-рекурсивных и общерекурсивных функций)

2.4. Подход А. Черча: Ламбда-исчисление. Его особенности. λ - выражения и их вычисления.

2.5. Определение λ-термов и λ-выражений. σ-редекс и β- редекс. Процесс редукции. Примеры редукций.

2.6. Нормальные формы λ-выражений и порядок редукций: аппликативный (АПР- стратегия энергичных вычислений) и нормальный (НПР- стратегия ленивых вычислений) порядок редукций. Следствие из теоремы Черча-Россера.

2.7. Рекурсивные функции. Комбинатор неподвижной точки.

2.8. Чистое λ-исчисление.

2.9. Машины Тьюринга.

2.10. Другие подходы к определению понятия алгоритма. Тезис Черча.

2.11. Алгоритмически неразрешимые проблемы.

2.12. Сложность алгоритмов: в наихудшем случае и поведения в среднем. Сложность задачи.

2.13. Классификация задач по сложности: класс Р и класс Е.

2.14. Класс NP. NP-трудные и NP-полные задачи. Теорема Кука.

3.1. Основная учебная литература
    Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.
     Шелупанов А.А., Зюзьков В.М. Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с.
     Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. – 304 с.: ил.
     Гетманова А.Д. Учебник по логике. 2-ое изд. – М.: Владос, 1995. – 303 с.
     Никифоров А. Книга о логике. – М.: Гнозис, 1996.
     Манин Ю.И. Доказуемое и недоказуемое. – М.: Советское радио, 1979.
     Манин Ю.И. Вычислимое и невычислимое. – М.: Советское радио, 1980. -128 с.
     Кац М., Улам С. Математика и логика. Ретроспектива и перспективы: Пер. с англ. – М.: Мир, 1971. – 254 с.
     Судоплатов С.В. и др. Математическая логика и теория алгоритмов. –М.: изд. Дом «ИНФРА», 2004.-224 с.
     Судоплатов  Дискретная математика
     Справочная книга по математической логике: В 4-х частях/Под ред. Дж. Барвайса. Ч.III. Теория рекурсии: Пер. с англ. – М.: Наука, 1982. – 360 с.
     Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982. – 112 с.
     Филд А., Харрисон П. Функциональное программирование. – М.: Мир, 1993. – 637 с.
     Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ. – Мир, 1983. – 256 с.
     Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
     Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. 536 с.
     Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика. – М.: Мир, 1985. – 606 с.
    Шевелев Ю.П. Высшая математика 6. Дискретная математика. Ч.2: Теория конечных автоматов. Комбинаторика. Теория графов (для автоматизированной технологии обучения): Учебное пособие. – Томск: Томск. гос. ун-т систем управления и радиоэлектроники, 1999. – 120 с.
     Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов./Под ред. В.А. Садовничего. – 3-е изд., стер. – М.: Высшая школа; 2001. – 384 с.
     Дискретная математика и математические вопросы кибернетики. Т 1./Под общей редакцией С.В. Яблонского и О.Б. Лупанова, М.: Наука, 1974. – 311 с.
    Кнут Д.  Искусство программирования для ЭВМ, т.т. 1,2. – М.: Мир, 1977.
    Глушков В.М.  Синтез цифровых автоматов. – М.: Физматгиз, 1962. – 476 с.
3.2. Дополнительная литература
1.    Носов В.А. Специальные главы дискретной математики: Учебное пособие. М.: Наука, 1990.
2.    Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. – М.: Физматгиз, 1963. – 556 с.
3.    Флорин Ж. Синтез логических устройств и его автоматизация. – М.: Мир, 1966. – 375 с.
 

+ БОНУС: Готовые шпаргалки (только распечатать и можно идти сдавать)