Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.4. Введение в логику высказываний

Высказывания и операции над ними

Под высказыванием понимают грамматически правильное повествовательное предложение, про которое можно сказать, что оно либо истинно, либо ложно, например: «Киев — столица Украины», «Париж — столица России». Первое высказывание истинно, второе — ложно.

Возьмем два простых высказывания:

А = «На улице идет дождь», В = «Над моей головой раскрыт зонтик».

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

1) отрицание: А = «На улице не идет дождь»;

2) дизъюнкция: А ∨ В = «На улице не идет дождь или над моей головой раскрыт зонтик»;

3) конъюнкция: А ∧ В = «На улице идет дождь и над моей головой не раскрыт зонтик»;

4) импликация: А → В = «Если на улице идет дождь, то над моей головой раскрыт зонтик»

5) эквивалентность: В ~ А = «Над моей головой раскрыт зонтик тогда и только тогда, когда на улице идет дождь».

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

Отрицание. Высказывание А по-другому можно прочитать так: «Истинно то, что на улице идет дождь». Поэтому, если А = 0, то это означает, что на улице не идет дождь. Дополняющее высказывание А также ориентируется на истинное высказывание, т.е. его следует понимать как «Истинно то, что на улице не идет дождь». Тогда А = 1 будет обозначать ту же самую ситуацию, что и в предыдущем случае, т.е. отсутствие дождя.

Дизъюнкция. В нашем конкретном примере дизъюнкция двух высказываний А и В, в принципе, может подразумевать и конъюнкцию этих же высказываний. Однако часто грамматический союз или не включает в себя союз и. Пусть даны два других высказывания:

P = «Петр находится в кинотеатре»,

Q = «Петр находится в бассейне».

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

P ∨ Q = «Петр находится в кинотеатре или/и в бассейне».

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

(P ∨ Q) ∧ (P ∧ Q).

Подобные высказывания называются строгой дизъюнкцией, которая означает «либо P, либо Q, но не P и Q одновременно». И хотя, с точки зрения логики Буля, эта логическая операция равносильна операции симметрической разности:

P + Q = (P ∨ Q) ∧ (P ∨ Q),

исторически сложилось так, что символ « + » в логике высказываний не используется.

Конъюнкция. Логический союз и необязательно должен представляться через грамматический союз и. В частности, выше приведенное выражение можно прочитать несколько иначе:

А ∧ В = «На улице идет дождь, а над моей головой не раскрыт зонтик»;

Союзы а и но по смыслу часто совпадают с союзом и, поэтому они используются в сложных конъюнктивных предложениях. Однако языковая ситуация может стать такой, что союз и перестает играть роль конъюнкции; приведем два предложения:

P ∧ Q = «Ему стало страшно и он убил человека».

Q ∧ P =«Он убил человека и ему стало страшно».

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

Q → P = «Когда он убил человека, ему стало страшно».

Импликация. Высказывание типа «если А, то В» носит объясняющий характер. Оно как бы разъясняет нам, почему имеет место событие В — потому что имело место событие А. Это свойство импликации особенно ценно для логики высказываний, о чем мы подробно остановимся в следующем подразделе.

Объясняющий характер импликации тесно связан с причинно-следственным отношением, при котором А выступает в роли причины, а В — следствия. Причинно-следственная связь между А и В грамматически может быть оформлена предложениями: «А является достаточным основанием для В», «В, потому что А», «В при условии выполнения А» и т.д. Если под А и В понимать прежнии высказывания, то результат причинно-следственного отношения можно оформить следующей таблицей истинности (табл. 1.21). Вторая строка таблицы говорит об отсутствии причинно-следственного отношения между событиями А и В.

Таблица 1.21

А	В	А → В	Результаты
0	0	1	Останусь сухим
1	0	0	Вымокну
0	1	1	Останусь сухим
1	1	1	Останусь сухим

Эквивалентность. Высказывание «А эквивалентно В» может быть с успехом заменено на «А равно В», «А тождественно В», «А равносильно В», «А тогда и только тогда, когда В» и т.д. Так как эквивалентность выражается через конъюнкцию двух импликаций:

А ~ В = (А → В) ∧ (В → А),

то это отношение часто возникает при одновременном выполнении двух условий: «из А следует В» и «из В следует А». Таким образом, при эквивалентности двух событий невозможно одному из них приписать роль только причины, а другому — только следствия. Например, два события:

R = «Нарастание анархии в обществе»,

S = «Падение авторитета власти»,

являются вполне равнопорядковыми событиями, поскольку причиной нарастания анархии в обществе является падение авторитета власти; и наоборот, падение авторитета власти происходит из-за нарастания анархии в обществе. В данной ситуации бессмысленно обвинять только власть в слабости и некомпетентности или обвинять народ в несознательности и недисциплинированности.

События R и S образуют логический круг; их будем называть сильно связанными событиями и выражать следующими тождественными формами:

R ~ S = (R ∧ S) ~ (R ∨ S) = (R ∨ S) → (R ∧ S).

Понятие «сильной связанности» совпадает с понятием «эквивалентности», если речь идет о двух событиях. Но возьмем, например, хорошо известное "объяснение", на чем держится Земля:

Земля (X) держится на трех китах (Y), киты (Y) держатся на водах океана (Z), океан (Z) держится на Земле (X).

Последовательность, куда входят три названных объекта X, Y и Z, тоже образуют логический круг:

(X → Y) ∧ (Y → Z) ∧ (Z → X).

Однако отношение эквивалентности (быть взаимной опорой друг для друга) между всеми тремя объектами, т.е.X ~ Y ~ Z, здесь не возникает. Да и не может возникнуть, так как мы ведь не утверждаем, что Земля является непосредственной опорой для китов (X ~ Y), или что киты являются непосредственной опорой для вод океана (Y ~ Z). Поэтому эквивалентность в данном случае проявляется весьма в своеобразной форме:

(X ∧ Y ∧ Z) ~ (X ∨ Y ∨ Z)   или

(X ∨ Y ∨ Z) → (X ∧ Y ∧ Z),

что можно истолковать в случае операции эквивалентности как: одновременное появление всех трех опор произойдет тогда и только тогда, когда возникнет хотя бы одна из опор, и наоборот; для операции импликации: если возникнет какая-нибудь одна из опор, то это приведет к появлению всех трех опор. Таким образом, сильная связанность, или логический круг, есть не логическая операция, а нечто промежуточное между причинно-следственным отношением и отношением эквивалентности. Подобные аномальные отношения возникают нередко, например, между членами преступной организации, где все связаны круговой порукой, чиновники часто пускают человека по кругу и он не может найти крайнего из них и так далее. Все эти социальные явления выпадают из рассмотрения математической логики.