Глава 6. Начала логики предложений

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

ных значений входящих в формулу элементарных предложений.

X1 ^ — X2 ложно и, значит, — (X1 ^ — X2) истинно; б) Еели X1 истинно, a X2 ложно, то — X2 истинно, X1 ^ — X2 ютшо и —(X1 ^ — X2) ложно; в) Если X1 ложно, то X1 ^ — X2 истинно при любом X2, и — (X1 ^ — X2) ложно.

Другой пример: истинностная таблица для формулы (X1 ^ X2 )& & — (X2 V X1) имеет вид: X1 X2 (X1 ^ X2)&—(X2 VX1) и и л и л л л и л л л и Легко убедиться, что таблица записана верно, непосредственно «вычислив» значение формулы для каждого из четырех наборов значений X1 X2 X1 V X2

значение И, а ее отрицание — (X1 V X2)—значение Л; поэтому конъюнкция (X1 ^ X2) & —(X2 V X1) ложна (так что значение импликации X1 ^ X2 вычислять не нужно).

Приведем пример построения истинностной таблицы для формулы, содержащей три элементарных предложения X1; X2, X3. В этом случае таблица имеет 8 строк: всевозможных наборов значений предло- X1 X2

значениями предложения X3. (Можно доказать, что для произвольного n число всевозможных наборов истинностных значений предложений X1,X2,..., Xn равно 2n.) При составлении истинностных таблиц удобно

располагать наборы значений элементарных предложений («слова» из букв If, Л) в лексикографическом порядке, т.е. так, как располагают слова в обычных словарях (так мы поступали и при n = 2). Для формулы — (X2 V —X1) ^ X1 & X3 при лексикографическом расположении строк получаем следущую таблицу: X1 X2 X3 —(X2 V—x1) ^ x1 &x3 И И И И И И Л И И Л И И И Л Л Л Л И И И Л И Л И Л Л И И Л Л Л И Последний столбец можно заполнить, выполнив для каждой строки непосредственное «вычисление».

X1 X3

X2 X1 импликация также истинна, так как имеет ложную посылку. Остается произвести непосредственное «вычисление» для одной строки — той, где X1 X2 X3

Задача. Составить истинностные таблицы для формул:

(а) —(—X2 V X2);

(б) (X1 & X2) V X3;

(в) (X1 ^ — X2) ^ — (X1 VX2)&— X3;

(г) (X1 ^ X2)&(—X3 X3);

(д) — ((X2 ^ (X3 ^ X1)) ^ X3 VX1 &X2).

2. Нетрудно заметить, что две разных формулы логики предложений могут иметь один и тот же смысл, т. е. быть синонимичными. Рассмотрим, например, предложения А = «Неверно, что Иванов и Петров—оба студенты» и B = «По крайней мере один из двоих —Иванов или Петров —не студент». Ясно, что эти предложения означают одно

X=

Y = «Петров студент», мы можем записать А и B в виде — (X & Y)

и —X V — Y соответственно. Теперь легко понять, почему А и B синонимичны — составив истинностные таблицы для соответствующих формул, мы видим, что эти таблицы совпадают: X Y — (X & Y) —X V—Y И и Л Л и л и и л и и и л л и и (Здесь две таблицы самоочевидным образом сведены в одну.)

Ясно, что предложения, выражаемые этими формулами, останутся

XY

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

Замечание. Рассматривая предложения А и B как «совпадающие по смыслу», мы, строго говоря, допустили неточность. Эти предложения вполне равнозначны .лишь с точки зрения истинности/ложности, смыс-

А

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

B

смысловой оттенок отсутствует. (Еще нагляднее это различие видно на примере более простых предложений «Иванов студент» и «Неверно, что Иванов не студент».) Такие предложения — равнозначные с точки зрения истинностных значений — можно было бы назвать «логически синонимичными», в отличие от «полностью синонимичных» — абсолютно тождественных по смыслу.

X & Y Y& X

синонимичны и «на самом деле.») Так что нам не случайно пришлось в главе 3, говоря об отождествлении в логике синонимичных предложений, сказать, что они отождествляются лишь «как правило». Теперь мы можем уточнить это так: в логике синонимичные предложения отождествляются, если их синонимия не вызвана синонимией выражающих их формул логики предложений или логики предикатов.

Мы можем теперь сказать, что две формулы логики предложений синонимичны — или, как принято говорить, равносильны, — если их истинностные таблицы совпадают. Но нам удобно будет сформулировать определение равносильности еще и в несколько иной форме. Для этого нужно будет ввести новое понятие, которое важно и само по себе—понятие булевой функции. Именно: булева функция — это функция F(х1,..., xn) (n = 1, 2,...), такая, что все независимые переменные пробегают двухэлементное множество {И,Л} и все значения функции также принадлежат этому множеству.

Всякую булеву функцию можно, очевидно, задать с помощью таблицы точно такого же вида, как те истинностные таблицы, которые сопоставляются формулам. Например, таблица X1 X2 F (X1,X2) if И И И л л л И л л л И задает функцию двух переменных F(X1,X2), такую, что F(И, И) = If,

F(И, Л) = Л, F(Л, И) = Л, F(Л, Л) = И.

F

ной таблицей некоторой формулы, говорят, что эта формула представ-

F

Например, только что упомянутая функция F(X1,X2) представляется, как легко проверить, формулой (X1 ^ X2)& (X2 ^ X1). (Для проверки можно, конечно, непосредственно «вычислить» истинностное значение формулы для каждой строки таблицы, но проще заметить, что каждая из двух входящих в нее импликаций ложна тогда и только тогда, когда ее посылка истинна, а заключение ложно, и, следовательно,

X1 X2

когда они различны.)

Естественно возникает вопрос: всякую ли булеву функцию можно представить формулой? Ответ на него — положительный, но доказательство этого факта выходит за рамки нашей книги.

Теперь мы можем сформулировать определение равносильности так:

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

Для обозначения равносильности формул используется знак = (он уже знаком нам по главе 3).

Равносильными являются, например, формулы — (X1 & X2) и —X1 V V —X2: мы фактически доказали это выше, когда обсуждали пример с

X X1 Y X2

но это, разумеется, не имеет никакого значения.)

Другим примером могут служить формулы (X1 V X2)& Х3 и X1 & & X3 V X2 & X3, как показывают их истинностные таблицы: X1 X2 X3 (X1 V Х2)&Хз Х1 & х3 V Х2 & х3 И И И И И И И Л Л Л И Л И И И И Л Л Л Л Л И И И И Л И Л Л Л Л Л И Л Л Л Л Л Л Л Задачи.

(а) X ^ —Y = Y ^ —X-,

(б) X ^ (Y ^ Z) = X & Y ^ Z.

(2) Равносильны ли формулы:

(а) —(X ^ Y) и X ^ —Y1

(б) (X ^ Y) ^ Z и X ^ (Y ^ Z)?

(в) (X ^ Y)&(X ^ Z) и X ^ Y & Z?

(г) (X ^ Y) V (X ^ Z)n X ^ (Y V Z)?

Равносильными могут быть и такие формулы, у которых множества входящих в них элементарных предложений не совпадают. Дело в том, что формула, содержащая, допустим, два элементарных предложения X1 X2 X1 X2

но и, например, функцию трех переменных X1; X2, X3, такую, что

X1 X2

X3

Рассмотрим, например, функцию C(X1,X2,X3), заданную следующей таблицей:

X1 X2 X3 C (Х1,Х2, Х3) И И И И И И л И И л И л И л л л л И И л л И л л л л И л л л л л X1 X2

X3

X1 X2

X3

есть И при Х1 = Х2 = И и Л при остальных наборах значений Х1

X2 X1 & X2

функцию C(Х1, Х2,Х3). Но эта функция представляется также и фор-

X1 & X2 & X3 V X1 & X2 & —X3

X1 & X2

X1 & X2 & X3 V X1 & X2 & —X3

Вот еще один пример такого рода: составив истинностную таблицу для формулы (Х1 ^ Х2)& (Х1 ^ —Х2), мы увидим, что она принимает

X1 X1

X2 —X1

Задача. Доказать, что:

(а) (Х1 VХ2 VХ3)&(Х1 VХ2 V—Х3) = Х1 VХ2;

(б) (Y ^ X)& (—Y ^ X) = X;

(в) X V (X & Y) = X;

(г) (X&Y ^ Z)&(X& —Y ^ Z) = X ^ Z.

3. Пользуясь понятием равносильности, можно установить ряд простых, но очень важных свойств пропозициональных связок. До некоторой степени они похожи на свойства арифметических действий над числами, но еще больше — на свойства операций над множествами, ко-торые были рассмотрены в главе 4. Все эти свойства имеют вид равно- сильностей и легко доказываются с помощью истинностных таблиц; их называют обычно основными равносильностями логики предложений или основными свойствами пропозициональных связок. Ради большей обозримости мы разобьем их на три группы.

В группу I войдут восемь соотношений, в которых участвуют только конъюнкция и дизъюнкция:

X V (Y V Z) = (X V Y) V Z (ассоциативность дизъюнкции).

X V Y = Y V X (коммутативность дизъюнкции).

X &(Y & Z) = (X & Y )&Z (ассоциативность конъюнкции).

X & Y = Y & X (коммутативность конъюнкции).

X &(Y V Z) = X & Y V X & Z (дистрибутивность конъюнкции по отношению к дизъюнкции).

І6- X V Y & Z = (X V Y)&(X V Z) (дистрибутивность дизъюнкции по отношению к конъюнкции).

x V X = X.

X & X = X.

Группу II составляют три соотношения, в которых, кроме конъюнкции и дизъюнкции, участвует отрицание:

1 ——X = X

ІІ2.

тт v. _ > («законы Де Моргана»).

П3. —(X & Y ) = —x V —Y I

Группа III состоит из трех соотношений, в которых участвует импликация:

ІІІь X ^ Y = —X V Y.

nh- X ^ Y = —(X& —Y).

III3. X ^ Y = —Y ^ —X («закон контрапозиции»).

Стоит заметить, что содержательный смысл соотношений группы III

XY Y X 1

можно, чтобы X было верно, a Y неверно» (Ш2); если из верности X Y Y X

если из неверности Y следует неверность X т0 из верности X следует

Y3

Основные равносильности логики предложений позволяют производить тождественные преобразования формул, т. е. переходить от одних формул к другим, равносильным, подобно тому, как производятся тождественные преобразования в элементарной алгебре. В частности: ввиду соотношений ^ и І3 в выражениях вида X V (Y V Z), X &(Y & Z) и т.п. можно опускать скобки (фактически мы это несколько раз уже

24

2 В честь одного из создателей математической логики Августа Де Моргана (Augustus De Morgan, 1806—1871).

в дизъюнкциях и конъюнкциях, соотношение 15 — раскрывать скобки.

1

2

23

отрицание, стоящее перед дизъюнкцией или конъюнкцией (причем дизъюнкция заменяется конъюнкцией, а конъюнкция — дизъюнкцией);

1

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

(1) (2)

(7) (В)

Пример. X & —Y V Z ^—(Х Z) =

= X & —Y V Z ^ ——(X & ——Z)

= X & —Y V Z ^ X & Z = = —(X & —Y V Z) V X & Z = = —(X & —Y )&—Z V X & Z =

= (—X V——Y)&—Z V X & Z = = (—X V Y)&—Z VX&Z =

X&-.ZVY& -.ZMX & Z.

Здесь при переходе от формулы (1) к формуле (2) импликация выражается через конъюнкцию и отрицание, при переходе к формуле (3) устраняются двойные отрицания, при переходе к формуле (4) импликация выражается через дизъюнкцию и отрицание, при переходе к формуле (5) отрицание дизъюнкции заменяется конъюнкцией отрицаний, при переходе к формуле (6) отрицание конъюнкции заменяется дизъюнкцией отрицаний, при переходе к формуле (7) еще раз устраняется двойное отрицание и при переходе к формуле (8) раскрываются скобки.

Задача. Привести к дизъюнктивной нормальной форме следующие формулы:

(а) XV—Z — Y&Z;

(б) (X - Y) - (Y - X);

(в) —(Х1 & — (Х2 V—X3) — ХО&Х2;

(г) ———(—X V—Y V—Z).

4. Булева функция называется тождественно истинной, если для всех наборов значений независимых переменных она принимает значение If, и тождественно ложной, если для всех наборов значений независимых переменных принимает значение Л. Формула, представляющая тождественно истинную или тождественно ложную булеву функцию, также называется тождественно истинной, соответственно тождественно ложной.

Тождественно истинны, например, следующие формулы: X V —X, —(X & —X) X - X X

— (X V—X), X & —X —(X — X) тождественно ложны.

Примеры тождественно истинных формул, содержащих две перемен-ных: X & Y V X & —Y V—X & Y V—X & —Y; (X — Y) — (—Y — —X). Читатель легко убедится в их тождественной истинности, составив для них истинностные таблицы.

Ясно, что все тождественно истинные формулы равносильны между собой, и всякая формула, равносильная тождественно истинной, сама тождественно истинна; то же верно для тождественно ложных формул. Очевидно также, что отрицание тождественно истинной формулы тождественно ложно, а отрицание тождественно ложной — тождественно истинно.

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

полностью обусловлена их логическим строением и не зависит от того, к какой предметной области они относятся. Сравним, например, два арифметических предложения: «Если натуральное число делится на 6, то оно делится на 3» и «Всякое натуральное число или делится на 3, или не делится». Оба они истинны, но истинность первого обусловлена законами арифметики, а истинность второго от этих законов не

х

предложение «х делится та 3» через X, то наше предложение выразится тождественно истинной формулой X V —X, и полученное из этой

X

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

Можно сказать, таким образом, что любая тождестенно истинная формула выражает некоторый логический закон. В частности, формула X V —X выражает закон исключенного третьего, а формула — (X & —X) — закон противоречия (см. гл. 1).

5. К указанным выше основным равносильностям мы можем теперь добавить несколько новых; их особенностью будет то, что некоторые из участвующих в них предложений предполагаются тождественно истинными или тождественно ложными. В этих соотношениях буква R

F

X

IVb X V R = R. IV2. X V F = X.

IV3. X & R = X. IV4. X & F = F.

IV5. X — R = R. IV6. F — X = R.

X

нимает значение И, то, поскольку R всегда имеет значение И, X & R

X

X & R принимает значение Л. Аналогично: каково бы ни было X, им- F - X

лишь тогда, когда посылка истинна, а заключение ложно. Остальные равносильности читатель докажет сам.

6

из лжи следует все, что угодно (по-латыни ex falso quodlibet).

Соотношения TV| (і во многих случаях позволяют упрощать формулы, т. е. находить для них равносильные формулы более простого вида. Именно, в силу IV2,3 в дизъюнкциях можно вычеркивать тождественно

3Иоанн Дуне Скот (Johannes Duns Scotus, 1265—1308) — один из крупнейших средневековых философов и богословов, монах-францисканец, родом из Шотландии.

ложные члены, а в конъюнкциях — тождественно истинные; в то же время тождественную истинность или тождественную ложность формулы нередко удается установить с помощью соотношений IV1J4,5,6 и законов исключенного третьего и противоречия. Кроме того, ввиду соотношений І7;8 в конъюнкциях и дизъюнкциях можно вычеркивать повторяющиеся члены.

Например, формула (—(X & —X — Y) V X) & (Y V Z V —Z) равно- X X & —X — Y

на (в силу IV6 и тождественной ложности формулы X & —X), так что дизъюнкция —(X & —X — Y) V X равносильна X (в силу IV2); б) дизъюнкция Y V Z V —Z тождественно истинна (в силу закона исключенного третьего и IV1), так что конъюнкция X &(Y V Z V —Z) равносильна X (в силу IV3). Другой пример: формула (X V Y V X)&(Х V Y) равносильна X V Y в силу 17 и І8.

Задачи. (1) Упростить формулы:

(а) (—X V—Z V X V Y )&(Х V—Z V X V Y )&(Х V—Z V Z V Y);

(б) X — (Y& —Y — Z);

(в) (Х1 — (Х2 — ...(Х„ — Y V—Y) ...))&Z.

(2) Вывести соотношения, аналогичные IV5 и IV6, с левыми частями R — X ж X — F.