ПРИЛОЖЕНИЕ № 2. Перечень вопросов необходимого минимума для получения

положительной оценки на экзамене по курсу «Математическая логика и теория алгоритмов»

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. Выполнимость и общезначимость формул логики предикатов.
29. Эквивалентные формулы логики предикатов.
30. Формальная аксиоматическая теория: алфавит, аксиомы, правила вывода.
31. Основные понятия теории доказательств: гипотеза, следствие, вывод, теорема, разрешимая и неразрешимая теория.
32. Аксиоматическая теория исчисления высказываний: система аксиом и правила вывода.
33. Теорема дедукции в исчислении высказываний.
34. Аксиоматическая теория исчисления предикатов первого порядка: система аксиом и правила вывода.
35. Теорема дедукции в исчислении предикатов.
36. Теорема о полноте теории исчисления высказываний.
37. Теорема о непротиворечивости теории исчисления высказываний.
38. Теорема о непротиворечивости теорий первого порядка.
39. Эффективная вычислимость функции.
40. Примитивная рекурсия.
41. Примитивно-рекурсивная функция.
42. Оператор минимизации.
43. Частично-рекурсивная функция.
44. Общерекурсивная функция.
45. Тезис Чёрча.
46. Машина Тьюринга, её компоненты и принцип работы.
47. Конфигурация машины Тьюринга.
48. Функция, вычислимая по Тьюрингу.
49. Тезис Тьюринга.
50. Композиция машин Тьюринга.
51. Разветвление машин Тьюринга.

Примечание: для получения положительной оценки все теоремы из данного списка достаточно знать без доказательств.