Алгоритм приведения формулы к виду ПНФ

Шаг 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), свободные переменные которых могут быть одинаковыми или разными.

 

Логика - доступно для всех