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

Подождите немного. Документ загружается.

Глава 3. Запись высказываний.

Логические формулы

Теперь мы должны строго определить выражения, с помощью которых

записываются высказывания в нашем формальном языке. Эти выраже-

ния называются логическими формулами, или просто формулами. Обыч-

ные математические формулы являются простейшим случаем логиче-

скиx (т. н. элементарные формулы).

С чисто формальной точки зрения предикаты (отношения) можно

рассматривать как функции, сопоставляющие своим аргументам истин-

ностные значения, т. е. функции, принимающие всего два значения: ис-

тина и ложь.

Функция, сопоставленная предикату

<, перера-

батывает пару чисел x, y в >, если x < y, и в ⊥,

если x > y.

(3.1)

Таким образом, приняв соглашения 1 и 2, мы должны, чтобы быть

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

Соглашение 3. Как только задана интерпретация и фикси-

рованы значения всех встречающихся в элементарной фор-

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

ние элементарной формулы.

В принципе, по соглашению 2, мы тогда можем определить истин-

ностные значения и всех более сложных формул, так как значения иx

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

способами более сложные формулы строятся из более простых.

Для образования новых формул из имеющихся используются логи-

ческие связки. Логические связки применяются к высказываниям и в

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

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

связки.

— высказывания, записанные на человеческом языке, A,

B — иx переводы на формальный язык.

§ 3.1. СВЯЗКА ‘И’

Союзу ‘и’ сопоставляется логическая связка &. Символ & называет-

ся конъюнкцией. Эта связка применяется при переводе на формальный

язык утверждений вида «

», «

, но и

также», «

вместе с

»,

, несмотря на

», «не только

, но и

», «как

, так и

», «

, хотя и

» и т. п. Все они переводятся одинаково: A & B. Разные слова здесь

выражают разное отношение к факту, но не меняют самого факта. Со-

ответственно, переводя A & B на естественный язык, нужно выбирать

подходящий, наиболее выразительный вариант.

Если

(x) означает ‘x — разбойник‘,

(x) — ‘x —

добрый’,

РГ

—константа для объекта ‘Робин Гуд’,

то

(

РГ

) &

(

РГ

) естественно перевести, напри-

мер, так: «Робин Гуд был добрым, хотя и разбой-

ником», или «Робин Гуд был разбойником, несмо-

тря на то, что был добрым».

(3.2)

Утверждение A & B истинно в том и только том случае, когда истинны

как A, так и B, и ложно во всех остальных случаях.

Заметим, что уже для этой простейшей связки ее математический

смысл не всегда совпадает с содержательным. В самом деле, математи-

чески

A & B и B & A означают одно и то же, а содержательно, скажем,

высказывания

Маша вышла замуж, и у нее родился ребенок;

(3.3)

У Маши родился ребенок, и она вышла замуж

(3.4)

понимаются несколько по-разному (пример Клини)

В примере Клини четко выявляется разница между описаниями состояний и дей-

ствий.

3.2. СВЯЗКА ‘ИЛИ’

§ 3.2. СВЯЗКА ‘ИЛИ’

‘

или

’ символически записывается A ∨ B. Знак ∨ называется дизъ-

юнкцией. Эта же связка применяется при переводе утверждений «

или

или оба вместе», «либо

, либо

», «

и/или

» и т. п. A ∨ B счи-

тается истинным, если хотя бы одно из двух составляющих утвержде-

ний истинно, и ложным лишь тогда, когда они оба ложны. В естествен-

ном языке ‘или’ порою используется как разделительная связка: ‘то или

другое, но не оба вместе’. Поэтому для хозяев был неожиданным ответ

Ходжи Насреддина на вопрос: «Что желаете поесть: плова или бешбар-

мака?» — «А разве у вас всего один котел?» Но чаще две возможности

просто несовместимы, и оба смысла совпадают. Если в A ∨ B

утверждения

несовместимы, то иx называют альтернативами.

Пример 3.2.1.

Для двух неравных чисел

есть две альтернативы:

или

a < b

, или

a > b

Если же в математике приходится иногда явно пользоваться “разде-

лительным или”, оно обозначается ⊕ (этой операции обычно избегают

из-за неудобства некоторых преобразований с ⊕; в частности, истин-

ность A ⊕ B ⊕ C означает вовсе не истинность одного и только одного

из высказываний

§ 3.3. СВЯЗКА ‘СЛЕДУЕТ’

«Из

следует

» символически записывается: A ⇒ B. Знак ⇒ называ-

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

точно так же переводящихся,служат: «

достаточное условие для

»,«

необходимое условие для

», «

, только если

», «

, если

», «в случае

выполнено и

», «

есть

».

Правила вычисления истинностного значения A ⇒ B нуждаются в

комментариях. Они опираются на содержательный смысл связки ⇒: из

можно сделать вывод (вывести следствие)

, и на наши гипотезы.

Рассмотрим верное утверждение: «Если n делится на 6, то n делится

и на 3». Будем теперь подставлять вместо n конкретные значения. По-

лучим, в частности, следующие три утверждения:

Если 6 делится на 6, то 6 делится на 3

(3.5)

Если 5 делится на 6, то 5 делится на 3

(3.6)

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

Если 3 делится на 6, то 3 делится на 3

(3.7)

Все эти утверждения также обязаны быть истинны. Но, пользуясь со-

глашением 2 и заменяя утверждения о делимости на 6 на иx конкретные

логические значения, получаем, что тогда должно быть

(1 ⇒ 1) = 1 (3.8)

(0 ⇒ 0) = 1 (3.9)

(0 ⇒ 1) = 1 (3.10)

Другими словами, должны быть истинны утверждения

Из истины следует истина

(3.11)

Из лжи следует ложь

(3.12)

Из лжи следует истина

(3.13)

Истинность (3.5), (3.6), (3.7) мы должны принять, если мы желаем

обеспечить возможность подстановки в доказанные теоремы конкрет-

ных значений переменных. А по соглашению 2 нам приходится принять

и (3.11), (3.12), (3.13).

Утверждение (3.7) и соответствующее ему (3.13) кажутся несколько

парадоксальными. Но мы знаем, что из ложных предположений можно

иногда содержательным рассуждением получить истинные следствия.

Например, из ложного предположения “существуют русалки” следует

истинное “купаться ночью в одиночку в незнакомом месте опас-

но”. Принципиально неправильная система мира Птолемея, в которой

центром Вселенной служит Земля, очень точно описывает видимые дви-

жения планет. Соглашение 2 опять-таки заставляет нас распространить

эту истинность на все мыслимые в математике случаи.

Правда,при этом приходится признать формально истинными и пред-

ложения типа

Если Волга впадает в Балтийское море, то Ижевск на-

ходится в тропиках.

(3.14)

Но при любой математической формализации происходит абстрагиро-

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

дят в разряд формально истинных либо формально ложных

Не бойтесь, гораздо больше содержательно осмысленных предложений переходит

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

3.4. СВЯЗКА ‘ТОГДА И ТОЛЬКО ТОГДА’

§ 3.4. СВЯЗКА ‘ТОГДА И ТОЛЬКО ТОГДА’

тогда и только тогда, когда

» символически записывается A ⇔ B.

Знак ⇔называется эквивалентностью.Той же связкой переводятся пред-

ложения «

эквивалентно

», «

необходимое и достаточное условие

для

», «если

, то и

, и наоборот» и т. п. Ритуальное выражение «тогда

и только тогда, когда» мы в дальнейшем будем сокращать ттт. A ⇔ B

истинно ттт истинностные значения

совпадают, и ложно ттт иx

истинностные значения различны. A ⇔ B выражается через ⇒ и &:

(A ⇒ B) & (B ⇒ A). (3.15)

Если знаком

= обозначено ‘есть по определению’, то можно запи-

сать

(A ⇔ B)

= (A ⇒ B) & (B ⇒ A). (3.16)

§ 3.5. СВЯЗКА ‘НЕ’

Утверждение «не

» символически записывается

. Знак

называ-

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

неверно», «

ложно», «

не может быть» и т. п.

истинно, когда

ложно

, и ложно, когда истинно

Связки

&, ∨, ⇒, ⇔,

называются связками исчисления высказыва-

ний или пропозициональными связками.

§ 3.6. ТАБЛИЦЫ ИСТИННОСТИ

Способы вычисления истинностных значений высказываний (A & B),

(A ∨ B), (A ⇒ B), (A ⇔ B),

можно резюмировать следующими

таблицами:

A B A & B A ∨ B A ⇒ B A ⇔ B

> > > > > >

> ⊥ ⊥ > ⊥ ⊥

⊥ > ⊥ > > ⊥

⊥ ⊥ ⊥ ⊥ > >

> ⊥

⊥ >

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

§ 3.7. ‘ДЛЯ ВСЕХ’

Утверждение «для всех x верно A(x)» символически записывается

∀x A(x). Символ ∀ называется квантором всеобщности. Эта же связка

используется при переводе утверждений «

верно при любом значении

x», «для произвольного x имеет место A(x)», «каково бы ни было x,

A(x)» и т. п.

Утверждение ∀x A(x) истинно ттт A(c) истинно, какой бы конкрет-

ный предмет c из универса нашей теории мы ни подставляли вместо x.

Другими словами, ∀x A(x) истинно ттт A(x) истинно при любом фик-

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

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

кретное значение x), такой, что A(c) ложно.

Заметим, что таблицы истинности для связок исчисления высказы-

ваний можно применять чисто механически и, в частности, вычислять

логические значения формул на машине, а определение истинностного

значения формулы ∀x A(x) не всегда сводится к простому вычислению.

Например, при данных конкретных натуральных x, y, z, n утверждение

(x + 1)

n+3

+ (y + 1)

n+3

6= (z + 1)

n+3

(3.17)

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

но на множестве

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

∀x ∀y ∀z ∀n((x + 1)

n+3

+ (y + 1)

n+3

6= (z + 1)

n+3

), (3.18)

стоит уже более 300 лет, и не видно способа ее решить окончатель-

но

. Эта проблема известна под названием великой теоремы Ферма. На

обычном математическом языке она формулируется следующим обра-

зом.

Доказать, что уравнение

+ y

= z

при n > 2 не имеет решений в положительных

целых числах.

(3.19)

Недавно появилось доказательство этой теоремы,но оно настолько сложно,что окон-

чательного признания еще не получило. А найти ошибку в сложном и длинном рассу-

ждении во много раз труднее, чем написать его.

3.8. ‘СУЩЕСТВУЕТ’

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

гих математическиx проблемах та, что рассматриваемое множество объ-

ектов (здесь натуральные числа) бесконечно, и проверить его все нет

даже принципиальной возможности. А математическое доказательство

позволяет нам единым образом обозреть все это бесконечное множество

и получить точный ответ.

§ 3.8. ‘СУЩЕСТВУЕТ’

Утверждение «существует такое

, что

A(x)

» записывается на языке ма-

тематики как ∃x A(x). Знак ∃ называется квантором существования.

Эта же связка применяется при переводе утверждений «A(x) верно при

некоторых

», «

A(x)

иногда верно», «есть такое

, при котором

A(x)

»,

«можно найти такое

, при котором

A(x)

» и т. п.

Высказывание

∃x A(x) истинно, если в нашем универсе найдется

хотя бы одно значение c, при котором A(c) истинно.∃x A(x) ложно,если

при любом значении c ложно A(c).

Нахождение истинностного значения

∃x A(x) также может соста-

влять проблему. Например, натуральное число n называется совершен-

ным, если сумма его делителей (исключая само n) равна n. 6 — совер-

шенное число, т. к. 6 = 1 + 2 + 3, 28 — также совершенное число, т. к.

28 = 1 + 2 + 4 + 7 + 14. Ясно, что при данном n проверка условия ‘n —

совершенное число’ чисто механический процесс, ее можно поручить

машине. Но проблема «существует ли нечетное совершенное число?»

стоит уже более 2000 лет, и не видно способа ее решить.

Заметим, что утверждение

∃x A(x) не отрицает того, что ∀x A(x).

В жизни же порою словом “некоторые” подчеркивают смысл “не все”.

Пример 3.8.1.

(Пример Клини) Политик, произнося «Некоторые поли-

тики — мошенники», имеет в виду «Неверно, будто все политики —

мошенники, но некоторые — мошенники», и делает упор на первой ча-

сти этого высказывания.

Итак, кванторы ∀ и ∃ всегда употребляются вместе с переменной и

заставляют ее пробегать весь универс.

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

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

В математике и в жизни сплошь и рядом мы заинтересованы в том, что-

бы заставить переменную пробегать не весь универс, а лишь некоторую

его часть. Мы говорим: «Все четные числа — составные», «Некоторые

молодые люди — студенты» и т. п. Наш символизм не мог бы быть хоть

сколько-нибудь практичен, если бы он не включал удобных способов

записи такиx суждений.

Первый приходящий в голову способ — писать выражения типа

∀r C(r), где r означает переменную для четных чисел, или же

∀r ∈

C(r). Введение т. н. “подчиненных” переменных (пробегающих

части универса) или т. н. “ограниченных” кванторов (вида ∀x ∈ X) воз-

можно, но при формализации всегда нужно следовать принципу “брит-

вы Оккама”: «Не умножайте сущностей без необходимости». Поэтому

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

попытаться сконструировать из старых.

Такое “конструктивное” определение новых понятий имеет еще од-

но преимущество: в “граничных” случаяx, противоречащих интуиции

и здравому смыслу, иx формальный смысл будет точно определен, и

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

не впасть в ненужные трудности либо даже в прямые противоречия.

Рассмотрим внимательнее утверждение «Все коровы любят сено».

Если универс нашей теории — множество всех живых существ, то на-

прашиваются два варианта перевода этого утверждения:

∀x(

(x) &

ЛС

(x)); (3.20)

∀x(

(x) ⇒

ЛС

(x)). (3.21)

Здесь

означает “ корова”, а

ЛС

— “ любит сено”.

Из варианта (3.20) следует, что всякое живое существо, в том числе

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

что, мягко говоря, несколько преувеличено. Вариант же (3.21) кажется

более многообещающим: коль скоро нам дана корова, она любит сено.

Проверим (3.21) тщательнее. Случай, соответствующий “здравому

смыслу”, — подстановка вместо x коровы Машки — ничего не дает.

Если

— эта корова, то

К(М)

истинно,

ЛС(М)

тоже истинно, и

(

) ⇒

ЛС

(

) &

ЛС

(

) истинны. Итак, “разумный” случай не дает нам

возможности отличить правильный вариант перевода на формальный

язык от неправильного.Рассмотрим теперь случаи безумные. Пусть

—

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

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

не любит. Значит,

(

) и

ЛС

(

) ложны, и значение

(

) ⇒

ЛС

(

) есть

⊥ ⇒ ⊥, т. е. истина. Теперь вместо коровы возьмем коня. Он сено лю-

бит, но коровой не является, и, подставляя соответствующие логические

значения, получаем ⊥ ⇒ >, т. е. опять-таки истину. Похоже на то, что

если все коровы любят сено, то (3.21) истинно.

В самом деле, единственный способ опровергнуть (3.21) — задать

такое

c, при котором

ЛС

тинно, а

ЛС

необходимо указать корову, которая сено не любит.

Аналогично, для утверждения «некоторые молодые люди — студен-

ты» есть две бросающиеся в глаза возможности перевода (

означает

“ молодой человек”,

— “ студент”):

∃x(

(x) &

(x)); (3.22)

∃x(

(x) ⇒

(x)). (3.23)

Рассуждениями, подобными тем,которые приводились для

∀,можно

установить, что (3.23) неправильно.

Итак,

“Все

есть

” переводится ∀x(A(x) ⇒ B(x)). (3.24)

“Некоторые

есть

” переводится ∃x(A(x) & B(x)). (3.25)

Подытожим

Формулы — выражения, обозначающие высказывания.

Сложные формулы строятся из более простых при помощи

логическиx связок и кванторов.

Логические связки применяются к высказыванию и в резуль-

тате дают высказывание.

Логические связки задаются таблицами истинности.

Кванторы заставляют переменную пробежать весь универс.

Они применяются к формуле с переменной и в результате

дают высказывание, не зависящее от данной переменной.

Квантор

∀ сочетается со связкой ⇒, а квантор ∃ — со связ-

кой &.

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

(A & B) (A ∧ B) A ∙ B A and B

(A ∨ B) A + B AB A or B

(A ⇒ B) (A ⊃ B) A ⇒ B A impl B

(A ⇔ B) A ≡ B (A ↔ B) A = B A ∼ B A eq B

A −

A A ∼ A notA

∀x A(x) (x)A Π

A (Ax)A

∃x A(x) (Ex)A Σ

A (Ex)A

Таблица 3.1: Различные обозначения логическиx связок

Для логических связок, к несчастью, еще не выработаны общепри-

нятые обозначения. Мы постарались выбрать наиболее выразительные

и распространенные. Другие системы обозначений можно резюмиро-

вать таблицей (3.1).

Упражнения к § 3.9

Упражнения, позаимствованные у Л. Кэрролла [21], помечены

[К]

Перевести на формальный язык.

3.9.1.

[K]

Ни одному лысому не нужна расческа.

3.9.2.

[K]

Все мои тетки не справедливы.

3.9.3.

[K]

Ни один кошмарный сон не приятен.

3.9.4.

[K]

Все битвы сопровождаются страшным шумом.

3.9.5. Не все двоечники ленивы.

3.9.6.

[K]

Каждый, кто упорно работает, добивается успеха.

3.9.7.

[K]

Ни один бездельник не станет знаменитостью.

3.9.8.

[K]

Некоторые художники не бездельники.

3.9.9.

[K]

Некоторые бездельники не художники.

3.9.10.

[K]

Некоторые подушки мягкие.

3.9.11.

[K]

Тот, кто может укрощать крокодилов, заслуживает уважения.

3.9.12.

[K]

Ни одна лягушка не имеет поэтической внешности.