Приведение логической формулы к днф

Приведение логической формулы к ДНФ можно произвести по следующему правилу:

1). С помощью равенства = x и законов де Моргана все отрицания “спускаются” до переменных;

2). Раскрываются скобки в полученном выражении;

3). С помощью выражений: x ·x = x , x x = x, x· = 0, x = 1

удаляются лишние конъюнкции и повторения переменных в конъюнкциях, а с помощью свойств констант удаляются и константы.

Пример. Привести к ДНФ следующую формулу: xy (y x z ) .

Преобразуем по закону де Моргана выражение во вторых скобках:

= & = & .

Раскрывая скобки в этом выражении получим:

Подставляя это выражение в исходную формулу и раскрывая скобки получим:

x y (y x z )( y ) = x y ( y y y x z x z y ) =

= x y ( y y 0 0 ) = x y y y = x y y y =

= y ( x ) y = y y .

Полученное выражение и есть ДНФ данной формулы.

Замечания:

1). ДНФ не является однозначно определенной.

2). Все ДНФ данной формулы равносильны.

Определение. Конъюнктивной нормальной формой (КНФ) логической функции называется конъюнкция разных дизъюнкций, которые не все являются полными.

Например, f( x,y,z ) = ( y )( z )( z ).