2.3.4 Приведение логических функций

Приведение к ДНФ

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

Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более одного раза.

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

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

• по правилу де Моргана все отрицания опускаются до переменных;

• раскрываются скобки;

• удаляются лишние конъюнкции и повторения переменных в конъюнкциях;

• с помощью законов 0 и 1 удаляются константы – единицы из конъюнкций, нули из дизъюнкций.

{Пример: Привести к ДНФ следующую логическую функцию двух переменных F (x₁, x₂) =  (x₁  x₂) ( x₁   x₂).

F (x₁, x₂) =  (x₁  x₂) ( x₁   x₂) =  x₁  x₂ ( x₁   x₂) =

=  x₁  x₂  x₁   x₁  x₂  x₂ =  x₁  x₂   x₁  x₂ =  x₁  x₂.}

Приведение к КНФ

КНФ – конъюнктивная нормальная форма – конъюнкция элементарных дизъюнкций.

Привести функцию к КНФ можно по аналогичному алгоритму как и к ДНФ. Кроме того, любую ДНФ можно привести к КНФ по правилу де Моргана.