31. Кванторы

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

а) Выражение (Vx)P(x) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен для всех предметов из поля М. Выра­жение (Vx)P(x) читается «для всякого х, Р(х)», здесь символ V — квантор общности.

б) Выражение (Зх)Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен хотя бы для одного предмета из по­ля М. Выражение (Зх)Р(х) читается «существует х, что Р(х)»; символ 3 — квантор существования.

Рассмотрим примеры применения операций квантирования к преди­катам. Пусть даны предикаты над полем натуральных чисел:

1. х² = х • х, тогда (Vx)(x² = х ■ х) — истинное высказывание;

2. х + 2 = 7, тогда (Vx)(x + 2 = 7) — ложное высказывание; а (Зх)(х + 2 = 7) — истинное высказывание;

3. х + 2 = х, тогда (Vx)(x + 2 = х) — ложное высказывание.

Название	Прочтение	Обозначение
Квантор общности	«все», «всякий», «каждый», «любой»	V
Квантор существования	« Хотя бы один », « найдется », « сущест­вует»	э

Квантор общности — это оператор, приводящий в соответствии лю­бому заданному предикату у = Р(х) такую двузначную логическую пере­менную z, которая принимает значение 1 тогда и только тогда, когда у = 1 при всех значениях х.

Квантор существования — это оператор, приводящий в соответствии любому одноместному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда у = О при всех значениях х.

Рассмотрим некоторые общие свойства введенных операторов.

В соответствии с определениями кванторов логическая переменная z в выражениях

2 = (Vx)P(x)l 2 = (3x)P(x)J

уже не является функцией предметной переменной х.

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

Например, в предикате

(Vx)A(x, у) V (3z)B(z, и)

переменные х и z — связанные, а у и и — свободные.

Если квантор общности или квантор существования применяется не к одноместному предикату, а к какому-нибудь /^-местному предикату, то в результате этого получается снова предикат, но за счет связывания одной предметной переменной получаемый предикат будет (к — 1)-местным.

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

Наряду с определенными предикатами — для которых истинность или ложность известны для каждого набора значений свободных пред­метных переменных, будем рассматривать переменные предикаты, для которых не определены значения. Будем обозначать переменные преди­каты большими буквами из конца латинского алфавита с приписанными предметными переменными или без них:

Щх₁₍...,х_п); Щх,у),....

Применяя к переменным предикатам операции A; V; —>; о; ; V; 3, по­лучим формулы логики предикатов, т. е. формулой логики предикатов называется выражение, составленное из переменных предикатов с помо­щью логических операций и кванторов и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.

Например, ((Vx)W(x, у) v В) —» U(z) — формула логики предикатов.

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

Сформулируем следующие правила.

1. Формула логики предикатов называется атомарной, т. е. элемен тарной, если в ней нет связанных переменных.

2. Пусть F — формула, тогда F — тоже формула. Свободные и связан­ные переменные формулы F — это соответственно свободные и связанные переменные формулы F.

3. Пусть F и G — формулы, причем в них нет предметных перемен­ных, которые были бы связаны в одной формуле и свободны в другой.

Тогда F Л G, F V G, F —>• G, F -н> G — формулы, в которых свободные переменные формул F и G остаются свободными, а связанные — связан­ными.

4. Пусть F — формула, содержащая свободную переменную х. Тогда (Vx)F, ( ix)F — тоже формулы, в которых переменная х связана, а осталь­ные свободные переменные, входящие в F, остаются свободными.

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

Значение формулы определено лишь тогда, когда задана какая-то ин­терпретация входящих в нее символов. Под интерпретацией понимают систему М = (М, f), состоящую из непустого множества М и соответ­ствия f, которое сопоставляет каждой формуле определенный предикат. При заданной интерпретации предметные переменные пробегают множе­ство М, а логические символы и символы кванторов имеют свой обычный смысл.