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

Пример 7.1. Рассмотрим функцию четырех переменных f(a, b, с, d) = : 1. f (0, 0, 0, 0) = =1 0=1, f (a, b, с, d) , 2. f (1, 1, 1, 1) = =0 0=0, f (a, b, с, d) . 3.Функция f (a, b, с, d) не является самодвойственной: f (0,1,1,1)= f (1,0,0,0). 4.Рассматриваемая булева функция f (a, b, с, d) немонотонная: (1, 0, 0, 0) ≥ (0, 0, 0, 0), f (1, 0, 0, 0) ≥ f (0, 0, 0, 0). 5.Установим, является ли булева функция f (a, b, с, d) линейной. Предположим, что она линейная и, следовательно, представима в виде (a, b, с, d) = с0 саа сbb ссс cdd. Найдем неизвестные коэффициенты с0, сa, сb, сc, сd, исходя из предположения о линейности этой функции. Зафиксируем набор (0, 0, 0, 0): f (0, 0, 0, 0). = 1, с0 са0 сb0 сc0 cd0=с0, с0=1. Аналогично определим коэффициенты сa, сb, сc, сd, фиксируя соответственно наборы 1000, 0100, 0010, 0001. Имеем: f (1, 0, 0, 0) = =0 0=0,1 са1 сb0 сc0 cd0=1 сa,1 сa=1, сa=1; f (0, 1, 0, 0) = =1 1=1, 1 1∙0 0∙0 сс0 cd0=1 сb, 1 сb=1, сb=0; f (0, 0, 1, 0) = =1 0=1, 1 1∙0 0∙0 сc∙1 cd0=1 cc, 1 сc=1, сa=0; f (0, 0, 0, 1) = =0 0=0, 1 1∙0 0∙0 0∙0 cd∙1=0 сa, 1 сd=0, сd=1. Окончательно получаем f(a, b, с, d) = 1 а d. Это равенство в каждой из остальных 11 строк таблицы истинности не сохраняется (проверте!). Действительно, например, f (1, 1, 1, 1) = =0 0=0, 1 1 1=1, 0 ≠ 1. Следовательно, сделанное предположение является неверным. Функция f (a, b, с, d) – нелинейная: f (a, b, с, d) .

Дата добавления: 2015-07-11