Замкнутые классы булевых функций

Тест для самоконтроля

Замкнутые классы булевых функций

1. Формула, порожденная логическими константами 0 и 1 и функциями ..., называются многочленом Жегалкина.

a) XY и X&Y
б) XY и X v Y
в) X v Y и X&Y

2. Определите замыкание множества из двух функций: конъюнкции и дизъюнкции.

а) Всевозможные ДНФ, такие, что входящие в них элементарные конъюнкции не содержат отрицаний переменных.
б) Всевозможные КНФ, такие, что входящие в них элементарные конъюнкции не содержат отрицаний переменных.
в) Всевозможные ДНФ.
г) Всевозможные КНФ.

3. Образуют ли замкнутый класс 2 функции X и ┐X?

а) Да
б) Нет>

4. Определите полна ли система {,┐}

а) Да
б) Нет

Предполные классы булевых функций

1. Определите функцию, двойственную функции X&Y.

a) ┐X&┐Y
б) X v Y
в) ┐X v ┐Y

2. Какая из функций не принадлежит ни T0 ни T1?

а) X&Y.
б) X v Y.
в) XY.
г) ┐X.

3. Можно ли утверждать, что никакой из пяти классов T0, T1, S, L, M не входит целиком ни в какой из остальных четырех?

а) Да
б) Нет