Вопросы к коллоквиуму по курсу "Теория дискретных функций" (II поток)
1.
Функции алгебры логики.
Существенные переменные. Равенства функций.
2.
Элементарные функции алгебры
логики и их свойства.
3.
Формулы и суперпозиции.
Равенства.
4.
Замыкания, замкнутость и
полнота систем булевых функций.
5.
Дизъюнктивная нормальная
форма. Полнота системы {&, V, ┐, 0,
1}.
6.
Замкнутость классов T0, T1, L и их отличие от P2.
7.
Замкнутость классов S, M и их отличие от P2.
8.
Попарная невложимость классов T0, T1, L, S, M.
9.
Получение из немонотонной
булевой функции с помощью констант 0 и 1 функции отрицания.
10.
Получение из
несамодвойственной булевой функции с помощью функции отрицания констант 0 и 1.
11.
Получение из нелинейной
булевой функции с помощью функции отрицания и констант конъюнкции.
12.
Теорема Поста о полноте в P2.
13.
Понятие базиса в замкнутом
классе булевых функций. Указание всех длин базисов в P2.
14.
Понятие предполного класса в P2. Предполнота классов T0, T1, L, S, M.
Отсутствие других предполных классов в P2.
15.
Большая теорема Поста о структуре
замкнутых классов в P2.
| 
