Дадим для примера определение первого предиката из приведенной группы.

Предикат ¬P(x) обращается в истинное высказывание при

всех тех и только тех значениях x из A, при которых предикат P(x) превращается в ложное высказывание, т. е. область истинности предиката ¬P(x) является дополнением до A области ис-

тинности предиката P(x).

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

§ 13. Кванторы

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

Если в P(x1, x2 , ... , xn ), где P — предикатная постоянная, а x1, x2 , ... , xn — предметные переменные, подставить вместо всех предметных переменных какие-нибудь их значения a1, a2 , ... ,an , то получим высказывание P(a1, a2 , ... , an ), истинное или ложное, относящееся к конкретной n-ке предметов (a1,a2 , ... , an ).

Например, если в двуместном предикате «x делится на y» подставить вместо переменных x и y пару чисел (12, 4), то получится истинное высказывание «12 делится на 4», если же подставить пару чисел (5, 3), то получится ложное высказывание «5 делится на 3». Каждое из этих высказываний относится к определенной паре чисел.

— 46 —

Из предикатов можно строить не только высказывания, относящиеся к определенной системе (паре, тройке и т. д.) предметов, но и высказывания, выражающие свойства предметов или отношения между предметами некоторого множества (высказывания о всеобщности), и высказывания о существовании предметов из данного множества (высказывания о существовании). Для построения таких высказываний вводятся операции связывания кванторами

(или навешивания кванторов).

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

В первом случае истинно высказывание «Для всех x из A имеет место (истинно) P(x)», во втором — высказывание «Существует x из A такое, что P(x) — истинно».

Выражение «для всех x» называется квантором общности и обозначается ( x).

Выражение «существует x такое, что» называется квантором существования и обозначается ( x).

Приписывание спереди к предикатной формуле квантора общности или существования называется операцией навешивания квантора или связывания квантором, а переменная, которая связывается квантором, называется связанной переменной.

Например, если P(x) — предикат «x — четное число», то ( x)P(x) — ложное высказывание «Всякое число — четное», а ( x)P(x) — истинное высказывание «Существует число x такое,

что оно четное».

Квантор общности можно рассматривать как обобщение конъюнкции, а квантор существования — как обобщение дизъюнкции.

Выше приведен пример преобразования одноместного предиката в высказывание с помощью квантора. Чтобы многоместный предикат преобразовать в высказывание, необходимо все предметные переменные связать кванторами. Пусть, например, x и y — переменные для действительных чисел, а < — знак бинарного отноше-

— 47 —

ния. Тогда из предиката x < y, связыванием переменных x и y кванторами можно получить восемь высказываний:

( x)( y)[x < y] — «для всякого x и для всякого y x < y»;	(1)
( y)( x)[x < y] — «для всякого y и для всякого x x < y»;	(2)

( x)( y)[x < y] — «существуетx исуществуетy такие, чтоx < y»; (3) ( y)( x)[x < y] — «существуетy исуществуетx такие, чтоx < y»; (4) ( x)( y)[x < y] — «для всякого x существует y такое, что x < y»; (5) ( y)( x)[x < y] — «существует y такое, что длявсякого x x < y»; (6) ( x)( y)[x < y] — «существует x такое, что длявсякого y x < y»; (7) ( y)( x)[x < y] — «для всякого y существует x такое, что x < y». (8)

Нетрудно заметить, что высказывания (1) и (2) оба ложны и имеют один и тот же смысл; высказывания (3) и (4) оба истинны и имеют один и тот же смысл. Но структуры высказываний (1) и (2), так же как структуры высказываний (3) и (4), отличаются лишь порядком одноименных кванторов. Таким образом, изменение порядка одноименных кванторов не влияет на смысл и значение истинности высказывания.

Высказывание (5) истинно, а высказывание (6) ложно. Но структуры этих высказываний отличаются лишь порядком разноименных кванторов. Как видно, изменение порядка разноименных кванторов приводит к изменению смысла и, возможно, значения истинности высказывания. Высказывание (5) утверждает об отсутствии во множестве R наибольшего числа, а высказывание (6) — о наличии такого числа.

Высказывание (7) ложно, а высказывание (8) истинно. Первое утверждает о наличии в R наименьшего числа, второе — об отсутствии такового. Структуры этих высказываний, так же как высказываний (5) и (6), отличаются лишь порядком разноименных кванторов.

Если двуместный предикат P(x, y) связывается квантором только по одной переменной, то в результате получается не высказыва-

— 48 —

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

Рассмотрим, например, формулу

( x)[x < y], где x, y A={1,2,3,4}.

y	( x)[x < y]
1	Л
2	И
3	И
4	И

Легко видеть, что эта формула определяет логическую функцию одной свободной переменной y. Составим таблицу истинности для этой функции.

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

Вообще, если в n-местном предикате связать кванторами k переменных (k ≤n), то получим логическую функцию n−k свободных переменных, т. е. n−k -местный предикат. В частности, при k =n получается 0-местный предикат, или высказывание.

§ 14. Формулы логики предикатов

Уточним смысл термина «формула» для логики предикатов. Всякая высказывательная переменная есть формула.

Всякий предикатный символ P(...), все пустые места которого замещены предметными переменными или постоянными есть формула.

Если ϕ(x1, x2 , ... , xn ) — формула, то ( xi )ϕ(x1, x2 , ... , xn ) и ( xi )ϕ(x1, x2 , ... , xn ) тоже формулы. В них переменная xi связана,

аостальные переменные такие же, как в ϕ(x1, x2 , ... , xn ).

—49 —

Если ϕ и ψ — формулы, причем в них нет таких предметных переменных, которые связаны в одной формуле и свободны в другой, то ¬ϕ,(ϕ ψ),(ϕ ψ),(ϕ ψ),(ϕ ψ) — тоже формулы. При этом свободные переменные в формулах ϕ и ψ остаются свобод-

ными во всех этих формулах.

Других формул в логике предикатов нет.

Формулы, определенные в 1 и 2, называют также элементарными формулами логики предикатов. Из 1 и 4 следует, что все формулы логики высказываний являются также формулами логики предикатов.

Приведем несколько примеров выражения математических предложений на языке логики предикатов.

1. Предложение «Всякое натуральное число больше нуля» можно сформулировать в виде импликации с квантором общности: «Для всякого x, если x натуральное число, то оно больше 0». В этом высказывании присутствуют два одноместных предиката: «x — натуральное число» — (N(x)) и x > 0 (последний предикат обозначим B(x)). После выделения этих двух одноместных предикатов высказывание запишется в виде:

( x)[x N x >0]

или в других обозначениях предикатов

	( x)[N(x) B(x)].
2.	Предложение « lim a	n	=a	— предел последовательности
	n→∞
{an }	равен a», по определению означает: «Для всякого положи-

тельного числа ε существует такой номер nε , что для всякого номера n, большего nε , выполнено неравенство an −a <ε».

Словесная формулировка определения составлена так, чтобы можно было без всяких преобразований записать его в символах логики предикатов:

— 50 —