Напишем:


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

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

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

 

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

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

Законы алгебры предикатов

Формулы называют равносильными, если при любых подстановках предметных постоянных они принимают одинаковое значение. Если две формулы F1 и F2 равносильны, т.е F1=F2, то они эквивалентны.

Если формула алгебры предикатов F имеет вхождением подфор­мулу Fi , т.е. F( t1;  t2;¼; Fi; ¼ ), для которой существует экви -валентная ей подформула Fj т.е. Fi = Fj, то возможна подстановка всюду в формулу F вместо формулы Fi подформулу Fj без нарушения истинности формулы, т.е.

 F( t1;  t2;¼; Fi; ¼ )= F( t1;  t2;¼; Fj; ¼ ).

Если в законах логики высказываний вместо имеющихся пропозициональных переменных всюду подставить предикаты так, чтобы вместо одной и той же пропозициональной переменной стоял один и тот же предикат, то получится закон логики предикатов.

Основные законы эквивалентных преобразований алгебры предикатов представлены в таблице.

 

 

Наименование закона и правила

Равносильные формулы

Fi=Fj

 

коммутативности

  

"x"y(F2(x; y))="y"x(F2(x; y))*);

$x$y(F2(x; y))=$y$x(F2(x; y))*).

*) только для одноименным кванторов.

 

 

 

дистрибутивности

"x(F1(x))&"x(F2(x))="x(F1(x)&F2(x))*);

$x(F1(x))Ú$x(F2(x))=$x(F1(x)ÚF2(x))**);

*)для логической связки “&” формул только с кванторами " по одной переменной x.

**)для логической связки “Ú” формул только с кванторами $ по одной переменной x.

идемпотентности

ÂÎ{";$}

Âx(F(x))Ú Âx(F(x))= Âx(F(x));

Âx(F(x))&Âx(F(x))= Âx(F(x))

исключенного третьего

Âx(F(x))ÚùÂx(F(x))=и, где       ÂÎ{";$}

противоречия

Âx(F(x))&ùÂx(F(x))=л, где           ÂÎ{";$}

де Моргана

"x(ùF(x))=ù$x(F(x));       $x(ùF(x))=ù"x(F(x))

дополнения

ù (ùÂx(F(x)))= Âx(F(x)),  где           ÂÎ{";$}

свойства констант

Âx(F(x))Ú и=и;                  Âx(F(x))Úл=Âx(F(x));

Âx(F(x))&л=л;                 Âx(F(x))&и=Âx(F(x)),

где ÂÎ{";$}.

 

 

Пример: F=ù$x1"x2(P1 (х1)®"x3 (P22. (х1; x3)ÚP23(x2;x3))).

Упростить формулу.

1)    выполнить операцию отрицания формулы:

F="x1ù"x2(P1 (х1)®"x3 (P22. (х1; x3)ÚP23(x2;x3)));

2)    выполнить операцию отрицания формулы:

F="x1$x2ù(P1 (х1)®"x3 (P22. (х1; x3)ÚP23(x2;x3)));

3) удалить логическую связку “®”:

F="x1$x2ù(ùP1 (х1)Ú"x3 (P22. (х1; x3)ÚP23(x2;x3)));

4) выполнить операцию отрицания формулы:

F="x1$x2(P1 (х1) &ù"x3 (P22. (х1; x3)ÚP23(x2;x3)));

5) выполнить операцию отрицания формулы:

F="x1$x2(P1 (х1) &$x3ù(P22. (х1; x3)ÚP23(x2;x3)));

6) выполнить операцию отрицания формулы:

F="x1$x2(P1 (х1) &$x3 (ùP22. (х1; x3)&ùP23(x2;x3)));

7)    перенести квантор $x3  влево:

F="x1$x2$x3 (P1 (х1) &ùP22. (х1; x3)&ùP23(x2;x3)).

 

       Пример: F="x(P1(х)®ùP2(х))®ù($x(P1(х)) &"x(P2(х))).

Упростить формулу.

1)    удалить логическую связку “®”:

F=ù("x(ùP1(х)ÚùP2(х)))Úù($x(P1(х)) &"x(P2(х)));

2)    выполнить операцию отрицания формулы:

F=$x(ù(ùP1(х)ÚùP2(х))))Ú "x(ùP1(х))Ú$x(ùP2(х)));

3)    выполнить операцию отрицания формулы:

F=$x(P1(х)&P2(х))Ú"x(ùP1(х))Ú$x(ùP2(х)));

4) применить закон дистрибутивности по квантору $x:

F=$x(P1(х)&P2(х)ÚùP2(х))Ú"x(ùP1(х));

5)применить закон дистрибутивности к формуле:

F=$x((P1(х)ÚùP2(х))&(P2(х)ÚùP2(х)))Ú"x(ùP1(х));

6) применить закон исключенного третьего и свойство констант для логической связки “&”:

F=$x((P1(х)ÚùP2(х)))Ú"x(ùP1(х));

7) применить закон де Моргана:

F=$x((P1(х)ÚùP2(х)))Úù$x(P1(х));

8) применить закон дистрибутивности по квантору $x:

F=$x(P1(х))Ú$x(ùP2(х))Úù$x(P1(х));

9) применить закон исключенного третьего:

F=$x(ùP2(х))Úи;

10)          применить свойство констант для логической связки “Ú”:

F=и,

т.е. формула F="x(P1(х)®ùP2(х))®ù($x(P1(х))&"x(P2(х))) является тождественно истиной.

 

 

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