§ 5. Равносильность формул алгебры предикатов. Основные равносильности алгебры предикатов.

Определение. Формулы алгебры предикатов F и Н с одноименными предикатными переменными называются равносильными, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом же множестве, они обращаются в равносильные предикаты.

Очевидно, что для алгебры предикатов место равносильности 1-29 алгебры высказываний, причем если какая-либо из этих формул содержит значения истины или лжи, то в формуле алгебры предикатов истина заменяется на выражение , а ложь на выражение .

Кроме равносильностей 1-29 в алгебре предикатов имеются новые равносильности относительно операций навешивания кванторов.

Рассмотрим основные из них.

I. (х) (y) F(x,y)  (y) (x) F(x,y)

II. (x) (y) F(x,y)  (y) (x) F(x,y).

Из формул I и II следует, что одноименные операции навешивания кванторов обладают свойством коммутативности, но разноименные операции навешивания кванторов таким свойством не обладают!

III. (х) (F(x)  H(x))  (x) F(x)  (x) H(x).

IV. (x) (F(x)  H(x))  (x) F(x)  (x) H(x).

Из формул III и IV следует, что операции навешивания кванторов  и  обладают свойством дистрибутивности соответственно относительно конъюнкции и дизъюнкции.

V.

VI.

Очевидно, что данные формулы позволяют выражать один квантор через другой.

VII.

VIII.

Заметим, что часто формулы VII и VIII называют формулами де Моргана алгебры предикатов.

Приведенные выше восемь дополнительных формул алгебры предикатов позволяют сложные предикатные формулы преобразовать в более простые, используя, разумеется, формулы 1-29 алгебры высказываний.