zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Математическая логика

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

Курс по выбору

Лектор: д.ф.-м.н., проф. Братчиков И.Л.

1. Введение

1.1. Понятие информационно-логических систем и их место в математике и информатике.
1.2. Роль математической логики, как теоретической основы математики. Влияние математической логики на развитие информатики.
1.3. Понятие искусственного интеллекта.
1.4. Примеры задач, решаемых рассуждениями. Необходимость формализации рассуждений.
1.5. Дедукция, силлогизм, индукция, математическая индукция.
1.6. Основные математические понятия, необходимые для изложения основ математической логики.

2. Исчисление высказываний

2.1. Формулы исчисления высказываний и их интерпретация.
2.1.1. Понятие высказывания.
2.1.2. Синтаксис исчисления высказываний (ИВ).
2.1.3. Интерпретация формул в ИВ.
2.1.4. Общезначимые, выполнимые и невыполнимые формулы.
2.1.5. Тривиальный алгоритм проверки выполнимости формул.
2.1.6. Алгоритм Куайна.
2.2. Алгебра логики и эквивалентные преобразования. Некоторые приложения алгебры логики.
2.3. Нормальные формы
2.3.1. Дизъюнктивные и конъюнктивные нормальные формы в ИВ (ДНФ и КНФ).
2.3.2. Методы построения ДНФ и КНФ, эквивалентных произвольным формулам ИВ: с помощью таблиц истинности, с помощью эквивалентных преобразований.
2.3.3. Алгоритм Девиса-Патнема для проверки выполнимости нормальных форм.
2.4. Метод резолюций в ИВ.
2.4.1. Проблема дедукции и ее значение в математической логике и информатике.
2.4.2. Прямая и обратная дедукции.
2.4.3. Теорема Робинсона и правило резолюций. Метод резолюций для решения проблемы дедукции.
2.4.4. Дизъюнкты Хорна. Метод резолюций для дизъюнктов Хорна. Оценка трудоемкости метода.

3. Исчисление предикатов (первого порядка)

3.1. Понятие предиката.
3.1.1. Ограниченность ИВ. Примеры рассуждений, не формализуемых в рамках ИВ.
3.1.2. Понятие предиката и примеры его использования в рассуждениях.
3.2. Синтаксис и семантика формул исчисления предикатов.
3.2.1. Синтаксис исчисления предикатов (ИП).
3.2.2. Семантика формул в ИП.
3.2.3. Кванторы и типы вхождения переменных в формулы.
3.2.4. Интерпретация формул в ИП. Примеры интерпретаций.
3.2.5. Общезначимые, выполнимые и невыполнимые формулы.
3.2.6. Схемы общезначимых формул, используемых для эквивалентных преобразований.
3.3. Клаузальные формы.
3.3.1. Подстановка и конкретизация в ИП.
3.3.2. Универсальное и экзистенциональное замыкания.
3.3.3. Предваренные и нормальные формы.
3.3.4. Сколемовские и клаузальные формы.
3.3.5. Алгоритм преобразования произвольной формулы ИП в клаузальную форму.
3.4. Эрбранова интерпретация.
3.4.1. Эрбранов универсум множества дизъюнктов.
3.4.2. Основные выражения и эрбранов базис. Н-интерпретация.
3.4.3. Теорема о невыполнимости множества дизъюнктов. Следствия теоремы.
3.5. Метод резолюций в ИП.
3.5.1. Проблема дедукции в ИП.
3.5.2. Фундаментальная резолюция.
3.5.3. Унификация с помощью подстановки.
3.5.4. Алгоритм унификации.
3.5.5. Метод резолюций для ИП.
3.5.6. Дизъюнкты Хорна и решение проблемы дедукции методом резолюций в ИП.
3.5.7. Примеры применения метода резолюций для решения проблемы дедукции.
3.5.8. Связь ИП с системами представления знаний в задачах искусственного интеллекта.

4. Аксиоматические системы

4.1. Определение аксиоматических систем.
4.1.1. Определение и свойства аксиоматических систем (АС). Области применения АС.
4.2. АС с правилом вывода Modus Ponens.
4.2.1. АС исчисления высказываний (с правилом вывода М.Р.).
4.2.2. Полнота и минимальность АС. Примеры доказательства теорем.
4.2.3. Теорема Эрбрана-Тарского и ее использование для упрощения доказательств.
4.3. АС натурального вывода.
4.3.1. Определение и особенности АС натурального вывода.
4.3.2. Правила вывода.
4.3.3. Примеры доказательства теорем.
4.4. Теории первого порядка.
4.4.1. Понятие о теориях первого порядка.
4.4.2. Примеры теорий и их использования.

5. Основы теории алгоритмов

5.1. Понятие алгоритма.
5.1.1. Неформальное определение алгоритма.
5.1.2. Примеры алгоритмов.
5.1.3. Основные свойства алгоритмов.
5.1.4. Роль алгоритмов в информатике.
5.1.5. Парадигма процедурного программирования.
5.2. Алгоритмические проблемы.
5.2.1. Проблема разрешимости.
5.2.2. Примеры неразрешимых проблем.
5.2.3. Понятие вычислимости и вычислительные процедуры.
5.3. Машины Тьюринга.
5.3.1. Определение машины Тьюринга.
5.3.2. Примеры машин Тьюринга.
5.3.3. Тезис Черча-Тьюринга.
5.3.4. Проблема остановки для машины Тьюринга.
5.4. Машины Тьюринга с разрешимой проблемой остановки.
5.4.1 Линейно-ограниченные автоматы.
5.4.2 Проблема остановки для линейно-ограниченных автоматов.
5.4.3. Машина Тьюринга как распознаватель формальных языков.
5.4.4. Двухленточные машины Тьюринга.
5.4.5. Автоматы с магазинной памятью.
5.4.6. Конечные автоматы.
5.4.7. Синтаксический анализ языков с помощью автоматов с магазинной памятью и конечных автоматов.

6. Заключение

6.1. Обзор приложений математической логики в информатике.
6.2. Парадигма логического программирования.
6.3. Язык Пролог как реализация метода резолюций для решения задач искусственного интеллекта.

Литература

  1. Клини С.К. Математическая логика. М.: Мир, 1973.
  2. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.
  3. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
  4. Тей А., Грибомон П. и др. Логический подход к искусственному интеллекту. Т.1. М.: Мир, 1990.
  5. Тей А., Грибомон П. и др. Логический подход к искусственному интеллекту. Т.2. М.: Мир, 1998.
  6. Ковальски Р. Логика в решении проблем. М.: Наука, 1990.
  7. Справочная книга по математической логике / Под ред. Барвайс Дж. М.: Наука, 1982.
  8. Ин Ц., Соломон Д. Использование Турбо-Пролога. М.: Мир, 1993.
  9. Братчиков И.Л. Синтаксис языков программирования. М.: Наука, 1975.