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