книги / Математическая логика и теория алгоритмов. Логика предикатов

2.1. Логика высказываний

Высказыванием будем называть любое утверждение, о котором из­ вестно, что оно либо истинно, либо ложно. Например, утверждения «2 х 2 = 4» и «Москва — столица России» являются истинными вы­ сказываниями, «2 х 2 = 5» и «В Арктике живут пингвины» — ложны­ ми высказываниями, предложение «Число букв „а“ в романе „Война и мир“ делится на 10» тоже является высказыванием (поскольку несомнен­ но, что это утверждение либо истинно, либо ложно). Высказываниями не являются предложения, не являющиеся повествовательными (напри­ мер, «Сколько будет дважды два?» и «Учите математику!»), утвержде­ ния, содержащие недостаточно ясно определённые понятия (например, «Сегодня хорошая погода»), и внутренне противоречивые утверждения (например, «Данное предложение ложно»).

Логико-математические формальные языки созданы для изучения не содержания высказываний, а их логической связи друг с другом. Что­ бы такое изучение стало возможным, необходимо отвлечься от содержа­ щейся в высказываниях «лишней информации». Значит, высказывания следует как-нибудь обозначать — и желательно покороче. Для этого бу­ дем использовать строчные латинские буквы. Высказывания, обознача­ емые одной буквой, будем называть простыми. Остальные высказыва­ ния будем называть сложными, они составляются из простых с помощью специальных символов, которые называются логическими связками. Эти символы можно рассматривать как аналоги выражений естественного языка, которые мы употребляем в логических рассуждениях. С выска­ зываниями используются следующие логические связки13:

А {конъюнкция) — аналог союза «и»; V {дизъюнкция) — аналог союза «или»;

-» {импликация) —аналог словесной конструкции «если..., то... »; -1 {отрицание) —аналог выражения «неверно, что... ».

Сложные высказывания в формальных языках строятся из простых, подобно тому как строятся буквенные выражения классической алгебры. При этом конъюнкция, дизъюнкция и импликация ставятся между дву­ мя высказываниями — подобно знакам операций сложения и умножения,

13В отличие от кванторов, речь о которых пойдёт ниже, они называются пропози­ циональными связками, от лат. propositio — высказывание. Их названия происходят от слов conjunctio — соединение, disjunctio — разделение, implicatio — переплетение.

а отрицание — перед высказыванием — подобно минусу, обозначающе­ му смену знака. Таким образом, сложные высказывания переводятся на русский язык в соответствии с правилами:

а Л 6	а и Ь;
а V b ^	а или 6;

а-+Ъ т=± если а, то 6;

-1й г=* неверно, что а.

Пример 2 .1 . Пусть введены следующие обозначения:

а?=* Алсу не вернулась к своему возлюбленному; b ^ наступила зима.

Тогда можно сделать следующие вольные переводы с формального язы­ ка на русский:

-»а ^ Алсу вернулась;

^зима не наступила;

аЛ Ь ^ и Алсу не вернулась, и зима наступила;

аУ	то ли Алсу не вернулась,
	то ли зима наступила;
а - * Ь ^	если Алсу не вернулась,
	значит, наступила зима.

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

Прим ер 2 .2 . Введем следующие обозначения:

ач=± число х делится на 2\ Ь^ число х делится на 5; с ^ число х делится на 6.

Теперь высказывание «Если число х делится на 2, но не делится на 3, то

оно не делится на 6» можно записать в виде (а Л -»Ь)		-ic.
Скобки в полученном выражении необходимы, поскольку выраже­
ние а Л -ib	нельзя прочесть однозначно. Действительно, его можно

понять и так: аЛ (->6 —>-»с). Тогда оно означает: «Число х делится на 2, и если оно не делится на 3, то не делится и на 6».

Упражнение 2.1. В примере 2.2 рассмотрены не все возможные способы расстановки скобок в выражении а Л ->Ь —>->с. Какой вариант не рассмотрен и какой ему соответствует перевод на русский язык?

В естественных языках логические операции могут выражаться очень разнообразно, в то время как средства формального языка ограни­ чены всего лишь небольшим набором символов. Как мы уже говорили, в свете наших целей это не недостаток его, а достоинство: благодаря этому формальный язык приобретает точность, которой естественные языки лишены. Но чтобы её добиться, требуется, чтобы сам язык был описан по возможности максимально точно. Для этого соотношение ло­ гических связок Л, V, -» со смыслом содержащих их высказываний следует изучить подробнее.

Пример 2.3. Рассмотрим следующее рассуждение: «Кот умыва­ ется — к гостям. Сегодня мой кот умывается. Значит, придут гости». Введём обозначения:

а т=£ кот умывается; b т=* придут гости.

Выражение «кот умывается к гостям» можно переформулировать в ви­ де: «Если кот умывается, то придут гости». На формальном языке оно приобретает вид а 6. В нашем рассуждении мы из того, что считаем верными утверждение а и утверждение а 6, выводим, что верно и утверждение Ь.

Пример 2.3 иллюстрирует применение закона отделения: если ис­ тинны высказывания а и а -+ Ь, то истинно высказывание Ь. Этот ло­ гический закон принято называть по-латински правилом modus ponens (мбдус пбненс). Герой следующего примера тоже пытается применить его.

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

А теперь — внимание, вопросы!

1.Докажите, что Петя допустил логическую ошибку.

2.Какую именно?

На первый вопрос ответить проще: действительно, куда деваться бедному коту, если в солнечный день Петя просыпал в доме перец?

Труднее ответить на второй вопрос. Чтобы разобраться, перефор­ мулируем предложение о том, что знает Петя, в виде «если..., то ...

Итак, кот перед дождём всегда чихает. Допустим, Петя видит, что идёт дождь. Тогда он может провести рассуждение: раз кот всегда чихает пе­ ред дождем, то и в этот раз он чихнул. При этом чихать не по случаю дождя коту не запрещается (см. выше)! Получается, Петя знает следую­ щее: если идёт дождь, то кот перед ним чихнул; а вывод Петя сделал, видимо, из совсем другого утверждения: если кот чихнул, то будет дождь — которое может оказаться ложным.

Ситуация с Петиным котом становится совсем простой, если вос­ пользоваться средствами логики высказываний. Обозначив

а ^ кот чихнул^ b т=±будет дождь,

получаем:

а —>b ^ если кот чихнул} то будет дождц Ь-+ а г=± если будет дождь, то кот чихнул =

= перед дождём кот всегда чихает

Петя из истинности высказываний а и Ъ -Ь а делает неправомерный вывод об истинности высказывания Ъ.

У праж нение 2.2. Придумайте свои примеры верного и неверного применений правила modus ponens.

В разобранных примерах мы переформулировали высказывание «кот умывается к гостям» в виде «если кот умывается, то придут гости», а похожее высказывание «кот чихает перед дождём» — в виде «если идёт дождь, то кот чихнул», поменяв местами выражения после «если» и «то». Чтобы прояснить смысл высказываний, мы ограничили использование возможностей языка, отказавшись от разнообразия аналогов конструк­ ции «если..., то... ». Так же поступают авторы математических текстов,

когда описывают логические операции, пользуясь естественным языком: ограничивают набор употребляемых выразительных средств надёжными словесными конструкциями: «пусть,.,, тогда... », «чтобы..., необходи­ мо, чтобы...», «для.. .достаточно, чтобы...», «значит», «следователь­ но». .. Но даже после таких ограничений смысл некоторых утверждений может потребовать уточнения.

У праж нение 2.3. Что можно сказать о каждом из приведённых ниже сложных предложений: это истинное высказывание? это ложное высказывание? это предложение не является высказыванием? Считай­ те, что все простые предложения, входящие в состав сложных, — вы­ сказывания. Если ответы вызывают существенные затруднения, читайте дальше.

• Россия — родина слонов, и 2 х 2 = 4.

• Россия — не родина слонов, или 2 x 2 = 4.

• Если 2 х 2 = 5, то этот текст писал папа римский.

• Если этот текст писал папа римский, то 2 х 2 = 4.

• Если 2 х 2 = 5, то 2 х 2 = 4.

• Если 2 х 2 = 5, то 2 х 2 = 5.

• Студент Петя решил задачу неверно, но неверно, что он её не решил.

2.2. Алгебра логики

Разобранные примеры показывают, что в естественном языке смысл предложений с описанием логических операций определяется очень нечётко. Дело в том, что он задаётся не столько правилами, сколько естественным путём складывающимися традициями, которые ни в какие формальные правила не вписываются. Поэтому для обеспечения требуе­ мой математикой логической строгости данное выше описание логиче­ ских связок Л, V, -» как аналогов некоторых оборотов естествен­ ного языка недостаточно. Чтобы определить смысл этих связок более точно, мы рассмотрим их как алгебраические операции на множестве В =s {И,Л}. Именно, введём правила, согласно которым высказывание,

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

Значение отрицания определить просто: высказывание -ю, истинно тогда и только тогда, когда высказывание а ложно. Определение конъ­ юнкции тоже не вызызвает проблем: высказывание a A b истинно тогда и только тогда, когда а истинно и b истинно14. В определении дизъюнк­ ции: высказывание а V Ьистинно тогда и только тогда, когда а истинно или b истинно — необходимо обратить внимание на то, что здесь мы имеем дело с «неисключающим ,,или“»: высказывание а V 6 истинно не только в том случае, когда истинно ровно одно из высказываний а и 6, но и в том случае, когда истинны оба. Русский союз «или» не всегда ис­ пользуется в соответствии с этим определением — мы часто употребляем «исключающее ,,или“». Например, студент, говорящий: «Я сдам сессию, или меня выгонят», видимо, подразумевает,что возможность истинности обеих половин сложного высказывания исключается: если уж он сессию сдаст, то деканат не дерзнёт его выгнать.

Ещё более тонкого анализа требует импликация. Что означает «ес­ ли а, то Ь»? Если а истинно, то b тоже истинно. А если а ложно? Оказы­ вается удобным считать, что в этом случае высказывание а —>b истинно независимо от значения Ь. В математических рассуждениях это свойство импликации встречается «на каждом шагу», да и в повседневной речи мы его порой используем. Например, когда преподаватель говорит: «Если студент N что-то понимает в моём предмете, то я — Александр Македон­ ский», он утверждает, по сути, следующее: либо высказывание «ЛГ чтото понимает в предмете» неверно, либо верно высказывание «Препода­ ватель является Александром Македонским»; возможность истинности обоих этих высказываний, по-видимому, не отрицается. Таким образом, договоримся, что высказывание а b истинно тогда и только тогда, когда истинно высказывание -«а V Ь.

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

Итак, суммируем выводы:

->а истинно	^ а ложно;
а Л Ь истинно	т=^ истинны оба высказывания а и b;
а V b истинно	истинно хотя бы одно

из высказываний а и Ь; a - t b истинно ч=± истинно хотя бы одно из высказываний -ia и b.

Для удобства объединим эти определения в следующей таблице ис­ тинности.

a	ъ	“1а	aV b	a Ab	a —ï b
и	и	л	И	И	и
и	л	л	И	л	л
л	и	и	И	л	и
л	л	и	л	л	и

У пражнение 2.4, А теперь еще раз ответьте на вопросы упражне­ ния 2.3.

Если высказывание о истинно, будем писать а = И, если ложно — будем писать а = J1. Это соглашение оправдывается тем, что для про­ ведения логических рассуждений не важно, что означает высказывание, важно лишь, истинно оно или ложно.

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

1. — «a = û A a = ûV û = a.

2.а V -ю = а -> о = И.

3.а Л -ia = Л.

4.а -> b = (-ia) V Ь.

5.Коммутативность операций дизъюнкции и конъюнкции:

aV b = 6Va, а/\Ь = ЬЛа.

6. Ассоциативность операций дизъюнкции и конъюнкции;

(а V 6) V с = а V (6 V с), (а/\Ь) Лс = аЛ(ЬЛс).

7. Дистрибутивность операций дизъюнкции и конъюнкции:

о V (ЬЛ с) = (а V 6) Л (а V с),

аЛ (Ь V с) = (а Л 6) V (а Л с).

8.Законы двойственности, или законы де Мбргана:

-»(а V Ь) = (-по) Л ("ifr), ”>(а Л 6) = (”>а) V ("»Ь).

Упраж нение 2.5. Докажите свойства 1-8.

2.3.Сложные предикаты

Определив правила построения сложных высказываний с помощью логических связок, естественно пойти дальше и применить логические связки к предикатам. Во многих случаях результат очевиден (см. при­ мер 1.18). Но раз уж мы отказались считать связки просто переводами выражений естественного языка на формальный и определили их как алгебраические операции на множестве высказываний, то и применение их к предикатам нужно стремиться рассмотреть на том же уровне логи­ ческой строгости.

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

Пусть задана функция п переменных / . Если зафиксировать зна­ чения любых т переменных (где т < га), то есть, присвоив этим пе­ ременным конкретные числовые значения, считать их константами, то получим функцию (п —т) переменных. Например, пусть п = 2, т = 1 и функция двух переменных / определена равенством f(x>y) = х + у. Зафиксируем значение одной из переменных: например, положим у = 1. Получаем /(я , 1) = х + 1. Это выражение можно рассматривать как определение функции одной переменной g, для которой имеем:

g(x) = f(x )l) = x + l.

Вернёмся к предикатам. Всякий n-местный предикат ставит в соот­ ветствие элементу множества Un значение из множества В. Пусть Р — n-местный предикат и ... ,хп — переменные. Зафиксируем значения каких-нибудь т переменных: например, положим х\ = а\, . . . , хт = О щ , где û i ,... ,a m G U. Тогда следующее равенство определяет (п - т)- местный предикат Q:

Q {% 1> •••»Я п - т ) = P f a l i •••»ttmj ® l j •••j Хп-т)>

Таким образом, можно сформулировать правило.

Всякий п-местный предикат превращается в (п —тп)-мест­ ный, если вместо т переменных подставить конкретные эле­ менты универсального множества.

П ример 2.5. Пусть U = R, Р — двуместный предикат,

Р(х,у) т=*х

Если положить х = 1. равенство Q(y) = Р(1,у) определит одноместный предикат:

Q(y) — 2/^1-

Теперь обобщим наши рассуждения на случай т = п. Если зафик­ сировать значение всех п переменных, от которых зависит значение чис­ ловой функции / , получим функцию, значение которой — константа. Например, пусть снова f(x,y) = х + у; положив х = 1, у = —1, по­ лучим константу /(1, —1) = 0. Если же зафиксировать значения всех п переменных, определяющих значение n-местного предиката, получит­ ся высказывание.

П ример 2.6. Положив в примере 2.5 х = 1, у = 2, получаем ис­ тинное высказывание 1 ^ 2 . Положив х = 1, у = 0, получаем ложное высказывание 1 ^ 0 .

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

Теперь вернёмся к вопросу о соединении предикатов с помощью ло­ гических связок. Значения, которые принимает предикат, определённый через другие предикаты, зависят от значений всех переменных, участ­ вующих в его определении. Значит, местность такого предиката можно положить равной количеству участвующих в определении переменных.

П ример 2.7. Пусть Р — одноместные предикаты ир — высказыва­ ние. Положим:

Q(x,y) = Р(х) А Р(у);

R(x) = Р(х) А Р(аs);

S(x) = Р(х) А р;

Т = р Л р.

Имеем: Q — двуместный предикат, R и S — одноместные предикаты, Т — высказывание.

Может оказаться, что значения предиката зависят не от всех пере­ менных, с помощью которых он определяется. В таком случае можно считать, что его местность меньше, чем число участвующих в определе­ нии переменных.

П ример 2.8. Пусть Р —одноместные предикаты и р — высказыва­ ние. Положим:

Q(x, у) = Р(х) V (Р(у) А ->Р(у))\1

R(x,y) = Р(х) А (Р(у) А ~'РЫ))\

S(y) = р V (Р(у) А ->Р(у))-

Поскольку Р(у) А ~>Р{у) = Л независимо от значения переменной у, то

Q(x,y) = Р(х) V Л = Р(я); Д(х,у) = Р(х) А Л = Л;

S(y) = р V Л = р.

Таким образом, фактически предикат Q можно считать одноместным, а предикаты R и S — нуль-местными, то есть высказываниями.