Напишем:


✔ Реферат от 200 руб.
✔ Контрольную от 200 руб.
✔ Курсовую от 500 руб.
✔ Решим задачу от 20 руб.
✔ Дипломную работу от 3000 руб.
✔ Другие виды работ по договоренности.

Узнать стоимость!

Не интересно!

 

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

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

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

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

 

 
форекс

Случайная новость