Программа экзамена по математической логике
Алгебра высказываний
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.	Понятие нелинейности булевой функции, значение нелинейности.

k-значные функции
36.	k-значные функции: основные определения, примеры.
37.	Полные системы k-значных функций. Полнота системы Поста.
38.	Критерии полноты: Слупецкого, Яблонского, Саломаа.(без. док.)
39.	.Лемма А.А. Нечаева
40.	.Критерий полноты k-значных функций.
41.	. Классификация k-значных функций относительно групп преобразований. Теорема о мощности класса функций, эквивалентных относительно заданной группы. 
42.	Основные группы преобразований множества Ωк и соотношение между ними. 
43.	Теорема  о  числе   функций, инвариантных относительно   заданной группы преобразований и ее применение для групп сдвигов, Джевонса и полной аффинной. 
44.	Утверждение об орбитах полной линейной группы.
45.	Теорема  о  тривиальности   группы   инерции   почти  всех  к-значных функций. 

Исчисление предикатов
46.	Общее понятие о логическом исчислении. Выводимость и доказуемость формул.
47.	Основные аксиомы исчисления предикатов и правила вывода. 
48.	Теоремы о выводимости формул алгебры предикатов. 
49.	Теорема об ограниченной дедукции. 
50.	Вспомогательные правила вывода: правила умножения формул, силлогизма, умножения посылок
51.	Правила: разделения посылок, перестановки посылок, сложения посылок, введения посылок, контрапозиции и де Моргана. 
52.	Правила -отрицания и -отрицания. 
53.	Правило противоречия. 
54.	Теорема дедукции для замкнутой формулы. 
55.	Интерпретация исчисления. Теорема об истинности формулы, выводимой из набора формул, истинных в некоторой интерпретации. Теорема Геделя о полноте (без. док.)

Теория алгоритмов
56.	Основные характерные свойства алгоритмов. 
57.	Нормальные алгоритмы Маркова: определения, примеры. 
58.	Принцип нормализации алгоритмов. Теорема о нормализации суперпозиции нормальных алгоритмов. 
59.	Геделевская нумерация алгоритмов. 
60.	Машины Тьюринга: определения, примеры. 
61.	Алгоритмически неразрешимые проблемы. Теорема о несуществовании НА, применимого к несамоприменимым алгоритмам. 
62.	Сложность НА, высиляющих булевы функции. 
63.	С ложность вычислений на машине Тьюринга, теорема о вычислимости арифметических функций. 
64.	Вычисления на недетерминированных машинах Тьюринга. Классы Р и NP. Примеры NP-полных задач.