Непейвода. Прикладная логика

3.9. ОГРАНИЧЕННЫЕ КВАНТОРЫ

41

3.9.31.

Точки A, B, C являются вершинами равнобедренного треуголь-

ника.

3.9.32.

Иванов, Петров, Васильев и Сидоров могут вытащить эту маши-

ну из ямы, если они трезвы и видят бутылку.

3.9.33. Иванов, Петров, Васильев и Сидоров не могут решать квадрат-

3.9.35. Квадратные корни из некоторых рациональных чисел иррацио-

нальны.

3.9.36.

Синус и косинус равны друг другу тогда и только тогда, когда

равны тангенс и котангенс.

3.9.37. [K] Когда кто-то поет больше часа, он надоедает.

3.9.38.

Все девочки боятся лягушек и мышей.

3.9.39.

Кошки бывают только белые и серые.

3.9.40.

[K] Все ораторы либо честолюбивы, либо скучны.

3.9.41.

Нет действительных чисел, больших 101010 .

3.9.42.

Число делится на 25 в том и только том случае, когда оно делится

на 50 либо дает при делении на 50 остаток 25.

3.9.43.

Все комплексные числа действительны или становятся действи-

тельными после умножения на i.

3.9.44.

Не все студенты отличники или спортсмены.

3.9.45.

Для того чтобы выполнялось равенство x = √

, необходимо

x2

и достаточно, чтобы x было положительным действительным чи-

слом.

3.9.46.

Не все, что рассказывал барон К. Ф. И. фон Мюнхгаузен, ложь.

3.9.47.

Некоторые людоеды —

плохие люди.

3.9.48.

Некоторые финансисты —

мошенники, но не все.

3.9.49.

Прапорщики любят порядок, и не только они.

3.9.50.

Милиционеры замешаны в преступлениях, но не все.

3.9.51.

Некоторые замки не отпираются, но запираются.

3.9.52.

Если будешь хорошо учиться, поступишь в вуз, а иначе прова-

лишься.

3.9.53.

Ничего не вижу, ничего не слышу, ничего не знаю.

3.9.54.

Молодо —

зелено.

3.9. ОГРАНИЧЕННЫЕ КВАНТОРЫ

43

44

ГЛАВА 3. ЗАПИСЬ ВЫСКАЗЫВАНИЙ

3.9.77. (Задача семиклассников)4 Ученик написал утверждение

x(От(x) Дв(x)),

где универсом является множество учеников класса, От(x) озна-

чает “ x —

отличник”,

Дв(x) — “ x —

двоечник”. Может ли оно

быть истинно?

Помимо , , операций суммы и произведения, стоит упомянуть сле-

дующие часто встречающиеся в языке математики кванторы:

1.

квантор образования множества (A(x) —

логическая формула):

{x | A(x)} .

Он строит по A(x) множество всех x, обладающих данным свой-

ством;

2.

квантор функциональности (t(x) — терм):

λx t(x) либо x 7→t(x).

Строит по выражению функцию, вычисляющую значения этого

выражения. Этот квантор особенно часто встречается в информа-

тике; в программировании ему соответствует описание процеду-

ры (t —

тело процедуры, x —

ее параметр);

3.

квантор “ тот самый” ( A(x) —

логическая формула):

ιx A(x).

A(x) должна принимать значение истина для единственного x.

Именно это x является значением выражения ιx A(x).

§ 4.2. “ МНОГОЭТАЖНЫЕ” КВАНТОРЫ.

ДОПОЛНИТЕЛЬНЫЕ ОГРАНИЧЕНИЯ.

Рассмотрим утверждение: “ Все здоровые осы злы”.

Здесь говорится, что

если данный нам объект x оса и притом здоровая, то x зол. Следователь-

но, формальная запись этого утверждения имеет вид

x((О(x) & Зд(x)) Зол(x)).

(4.1)

Для удобства записи и чтения формальных выражений принято счи-

тать, что связки и связывают слабее, чем &

и , и утверждение

(4.1) можно переписать в форме

x(О(x) & Зд(x) Зол(x)).

(4.2)

4.2. МНОГОЭТАЖНЫЕ. . .

47

Аналогично утверждение “ Некоторые старательные ученики —

от-

личники” можно записать в виде

x(С(x) & У(x) & О(x)).

(4.3)

Итак, если на значения переменной накладываются сразу несколько

ограничений, то все они перечисляются через &, а затем надстраивается

ограниченный квантор по обычным правилам.

По этой методике утверждение (4.1) нужно записывать в следующем

порядке:

(4.4)

О(x) & Зд(x) ;

О(x) & Зд(x) Зол(x);

x (О(x) & Зд(x) Зол(x)) .

Итак, логическую формулу, являющуюся переводом предложения

естественного языка, чаще всего естественно писать изнутри, начиная с

середины, а не спереди, как мы пишем обычные предложения. Впрочем,

если вы уже видите перед мысленным взором всю формулу целиком, за-

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

чинать с начала —

пожалуй, худший из возможных способов действий

(с конца и то лучше).

Теперь рассмотрим утверждение: “ Некоторые парни и девушки дру-

жат друг с другом”. Оно имеет две эквивалентные формы, обе они до-

пустимы:

x(П(x) & y(Д(y) & Др(x, y) & Др(y, x)));

(4.5)

x y(П(x) & Д(y) & Др(x, y) & Др(y, x)).

(4.6)

Хоть эти две формы и эквивалентны, но (4.6), пожалуй, несколько

выразительнее и яснее подчеркивает равноправие парней и девушек в

данном высказывании.

Сокращение для утверждений типа (4.6):

x, y (П(x) & Д(y) & Др(x, y) & Др(y, x)) ,

(4.7)

т. е. несколько однородных кванторов соединяются в один.

Аналогично утверждение “ произведение двух отрицательных чисел

положительно” может быть записано в виде

x, y(x < 0 & y < 0 x · y > 0).

(4.8)

очевидно, гораздо более искусственна.

Перевод утверждения «для всякого натурального числа есть боль-

шее» можно записать следующим образом:

x (x N y (y N & y > x)) .

(4.9)

Заметим, что это утверждение удобнее писать, начиная с внутренне-

го квантора, т. е. сначала перевести, что означает «Для x есть большее

его натуральное число», а затем уже расшифровать начало предложе-

ния: «для всякого x».

В (4.9) квантор был явно назван и в человеческой формулировке,

а в (4.8)

нам пришлось его восстанавливать, исходя из смысла утвер-

ждения.

В общем случае при переводе содержательного утверждения

на формальный язык ни одна переменная, которая не была названа явно

в исходной формулировке, не должна оставаться не связанной кванто-

ром. Иначе неизбежны грубые ошибки.

При переводе утверждений с вложенными кванторами необходимо

тщательнейшим образом следить за порядком кванторов и иx областью

действия. Например, если утверждение (4.9), конечно же, истинно, то

утверждение

y (y N & x(x N y > x))

(4.10)

ложно. В самом деле, прочтем его. Читать также начинают изнутри.

Внутри у нас говорится, что всякое натуральное число x меньше y. Ну,

а как же само y? Оно же не может быть меньше самого себя! Значит,

внутреннее утверждение ложно. А снаружи стоит квантор, говорящий,

что существует такое натуральное число. . . Этого быть не может.

Итак, все утверждение (4.10) в целом выражает утверждение есте-

ственного языка “ Существует наибольшее натуральное число”, которое

ложно.

этого примера виден и способ чтения формальных выражений.

Из

Мы начинаем с внутренниx кванторов, и, прочитав утверждение “ на-

черно”,

в уродливых для естественного языка формах типа “ для всех

4.2. МНОГОЭТАЖНЫЕ. . .

49

переменных, которые в формальном выражении были связаны. Упоми-

нание же о тех переменных, которые были свободны, по которым кван-

торов навешено не было, обязательно остается.

Например, выражение

z (z R & x < z & z < y)

(4.11)

можно прочитать как “ Существует действительное число z, такое, что

x меньше z, а z меньше y”, и переформулировать начисто: “ Между x и

y есть действительное число”.

Теперь об области действия кванторов. В традиционной математи-

ческой логике, т. н. классической, допустимо эквивалентное преобразо-

вание (4.9) в

x y (x N y N & y > x) ,

(4.12)

но такую переформулировку мы решительно не рекомендуем. Во-

первых, она, несомненно, менее выразительна и в более сложных слу-

чаяx даже прямо провоцирует на ошибки; во-вторых, она уже не имеет

места при переходе ко многим неклассическим логикам, которые сейчас

приобретают все большее и большее значение.

И, наконец, рассмотрим утверждение: “ Все волки и зайцы серы”.

Для него прямо ошибочен перевод

x (В(x) & З(x) С(x)) ,

(4.13)

x, y(В(x) & З(y) С(x) & C(y))

(4.14)

и лучше всего перевод

x (В(x) С(x)) & x (З(x) C(x)) ,

(4.15)

где каждый квантор относится лишь к тем утверждениям, которые он

связывает.

Подытожим: