Задача на нахождение ДНФ, КНФ, СДНФ, СКНф, полином Жегалкина

⌐((z→x)↔(y│x));

Решение:

Приведем формулу ⌐((z→x)↔(y│x)) к ДНФ (дизъюнктивной нормальной
форме), то есть получим дизъюнкцию конъюнкций: ⌐((z→x)↔(y│x))

Избавимся от эквиваленции, используя формулу (а↔b)=(a—>b)/\(b—>a):

⌐(((z→x)—>(y│x)) /\ ((y│x)—>(z→x)))

Избавимся от импликации (a—>b=⌐a\/b)и от штриха Шеффера ( a|b=⌐ (a/\b) ):

⌐( ( (⌐z\/x)—>( ⌐(y/\x) ) ) /\ (⌐ (y/\x) —> (⌐z\/x) ) )= =⌐( (⌐ (⌐z\/x) \/ ( ⌐ (y/\x) ) ) /\ (⌐(⌐(y/\x)) \/ (⌐z\/x) ) )

Используя свойство, что ⌐(⌐а)=а, получим

⌐( (⌐ (⌐z\/x) \/ ( ⌐ (y/\x) ) ) /\ ( (y/\x) \/ (⌐z\/x) ) )

Используя законы Де Моргана: ⌐ (a\/b)= ⌐a /\ ⌐b ; ⌐ (a/\b)= ⌐a \/ ⌐b , упростим

⌐( (z /\ ⌐x) \/ ( ⌐y \/ ⌐x) ) ) /\ ( (y/\x) \/ (⌐z\/x) ) ) = ⌐ ( (z /\ ⌐x) \/ ( ⌐y \/ ⌐x) ) \/ ⌐ ((y/\x)
\/ (⌐z\/x))=

= (⌐ (z /\ ⌐x) /\ ⌐ ( ⌐y \/ ⌐x) ) \/ (⌐ (y/\x) /\ ⌐(⌐z\/x))=((⌐z \/ x) /\ (y /\ x) ) \/ (⌐y\/⌐x)/\ (z/\⌐x))
Используя свойство дистрибутивности (a\/b)/\c=(a/\c) \/ (b/\c) , получим:

 (⌐z /\ y /\ x) \/ (x /\y/\x) \/ (⌐y/\z/\⌐x)\/(⌐x/\z/\⌐x)

 Зная, свойство идемпотентности: а /\ а = а, получим ДНФ(дизъюнкция элементарных
конъюнкций) исходной формулы:

(⌐z /\ y /\ x) \/ (x /\y) \/ (⌐y/\z/\⌐x)\/(⌐x/\z)

Теперь получим СДНФ формулы, нужно чтобы в каждой конъюнкции
в ДНФ, были все слагаемые, для этого используем закон склеивания

a=(a /\ b) \/ (a /\ ⌐b)=a /\ (b \/ ⌐b):

(⌐z /\ y /\ x) \/ (x /\y/\ (z \/ ⌐z)) \/ (⌐y/\z/\⌐x)\/(⌐x/\z/\ (y \/⌐y))

Используя свойство дистрибутивности,

(⌐z /\ y /\ x) \/ (x /\y/\ z) \/ (x /\y/\ ⌐z) \/
(⌐y/\z/\⌐x)\/(⌐x/\z/\ y) \/ (⌐x/\z/\⌐y)=

=( х /\ у /\ ⌐z) \/ (x /\y/\ z) \/ (x /\y/\ ⌐z) \/ (⌐x /\ ⌐y /\ z) \/ (⌐x /\ y /\z) \/ (⌐x /\ ⌐y /\ z)
Уберем одинаковые слагаемые, получим СДНФ исходной формулы:

( х /\ у /\ ⌐z) \/ (x /\y/\ z) \/ (⌐x /\ ⌐y /\ z) \/ (⌐x/\ y /\z)

Приведем формулу ⌐((z→x)↔(y│x)) к КНФ (конъюнктивной нормальной
форме), то есть получим конъюнкцию дизъюнкций:
Выше мы избавились от эквиваленции, импликации, штриха
Шеффера и отрицания получили

⌐((z→x)↔(y│x))= ((⌐z \/ x) /\ (y /\ x) ) \/ (⌐y\/⌐x) /\ (z/\⌐x))

 Воспользуемся свойством дистрибутивности (a/\b) \/ c=(a\/c) /\ (b\/c):

((⌐z \/ x) \/ ((⌐y\/⌐x) /\ (z/\⌐x)) ) /\ ((y /\ x) \/ ((⌐y\/⌐x) /\ (z/\⌐x)) )==(⌐z \/ x \/ ⌐y\/⌐x) /\ (⌐z \/ x \/ (z/\⌐x)) /\ ((y \/ ((⌐y\/⌐x) /\ (z/\⌐x)) ) /\(x\/((⌐y\/⌐x) /\ (z/\⌐x)))=
=(⌐z\/ x \/ ⌐y\/⌐x)
/\ (⌐z \/ x \/ z) /\ (⌐z \/ x \/ ⌐x) /\ (y \/ ⌐y\/⌐x) /\ (y \/ (z/\⌐x)) /\ (х\/⌐y\/⌐x) /\ (x\/(z/\⌐x))=
=(⌐z \/ x \/ ⌐y\/⌐x) /\ (⌐z \/ x \/ z) /\ (⌐z \/ x \/ ⌐x) /\ (y \/ ⌐y\/⌐x) /\ (y \/ z) /\ (y \/ ⌐x) /\ (х\/⌐y\/⌐x)
/\ (x\/z) /\ (x\/⌐x)=

Упростим множители за счет свойств ⌐a
\/ a =1, b\/1=1, a/\1=a

(⌐z \/ ⌐y \/ 1) /\ (x \/ 1) /\ (⌐z \/ 1) /\ (1\/⌐x) /\ (y \/ z) /\ (y \/ ⌐x) /\ (⌐y\/1) /\ (x\/z) /\ 1=

= 1 /\ 1 /\ 1 /\ 1 /\ (y \/ z) /\ (y \/ ⌐x) /\ 1 /\ (x\/z) /\ 1

Получили КНФ
(конъюнкция элементарных дизъюнкций) исходной формулы:

(y \/ z) /\ (y \/ ⌐x) /\ (x\/z)

Теперь получим СКНФ исходной формулы, для этого в
дизъюнкциях из КНФ должны присутствовать все слагаемые, добавим с помощью
формул

(⌐a /\ a =0, a\/0=a)не достающие слагаемые , получим (y \/ z\/(х /\ ⌐x)) /\ (y \/ ⌐x \/(z /\ ⌐z)) /\ (x\/z\/(y /\ ⌐y)), можно записать:
Используя свойство дистрибутивности, (y \/ z \/ х) /\( y \/ z\/ ⌐x) /\ (y \/ ⌐x \/ z ) /\ ( y
\/ ⌐x \/ ⌐z) /\ (x \/ z \/ y) /\ (x \/ z \/ ⌐y)

Избавимся от одинаковых множителей, получим СКНФ исходной формулы:
(x \/ y \/ z) /\ (⌐x \/ y \/ z) /\ (⌐x\/ y \/ ⌐z) /\ (x \/ ⌐y \/ z)

посмотреть еще задачи по дискретной математике