Шаг 1. Исключить всюду логические связки « и ® по правилам:
(F1«F2)=(F1®F2)& (F2®F1)=(ùF1ÚF2)&(ùF2ÚF1);
(F1®F2)=(ù F1ÚF2);
Шаг 2. Продвинуть отрицание до элементарной формулы по правилам:
ù»x(F)=$x(ùF); ù(F1ÚF2)=(ùF1&ùF2);
ù$x(F)=»x(ùF);. ù(F1&F2)=(ùF1ÚùF2);
Шаг 3. Переименовать связанные переменные по правилу:
“ найти самое левое вхождение предметной переменной такое, что это вхождение связано некоторым квантором, но существует еще одно вхождение этой же переменной; затем сделать замену связанного вхождения на вхождение новой переменной “, операцию повторять пока возможна замена связанных переменных;
Шаг 4. Вынести кванторы влево по законам алгебры логики.
Шаг 5. Преобразовать бескванторную матрицу к виду КНФ. Алгоритм приведения матрицы формулы к виду КНФ приведен в алгебре высказываний.
Пример : F=(«x(P1 (х)®»y(P2 (y)®P3 (z))))&(ù»y(P24 (x; y)®P5.(z))).
Привести формулу к виду ПНФ.
l) удалить логические связки “®”:
F=(«x(ùP1 (х)Ú»y(ù P2 (y)ÚP3 (z))))&(ù»y(ù P24 (x; y)ÚP5.(z)));
2) применить закон де Моргана ù «x( F(x))=$x ù F(x)):
F=(«x(ùP1.(х)Ú»y(ù P2 (y)ÚP3 (z))))&($y(ù(ù P24 (x; y)ÚP5.(z)));
3) применить закон де Моргана ù(F1ÚF2)=(ùF1&ùF2):
F=»x(ùP1.(х)Ú»y(ù P2 (y)ÚP3 (z)))&($y(P24 (x; y)&(ùP5.(z))));
4) переименовать связанную переменную x=w:
F=»w(ùP1 (w)Ú»y(ù P2 (y)ÚP3 (z)))&($y(P24 (x; y)&(ù P5.(z))));
5) переименовать связанную переменную y=v:
F=»w(ùP1 (w)Ú»v(ùP2 (v)ÚP3 (z)))&($y(P24 (x; y)&(ùP5.(z))));
6) вынести квантор «v влево:
F=»w»v(ùP1 (w)ÚùP2 (v)ÚP3 (z))&($y(P24 (x; y)&(ùP5.(z))));
7) вынести квантор $y влево:
F=»w»v$y(ùP1 (w)ÚùP2 (v)ÚP3 (z))&P24 (x; y)&ùP5.(z).
Матрица ПНФ содержит три элементарных дизъюнкта:
K={(ùP1 (w)ÚùP2 (v)ÚP3 (z)); P4 (x; y); ùP5.(z)}.
Пример: F = «x(P1 (х)«$x(P2 (x)))®»y(P3.(y)).
Привести формулу к виду ПНФ.
1) удалить логические связки “«”:
F=»x((P1 (х)®$x(P2 (x)))&($x(P2 (х))®P1 (x)))®»y(P3.(y));
2) удалить логические связки “®”:
F=ù(«x((ùP1.(х)Ú$x(P2 (x)))&(ù$x(P2.(х))ÚP1 (x)))Ú»y(P3.(y));
3) применить закон ù»x(F(x))=$x(ùF(x)):
F=$x(ù((ùP1.(х)Ú$x(P2 (x)))&(ù$x(P2 (х))ÚP1 (x))))Ú»y(P3.(y));
4) применить закон де Моргана ù(F1&F2)=(ùF1ÚùF2):
F=$x((ù(ùP1 (х)Ú$x(P2 (x)))Ú(ù(ù$x(P2.(х))ÚP1 (x))))Ú»y(P3.(y));
5) применить закон де Моргана ù(F1ÚF2)=(ùF1&ùF2):
F=$x((P1 (х)&(ù$x(P2 (x))))Ú($x(P2 (х))&(ùP1 (x))))Ú»y(P3.(y));
6) применить закон ù$x(F(x))= «x (ùF(x)):
F=$x((P1 (х)&»x(ùP2.(x)))Ú($x(P2 (х))&(ùP1 (x))))Ú»y(P3.(y));
7) переименовать связанную переменную x=z:
F=$z((P1.(z)&»x(ù P2 (x)))Ú($x(P2.(х))&(ùP1.(z))))Ú»y(P3.(y));
8) переименовать связанную переменную x=w:
F=$z(P1 (z)&»w(ùP2 (w))Ú$x(P2 (х)&ùP1 (z)))Ú»y(P3.(y));
9) вынести квантор «w, $x и «y влево:
F=$z»w$x»y(P1 (z)&ùP2 (w)ÚP2 (х)&ùP1 (z)ÚP3.(y));
10) преобразовать матрицу к виду КНФ:
F=$z»w$x»y((P1 (z)ÚP2 (х)ÚP3.(y))&(ùP2 (w)ÚP2 (х)ÚP3.(y))& (ùP2 (w)ÚùP1 (z)ÚP3.(y))).
Матрица ПНФ содержит три элементарных дизъюнкта:
K={(P1 (z)ÚP2 (х)ÚP3.(y)); (ùP2 (w)ÚP2 (х)ÚP3.(y)); (ùP2 (w)ÚùP1 (z)ÚP3.(y))}.
Пример: F=»x$y(P21 (х; y))&ù($x»y(P22(x; y))).
Привести формулу к виду ПНФ.
1) применить закон ù$x(F(x))=»x(ùF(x)):
F=»x$y(P21(х; y))&(«xù(«y(P22(x; y))));
2) применить закон ù»x(F(x))= $x(ùF(x)):
F=»x$y(P21(х; y))&(«x$y(ù(P22(x; y))));
3) вынести квантор «x по закону дистрибутивности:
F=»x($y(P21(х; y))&$y(ù(P22(x; y))));
4) переименовать связанную переменную y=v:
F=»x($z(P21(х; z))&$y(ù(P22(x; y))));
5) вынести кванторs $z и $y влево:
«x$z$y(P21(х; z)&ùP22(x; y)).
Матрица ПНФ содержит два элементарных дизъюнкта:
K={P21(х; z); ùP22(x; y)}.
Пример: M=P1(z)&ùP2(w)ÚP2(х)&ùP1.(z)ÚP3.(y);
1) по закону дистрибутивности:
M=P1.(z)&ùP2 (w)Ú(P2 (х)ÚP3.(y))&(ù P1 (z)Ú(P3.(y));
2) по закону дистрибутивности:
M=(P1.(z)&ùP2.(w)ÚP2.(х)ÚP3.(y))&(P1.(z)&ùP2.(w)ÚùP1.(z)Ú P3.(y));
3) по закону дистрибутивности:
M =(P1.(z)ÚP2.(x)ÚP3.(y))&(ù P2.(w)ÚP2.(x)ÚP3.(y))&
(P1.(z)ÚùP1.(z)ÚP3.(y))&(ùP2.(w)ÚùP1.(z)ÚP3.(y));
4) по закону исключенного третьего:
M=(P1.(z)ÚP2.(x)ÚP3.(y))&(ùP2.(w)ÚP2.(x)ÚP3.(y))&
&(ù P2.(w)ÚùP1.(z)ÚP3.(y)).
Матрица содержит три элементарных дизъюнкта:
K={(P1.(z)ÚP2.(x)ÚP3.(y)); (ùP2.(w)ÚP2.(x)ÚP3.(y)); (ù P2.(w)ÚùP1.(z)ÚP3.(y))}.
Дизъюнкты матрицы содержат контрарные атомы P1.(z) и ùP1.(z), P2.(x) и ùP2.(w), свободные переменные которых могут быть одинаковыми или разными.