Вопросы к коллоквиуму по курсу "Теория дискретных функций" (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.