Расчетное задание по "Дискретной математике"

 

 

 

 

 

 

 

 

 

18. Функция принадлежит классу булевых функций, сохраняющих нуль, так как .

19. Функция принадлежит классу булевых функций, сохраняющих единицу, так как .

20. Функция не принадлежит классу самодвойственных булевых функций, так как эта функция не самодвойственная, поскольку различны не все ее значения, симметричные относительно средней линии таблицы значений (см. табл. 3.1).

21. Функция не принадлежит классу линейных булевых функций, так как она равносильна полученному в п. 17 полиному Жегалкина третьего порядка.

Рис. 3.4

22. Проверим принадлежность булевой функции классу монотонных булевых функций, использовав 3-мерный единичный куб. Укажем на каждом его ребре стрелки в направлении соответствующей оси координат (см. рис. 3.4). Функция не принадлежит классу , так как на рис. 3.4 есть ребро с направлением стрелки от отмеченной вершины к неотмеченной.

Проверим принадлежность булевой  функции классу методом расщепления. Кортеж значений этой функции разделяем на два кортежа: и . Получаем . Далее делим получившиеся картежи пополам. Получаем: . В процессе знак поменялся. Следовательно, функция не принадлежит классу .

23. Для проверки полноты множества составим таблицу Поста (см. табл. 3.8). Множество неполное, так как в этой таблице есть столбец только со знаком «+».

Таблица 3.8
Функция	Класс
	+	+	–	–	–

 

 

 

 

 

 

24. Так как множество неполное, подберем такие 2-местные булевы функции , , (одну, две или при необходимости три функции), чтобы множество (или , или ) было базисом класса всех булевых функций.

Для этого используем таблицу  Поста для всех шестнадцати 2-местных булевых функций (см. табл. 3.9). Найдем в этой таблице такую 2-местную булеву функцию , в строке для которой есть хотя бы один знак «+» (в противном случае эта функция одна образует базис класса всех булевых функций), а в столбце и этой строки есть знак «–». Например, такой функцией будет  — отрицание х, т.е. . Составив таблицу Поста (см. табл. 3.10), определим, что множество  — это базис класса всех булевых функций.

Таблица 3.9
Функция	Класс
	+	–	–	+	+
	–	+	–	+	+
	+	+	+	+	+
	+	+	+	+	+
	–	–	+	+	–
	–	–	+	+	–

 

 

 

 

 

 

 

 

 

 

 

Окончание таблицы 3.9
Функция	Класс
	+	+	–	–	+
	+	+	–	–	+
	–	+	–	+	–
	+	–	–	+	–
	–	–	–	–	–
	–	–	–	–	–
	–	+	–	–	–
	+	–	–	–	–
	–	+	–	–	–
	+	–	–	–	–

 

 

 

 

 

 

 

 

Таблица 3.10
Функция	Класс
	+	+	–	–	–
	–	–	+	+	–