Лекции Просолупов

Лекция 17. Теоремы исчисления высказываний

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

Лемма 49.5 . Пусть, — формула. Тогда ( ).

Доказательство. Построим вывод для формулы ( ):

1.(( (( ) )) (( ( )) ( ))) — аксиома 2 после подстановки вместо формулы , вместо — ( ) и вместо — .

2.( (( ) )) — аксиома 1 после подстановки ← , ← ( ).

3.(( ( )) ( )) — применение правила вывода MP к строкам 2 и

1.

4.( ( )) — аксиома 1 после подстановки ← , ← .

5.( ) — MP к строкам 3 и 4.

Замечание 49.6 . Формулы, для которых мы доказали, что они являются теоремами данной формальной теории, в дальнейшем можно использовать в выводах наравне с аксиомами. Действительно, раз для такой формулы существует вывод, мы всегда можем привести его как составную часть других выводов, но не будем этого делать для краткости.

Теорема 49.7 (Теорема о дедукции). Пусть и — формулы, — некоторое множество формул теории . Тогда из , следует, что ( ).

Доказательство. Пусть 1, 2, ..., = — вывод из множества посылок

{ }. Докажем по индукции, что , = 1, 2, ..., .

1)Пусть = 1. 1 — аксиома, или 1 , или 1 = .

a)Пусть 1 — аксиома.

1.1 — аксиома.

2.1 ( 1) — аксиома 1.

3.1 — MP из 1 и 2. Следовательно 1 1.

b)Пусть 1 .

1.1 — посылка.

2.1 ( 1) — аксиома 1.

3.1 — MP из 1 и 2. Следовательно 1 1 1.

c)Пусть 1 = . По лемме 49.5 = 1 1.

2)Пусть для всех < верно, что . Докажем, что .

—аксиома, или , или = , или получена по правилу вывода modus ponens. Первые три случая доказываются аналогично соответствующим пунктам базы индукции.

d) — результат применения MP к формулам и , , < . Тогда, ,

111

и = . Построим вывод:

1.( ( )) (( ) ( )) — аксиома 2 ( ← , ← ,← ).

2.( ( )) — посылка.

3.(( ) ( )) — MP из 2 и 1.

4.( ) — посылка.

5.( ) — MP из 4 и 3.

Таким образом, ( ( )), ( ) ( ). Следовательно, (). Следовательно, ( ).

Пример 49.8 . С помощью теоремы о дедукции мы могли бы гораздо проще доказать лемму 49.5:

1)— посылка.

2)— по теореме о дедукции, поскольку .

Следствие 49.9 . Пусть, , и — некоторые формулы теории . Тогда

, .

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

1)— посылка.

2)— посылка.

3)— MP из 1 и 2.

4)— посылка.

5)— MP из 3 и 4.

Таким образом, , , . Следовательно, по теореме о дедукции

, .

Следствие 49.10 . Пусть, , и — некоторые формулы теории . Тогда

( ), .

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

1)— посылка.

2)( ) — посылка.

3)— MP из 1 и 2.

4)— посылка.

5)— MP к 4 и 3.

, ( ), . Следовательно, по теореме о дедукции ( ),

.

Лемма 49.11 (Список теорем). Пусть и — произвольные формулы теории. Тогда следующие формулы являются теоремами :

112

1.¬¬ — закон отрицания отрицания.

2.¬¬ — закон отрицания отрицания.

3.¬ ( ) — из ложных посылок можно вывести что угодно.

4.(¬ ¬ ) ( ) — доказательство от противного.

5.( ) (¬ ¬ ) — доказательство от противного.

6.(¬ ¬( )) — из истинных посылок нельзя вывести ложное

заключение.

7. ( ) ((¬ ) ) — если выводима и из и из его отрицания, то истинна независимо от посылок.

Доказательство. Докажем, например, для формул 1 и 3. 1.

1)(¬ ¬¬) ((¬ ¬) ) — аксиома 3.

2)¬¬ — посылка.

3)¬¬ (¬ ¬¬) — аксиома 1.

4)¬ ¬¬ — MP из 2 и 3.

5)(¬ ¬) — MP из 4 и 1.

6)¬ ¬ — лемма 49.5.

7)— MP из 6 и 5.

Таким образом, ¬¬ и по теореме о дедукции ¬¬ . 3.

1)(¬ ) — аксиома 1.

2)¬ (¬ ¬ ) — аксиома 1.

3)— посылка.

4)¬ — MP из 3 и 1.

5)¬ — посылка.

6)¬ ¬ — MP из 5 и 2.

7)(¬ ¬ ) ((¬ ) ) — аксиома 3.

8)((¬ ) ) — MP из 6 и 7.

9)— MP из 4 и 8.

Таким образом, , ¬ . Тогда по теореме о дедукции, ¬ и ¬

( ).

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

113

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

Лемма 49.12 . Аксиомы теории являются тавтологиями.

Доказательство. 1)

( ( )) = = 1.

2)

(( ( )) (( ) ( ))) =

== =

=( )( ) ( )( ) = =

=( )( ) = = 1

3)

((¬ ¬ ) ((¬ ) ) = = = = ( ) = = 1.

Лемма 49.13 . Любая теорема теории является тавтологией.

Доказательство. Пусть для формулы теории существует вывод 1, 2, ...,

= . Докажем по индукции, что — тавтология, = 1, . По определению вывода, 1 является аксиомой и по лемме 49.12 она является тавтологией.

Пусть формулы — тавтология, = 1, . Рассмотрим +1: она является аксиомой, или получена по правилу вывода modus ponens из предыдущих формул. Если +1 — аксиома, то она является тавтологией по лемме 49.12. Пусть +1 получена по правилу modus ponens из формул и = +1, , ≤ . По индукционному предположению, и — тавтологии. Пусть, на некотором наборе значений пропозициональных букв формула +1 принимает значение 0. Тогда на этом наборе

= +1 = 1 0 = 0. ?!

Противоречие. Следовательно +1 — тавтология. Следовательно — тавтология.

Пусть — формула, в которую входят пропозициональные буквы 1, 2, ..., . Когда нам будет необходимо подчеркнуть, от каких значений рассматривается , будем писать ( 1, 2, ..., ), имея в виду, что вместо пропозициональной буквы

подставляется значение , = 1, .

114

Как и раньше, будем использовать знак степени для обозначения наличия или отсутствия отрицания:

Лемма 49.14 . Пусть 1, 2, ..., — все пропозициональные буквы, которые входят в формулу , и пусть 1, 2, ..., — логические константы. Тогда

1 1 , 2 2 , ..., ( 1, 2,..., ).

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

.

1)Пусть = 0. Тогда = 1, ( 1) = 1, ( 1) = 1 1 .

1 1 = ( 1).

2)Пусть утверждение верно для любого < . Докажем для случая логических связок в . Формула , в зависимости от своей последней логической связки, может

быть одного из двух видов: = ¬ 1 или = ( 1 2).

a) Пусть = ¬ 1. Рассмотрим два варианта

Пусть 1( 1, ..., ) = 0. По индукционному предположению 1 1 , 2 2 , ..., ¬ 1. ¬ 1 = = ¬ 1( 1,..., ) = ( 1,..., ). Следовательно,

1 1 , 2 2 , ..., ( 1, 2,..., ).

Пусть 1( 1, ..., ) = 1.

( 1,..., ) = ¬ 1( 1,..., ) = ¬ = ¬¬ 1.

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

1.1 ¬¬ 1 — пункт 2 из леммы 49.11.

2.1 — посылка.

3.¬¬ 1 — MP из 2 и 1.

Таким образом, 1 ¬¬ и

1 1 , 2 2 , ..., ¬¬ 1 = ( 1, 2,..., ).

b)Пусть = ( 1 2). Рассмотрим несколько вариантов. Пусть 1( 1, ..., ) = 0, 2( 1, ..., ) = 0. Тогда

( 1,..., ) = 0 0 = = ( 1 2).

115

Рассмотрим вывод:

1.¬ 1 — посылка.

2.¬ 1 ( 1 2) — пункт 3 из леммы 49.11.

3.( 1 2) — MP из 1 и 2.

Таким образом, ¬ 1 ( 1 2) = ( 1,..., )

1 1 , ..., ( 1,..., ).

Пусть 1( 1, ..., ) = 0, 2( 1, ..., ) = 1. Тогда

1 1 , ..., ¬ 1, 1 1 , ..., 2.

( 1,..., ) = 0 1 = = ( 1 2).

Рассмотрим вывод:

1.¬ 1 — посылка.

2.¬ 1 ( 1 2) — пункт 3 из леммы 49.11.

3.( 1 2) — MP из 1 и 2.

Таким образом, ¬ 1 ( 1 2) = ( 1,..., )

1 1 , ..., ( 1,..., ).

Пусть 1( 1, ..., ) = 1, 2( 1, ..., ) = 0. Тогда

1 1 , ..., 1, 1 1 , ..., ¬ 2.

( 1,..., ) = 1 0 = 0 = ¬( 1 2).

Рассмотрим вывод:

1.1 — посылка.

2.¬ 2 — посылка.

3.1 (¬ 2 ¬( 1 2)) — пункт 6 из леммы 49.11.

4.¬ 2 ¬( 1 2) — MP из 1 и 3.

5.¬( 1 2) — MP из 2 и 4.

Таким образом, 1, ¬ 2 ¬( 1 2) = ( 1,..., )

1 1 , ..., ( 1,..., ).

Пусть 1( 1, ..., ) = 1, 2( 1, ..., ) = 1. Тогда

( 1,..., ) = 1 1 = = ( 1 2).

Рассмотрим вывод:

1.2 — посылка.

2.2 ( 1 2) — аксиома 1.

116

3. ( 1 2) — MP из 1 и 2.

Таким образом, 2 ( 1 2) = ( 1,..., )

1 1 , ..., ( 1,..., ).

Утверждение доказано.

Пример 49.15 . Пусть, = 1 2. Если 1 = 1, 2 = 0, то ( 1, 2) = 0. Следовательно, по лемме 49.14,

1, ¬ 2 ¬( 1 2).

Покажем, что это действительно так. Вывод:

1)1 (¬ 2 ¬( 1 2)) — лемма 49.11 пункт 6.

2)1 — посылка.

3)¬ 2 — посылка.

4)(¬ 2 ¬( 1 2)) — MP из 2 и 1.

5)¬( 1 2) — MP из 3 и 4.

Что и требовалось доказать.

117

Лекция 19. Полнота, независимость аксиом исчисления высказываний

Теорема 49.16 . (о полноте исчисления высказываний) Формула формальной теории есть тавтология тогда и только тогда, когда — теорема теории .

Доказательство. Достаточность следует из леммы 49.13.

Покажем необходимость. Пусть — тавтология. Пусть 1, 2, ..., — все пропозициональные буквы, которые входят в формулу , и пусть 1, 2, ..., — логические константы. По лемме 49.14

Построим вывод:

1)— посылка.

2)¬ — посылка.

3)( ) ((¬ ) ) — теорема 7 из леммы 49.11.

4)((¬ ) ) — MP из 1 и 3.

5)— MP из 2 и 4.

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

Определение 49.18 . Формальная теория с операцией ¬ непротиворечива, если в ней не существует такой формулы , что и ¬ .

Следствие 49.19 . Формальная теория непротиворечива.

118

Доказательство. Если , то — тавтология. Тогда ¬ не является тавтологией и по теореме 49.16: ̸ ¬.

§50. Независимость аксиом исчисления высказываний

Определение 50.1 . Пусть B — множество аксиом формальной теории . Тогда B — независимое множество аксиом, если существует такая формула, что не может быть выведена в без использования аксиом из B:

B ̸ .

Теорема 50.2 (о независимости схем аксиом теории ). Каждая из схем аксиом 1,2,3 теории независима.

Замечание 50.3 . Имеется в виду, что множество всех аксиом по схеме ( = 1, 2, или 3) независимо.

Доказательство. 1) Докажем независимость схемы 1:

( ( )).

Поскольку вывод формул в формальной теории происходит в соответствии с

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

следующим образом:

Можно показать непосредственной проверкой, что, при таком задании операций, значения всех аксиом по схемам 2 и 3 всегда будет 0.

119

Рассмотрим, как работает правило вывода modus ponens: если = 0 и = 0, то согласно нашему описанию операции будет верно и = 0. При этом аксиома 1 может принимать ненулевые значения:

( ( ))| =1, =2 = 1 (2 1) = 1 0 = 2.

Следовательно, пользуясь правилом вывода modus ponens из аксиом 2 и 3 нельзя получить любую аксиому схемы 1.

2) Доказательство независимости схемы аксиом 2 аналогично доказательству предыдущего пункта. Определим таблицы для операций ¬ и следующим образом:

Можно показать непосредственной проверкой, что значения аксиом 1 и 3, при таком определении, всегда 0, а также, что modus ponens сохраняет 0. В то же время

(( ( )) (( ) ( )))| = =0, =1 =

=((0 (0 1)) ((0 0) (0 1))) = ((0 2) (0 2)) =

=1 1 = 2.

Следовательно, пользуясь правилом вывода modus ponens из аксиом 1 и 3 нельзя получить любую аксиому схемы 2.

3) Докажем независимость схемы 3:

((¬ ¬ ) ((¬ ) )).

Рассмотрим оператор , сопоставляющий произвольной формуле формулу ( ), полученную удалением всех символов ¬. Тогда, для любой аксиомы по схеме 1 или 2, ( ) также будет аксиомой по схеме, соответственно, 1 или 2. Следовательно, по лемме 49.13, для любой аксиомы по схеме 1 или 2, ( ) — тавтология.

120