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