Замкнутые и полные классы булевых функций двух переменных. Примеры полных систем булевых функций. Формулировка теоремы о полных классах булевых функций произвольного числа аргументов.
1. a) Выразить все основные операции:
1) через дизъюнкцию, конъюнкцию и отрицание;
2) через конъюнкцию и отрицание;
3) через дизъюнкцию и отрицание;
4) через импликацию и отрицание.
б). Рассмотреть различные способы задания булевой функции от трех пе-
ременных, которая:
a) принимает значение 1 в том и только в том случае, когда ровно две
переменные равны нулю;
b) принимает такое же значение, как большинство (или меньшинство)
переменных.
2. Проверить самодвойственность функций.
1). 
2). 
3). 
4). 
5). 
3. Проверить монотонность функций.
1. 
2. 
3. 
4. 
5). 
4. Всегда ли на множестве булевых функций:
a) пересечение замкнутых классов является замкнутым классом;
b) разность замкнутых классов есть замкнутый класс;
c) дополнение замкнутого класса не является замкнутым классом?
5. Показать, что суперпозиция линейных функций является линейной
функцией.
6. Показать, что классы функций, сохраняющих константу, замкнуты.
7. Показать, что суперпозиция самодвойственных функций является самодвойственной.
8. Доказать замкнутость класса монотонных функций.
9. Проверить полноту следующих систем.
1). 
2). 
3). 
4). 
5). 
Литература:[2,3,4,7,16,17,19,21,23,24,25]
Учебно-методическая литература:[2]
Дата добавления: 2015-09-12; просмотров: 73 | Поможем написать вашу работу | Нарушение авторских прав |