С помощью эквивалентных преобразований привести формулу к ДНФ, КНФ; привести к СДНФ, СКНФ с помощью аналитического способа и табличного способа. Проверить линейность булевой функции, заданной этой формулой, с помощью полинома Жегалкина и методом неопределенных коэффициентов.
Решение.
F=X→Y(Y→X)|X→Z(Z→X) = ¬(X→Y(Y→X) X→Z(Z→X))=
=¬(X v Y(Y vX) X v Z(Z v X)) = ¬(X Y Z v XY Z)=(X v Y v Z)(X vY vZ) (КНФ, СКНФ)
(X v Y v Z)(X vY vZ) = XY v XZ v X Y v YZ v X Z v Y Z = ДНФ
выполняем расщепление, склеиваем одинаковые конъюнкции
= XYZ v X YZ v XYZ v X Y Z v X Y Z v X YZ (СДНФ)
Построим таблиц истинности
X Y Z
X→Y
Y→X
X→Y(Y→X)
X→Z
Z→X
X→Z(Z→X)
F
0 0 0
1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0 1
0 1 0 1 0 0 1 1 1 1
0 1 1
1 0 0 1 0 0 1
1 0 0
0 1 0 0 1 0 1
1 0 1 0 1 0 1 1 1 1
1 1 0 1 1 1 0 1 0 1
1 1 1
1 1 1 1 1 1 0
Сформируем СКНФ по нулевым наборам:
F=(X v Y v Z)(X vY vZ)
Сформируем СДНФ по единичным наборам:
F= XYZ v X YZ v XYZ v X Y Z v X Y Z v X YZ
Сформируем полином Жегалкина данной функции.
(X v Y v Z)(X vY vZ)=((XY⊕X ⊕Y)v Z)( (XY⊕X ⊕Y) vZ)=
=(XYZ⊕XZ ⊕YZ⊕XY⊕X ⊕Y ⊕Z)( XYZ⊕XZ ⊕Y Z ⊕XY⊕X ⊕Y⊕Z) = XZ Y⊕YZX ⊕XY Z⊕XY Z ⊕ XY⊕XZ⊕X Y Z⊕X Y ⊕
⊕YZ⊕XYZ⊕XZ⊕YZ= XZ⊕YZ⊕XY⊕X ⊕Y ⊕Z
При выполнении преобразований использовали тождества:
X ⊕X=0; X= X ⊕1
Полином Жегалкина содержит конъюнкции => функция нелинейна.
Полином можно построить по таблице истинности. Запишем общий вид полинома и затем определим коэффициенты.
F(X,Y,Z) =a1XYZ⊕a2XZ⊕a3YZ⊕a4XY⊕a5X ⊕a6Y ⊕a7Z⊕a8
F(0,0,0) =0 => a8=0
F(0,0,1) =1 => a7⊕ a8=1 => a7=1
F(0,1,0) =1 => a6⊕ a8=1 => a6=1
F(0,1,1) =1 =>a3⊕ a6⊕ a7⊕a8=1 => a3=1
F(1,0,0) =1 => a5⊕ a8=1 => a5=1
F(1,0,1) =1 =>a2⊕ a5⊕ a7⊕a8=1 => a2=1
F(1,1,0) =1 =>a4⊕ a5⊕ a6⊕a8=1 => a4=1
F(1,1,1) =0 =>a1⊕a2⊕a3⊕a4⊕ a5⊕ a6⊕a7⊕a8=0 => a1=0
F(X,Y,Z) =XZ⊕YZ⊕XY⊕X ⊕Y ⊕Z
