булева-алгебра - Булевы функции

Я думаю, имелось в виду то, что $%f$% сначала надо представить в виде полинома Жегалкина. Выражение $%x(x\lor z)$% очевидным образом упрощается до $%x$%, поэтому $%f=(x+y+yz)\lor x=x+x+y+yz+x+xy+xyz=x+y+xy+yz+xyz$%. Таким образом, $%f(x,y,z)=x+y+xy+yz+xyz$% представлена полиномом Жегалкина. Для отрицания $%f$% полином получается добавлением слагаемого 1.

Функция $%\bar{f}$% не принадлежит ни одному из пяти предполных классов двузначной логики, что легко проверяется непосредственно. Значит, через одну эту функцию можно всё выразить. Функцию $%f$% при этом можно не задействовать. Заметим, что через неё одну нельзя выразить отрицание, так как она сохраняет $%0$%.

Итак, $%\bar{f}(x,y,z)=1+x+y+xy+yz+xyz$%. Подставляя $%x=y=z$%, имеем $%\bar{f}(x,x,x)=1+x=\bar{x}$%, то есть отрицание выражено. Теперь можно подставить отрицания первой и третьей переменной, везде беря $%x$%, и получится $%\bar{f}(\bar{x},x,\bar{x})=0$%, так как нелинейные члены исчезнут в силу $%x\bar{x}=0$%, а линейная часть станет равна $%1+\bar{x}+x=0$%. Таким образом, у нас выражается $%0$%, и его можно подставить вместо $%z$%, получая $%\bar{f}(x,y,0)=(1+x)(1+y)=\bar{x}\bar{y}$%. Тогда подстановка $%\bar{f}(\bar{x},\bar{y},0)$% даёт конъюнкцию $%xy$%.