Непейвода Н.Н. Прикладная логика
Подождите немного. Документ загружается.
3.9. ОГРАНИЧЕННЫЕ КВАНТОРЫ
41
3.9.13.
[K]
Ни одна тачка не комфортабельна.
3.9.14.
[K]
Всякий орел умеет летать.
3.9.15.
[K]
Некоторые свиньи не умеют летать.
3.9.16.
[K]
Некоторые свиньи — не орлы.
3.9.17.
[K]
Ни один судья не справедлив.
3.9.18.
[K]
Ни один ребенок не любит прилежно заниматься.
3.9.19.
[K]
Все шутки для того и предназначены, чтобы смешить людей.
3.9.20.
[K]
Ни один парламентский акт не шутка.
3.9.21.
[K]
Пауки ткут паутину.
3.9.22.
[K]
Все лекарства имеют отвратительный вкус.
3.9.23.
[K]
Ни у одной ящерицы нет волос.
3.9.24.
[K]
Все свиньи прожорливы.
3.9.25.
[K]
Все, что сделано из золота, драгоценно.
3.9.26.
[K]
Некоторые секретари — птицы.
3.9.27.
[K]
Все секретари заняты полезным делом.
3.9.28.
[K]
Ничто разумное не ставит меня в тупик.
3.9.29.
[K]
Логика часто ставит меня в тупик.
3.9.30.
[K]
Некоторые цыплята — не кошки.
3.9.31. Точки
A, B, C являются вершинами равнобедренного треуголь-
ника.
3.9.32. Иванов,Петров, Васильев и Сидоров могут вытащить эту маши-
ну из ямы, если они трезвы и видят бутылку.
3.9.33. Иванов, Петров, Васильев и Сидоров не могут решать квадрат-
ные уравнения, даже если они трезвы, но видят бутылку.
3.9.34. Не все углы, синус которых больше
1/2, больше π/6.
42
ГЛАВА 3. ЗАПИСЬ ВЫСКАЗЫВАНИЙ
3.9.35. Квадратные корни из некоторых рациональных чисел иррацио-
нальны.
3.9.36. Синус и косинус равны друг другу тогда и только тогда, когда
равны тангенс и котангенс.
3.9.37.
[K]
Когда кто-то поет больше часа, он надоедает.
3.9.38. Все девочки боятся лягушек и мышей.
3.9.39. Кошки бывают только белые и серые.
3.9.40.
[K]
Все ораторы либо честолюбивы, либо скучны.
3.9.41. Нет действительных чисел, больших
10
10
10
.
3.9.42. Число делится на 25 в том и только том случае, когда оно делится
на 50 либо дает при делении на 50 остаток 25.
3.9.43. Все комплексные числа действительны или становятся действи-
тельными после умножения на
i.
3.9.44. Не все студенты отличники или спортсмены.
3.9.45. Для того чтобы выполнялось равенство
x =
√
x
2
, необходимо
и достаточно, чтобы 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
3.9.55. Взялся за гуж — не говори, что не дюж.
3.9.56. Чтобы не быть собакой, достаточно быть кошкой.
3.9.57. Чтобы не быть человеком, необходимо быть свиньей.
3.9.58. Некоторые кошки поют по ночам.
3.9.59. Все компакты совершенно нормальны.
3.9.60. Некоторые мюмзики не куздры.
3.9.61. Три точки
A, B, C лежат на одной окружности.
3.9.62. Три точки
A, B, C не лежат на одной прямой.
3.9.63. Числа
a и b имеют одинаковый знак.
3.9.64. Одно из чисел
a, b равно 0.
3.9.65. Числа
a и b имеют разные знаки.
3.9.66. Ромео и Джульетта любят друг друга.
3.9.67. Гамлет и Клавдий ненавидят друг друга.
3.9.68. Мери любила Печорина, но не взаимно.
3.9.69. Чтобы прийти на свадьбу, необходимо приглашение жениха или
невесты.
3.9.70. Некоторые лентяи не оптимисты, но жизнелюбы.
3.9.71. Все замки отпираются и запираются.
3.9.72. Никто из нашего класса не поехал в Москву и Париж.
3.9.73. Все мои одноклассники поехали в Москву и Париж.
3.9.74. Некоторые числа четные.
3.9.75. Некоторые лекции невозможно понять.
3.9.76. Всякому в Москве не перекланяешься.
44
ГЛАВА 3. ЗАПИСЬ ВЫСКАЗЫВАНИЙ
3.9.77. (Задача семиклассников)
4
Ученик написал утверждение
∀x(
От
(x) ⇔
Дв
(x)),
где универсом является множество учеников класса,
От
(x) озна-
чает “x — отличник”,
Дв
(x) — “x — двоечник”. Может ли оно
быть истинно?
4
Формулировка данной задачи принадлежит ученикам 7-го класса ижевской школы
№ 29.
Глава 4. Методы перевода
с естественного языка
на математический
и обратно
В принципе все это пособие посвящено соотношениям между матема-
тическим и “человеческим” языком, но в данном параграфе мы специ-
ально останавливаемся на элементарных методах перевода более слож-
ных, чем в предыдущих параграфах, утверждений. Начнем с раздела, в
котором более подробно рассмотрена внутренняя структура формул.
§ 4.1. КВАНТОРЫ. ОБЛАСТИ ДЕЙСТВИЯ.
СВОБОДНЫЕ И СВЯЗАННЫЕ ПЕРЕМЕННЫЕ
Мы познакомились с двумя кванторами — ∀ и ∃. В математике кван-
торные операции над выражениями, содержащими переменные, встре-
чаются сплошь и рядом. Например, известная операция суммы
n
X
i=1
a
i
связывает переменную i, заставляя ее пробежать все натуральные числа
от 1 до n, и также может считаться квантором. Вообще, в математиче-
ской формализации квантор — это операция, применяющаяся к выра-
жению (называемому подкванторным), содержащему переменные (на-
зываемые переменными данного квантора), и дающая в результате вы-
ражение, от этиx переменных не зависящее, смысл которого описывает-
ся через совокупность значений подкванторного выражения на области
изменения переменных квантора.
46
ГЛАВА 4. МЕТОДЫ ПЕРЕВОДА
Помимо ∀,∃, операций суммы и произведения, стоит упомянуть сле-
дующие часто встречающиеся в языке математики кванторы:
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) нужно записывать в следующем
порядке:
⇒
О
(x) &
Зд
(x) ⇒;
О
(x) &
Зд
(x) ⇒
Зол
(x);
∀x (
О
(x) &
Зд
(x) ⇒
Зол
(x)) .
(4.4)
Итак, логическую формулу, являющуюся переводом предложения
естественного языка, чаще всего естественно писать изнутри, начиная с
середины, а не спереди, как мы пишем обычные предложения.Впрочем,
если вы уже видите перед мысленным взором всю формулу целиком, за-
писать ее на бумаге можно в любом порядке. Но если это не так, то на-
чинать с начала — пожалуй, худший из возможных способов действий
(с конца и то лучше).
Теперь рассмотрим утверждение: “Некоторые парни и девушки дру-
жат друг с другом”. Оно имеет две эквивалентные формы, обе они до-
пустимы:
∃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)
48
ГЛАВА 4. МЕТОДЫ ПЕРЕВОДА
Форма
∀x (x < 0 ⇒ ∀y (y < 0 ⇒ x ∙ y > 0)) ,
очевидно, гораздо более искусственна.
Перевод утверждения «для всякого натурального числа есть боль-
шее» можно записать следующим образом:
∀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 кванторов, и, прочитав утверждение “на-
черно”, в уродливых для естественного языка формах типа “для всех
x, такиx, что... , существует y, такое, что...”, стремимся переформу-
лировать полученное предложение более кратко и более красиво, более
выразительно. При этом по возможности изгоняется упоминание о тех
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)
где каждый квантор относится лишь к тем утверждениям, которые он
связывает.
Подытожим
:
Если предложение достаточно сложное, его перевод на фор-
мальный язык лучше всего писать изнутри, начиная с самой
главной части данного предложения.
50
ГЛАВА 4. МЕТОДЫ ПЕРЕВОДА
Порядок кванторов часто имеет решающее значение.
Не стесняйтесь гнаться за выразительностью: это окупается.
При переводе на формальный язык нужно по мере возмож-
ности уменьшать области действия кванторов,чтобы каждый
из них (в идеале) включал в свою область лишь утвержде-
ния, говорящие о связываемой им переменной.
При чтении сложной формулы начинайте изнутри. Если за-
труднительно сразу понять ее смысл, сначала прочитайте ее
начерно, а затем начисто, изгоняя явное упоминание кван-
торов и связанных переменных.
Свободные переменные должны входить в окончательную
словесную формулировку утверждения.
Упражнения к § 4.2
Записать на формальном языке.
4.2.1. Все моряки боятся пиратов.
4.2.2. Все жулики боятся милиционеров.
4.2.3. Маленькие девочки боятся зубных врачей.
4.2.4. Некоторые зубные врачи боятся маленьких девочек.
4.2.5. Зайцы не всегда глупее лис.
4.2.6. Некоторые индейцы были храбрее белых.
4.2.7. Некоторые школьники — отличники или спортсмены.
4.2.8. Все первокурсники и второкурсники пришли на лекцию.
4.2.9. Некоторые комплексные числа, отличные от 0 и являющиеся зна-
чениями функции
f, не положительны и не отрицательны.
4.2.10. Логарифмы всех положительных рациональных чисел иррацио-
нальны.
4.2.11. Квадратные корни из некоторых рациональных положительных
чисел иррациональны.