Алгоритм преобразования КНФ к виду СКНФ.

Алгоритм преобразования ДНФ к виду СДНФ.

Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).

Шаг 1: если в элементарную конъюнкцию F не входит подформула F_i или ù F_i, то дополнить элементарную конъюнкцию высказыванием (F_iÚù F_i) и выполнить преобразование формулы по закону дистрибутивности:

F&(F_iÚù F_i)= F&F_iÚF&ù F_i;

Шаг 2: если в элементарную конъюнкцию F не входит подформула F_j или ùF_j, то повторить шаг 1, иначе – конец.

Пример: Дано F=F₁&ù F₂ÚF₁&ù F₃&F₄ÚF₁&F₂&F₃&ù F₄.

Преобразовать формулу к виду СДНФ:

1) F=F₁&ù F₂&(F₃Úù F₃) Ú F₁&ù F₃&F₄&(F₂Úù F₂)ÚF₁&F₂&F₃&

ù F₄;

2)F=F₁&ù F₂&F₃ÚF₁&ù F₂&ù F₃ÚF₁&F₂&ù F₃&F₄ÚF₁&ù F₂&

ù F₃&F₄Ú F₁&F₂&F₃&ù F₄;

3) F=F₁&ù F₂&F₃&(F₄Úù F₄)ÚF₁&ù F₂&ù F₃&(F₄Úù F₄)ÚF₁&F₂&

ù F₃&F₄Ú F₁&ù F₂&ù F₃&F₄Ú F₁&F₂&F₃&ù F₄;

4) F=(F₁&ù F₂&F₃&F₄)Ú(F₁&ù F₂&F₃&ù F₄)Ú(F₁&ù F₂&ù F₃&F₄)Ú

(F₁&ù F₂&ù F₃&ù F₄)Ú (F₁&F₂&ù F₃&F₄)Ú (F₁&ù F₂&ù F₃&F₄)Ú (F₁&F₂&F₃&ù F₄).

Шаг 1: если в элементарную дизьюнкцию F не входит подформула F_i или ù F_i, то дополнить элементарную дизьюнкцию высказыванием (F_i&ùF_i) и выполнить преобразование формулы по закону дистрибутивности:

FÚ(F_i &ù F_i) = (FÚ F_i)&(FÚù F_i);

Шаг 2: если в элементарную конъюнкцию F не входит подформула F_j или ù F_j, то повторить шаг 1, иначе – конец.