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

Рассмотрим ряд равносильностей, играющих большую роль в логике предикатов. Строгое их доказательство проводить не будем. Равносильность

соответствует обычному пониманию смысла кванторов.

Высказывания «Неверно, что всякий объект удовлетворяет условию A(х)» и «Существует объект х, не удовлетворяющий условию имеют одинаковый смысл, что и отражает равносильность (1).

Равносильность

соответствует тому, что высказывание «Неверно, что существует объект удовлетворяющий условию обычно понимают в том же смысле, что и высказывание «Ни один объект не удовлетворяет условию

Применяя отрицание к обеим частям (1) и (2) и учитывая закон двойного отрицания, получаем еще две равносильности:

они показывают, что квантор существования можно выразить через квантор общности и наоборот.

Следующие две равносильности выражают свойства дистрибутивности квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции:

С истинностью этих равносильностей находятся в соответствии следующие содержательные рассуждения. Левая часть (5) принимает значение И в том и только в том случае, когда или или принимает значение И хотя бы для одного допустимого значения т. е. когда по крайней мере один из предикатов выполним. Но как раз в этом и только в этом случае будет выполним предикат т. е. будет истинным высказывание Аналогичные рассуждения можно провести относительно равносильности (6).

Квантор существования не дистрибутивен относительно конъюнкции, т. е. формулы не равносильны. Нетрудно подобрать пример двух выполнимых предикатов, конъюнкция которых невыполнима. Для таких предикатов первая формула принимает значение Л, а вторая — И. Также не равносильны формулы и т. е. квантор общности не дистрибутивен относительно дизъюнкции.

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

В логике высказываний существует общий метод, позволяющий за конечное число шагов выяснить для любой пропозициональной формулы, является ли она тождественно истинной (метод Истинностных таблиц). В логике предикатов не существует такого общего метода, по которому за конечное число шагов для любой предикатной формулы можно решить, общезначима она или нет. Для некоторых видов формул такие методы существуют.