ВОПРОСЫК ЭКЗАМЕНУ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
1. Определение высказывания. Примеры высказываний.
2. Парадокс Рассела.
3. Основные действия над высказываниями (дизъюнкция, конъюнкция, импликация, сумма по модулю 2 и т.д. всего восемь).
4. Определение и интерпретация логической формулы. Тавтологии, невыполнимые формулы. Примеры.
5. Основные равносильности(законы поглощения, двойственности, свойства импликации, распределительные законы), доказательство при помощи таблиц истинности.
6. Понятие булевой алгебры. 3 интерпретации(теория множеств, алгебра высказываний, теория вероятностей)
7. СДНФ и СКНФ.
8. Булевы функции. Теорема о представлении n-местной функции в виде суперпозиции двуместных.
9. Двойственные и самодвойственные функции. Основные двойственности.
10. Теорема о двойственной функции для композиции.
11. Сокращение логических формул. Метод Квайна. Пример.
12. Полином Жегалкина. Количество различных полиномов Жегалкина. Единственность полинома Жегалкина для любой Булевой функции.
13. Представление основных логических функций полиномами Жегалкина. Линейные функции.
14. Полные системы, базисы. Примеры полных базисов. Штрих Шеффера и стрелка Пирса как одноэлементные базисы.
15. Понятие замкнутого класса. Пять важнейших замкнутых классов. Доказательство их замкнутости, теорема Поста.
16. Техническое применение булевых функций. Машина для голосования.
17. Техническое применение булевых функций. N-разрядный сумматор.
18. Многозначные логики. Основные функции, сравнение с двузначной логикой. Трехзначная логика Лукасевича. Доказательство законов с max и min (распределительный, идемпотентность) Разложение функции в «СДНФ» в к-значной логике.
19. Нечеткие множества, характеристические функции, действия с нечеткими множествами, примеры. Устройство простейшего микроконтроллера. Фаззификация и дефаззификация.
20. Нечеткая логика, действия с нечеткими высказываниями, примеры. нечеткая вероятность(на примере).
21. Исчисление высказываний. Аксиомы и правила вывода. Дерево вывода, структурное правило.
22. Правила сложного заключения, силлогизма, контрпозиции, снятия двойного отрицания.(вывод).
23. Понятие вывода из совокупности формул. Гипотезы. Дерево вывода. Теорема дедукции.
24. Правило введения конъюнкции.
25. Вывод правила сведения к противоречию. Лемма.
26. Формальный вывод закона двойственности.
Формальный вывод закона исключенного третьего.
28. Теорема о том, что выводимая формула является тавтологией.
29. Теорема о выводе формулы или ее отрицания при различных логических значениях переменных, входящих в формулу.
30. Теорема о выводимости тавтологии.
31. Метод резолюций в исчислении высказываний. Основные соотношения
32. Метод резолюций в исчислении высказываний применительно к хорновским дизъюнктам. Линейная резолюция. Правила, факты, цели.
33. Разрешимость, непротиворечивость, полнота исчисления высказываний.(доказательства).
34. Определение предиката. Примеры. Область истинности предиката. Кванторные операции, перестановочность. Продвижение отрицания за знак квантора.
35. Определения формулы логики предикатов. Термы. Интерпретация формулы. Основные равносильности в логике предикатов. Вынесение кванторов за знаки дизъюнкции и конъюнкции.
36. Примеры общезначимых формул.
37. Логико-математические языки. Язык AR. Примеры математических утверждений, записанных в языке AR. Понятие модели.
38. Примеры математических утверждений, записанных в языке AR.
39. Скулемовская форма формулы логики предикатов. Предваренная форма формулы логики предикатов.
40. Исчисление предикатов, аксиомы. Правила вывода. Структурное правило
41. Теорема Геделя о полноте исчисления предикатов. Пример вывода в исчислении предикатов. Общезначимые формулы. Выполнимые формулы
42. Особенности подстановок в формулы логики предикатов. Коллизия переменных. Примеры.
43. Формальная аксиоматические теории, определение. Полнота, непротиворечивость, разрешимость теории.
44. Формальная теория AR. Запись математических утверждений на языке теории AR. Примеры. Теорема Геделя о неполноте.
45. Унификация формул в исчислении предикатов. Метод резолюций в исчислении предикатов.
46. Пример применения метода резолюций в исчислении предикатов.
47. Теория алгоритмов. Дискретные объекты, кодировка натуральными числами. Сведение вопроса о существовании алгоритма к вопросу о вычислении функции на натуральных числах, множествах слов в некотором алфавите.
48. Интуитивное понятие вычислимой функции. Рекурсивные и рекурсивно перечислимые множества.
49. Машина Тьюринга, общие понятия.
50. Нормальные алгорифмы Маркова. Пример с двоичным разложением.
51. Примитивно-рекурсивные и частично-рекурсивные функции.
52. Машина Поста, пример вычитания чисел.
53. Тезис Черча.(Эквивалентность пяти подходов к вычислимости.)
54 Классы NP и P проблема их равенства.