Отрицание кванторных предикатов

Два предиката будем считать равносильными, если их значения истинности совпадают при всех значениях входящих в них свободных переменных. При этом имеется в виду, что свободные переменные в одном предикате не являются связанными в другом.

Справедливы следующие равносильности, относящиеся к отрицаниям кванторных предикатов:

.

Действительно, в первой из них левая часть читается: неверно, что для каждого x предикат P(x) истинен; правая – существует x, для которого P(x) ложен. Ясно, что эти два утверждения имеют один и тот же смысл. Аналогичным рассуждением убеждаемся в справедливости второй равносильности.

Таким образом, знак отрицания можно ввести под знак квантора, заменив квантор на двойственный.

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

Пример.

Формулы, в которых из операций алгебры высказываний имеются только операции ^–, Ù, Ú, а знаки отрицания относятся только к элементарным предикатам, называются приведенными формулами.

Тест