Переход от нормальных к составным формам ПФ

Аналитический способ

СДНФ и СКНФ содержат, в отличии от нормальной, дизъюнкции и конъюнкции только максимального ранга r.

Это дает возможность производить переход по следующим правилам.

Правило 1.    для перехода от произвольной ДНФ К- го ранга (К<r) к СДНФ r- го ранга необходимо конъюнкции ДНФ последовательно умножать на логическое выражение (Х_i^X_i) где,

                X_i – она из переменных, не вошедшая в данную конъюнкцию.

                Число таких преобразований для каждой конъюнкции д.б. (r-k)

Пример. Преобразовать ДНФ

            F_СДНФ(Х_1,Х₂,Х₃) = Х₁*Х₂^Х₃ в СДНФ

             R = 3-го ранга

А) Х₁*Х₂(Х₃^Х₃) = Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃

Б) Х₃(Х₁^Х₁)= Х₃*Х₁^Х₃*Х₁ – 1-е преобразование

В) (Х₃*Х₁^Х₃*Х₁)(Х₂^Х₂) = Х1*Х₂*Х₃^Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃ = 2-е преобразование.

Г) F_СДНФ(Х₁,Х₂,Х₃) = Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃^ Х₁*Х₂*Х₃

Правило 2:  Для перехода от произвольной КНФ к СКНФ r-го ранга необходимо дизъюнкции, входящие в КНФ к-го ранга последовательно симулировать с логическим выражением Х_i*Х_i (Х^0) = Х

Где Х_i - одна из переменных, не входящая в данную дизъюнкцию. Число преобразований для каждой дизъюнкции д.б. (r-k)