Читайте также:
|
Содержание разделов дисциплины.
Раздел 1. Введение.
Понятие информационно-логических систем и их место в математике и информатике. Роль математической логики, как теоретической основы математики. Влияние математической логики на развитие информатики. Понятие искусственного интеллекта. Примеры задач, решаемых рассуждениями. Необходимость формализации рассуждений. Дедукция, силлогизм, индукция, математическая индукция. Основные математические понятия, необходимые для изложения основ математической логики.
Раздел 2. Исчисление высказываний.
Формулы исчисления высказываний и их интерпретация. Понятие высказывания. Синтаксис исчисления высказываний (ИВ). Интерпретация формул в ИВ. Общезначимые, выполнимые и невыполнимые формулы. Тривиальный алгоритм проверки выполнимости формул. Алгоритм Куайна.
Алгебраический подход к ИВ. Алгебра логики и эквивалентные преобразования. Некоторые приложения алгебры логики. Нормальные формы.
Дизъюнктивные и конъюнктивные нормальные формы в ИВ (ДНФ и КНФ). Методы построения ДНФ и КНФ, эквивалентных произвольным формулам ИВ: с помощью таблиц истинности, с помощью эквивалентных преобразований. Алгоритм Девиса-Патнема для проверки выполнимости нормальных форм.
Метод резолюций в ИВ. Проблема дедукции и ее значение в математической логике и информатике. Прямая и обратная дедукции. Теорема Робинсона и правило резолюций. Метод резолюций для решения проблемы дедукции. Дизъюнкты Хорна. Метод резолюций для дизъюнктов Хорна. Оценка трудоемкости метода.
Раздел 3. Исчисление предикатов (первого порядка).
Понятие предиката. Ограниченность ИВ. Примеры рассуждений, не формализуемых в рамках ИВ. Понятие предиката и примеры его использования в рассуждениях. Синтаксис и семантика формул исчисления предикатов.
Синтаксис исчисления предикатов (ИП). Семантика формул в ИП. Кванторы и типы вхождения переменных в формулы. Интерпретация формул в ИП. Примеры интерпретаций. Общезначимые, выполнимые и невыполнимые формулы. Схемы общезначимых формул, используемых для эквивалентных преобразований. Клаузальные формы. Подстановка и конкретизация в ИП. Универсальное и экзистенциональное замыкания. Предваренные и нормальные формы. Сколемовские и клаузальные формы. Алгоритм преобразования произвольной формулы ИП в клаузальную форму. Эрбранова интерпретация.
Эрбранов универсум множества дизъюнктов. Основные выражения и эрбранов базис. Н-интерпретация. Теорема о невыполнимости множества дизъюнктов. Следствия теоремы. Метод резолюций в ИП. Проблема дедукции в ИП. Фундаментальная резолюция. Унификация с помощью подстановки. Алгоритм унификации. Метод резолюций для ИП. Дизъюнкты Хорна и решение проблемы дедукции методом резолюций в ИП. Примеры применения метода резолюций для решения проблемы дедукции. Связь ИП с системами представления знаний в задачах искусственного интеллекта.
Дата добавления: 2015-04-11; просмотров: 77 | Поможем написать вашу работу | Нарушение авторских прав |