П.3. Кванторные операции над предикатами

Пусть имеется предикат Р (х), определенный на мно­жестве М. Если , то при подстановке а вместо х в предикат Р (х) получится высказыва­ние Р (а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных выс­казываний в логике предикатов рассматривается еще две операции, которые превращают одноместный пре­дикат в высказывание.

Определение 8. Пусть Р (х) – предикат, определен­ный на множестве М. Под выражением понима­ют высказывание, истинное, когда Р (х) тождественно истинный на множестве М предикат, и ложное в против­ном случае. Это высказывание уже не зависит от х. Со­ответствующее ему словесное выражение будет: «Для вся­кого х Р (х) истинно». Символ называют квантором всеобщности.

Переменную х в предикате Р (х) называ­ют свободной (ей можно придавать различные значения из М), в высказывании переменную х называют связанной квантором .

Определение 9. Пусть Р (х) – предикат, определенный на множестве М. Под выражением понимают выс­казывание, которое является истинным, если существует хотя бы один элемент , для которого Р (х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет: «Существует х, при котором Р (х) истинно». Сим­вол называют квантором существования. В высказы­вании переменная х связана квантором .

Приведем пример употребления кванторов.

Пример 5. Пусть на множестве N натуральных чисел задан предикат Р (х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания: – «Все натуральные числа кратны 5»; – «Су­ществует натуральное число, кратное 5». Очевидно, пер­вое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание истинно только в том единственном случае, когда Р (х) – тождественно истинный предикат, а высказывание ложно толь­ко в том единственном случае, когда Р (х) – тождествен­но ложный предикат.

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

Таким образом, может быть получено одно из восьми высказываний: , , , , , , , .

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

Пример 6. Пусть предикат Q (х,у): «х у» определен множестве N × N. Показать, что высказывания и имеют различные логические значения.

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

Далее рассмотрим предикат Р (x), опреде­ленный на конечном множестве М = { а ₁, а ₂, …, а_n }.

Если предикат Р (x) является тождественно истинным, то истинными будут высказывания Р (а ₁), Р (а ₂),..., Р (а_n). При этом истинными будут высказыва­ние и конъюнкция Р (а ₁)& Р (а ₂)&...& Р (а_n).

Если же хотя бы для одного элемента Р (а_k) окажется ложным, то ложными будут высказывание и конъюнкция Р (а ₁)& Р (а ₂)&...& Р (а_n). Следова­тельно, справедлива равносильность

.

Нетрудно показать, что справедлива и равносиль­ность

.

Это означает, что кванторные операции обобщают операции конъюнкции и дизъюнкции на случай бесконечных облас­тей.