Приведение днф функции к кнф
Пусть ДНФ функции имеет следующий вид:
K1 
K2 …
Kn,
где Ki – некоторые конъюнкции, не обязательно полные. Обозначим через Di – дизъюнкции, не обязательно полные. Тогда, используя закон де Моргана получим:
.
Раскрывая скобки в выражении D1 D2 … ·Dn и удаляя лишние конъюнкции и повторения переменных в полученных конъюнкциях, получим:
= 
.
Полученное выражение с помощью закона де Моргана преобразуем к виду:
.
Это и будет КНФ функции для исходной ДНФ.
Пример. Привести к КНФ функцию, заданную в ДНФ:
f( x,y,z) = x
y x
.
Используя закон де Моргана, раскрывая затем скобки и удаляя лишние конъюнкции, получим:
предыдущаяследующая