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