Глава 7. Начала логики предикатов

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

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

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

Примеры. (1) Формула 4x3yF(х, у) содержит один двуместный предикатный символ F(х,у). При замещении его предикатом, определенным на множестве натуральных чисел и означающим х < у, формула превращается в истинное предложение «Для любого натурального числа существует натуральное число, которое больше него», при замещении предикатом, определенным на том же множестве и означающим х > у, —в ложное предложение «Для любого натурального числа

существует натуральное число, которое меньше него», при замещении

у

х

мать», при замещении предикатом, определенным на том же множестве

ух человека есть или был сын».

Если в формуле —ЗхЛ(х,у) — —B(y) заместить двуместный предикатный символ Л(х, у) предикатом, определенным на множестве лю-

ху

ный предикатный символ B(x) —предикатом, определенным на том же

х

у

у

у

Л(х, у)

ху

ух

B(x) — предикатом, определенным на множестве людей и означающим

х

у

учителем в школе» (очевидно, тождественно истинный).

Формула Ухіуіг(Л(х, у) & A(y, z) — Л(х, z)) при замещении пре-

Л( х, у) ху

х у z х у у z

х z х

с у'ом» —в ложное предложение «Каковы бы ни были люди х, у, z, если х знаком с у'ом и у знаком с Z'OM, ТО х знаком с Z'OM».

(4) Рассмотрим формулу УхіуУгіі(Б(х, у, z) & S(у,х,Ь) — E(z,t)).

2. В логике предложений главным рабочим инструментом было у нас понятие равносильности формул. Аналогичное понятие можно ввести и в логике предикатов. Именно, две незамкнутые формулы логики предикатов называются равносильными, если при любом замещении входящих в них предикатных символов конкретными предикатами они превращаются в один и тот же предикат, а две замкнутые — если при любом таком замещении они превращаются в предложения, имеющие одинаковые истинностные значения.

Для обозначения равносильности формул логики предикатов исполь- =

Рассмотрим теперь несколько примеров.

Пример 1. —(F(x)&G(x)) = —F(х) V—G(x).

В самом деле, если мы заместим F и G произвольными одноместными предикатами Fo и Go, а затем дадим переменной х произвольное значение х0, то формула —(F(х) & G(x)) превратится в предложение — (F0(x0) & G0(x0)), а формула —F(х) V— G(x)— в предложение —Fo(xo) V— G0(x0); но истинностные значения этих предложений совпадают. Таким образом, значения предикатов — (F0(x) & G0 (х)) и —F0(x) V— G0(x) совпадают при любых значениях х, — иначе говоря, это не разные предикаты, а один и тот же предикат. (Напомним, что предикат — частный случай функции, а функции совпадают, если совпадают их области определения и совпадают их значения при любых значениях независимой переменной.)

Замечание. Проведенное только что рассуждение было основано на том, что формулы —(F(x)&G(x)) и —F(х) V—G(x) получаются из равносильных формул логики предложений —(X & Y) и —X V —Y заменой элементарных предложений X и Y формулами F(х) и G(x). Точно

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

Пример 2. Vx(F(x)&G(x)) = VxF(x)&VxG(x).

В самом деле: обе эти формулы замкнуты, и первая из них при замещении F(x) и G(x) конкретным: предикатами Fo(x) и G0(x) превращается в истинное предложение в том и только том случае, когда предикат F0(x)&G0(x) тождественно истинен; но этот предикат тождественно истинен тогда и только тогда, когда тождественно истинны оба предиката F0(x) и G0(x) —иначе говоря, когда истинны предложения VxF0(x) и VxG0(x), или, еще иначе, когда истинна их конъюнкция, в которую как раз и превратилась наша вторая формула.

Пример 3. Формулы 3x(F(x)&G(x)) и 3xF(x)&3xG(x) не равносильны.

Чтобы убедиться в этом, достаточно найти одно замещение F(x) и G(x) конкретными предикатами, при котором одна из наших формул превратилась бы в истинное предложение, а другая —в ложное. Но если FG

xx

то первая формула превратится в ложное предложение «Существует натуральное число, являющееся одновременно четным и нечетным», а вторая —в истинное предложение «Существуют как четные, так и нечетные натуральные числа».

Пример 4. 3x(F(x) V G(x)) = 3xF(x) V3xG(x).

F(x) G(x)

ми предикатами F0(x) и G0(x) превращается в ложное предложение в том и только том случае, когда предикат F0(x) V G0(x) тождественно ложен; но этот предикат тождественно ложен тогда и только тогда, когда тождественно ложны оба предиката F0(x) и G0(x) — иначе говоря, когда ложны предложения 3xF0(x) и 3xG0(x), или, еще иначе, когда ложна их дизъюнкция, в которую превратилась вторая формула.

Пример 5. Формулы Vx(F(x) V G(x)) и VxF(x) VVxG(x) не равносильны.

Читателю предлагается убедиться в этом самостоятельно, подобрав подходящее замещение (как в примере 3).

Пример 6. Формулы Vx3yF(x,y) и 3yVxF(x,y) не равносильны.

Действительно, если заместить предикатный символ F(x,y) предикатом, определенным на множестве натуральных чисел и означающим x < y, то первая формула превратится в истинное предложение «Для любого натурального числа существует натуральное число, которое больше него» (ср.

Задачи.

(а) Доказать, что Vx3y(F(x)&G(y)) = 3yVx(F(x)&G(y)).

&V

(а) Равносильны ли формулы

Vx(F (x) — G(x)) и VxF (x) — VxG(x)? V3

3. Как нам известно из предыдущей главы, в логике предложений имеется простой способ, позволяющий для любых двух формул узнать, равносильны ли они: достаточно сравнить их истинностные таблицы. В логике предикатов подобного способа нет, и было бы бесполезно пытаться его найти: доказано, что не существует никакого универсального метода, который позволял бы «механически», с помощью одних и тех же четко определенных правил, для любых двух формул логики предикатов выяснять, являются ли они равносильными. Поэтому равносильность приходится в разных случаях доказывать по-разному, и это может оказаться совсем не просто. Но для некоторых важных частных случаев все-таки есть простые способы доказательства равносильности. Иногда удается, например, воспользоваться средствами логики предложений (см. выше, пример 1 предыдущего пункта и замечание к нему). В ряде других случаев можно пользоваться свойствами кванторов. Вот наиболее важные из этих свойств (их часто называют основными равно- сильностями логики предикатов). Мы разделим их на четыре группы:

Группа I: перестановка одноименных кванторов.

І1. VxVyF(x,y) = VyVxF(x,y).

І2- 3x3yF(x,y) = 3y3xF(x,y).

Для доказательства соотношения її достаточно заметить, что при

F

как левая, так и правая его части превращаются в истинные предложения тогда и только тогда, когда этот предикат тождественно истинен. В случае соотношения 12 можно рассуждать аналогично. ?

Группа II: связь между разноименными кванторами. 11ь —VxF (х) = Зх—F (х). II2. —3xF (х) = Vx—F (х).

Докажем соотношение II ь Заместим предикатный символ F произвольным одноместным предикатом F0. Если предложение —VxF0(x) истинно, то предложение VxF0(x) ложно; следовательно, предикат F0

— F0

является тождественно ложным, т.е.

2

лезно попытаться провести это доказательство самому.

Замечание. Если некоторый одноместный предикат P(х) определен на конечном множестве {а1,... an}, то VxP(х) означает то же, что P(а1) & ... & P(an), a 3xP(х) —то же, что P(a1) V ... V P(an). В общем случае кванторы общности и существования можно понимать как «бесконечную конъюнкцию» и «бесконечную дизъюнкцию». Тогда соотношения группы II оказываются обобщениями на «бесконечный случай» законов Де Моргана.

Группа III: вынесение кванторов за скобки.

Для произвольной формулы Ф. не содержащей свободных вхождений

х

ІЩ. Ф&VxF(х) = Vx( Ф&F(х)).

Ф VVxF(х) = Vx(0 V F(х)).

Ф & 3xF(х) = Зх( Ф & F(х)).

Ф V3xF(х) = Зх(Ф V F(х)).

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

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

F

F0

щие в Ф. — произвольными предикатами соответствующей вместимости;

0

если предложение Ф0 & VxF0(x) истинно, то истинны оба предложения Ф0 и VxF0(x); из истинности VxF0(x) следует, что предикат F0(x) тож-

0 & F0 ( x)

истинен, так что Vx(00 & F0(x)) —истинное предложение. С другой стороны, если Ф0 & VxF0(x) ложно, то ложно либо Ф0, ли б о VxF0(x); в пер- 0 & F0 ( x)

предикат F0(x) не тождественно истинен, и, стало быть, не тождествен-

0 & F0 (x)

Vx(00&F0(x)) ложно. ?

Группа IV: переименование связанных переменных.

IVь VxF(x) = VyF(y).

Эти соотношения следуют из того, что, как было отмечено еще в главе 5 (с. 47), предложения VxF0(x) и VyF0(y) имеют одинаковые ис-

F0

для 3xF0(x) и 3yF0(y).

xy

разумеется, брать любые другие переменные.

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

Рассмотрим несколько примеров.

Пример 1. Vx(F(x) — 3yG(x,y)) = Vx(—F(x) V3yG(x,y)) =

= Vx3y(—F(x) V G(x, y)) = Vx3y(F(x) — G(x, y)).

Здесь на первом шаге импликация выражается через дизъюнкцию и отрицание, на втором из дизъюнкции выносится за скобки квантор

существования по y (это можно сделать, поскольку формула —F(x)

y

импликация.

Пример 2. —Vx—F(x)&—VxG(x) = 3x——F(x)&3x—G(x) = = 3xF (x)&3y—G(y) = 3x(F (x)&3y—G(y)) = = 3х3у(F (x)&— G(y)).

ї

устраняется двойное отрицание и одновременно связанная переменная х в формуле 3х—G(x) переименовывавтся в у, на третьем выносится за

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

Пример 3. —3xVyF(х,у) VVxG(x) =

= Vx—VyF(х,у) VVzG(z) = Vx3y—F(х,у) VVzG(z) = = Vx3y(—F(х, у) V VzG(z)) = = Vx3yVz(—F(х, у) V G(z)).

2

связанная переменная х в формуле VxG(x) переименовывается в z, на

ї

х у z

В каждом из приведенных примеров результатом преобразования является формула, в которой все кванторы «вынесены вперед» — иначе говоря, формула, начинающаяся с «кванторной приставки» (или «префикса»), за которой следует бескванторная формула. Такие формулы называют формулами в префиксной нормальной форме (сокращенно п. н. ф.). Нетрудно понять, что к п. н. ф. можно привести любую формулу логики предикатов.

Пример 4. —Vx3yVz(L(x, z) — C(y,z)) =

= 3x—3yVz(L(x, z) — C(y,z)) = = 3xVy—Vz(L(x, z) — C(y,z)) = = 3xVy3z—(L(x, z) — C(y,z)).

ї 2 ї после чего получается формула, в которой все кванторы заменены «противоположными», а отрицание стоит справа от кванторной приставки. Таким способом можно, очевидно, образовать отрицание любой формулы в префиксной нормальной форме.

Пример 4 (продолжение). Преобразуя последнюю формулу дальше (выражая импликацию через конъюнкцию и отрицание и устраняя двойное отрицание), получаем формулу 3xVy3z(L(x, z) & —C(у, z)).

х

у

z

символы L(x,z) и C(y,z) предикатами, означающими соответственно

«z работает та преприятии x» и «Дети z'a могут посещать детский y

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

Задачи. (1) Привести к п.н. ф.:

(а) VxF(x) — 3yG(x,y)\

(б) (—VxF(x,y) — 3yG(y, z)) & —3tH(t);

(в) —3x(—Vy3zF(x, y, z) V —3xG(x, y, z)).

(2) Образовать отрицания формул, полученных в результате решения задачи 1.

5. В логике предикатов имеются также понятия, аналогичные понятиям тождественно истинной и тождественно ложной формулы логики предложений, хотя имена им здесь даются другие. Именно: формула логики предикатов называется всюду истинной, если при любом замещении входящих в нее предикатных символов конкретными предикатами она превращается в истинное предложение (если она замкнута) или в тождественно истинный предикат (если она не замкнута); формула логики предикатов называется невыполнимой, если при любом замещении входящих в нее предикатных символов конкретными предикатами она превращается в ложное предложение (если она замкнута) или в тождественно ложный предикат (если она не замкнута).

Вместо «всюду истинная» в литературе на русском языке часто используется неудачный термин «общезначимая» (возникший в результате неверного перевода немецкого allgemeingultig).

Формулу, не являющуюся невыполнимой, естественно назвать выполнимой.

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

x

Vx

3x

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

Рассмотрим теперь несколько простых примеров.

Пример 1. Формула F(х) V —F(х) всюду истинна. В самом деле, ес- F F0

х х0

закона исключенного третьего) предложение F0(x0) V—F0(x0). Таким

F

наша формула превращается в тождественно истинный предикат.

Пример 2. Формула Vx(F(х) V —F(х)) также всюду истинна (см. замечание на предыдущей странице, пункт (в)).

Пример 3. Формула VxF(х) — 3xF(х) всюду истинна, т.к. для любого предиката F0, для которого предложение VxF0(x) истинно, предложение 3xF0(x) также истинно, а потому истинна и импликация VxF0(x) — 3xF0(x), то она истинна и тогда, когда предложение VxF0(x) ложно.

Примеры 4, 5. Формула 3yVxF(х, у) — Vx3yF(х, у) всюду истинна.

F

F0

нашей импликации утверждает, что в области прибытия отношения имеется элемент, связанный этим отношением с каждым элементом области отправления, а заключение — что для каждого элемента области отправления существует — вообще говоря, свой — связанный с ним элемент области прибытия. Очевидно, из истинности посылки вытека-ет истинность заключения. В то же время при истинном заключении посылка может оказаться ложной; так будет, например, если F0(x, у) — предикат, определенный на множестве натуральных чисел и означающий х < у (см. выше, пример 6 на с. 76). Поэтому обратная импликация Vx3yF(х,у) — 3yVxF(х,у) не является всюду истинной. Однако она выполнима: она превращается в истинное предложение, например, в случае, когда F0(х, у) —предикат, определенный на множестве целых отрицательных чисел и означающий по-прежнему х < у (поскольку посылка в этом случае ложна).

Vx3yF(x, y)

истинна. Читатель легко убедится в этом, рассмотрев те же предикаты, которые были использованы в предыдущем примере.

Примеры 7, 8. Формула F(x) & —F(x) невыполнима: каким бы предикатом F0 мы ни заместили символ F, предикат F0(x)&—F0(x) будет тождественно ложен. Вместе с этой формулой невыполнима и формула 3x(F(x) & —F(x)) (ср. выше пример 2).

Остается добавить, что никакого универсального метода проверки формулы на всюду-истинность или на выполнимость не существует; положение здесь таково же, как для равносильности (см. выше).

Задачи. (1) Показать, что следующие формулы всюду истинны:

(а) VxF(x) VVxG(x) —Vx(F(x) V G(x));

(б) 3x(F(x)&G(x)) — 3xF(x) & 3xG(x));

(в) 3xG(x,x) — 3y3zG(y, z).

Показать, что импликации, обратные формулам задачи (1), выполнимы, но не являются всюду истинными.

Показать, что следующие формулы выполнимы, но не являются всюду истинными:

(а) 3xF(x,y)&3xF(y, x);

(б) VxF(x, y) V VxF(y, x).

Показать, что следующие формулы невыполнимы:

(а) 3x((F(x) — —F(x))&(—F(x) — F(x)));

(б) 3yVxF(x,y)&Vx3y—F(y, x);

(в) (G(x) — G(y))&3xG(x)&3x—G(x).