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