1. Понятие высказывания. Логические связки. Формулы логики высказываний.
2. Равносильность формул логики высказываний. Основные равносильности.
3. Тождественно-истинные формулы логики высказываний. Важнейшие тавтологии. Правильные рассуждения. Утверждение о правильности рассуждения по схеме
(Р1, …, Рn)=>Q.
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. Примеры простейших примитивно рекурсивных функций.
29. Теорема о примитивной рекурсивности суммы и произведения примитивно рекурсивных функций (без доказательства). Примитивная рекурсивность функций “частное от деления х на y”, “остаток от деления х на y”, “признак деления х на y”.
30. Ограниченный оператор минимизации и его применения. Теорема Робинсона об одноместных примитивно рекурсивных функциях (без доказательства).
31. Неограниченный оператор минимизации. Частично рекурсивные функции. Тезис Черча о вычислимых функциях.
32. Общерекурсивные функции. Функция Аккермана. Теорема Аккермана (без доказательства).
33. Словарные функции. Определение машины Тьюринга.
34. Способы задания машин Тьюринга. Реализация на машине Тьюринга программы “перенос нуля”.
35. Неприменимость машины Тьюринга к исходной информации (привести пример). Тезис Тьюринга. Теорема о соответствии между частично рекурсивными функциями и функциями, вычислимыми по Тьюрингу (без доказательства).
36. Определение нормального алгоритма Маркова и порядок его работы.
37. Пример работы нормального алгоритма Маркова. Тезис Маркова. Теорема об эквивалентности машин Тьюринга и нормальных алгоритмов Маркова.
38. Сравнительный анализ трех типов алгоритмических моделей. Оценка сложности алгоритма.
39. Проблема остановки машины Тьюринга и проблема ее самоприменимости. Теорема Райса (без доказательства) и ее смысл.
40. Проблема эквивалентности слов для ассоциативных исчислений и проблема соответствий Поста.
41. Особенности прикладных исчислений. Теорема об основных свойствах равенства в теории с равенством.
42. Формальная арифметика. Теоремы Геделя о неполноте (без доказательства) и их смысл.
