Формализация предложений с помощью логики предикатов

Рассмотрим новые операции, которые применяются к предикатам или высказываниям и дают в результате их применения предикаты или высказывания. Эти операции выражают утверждения общности или существования.

Квантор общности.Пусть А (х) — предикат от одной свободной переменной х. Под выражением будем подразумевать высказывание, истинное, если А (х) прини­мает значение 1 для всех допустимых значений перемен­ной х, т. е. если предикат А (х) тождественно истинен, и ложное в противном случае. Высказывание уже не зависит от х. Символ , приписываемый слева к пре­дикату А (х), называется квантором общности по перемен­ной х. Если же А есть высказывание, то есть выска­зывание, истинное тогда и только тогда, когда А истинно.

Рассмотрим теперь предикат от нескольких свободных переменных, например предикат А (х, у, z) от трех пере­менных. Этот предикат при произвольной замене всех сво­бодных переменных, кроме х, их значениями b и с пред­ставляет собой предикат, зависящий только от свободной переменной х, а выражение

есть высказывание. Предикат становится высказыванием в результате задания значений всех входя­щих в него свободных переменных, кроме х, значит, от х не зависит. Таким образом, зависит от всех свободных переменных, входящих в А(х, у, z), кроме х, т. е. это двухместный предикат от у и z. Этот предикат на данном наборе значений свободных переменных b, с принимает значение 1 тогда и только тогда, когда преди­кат А(х, у, z), зависящий только от одной свободной пе­ременной x, является тождественно истинным. Символ можно читать так: «для всякого х» или «для всех х»_, а запись читается так: «для всякого х имеет место А (х, у,z)» или, короче, «для каждого х A (x, у, z)».

Переменная х, от которой предикат не зависит, называется связанной переменной(в отличие от переменных y_t z, которые являются свободными).

Для квантора существования употребляется символ , приписываемый слева к преди­кату или высказыванию. Пусть А (х) — предикат от одной свободной переменной х. Под выражением будем подразумевать высказывание, истинное, если А (х) прини­мает значение 1 хотя бы для одного из допустимых зна­чений переменной х, т. е. предикат А (х) является выпол­нимым, и ложное в противном случае.

Пусть теперь A(x, у, z) есть трехместный предикат. Если в этом предикате заменить все свободные переменные, кроме х их значениями, например значениями b, с, то получится предикат A (x, b, с), зависящий только от од­ной свободной переменной х, а выражение

будет высказыванием. Значит, выражение есть предикат, становящийся высказыванием в резуль­тате задания значений всех свободных переменных, кроме x и, значит, от х не зависит. Таким образом, выражение есть предикат, зависящий только от у и z,значит, применение квантора к трехместному предикату привело к двухместному предикату. Переменная х, от ко­торой предикат не зависит, называется связанной переменной.

Предикат принимает значение 1 на данном наборе b, с допустимых значений тогда и только тогда, когда одноместный предикат А (х, b, с) выполним.

Символ называется квантором существования по переменной х и читается так: «существует х такое, что». Выражение читается так: «хотя бы при одном х имеет место А (х, у, z) или «существует такое х, что А(х, у, z)».

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

или .

Скобки обычно опускают, получая при этом выражения

или .

Отметим, что одинаковые кванторы можно переставлять, получая при этом эквивалентные высказывания, т. е. истин­ные эквиваленции:

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

Рассмотрим применение кванторов на примере. Пусть x+y > 0 — двухместный предикат, где х и y-целочислен­ные переменные. Этот предикат выражает положительность суммы двух целых чисел и представляет собой некоторое высказывание всякий раз, когда переменным х и у при­даются конкретные значения. Если к этому предикату при­менить квантор существования по переменной у, то полу­чится одноместный предикат

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

утверждающее, что для всякого целого числа х существует некоторое целое число у такое, что их сумма положительна. Это высказывание надо отличать от высказывания

утверждающего, что существует целое число, сумма кото­рого со всяким целым числом положительна. Это послед­нее высказывание ложно.

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

Пусть А (х) — обозначение предиката «х — нечетное число», а В (х) — обозначение предиката «х — простое число», где х — целочисленная переменная.

1. Высказывание «Всякое нечетное число является про­стым числом» можно переформулировать следующим обра­зом: «Для всякого х, если х — нечетное, то x — простое число». Теперь ясно, что это высказывание на языке пре­дикатов запишется так:

2. Высказывание «Никакое нечетное число не является простым числом», или «Для всякого х_, если х — нечетное, то х не является простым», в символической форме запи­шется так:

Заметим, что истинностное значение высказывания в наших рассуждениях не играет роли.

3. Следующий тип высказывания: «Некоторые нечетные числа — простые». Суть его в том, что существует такое х, которое одновременно является и нечетным числом, и про­стым. Поэтому высказывание третьего типа на языке ло­гики предикатов запишется в виде

Эта последняя запись не эквивалентна записи

К четвертому типу относится высказывание «Некоторые нечетные числа не являются простыми»:

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

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

Равносильность соответствует высказыванию «Существует объект х, не удовлетворяю­щий условию А(х)».

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

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

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

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

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