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

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

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Узнать стоимость

Формулы называют равносильными, если при любых подстановках предметных постоянных они принимают одинаковое значение. Если две формулы 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(х))) является тождественно истиной.

Внимание!
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы.

 

 

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

  • Задание 20.
     Правильно ли сделаны следующие выводы?...