Вопросы для подготовки к коллоквиуму по дисциплине
«Дискретная математика и математическая логика»
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.

Определение булевой функции.
Таблицы истинности логических связок.
Формула логики высказываний.
Тождественно истинные/ложные и выполнимые формулы.
Существенные и фиктивные переменные в формулах.
Эквивалентные формулы.
Основные эквивалентности.
Теорема о разложении булевой функции.
Двойственные формулы.
Двойственные булевы функции.
Принцип двойственности.
Конъюнкты и дизъюнкты, ДНФ и КНФ.
Совершенные конъюнкты и дизъюнкты . СДНФ и СКНФ.
Теоремы существования и единственности СДНФ и СКНФ.
Минимальная ДНФ
Импликант, простой импликант.
Моном, полином Жегалкина.
Теорема существования и единственности полинома Жегалкина.
Суперпозиция функций.
Замкнутый класс булевых функций.
Замыкание системы булевых функций.
Полная (в классе К) система булевых функций.
Базис (класса К).
Классы Поста.
Леммы о несамодвойственной, немонотонной и нелинейной функциях.
Теорема Поста о полноте системы булевых функций.
Максимальный замкнутый класс.
Теорема о максимальных замкнутых классах.
Логическое следование.
Свойства логического следования.

Требуется знать и понимать определения и формулировки, уметь приводить примеры (что-то
вроде того: привести пример линейной функции, распознать, какие из формул являются ДНФ,
и т.п.).