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

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

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

.

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

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

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

Пример.

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

Пример 1. Какие из следующих выражений явля­ются формулами логики предикатов? В каждой форму­ле выделите свободные и связанные переменные.

1)

2)

3) P(x)& x Q(x);

4) x (P(x) →Q(x)) ↔ ( x P(x) → x R(x,y));

5) (P(x) ↔Q(x)) v y ( y R(y));

6) x z (P(x,y) →P(y,z)).

Решение. Выражения 1), 2), 4), 6) являются форму­лами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3) и 5) не яв­ляются формулами. В выражении 3) операция конъюн­кция применена к формулам Р(х) и x Q(x); в первой из них переменная х свободна, а во второй связана кванто­ром общности, что противоречит определению форму­лы. В выражении 5) квантор существования по перемен­ной у навешен на формулу y R(y), в которой перемен­ная у связана квантором общности, что также противо­речит определению формулы.

В формуле 1) переменная у свободна, а переменные х и z связаны. В формуле 2) нет предметных переменных. В формуле 4) переменная х связана, а переменная у сво­бодна.

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значения трех видов переменных, входящих в формулу:

         а)    переменных высказываний;

              б)     свободных предметных переменных из множества М;

         в)    предикатных переменных.

При конкретных значениях этих переменных фор­мула принимает конкретное логическое значение.

Пример 2. Дана формула x(P(x)&Q(x) →R(x)), где предикаты Р(х}, Q(x) и R(x) определены на множестве N. Найти ее значение, если

 Р(х): «число х делится на 3», Q(х): «число х де­лится на 4», R{x): «число х делится на 2»;

 Р(х): «число х делится на 3», Q(x): «число х делится на 4», R(x): «число х делится на 5».

Решение. В обоих случаях конъюнкция P(x)&Q(x) есть утверждение, что число х делится на 12. Но тогда при всех х, если число х делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.

Так как из делимости числа х на 12 не при всех х сле­дует делимость числа х на 5, то в случае 2) формула ложна.

Пример 3. Вычислить значение формулы х у P(х,у) → х у Р(х,у), если предикат Р(х,у) имеет значение Р⁰(х,у) - «число x меньше числа у» иопределен на множестве М = N х N.

Решение. Так как при указанном значении предика­та Р(х, у) высказывание x у Р(х, у) означает утвержде­ние, что для любого натурального числа х найдется нату­ральное число у, большее числа х, то это высказывание истинно. В то же время высказывание х у Р(х,у) оз­начает утверждение, что существует натуральное число х, которое меньше любого натурального числа у, которое ложно. При этом исходная формула, очевидно, ложна.