Лекция 5. Теоремы о выводимых формулах

Рассмотрим основные свойства выводимости, в которых A и B —

произвольные формулы исчисления высказываний. Приведем первое из

этих свойств: если выводима формула A ∨ B, то выводима формула

B ∨ A. По существу это новое правило вывода. Поэтому мы формули-

руем его в следующем виде.

СВОЙСТВО 1 Справедливо правило вывода (коммутативность)

A ∨ B

B ∨ A

. (13)

Доказательство. Дано, что _ A ∨ B. Необходимо доказать _ B ∨ A.

Применим правило сечения

A ∨ B, ￢A ∨ A

B ∨ A

. (14)

Посылка A∨B выводима по условию теоремы. Посылка ￢A∨A выводи-

ма, так как является пропозициональной аксиомой. Следовательно, за-

ключение правила B ∨A также является выводимой формулой. Свойство

доказано.

СВОЙСТВО 2 Справедливо правило

(A ∨ B) ∨ C

A ∨ (B ∨ C)

. (15)

Доказательство. Установим, что _ A ∨ (B ∨ C) в 6 шагов.

1. _ (A ∨ B) ∨ C по условию,

2. _ C ∨ (A ∨ B) по правилу коммутативности,

3. _ (C ∨ A) ∨ B по правилу ассоциативности,

4. _ B ∨ (C ∨ A) по правилу коммутативности,

5. _ (B ∨ C) ∨ A по правилу ассоциативности,

6. _ A ∨ (B ∨ C) по правилу коммутативности.

Свойство доказано.

По существу мы установили

23

СВОЙСТВО 3 Если выводима формула (A ∨ B) ∨ C, то выводимы

все формулы, полученные из нее с помощью произвольной цикличе-

ской перестановки членов и произвольной расстановки скобок.

СВОЙСТВО 4 Формула ￢￢A∨B выводима тогда и только тогда,

когда выводима формула A ∨ B.

Доказательство. Пусть выводима формула ￢￢A ∨ B. Применим пра-

вило сечения

￢A ∨ A, ￢￢A ∨ B

A ∨ B

. (16)

Посылки ￢￢A ∨ B и ￢A ∨ A выводимы (первая — пропозициональная

аксиома, вторая по условию ). Следовательно, _ A ∨ B.

Обратно, пусть выводима формула A ∨ B. Применим правило сечения

A ∨ B, ￢A ∨￢￢A

B ∨ ￢￢A

. (17)

Посылка A ∨ B выводима по условию. Посылка ￢A ∨ ￢￢A выводи-

ма, т.к. _ ￢￢A ∨ ￢A (пропозициональная аксиома) и по коммутативно-

сти _ ￢A ∨ ￢￢A. Получим _ B ∨ ￢￢A и по свойству коммутативности

_ ￢￢A ∨ B.

Свойство доказано.

СВОЙСТВО 5 Пусть дана формула A = A1 ∨ A2 · · · ∨ An, у кото-

рой выводим один из ее членов Ai, где i = 1, 2, . . ., n. Тогда выводима

формула A.

Доказательство. Если i = n, то применим несколько раз правило рас-

ширения. Получим

_ An−1 ∨ An, _ An−2 ∨ An−1 ∨ An, . . . , _ A1 ∨ A2 ∨ . . . ∨ An,

т.е. _ A. Если i _= n, то рассмотрим C = Ai+1 ∨ . . . ∨ An. Как и выше

получаем

_ Ai ∨ C, _ Ai ∨ Ai+1 ∨ C, . . . , _ A1 ∨ A2 ∨ . . . ∨ An,

т.е. _ A. Свойство доказано.

СВОЙСТВО 6 Пусть дана формула A = A1 ∨ A2, . . . , ∨An, причем

для некоторых ее членовAi, Aj, где i, j ∈ {1, 2, . . ., n}, выводимафор-

мула Ai ∨ Aj . Тогда выводима формула A.

Доказательство проводим индукцией по числу n. Пусть A—контрпример

с наименьшим n. Если i = j, то _ Ai ∨ Ai. По правилу сокращения _ Ai.

По предыдущей теореме _ A и A — не контрпример. Поэтому считаем

i _= j. С учетом _ Aj ∨ Ai можно считать, что i < j.

Если i > 1, то формула B = A2 ∨ A3, . . . , ∨An содержит члены Ai, Aj,

причем _ Ai ∨ Aj . Тогда по индукции _ B и по правилу расширения _ A.

Пусть i = 1. Тогда _ A1 ∨ Aj. Если при этом j = 2, то _ A1 ∨ A2.

Обозначим C = A3, . . . , ∨An. По правилу расширения _ (A1 ∨ A2) ∨ C.

По правилу ассоциативности _ A = A1 ∨ (A2 ∨ C), что и нужно.

Пусть j > 2. По индукции получаем _ A1 ∨ C для C = A3 ∨ · · · ∨ An.

Тогда

1. _ C ∨ A1 (по коммутативности),

2. _ (C ∨ A1) ∨ A2 (по правилам расширения и коммутативности),

3. _ C ∨ (A1 ∨ A2) (по ассоциативности),

4. _ (A1 ∨ A2) ∨ C (по коммутативности),

5. _ A1 ∨ (A2 ∨ C) (по свойству 3),

т.е. _ A.

Свойство доказано.

СВОЙСТВО 7 Пусть дана формула A = A1 ∨ A2 ∨ · · ·∨ An, причем

для некоторых ее членов Ai1, Ai2, . . ., Aim выводима формула

Ai1

∨ Ai2

∨ · · · ∨ Aim. (18)

Тогда выводима даннаяформула A.

Доказательство проводим индукцией по числу m. Пусть A — контрпри-

мер с наименьшим m. По свойствам 5 и 6 имеемm > 2.

Нам дана выводимая формула Ai1

∨ Ai2

∨ · · · ∨ Aim, т.е. формула

Ai1

∨ (Ai2

∨ · · · ∨ (Aim−1

∨ Aim)), по соглашению о правосторонней рас-

становке скобок. Рассмотрим другую формулу

(Ai1

∨ Ai2) ∨ Ai3

∨ · · · ∨ Aim. (19)

Она выводима по правилу ассоциативности и с учетом выводимости фор-

мулы (18). Она содержит m − 1 членов следующего вида:

один член Ai1

∨ Ai2и m − 2 членов Ai3, . . . , Aim. (20)

По индукции, если выводима формула, составленная из этихm−1 чле-

нов, то выводима формула F, содержащая эти члены. Рассмотрим в ка-

честве F формулу

(Ai1

∨ Ai2) ∨ A. (21)

Формула (19) составлена из из ее m − 1 членов формулы (21) и выво-

дима. Поэтому по индукции выводима формула (21). Тогда

1. _ (Ai2

∨ A) ∨ Ai1 (по ассоциативности),

2. _ (Ai2

∨ A) ∨ A ( по предыдущему свойству),

3. _ Ai2

∨ (A ∨ A) (по ассоциативности),

4. _ (A ∨ A) ∨ Ai2(по коммутативности),

5. _ (A ∨ A) ∨ (A ∨ A) (по предыдущему свойству),

6. _ A ∨ A (по правилу сокращения),

7. _ A (по правилу сокращения).

Свойство доказано.

Замечание. Из данного свойства следует, что перестановка членов в

формуле A = A1∨A2∨· · ·∨An, не влияет на выводимость этой формулы.

СВОЙСТВО 8 Справедливо правило

￢A ∨ C, ￢B ∨ C

￢(A ∨ B) ∨ C

. (22)

Доказательство. Имеем:

1. _ ￢(A ∨ B) ∨ (A ∨ B) (по пропозициональной аксиоме),

2. _

_

￢(A ∨ B) ∨ A

_

∨ B (по свойству 3),

3. _ B ∨

_

￢(A ∨ B) ∨ A

_

(по свойству 3).

Итак, в следующем правиле сечения все посылки выводимы

B ∨

_

￢(A ∨ B) ∨ A

_

, ￢B ∨ C

(￢(A ∨ B) ∨ A) ∨ C

.

Поэтому

_

￢(A ∨ B) ∨ A

_

∨ C. По циклической перестановке членов

имеем _ A ∨

_

C ∨ ￢(A ∨ B)

_

и по дано _ ￢A ∨ C.

26

По правилу сечения

A ∨

_

C ∨ ￢(A ∨ B)

_

, ￢A ∨ C _

C ∨￢(A ∨ B)

_

∨ C

получаем _

_

C ∨ ￢(A ∨ B)

_

∨ C. Из членов этой выводимой формулы

составлена формула ￢(A ∨ B) ∨ C. По свойству 6 она сама выводима.

Свойство доказано.

Лекция 6. Совпадение классов выводимых и тожде-

ственно истинных формул

В лекции 2 мы сформулировали следующую задачу: «получить до-

статочно простой способ конструирования тождественно истинных фор-

мул—законов логики высказываний». В предыдущей лекции рассмотрен

класс выводимых формул. Формулы этого класса по определению имеют

простую и обозримую конструкцию.

Мы докажем совпадение понятий «выводимая формула» и «тожде-

ственно истинная формула». Тем самым мы получим полное описание

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

ТЕОРЕМА 8 Всякая выводимая формула является тождествен-

но истинной формулой.

Доказательство. Пусть дана произвольная формула X. Напомним

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

1. Пропозициональные аксиомы, то есть формулы вида ￢A∪A - выво-

димые формулы.

2. Если посылки правила вывода - выводимые формулы, то заключение

- выводимая формула,

3. Выводимость формулы X получается получается несколькими при-

менениями правил 1 и 2.

Правила вывода имеют следующий вид.

A

B ∨ A

правило расширения,

A ∨ A

A

правило сокращения,

A ∨ (B ∨ C)

(A ∨ B) ∨ C

правило ассоциативности,

A ∨ B, ￢A ∨ C

B ∨ C

правило сечения.

28

Каждой формуле X однозначно приписан наименьший номер шага, на

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

этому номеру n.

Пусть n = 1. Тогда X - пропозициональная аксиома, т.е. X = ￢A ∨ A

для некоторой формулы A. Формула A содержит буквы, которым при-

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

истина так и ложь. Однако формула X всегда истинна, так как одна из ее

частей A или ￢A является истинной.

Предположим, утверждение верно для всех формул с номером n. По-

кажем справедливость утверждения для формул с номером n + 1. Пусть

формула X имеет номер n+1. Тогда она совпадает с заключением одного

из правил вывода, где где в посылке расположены формулы с номером n.

Они тождественно истинны по предположению индукции.

Возможны 4 случая для вида правила вывода.

1. Пусть рассматривается правило расширения с посылкой A и заклю-

чением X = B ∨ A. Так как посылка A — тождественно-истинная

формула, то значения A всегда равны И. Поэтому значения форму-

лы X = B ∨ A всегда равны И, т.е. X — тождественно истинная

формула.

2. Пусть имеется правило сокращения с посылкой A ∨ A и заключени-

ем A. Так как посылка A ∨ A—тождественно истинная формула, то

заключениеA тождественно истинно. Действительно, если при неко-

тором наборе букв, входящих в A значение A равно Л, то значение A

при этом наборе букв равно Л∨ Л=Л. Это противоречие, так как по-

сылка A ∨ A—тождественно истинная формула,

3. Пусть мы имеем правило правило ассоциативности с посылкой A ∨

(B ∨ C) и заключением (A ∨ B) ∨ C. Так как посылка тождественно

истинна, то при любом наборе значений букв, входящих в формулы

A,B,C, среди значений есть значение И(иначе значение X равно

Л∨(Л∨ Л)= Л). Тогда заключение (A∨B)∨C также принимает зна-

чение И. Получили, что формула (A∨B) ∨C тождественно истинна.

4. Пусть имеется правило сечения с двумя посылками A ∨ B и ￢A ∨ C

(которые тождественно истинны) и заключением B ∨ C. Предполо-

жим, что при некотором наборе букв, входящих в формулы A,B,C,

значение заключения B ∨ C есть Л. Тогда значение формулы B и

29

значение C есть Л. Если значение формулы A равно Л, то значение

формулы A ∨ B равно Л, противоречие с тождественной истинно-

стьюA∨B. Если значение формулы A равно И, то значение формулы

￢A∨C равно Л, противоречие с тождественной истинностью ￢A∨C.

Значит формула B ∨ C тождественно истинна. Теорема доказана.

Докажем обратное утверждение для теоремы 8.

ТЕОРЕМА 9 Всякая тождественно истиннаяформула является

выводимой формулой.

Доказательство. Пусть формула A является тождественно истинной.

Тогда тождественно истинна формула A ∨ A. Достаточно проверить ее

выводимость. Действительно, из выводимости формулы A∨A по правилу

сокращения следует выводимость формулы A, что и нужно.

Вместо доказательства выводимости формулы A ∨ A докажем более

общий факт:

если формула A1 ∨ A2 ∨ · · · ∨ An, где n _ 2 — тождественно

истинна, то она выводима.

При n = 2 и A1 = A2 = A получим то, что требуется. Итак, дано, что

формула

X = A1 ∨ A2 ∨ · · · ∨ An (23)

является тождественно истинна и n _ 2. Докажем, что X - выводимая

формула, рассматривая несколько случаев.

Случай 1. Рассмотрим вначале случай, когда число символов в каждой

формуле A1, A2, . . ., An равно 1 или 2. Из определения формулы следует,

что формулы A1, A2, . . ., An являются буквами или отрицанием букв. По-

этому формула X — элементарная дизъюнкция и имеет вид, подобный

виду: X = C ∨ ￢D ∨ A ∨ ￢C, где A,D,C —буквы. Элементарная дизъ-

юнкция является тождественно истиной, тогда и только тогда, когда в нее

входит некоторая буква вместе со своим отрицанием.

Поэтому в формуле X есть вхождение некоторой буквы A вместе с

вхождением отрицания ￢A. Выводимость формулы не зависит от по-

рядка членов по свойству 7. Переставляя компоненты считаем, что

X = X1 ∨ X2 ∨ . . . ∨ (￢A ∨ A). Имеем_ ￢A∨A (пропозициональная ак-

сиома). Применяя несколько раз правило расширения, получим _ X.

Случай 1 рассмотрен.

Предположим, что утверждение теоремы 2 не выполняется.Среди всех

формул X, которые не удовлетворяют заключению ( т.е. не являются вы-

водимыми) рассмотрим контрпримерX = A1∨A2∨· · ·∨An с наименьшим

количеством символов.

Рассмотрим строение каждого члена A1, A2, . . .An формулы X. По-

скольку cлучай 1 рассмотрен, то можно считать, что среди членов

A1, A2, . . .An есть член Ai, который не является буквой и не является от-

рицанием буквы. Члены A1, A2, . . .An в записи X можно переставлять; по

свойству 7 это не влияет на выводимость формулы. Поэтому считаем, что

A1 не буква и не является отрицанием буквы. Любая формула X, отлич-

ная от буквы, построена из ранее полученных формул Y и Z с помощью

одного из двух действий: 1)X = ￢Y или 2)X = Y ∨Z. Если при этом фор-

мула X отличная от отрицания буквы, то в случае 1) имеем 1 а) X = ￢￢Z

или 1 б) X = ￢(Y ∨ Z). Поэтому выполнена одна из 3 возможностей:

1. A1 = ￢￢B,

2. A1 = ￢(B ∨ C),

3. A1 = B ∨ C.

Обозначим D = A2 ∨ · · · ∨ An.

Случай 1 A1 = ￢￢B. Тогда X = (￢￢B) ∨ D. Рассмотрим новую

формулу X1 = B ∨ A2 ∨ . . .An = B ∨ D. Формула X1 принимает оди-

наковые значения с формулой X, и поэтому, X1 тождественно истинна.

Она имеет на 2 символа меньше, чем формула X. По индукции заключа-

ем _ X1 = B ∨ D. о свойству выводимости 4 получаем _ X = ￢￢B ∨ D

Случай 2 A1 = ￢(B ∨ C). Тогда X = ￢(B ∨ C) ∨D. Введем две новые

формулы X1 = ￢B ∨ A2 ∨ . . .An = ￢B ∨ D и X2 = ￢C ∨ A2 ∨ . . .An =

￢C ∨ D. Методом от противного установим тождественную истинность

формул X1 и X2. Предположив, что при некотором наборе значений букв

формула X1 ложна. Получим, что значение X1 и значение D ложны. То-

гда значение формулы X = ￢(B ∨C)∨D ложно, независимо от значения

C. Противоречие с тем, что X тождественно истинна. Рассуждения для

X2 аналогичны. Итак, формулы X1 = ￢B ∨ D и X2 = ￢C ∨ D тожде-

ственно истинны и выводимы по предположению индукции. По свойству

8 выводима формула X = ￢(B ∨ C) ∨ D.

Случай 3 A1 = B ∨ C. Подставив в формулу X, получим

X = (B ∨ C) ∨ A2 ∨ . . .An = (B ∨ C) ∨ D Выводимость формулы X

равносильна выводимости формулы Y = B∨(C∨D) = B∨C∨A2∨. . .An

со стандартной расстанокой скобок и числом членов на 1 больше, чем

в X. Число символов тоже, что и в формуле X. Операцию перехода от

формулы X к формуле Y назовем «измельчением звеньев». Она не меня-

ет число символов в формуле. Поэтому мы могли среди контрпримеров с

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

дальнейшего измельчением членов. Тогда последний случай невозможен.

Теорема доказана.

Мы завершили раздел логики, относящийся к исчислению высказыва-

ний.