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

Приведение КНФ к ДНФ осуществляется путем раскрытия скобок и удаления полученных лишних конъюнкций и повторных переменных.

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

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

Раскроем скобки:

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

= x z x y y y z y.

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

f( x,y,z ) = x z y ( x ) y ( z 1 ) = x z y∙1 y ·1 = x z y.

Теорема. Для любых двух эквивалентных формул f₁ и f₂ существует экви-валентное преобразование f₁ в f₂ с помощью основных свойств булевых операций.

Доказательство: Преобразуем f₁ и f₂ в СДНФ. Так как f₁ ~ f₂, то их СДНФ совпадают.