Совершенные дизъюнктивные нормальные формы

Обозначим:
f1=x∧y∧¬z
f2=¬y∨z
f3=¬x∧y
f4=¬x∨f1
f5=¬f2∧f3
f=f4→f5
Построим таблицу истинности:
x
y
z
¬x
¬y
¬z
f1
f2
¬f2
f3
f4
f5
f
0 0 0 1 1 1 0 1 0 0 1 0 0
0 0 1 1 1 0 0 1 0 0 1 0 0
0 1 0 1 0 1 0 0 1 1 1 1 1
0 1 1 1 0 0 0 1 0 1 1 0 0
1 0 0 0 1 1 0 1 0 0 0 0 1
1 0 1 0 1 0 0 1 0 0 0 0 1
1 1 0 0 0 1 1 0 1 0 1 0 0
1 1 1 0 0 0 0 1 0 0 0 0 1
Для каждого набора переменных, при котором функция равна 1, записываем конъюнкции, в которых с отрицанием берутся переменные, имеющие значение «0» . В результате получаем СДНФ:
¬xy¬z∨x¬y¬z∨x¬yz∨xyz
Для каждого набора переменных, при котором функция равна 0, записываем дизъюнкции, в которых с отрицанием берутся переменные, имеющие значение «1». В результате получаем СКНФ:
(x∨y∨z)(x∨y∨¬z)(x∨¬y∨¬z)(¬x∨¬y∨z)
Получим СДНФ и СКНФ аналитически. Для этого избавимся от импликации и упростим функцию:
¬¬x∨x∧y∧¬z∨(¬¬y∨z∧(¬x∧y))
По правилам де Моргана, двойного отрицания и формуле поглощения:
¬¬x∨x∧y∧¬z=¬¬x∧¬x∧y∧¬z=x∧¬x∧y∧¬z=x∧¬x∨¬y∧¬z=x∧¬x∨¬y∨¬¬z=x∧¬x∨¬y∨z=x∧(¬y∨z)
¬¬y∨z=¬¬y∧¬z=y∧¬z
Тогда:
¬x∨x∧y∧¬z→¬¬y∨z∧¬x∧y=x∧¬y∨z∨y∧¬z∧¬x∧y=x∧¬y∨z∨¬x∧y∧¬z=x∧¬y∨(x∧z)∨¬x∧y∧¬z
Получили ДНФ