Программа по дискретной математике и математической логике.
2 семестр, 1 курс.

1. Формализация понятия с помощью машин Тьюринга и тезис Черча.
2. Понятие булевой функции. Функции от 1 и 2 переменных. Задание булевых функций таблицами и формальными выражениями.
3. Эквивалентные преобразования формул, задающих булевы функции. Коньюнктивные и дизъюнктивные нормальные формы. Задание произвольной формулы с помощью ДНФ.
4. Выразимость булевых функций друг через друга. Замкнутые классы.
5. Классы Т0, Т1 и класс S самодвойственных функций.
6. Класс монотонных функций.
7. Полиномы Жегалкина и класс линейных функций.
8. Теоремы Поста.
9. Предполные классы.
10. Релейно-контактные схемы.
11. Язык логики высказываний, связь с булевыми функциями.
12. Теоремы о замене и основных эквивалентностях.
13. Понятие логического следования. Теорема о свойствах этого понятия. Правила логических умозаключений.
14. Связь между понятиями: логическгого следования, тавтологии,эквивалентности формул.
15. Понятие простой теоремы и производных от нее высказываний. Анализ правильности рассуждений. Методы доказательства в математике.
16. Аксиомы, правило вывода и вывод в ИВ Гильберта.
17. Теорема дедукции.
18. Непротиворечивость ИВ Гильберта.
19. Непротиворечивость множества формул.
20. Теория интерпретации.
21. Теорема Линденбаума.
22. Теоремы: о полноте, обобщенная о полноте, компактности, адекватности ЛВ и ИВ.
23. Независимость акисом ИВ.
24. Выводимость и выполнимость. Алгоритмическая разрешимость проблемы выводимости в ИВ.
25. Алгоритм Куайна и семантическое дерево.
26. Семантическое дерево, полное семантическое дерево и частичня интерпретация, определяемая его вершинами.
27. Правило резолюции и его применение к коньюнктивным нормальным формам.
28. Алгоритм проверки выполнимости КНФ с помощью правила резолюции.
29. ИВ Генцена. Теорема о полноте.