Приведение днф функции к кнф

Пусть ДНФ функции имеет следующий вид: K₁ K₂ … K_n,

где K_i – некоторые конъюнкции, не обязательно полные. Обозначим через D_i – дизъюнкции, не обязательно полные. Тогда, используя закон де Моргана получим:

.

Раскрывая скобки в выражении D₁∙ D₂ … ·D_n и удаляя лишние конъюнкции и повторения переменных в полученных конъюнкциях, получим:

= .

Полученное выражение с помощью закона де Моргана преобразуем к виду:

.

Это и будет КНФ функции для исходной ДНФ.

Пример. Привести к КНФ функцию, заданную в ДНФ:

f( x,y,z) = x y x .

Используя закон де Моргана, раскрывая затем скобки и удаляя лишние конъюнкции, получим:

Применяя к этому выражению закон де Моргана получим:

f( x,y,z) = .

Это и есть искомая КНФ для заданной функции.