Приведение формулы к ДНФ (дизъюнктивной нормальной форме), КНФ (конъюнктивной нормальной форме), СДНФ (совершенной дизъюнктивной нормальной форме) и СКНФ (совершенной конъюнктивной нормальной форме) состоит из ряда равносильных преобразований, которые можно применять к исходной формуле․
Исходная формула⁚ F(X,Y,Z) Xv ((Y! vZ) -> (ZnY!))
1․ Приведение к ДНФ⁚
ДНФ представляет собой логическое выражение, в котором логическое ИЛИ (v) связывает логические переменные и их отрицания․F(X,Y,Z) Xv((Y! v Z) -> (Z n Y!))
Сначала раскроем выражение в скобках⁚
(Y! v Z) -> (Z n Y!) (Y! v Z) -> (Z n Y!)
Затем раскроем импликацию (A -> B) в две дизъюнкции (~A v B)⁚
(Y! v Z) -> (Z n Y!) ~(Y! v Z) v (Z n Y!)
Теперь получаем ДНФ для исходной формулы⁚
F(X,Y,Z) Xv(~(Y! v Z) v (Z n Y!))
2․ Приведение к КНФ⁚
КНФ представляет собой логическое выражение, в котором логическое И (n) связывает логические переменные и их отрицания․F(X,Y,Z) Xv(~(Y! v Z) v (Z n Y!))
Сначала раскроем выражение в скобках⁚
~(Y! v Z) v (Z n Y!) (~Y! n ~Z) v (Z n Y!)
Теперь получаем КНФ для исходной формулы⁚
F(X,Y,Z) (Xv~Y! v ~Z) n (XvZ n XvY!)
3․ Приведение к СДНФ⁚
СДНФ представляет собой дизъюнкцию всех непротиворечивых комбинаций значений переменных, при которых исходная формула принимает значение истина․F(X,Y,Z) (Xv~Y! v ~Z) n (XvZ n XvY!)
Выпишем все непротиворечивые комбинации значений переменных⁚
F(0,0,0) (0 v 1 v 1) n (0 v 0 n 0) 1 n 0 0
F(0,0,1) (0 v 1 v 0) n (0 v 1 n 0) 1 n 0 0
F(0,1,0) (0 v 0 v 1) n (0 v 0 n 1) 1 n 0 0
F(0٫1٫1) (0 v 0 v 0) n (0 v 1 n 1) 1 n 1 1
F(1,0,0) (1 v 1 v 1) n (1 v 0 n 0) 1 n 0 0
F(1,0,1) (1 v 1 v 0) n (1 v 1 n 0) 1 n 0 0
F(1,1,0) (1 v 0 v 1) n (1 v 0 n 1) 1 n 1 1
F(1,1,1) (1 v 0 v 0) n (1 v 1 n 1) 1 n 1 1
Таким образом, получаем СДНФ для исходной формулы⁚
F(X,Y,Z) (Xv~Y! v ~Z) n (XvZ n XvY!) XvZ n XvY!4․ Приведение к СКНФ⁚
СКНФ представляет собой конъюнкцию всех противоречивых комбинаций значений переменных, при которых исходная формула принимает значение ложь․F(X,Y,Z) (Xv~Y! v ~Z) n (XvZ n XvY!)
Выпишем все противоречивые комбинации значений переменных⁚
F(0,0,0) (0 v 1 v 1) n (0 v 0 n 0) 1 n 0 0
F(0,0,1) (0 v 1 v 0) n (0 v 1 n 0) 1 n 0 0
F(0,1,0) (0 v 0 v 1) n (0 v 0 n 1) 1 n 0 0
F(1,0,0) (1 v 1 v 1) n (1 v 0 n 0) 1 n 0 0
Таким образом, получаем СКНФ для исходной формулы⁚
F(X,Y,Z) (Xv~Y! v ~Z) n (XvZ n XvY!) 0
Теперь мы привели исходную формулу к ДНФ, КНФ, СДНФ и СКНФ с помощью равносильных преобразований․ Это позволяет нам более удобно осуществлять анализ и работы с данной логической формулой․