Вопросы к коллоквиуму по
ДИСКРЕТНОЙ МАТЕМАТИКЕ и МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
1 семестр, 2курс
лекционных часов- 18
практических - 18
Понятие предиката, примеры предикатов.
Сигнатура,язык логики предикатов,термы,формулы логики предикатов.
Алгебраические системы данной сигнатуры.
Модели и интерпретации формул данной сигнатуры.
Истинность формул на модели.
Изоморфизм моделей, элементарная эквивалентность, выразимость.
Предваренные нормальные формы.
Сколемовские нормальные формы.
Аксиомы, правило вывода и вывод в ИП Гильберта.
Теорема дедукции.
Непротиворечивость ИП Гильберта.
Теоремы:о полноте,обобщенная о полноте,компактности, адекватности ЛП и ИП.
Независимость аксиом ИП Гильберта.
Выводимость и выполнимость. Алгоритмическая неразрешимость проблемы выводимости в ИП.
Эрбранова область.
Правило резолюции.
Алгоритм проверки с помощью правила резолюции.
ИП Генцена.
ЛИТЕРАТУРА:
Мендельсон Э. Введение в математическую логику. М.,1976
Новиков П.С. Элементы математической логики . М.,1973
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, матаматической логике и теории алгоритмов. М.,1975
Ершов Ю.Л., Палютин Е.А. Математическая логика М.,1979
Клини С. Математическая логика М.,1973
Тейз А., Гриботон П., Луи Ж. и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию М.,1990