Просолупов Е.В. Конспект курса: Основы дискретной математики
Подождите немного. Документ загружается.
Замечание 2.2.3 . В алфавите формальной теории L нет символов
∨, ∧, ≡. Тем не менее, мы можем использовать эти символы, как
краткую форму записи в некоторых сложных выражениях:
(A ∨ B) = (¬A ⊃ B),
(A ∧ B) = (¬(A ⊃ ¬B)),
(A ≡ B) = ((A ⊃ B) ∧ (B ⊃ A)) = (¬((A ⊃ B) ⊃ ¬(B ⊃ A))).
Для простоты иногда будем опускать внешние скобки в записи
формул: вместо (A ⊃ B) — писать A ⊃ B.
Далее в этой главе мы будем говорить только о формальной теории
исчисление высказываний; для простоты, вместо `
L
A будем писать ` A.
Лемма 2.2.1 . Пусть, A — формула. Тогда ` (A ⊃ A).
Доказательство. Построим вывод для формулы (A ⊃ A):
1. ((A ⊃ ((A ⊃ A) ⊃ A)) ⊃ ((A ⊃ (A ⊃ A)) ⊃ (A ⊃ A))) — аксиома 2
после подстановки вместо A формулы A, вместо B — (A ⊃ A) и вместо
C — A.
2. (A ⊃ ((A ⊃ A) ⊃ A)) — аксиома 1 после подстановки A ← A,
B ← (A ⊃ A).
3. ((A ⊃ (A ⊃ A)) ⊃ (A ⊃ A)) — применение правила вывода MP к
строкам 2 и 1.
4. (A ⊃ (A ⊃ A)) — аксиома 1 после подстановки A ← A, B ← A.
5. (A ⊃ A) — MP к строкам 3 и 4.
¤
Замечание 2.2.4 . Формулы, для которых мы доказали, что они
являются теоремами данной формальной теории, в дальнейшем можно
использовать в выводах наравне с аксиомами. Действительно, раз для
такой формулы существует вывод, мы всегда можем привести его
как составную часть других выводов, но не будем этого делать для
краткости.
Пример 2.2.2 . Рассмотрим формализацию следующего рассуждения.
"Если Вася баскетболист,то Вася высокий. Вася баскетболист.
Следовательно Вася высокий."
131
Обозначим через A высказывание "Вася баскетболист" и через B —
"Вася высокий". Тогда наше рассуждение будет имеь вид:
A ⊃ B, A
B
.
Чтобы убедиться, что оно верно, проверим, является ли формула
(A ⊃ B) A ⊃ B тавтологией.
(A ⊃ B)A ⊃ B = (A ∨ B)A ∨ B = A ∨ B ∨ A ∨ B = AB ∨ A ∨ B =
= (A ∨ A)(B ∨ A) ∨ B = B ∨ A ∨ B = 1.
Теперь рассмотрим это рассуждение с точки зрения теории L.
1) A — посылка.
2) A ⊃ B — посылка.
3) B — MP к 1 и 2.
Следовательно, A, A ⊃ B ` B.
Согласно определению 2.2.2, если формула B получина по правилу
вывода MP из предыдущих, формула B является их логическим
следствием.
2.2.4 Теоремы исчисления высказываний
Теорема 2.2.2 (Теорема о дедукции). Пусть A и B — формулы, Γ
— некоторое множество формул теории L. Тогда из Γ, A ` B следует,
что Γ ` (A ⊃ B).
Доказательство. Пусть B
1
, B
2
, ..., B
n
= B — вывод B из множества
посылок Γ ∪ {A}. Докажем по индукции, что Γ ` A ⊃ B
i
, i = 1, 2, ..., n.
1) Пусть i = 1. B
1
— аксиома, или B
1
∈ Γ, или B
1
= A.
a) Пусть B
1
— аксиома.
1. B
1
— аксиома.
2. B
1
⊃ (A ⊃ B
1
) — аксиома 1.
3. A ⊃ B
1
— MP из 1 и 2.
Следовательно ` A ⊃ B
1
⇒ Γ ` A ⊃ B
1
.
b) Пусть B
1
∈ Γ.
1. B
1
— посылка.
132
2. B
1
⊃ (A ⊃ B
1
) — аксиома 1.
3. A ⊃ B
1
— MP из 1 и 2.
Следовательно B
1
` A ⊃ B
1
⇒ Γ ` A ⊃ B
1
.
c) Пусть B
1
= A. По лемме 2.2.1 ` A ⊃ A = A ⊃ B
1
⇒ Γ ` A ⊃ B
1
.
2) Пусть для всех l < k верно, что Γ ` A ⊃ B
l
. Докажем, что
Γ ` A ⊃ B
k
. B
k
— аксиома, или B
k
∈ Γ, или B
k
= A, или B
k
получена
по правилу вывода modus ponens. Первые три случая доказываются
аналогично соответствующим пунктам базы индукции.
d) B
k
— результат применения MP к формулам B
i
и B
j
, i, j < k. Тогда,
Γ ` A ⊃ B
i
, Γ ` A ⊃ B
j
и B
j
= B
i
⊃ B
k
. Построим вывод:
1. (A ⊃ (B
i
⊃ B
k
)) ⊃ ((A ⊃ B
i
) ⊃ (A ⊃ B
k
)) — аксиома 2 (A ← A,
B ← B
i
, C ← B
k
).
2. (A ⊃ (B
i
⊃ B
k
)) — посылка.
3. ((A ⊃ B
i
) ⊃ (A ⊃ B
k
)) — MP из 2 и 1.
4. (A ⊃ B
i
) — посылка.
5. (A ⊃ B
k
) — MP из 4 и 3.
Таким образом, (A ⊃ (B
i
⊃ B
k
)), (A ⊃ B
i
) ` (A ⊃ B
k
). Следовательно,
Γ ` (A ⊃ B
k
). Следовательно, Γ ` (A ⊃ B ).
¤
Пример 2.2.3 . С помощью теоремы о дедукции мы могли бы гораздо
проще доказать лемму 2.2.1:
1) A — посылка.
2) A ⊃ A — по теореме о дедукции, поскольку A ` A.
Следствие 2.2.3 . Пусть, A, B и C — некоторые формулы теории L.
Тогда A ⊃ B, B ⊃ C ` A ⊃ C
Доказательство.
1) A — посылка.
2) A ⊃ B — посылка.
3) B — MP из 1 и 2.
4) B ⊃ C — посылка.
5) C — MP из 3 и 4.
Таким образом, A, A ⊃ B, B ⊃ C ` C. Следовательно, по теореме о
дедукции A ⊃ B, B ⊃ C ` A ⊃ C.
133
¤
Следствие 2.2.4 . Пусть, A, B и C — некоторые формулы теории L.
Тогда A ⊃ (B ⊃ C), B ` A ⊃ C.
Доказательство.
1) A — посылка.
2) A ⊃ (B ⊃ C) — посылка.
3) B ⊃ C — MP из 1 и 2.
4) B — посылка.
5) C — MP к 4 и 3.
A, A ⊃ (B ⊃ C), B ` C. Следовательно, по теореме о дедукции
A ⊃ (B ⊃ C), B ` A ⊃ C.
¤
Лемма 2.2.5 (Список теорем). Пусть A и B — произвольные
формулы теории L. Тогда следующие формулы являются теоремами
L:
1. ¬¬B ⊃ B — закон отрицания отрицания.
2. B ⊃ ¬¬B — закон отрицания отрицания.
3. ¬A ⊃ (A ⊃ B) — из ложных посылок можно вывести что угодно.
4. (¬B ⊃ ¬A) ⊃ (A ⊃ B) — доказательство от противного.
5. (A ⊃ B) ⊃ (¬B ⊃ ¬A) — доказательство от противного.
6. A ⊃ (¬B ⊃ ¬(A ⊃ B)) — из истинных посылок нельзя вывести
ложное заключение.
7. (A ⊃ B) ⊃ ((¬A ⊃ B) ⊃ B) — если B выводима и из A и из его
отрицания, то B истинна независимо от посылок.
Доказательство. Докажем, например, для формул 1 и 3.
1.
1) (¬B ⊃ ¬¬B) ⊃ ((¬B ⊃ ¬B) ⊃ B) — аксиома 3.
2) ¬¬B — посылка.
3) ¬¬B ⊃ (¬B ⊃ ¬¬B) — аксиома 1.
4) ¬B ⊃ ¬¬B — MP из 2 и 3.
5) (¬B ⊃ ¬B) ⊃ B — MP из 4 и 1.
6) ¬B ⊃ ¬B — лемма 2.2.1.
134
7) B — MP из 6 и 5.
Таким образом ¬¬B ` B и по теореме о дедукции ` ¬¬B ⊃ B.
3.
1) A ⊃ (¬B ⊃ A) — аксиома 1.
2) ¬A ⊃ (¬B ⊃ ¬A) — аксиома 1.
3) A — посылка.
4) ¬B ⊃ A — MP из 3 и 1.
5) ¬A — посылка.
6) ¬B ⊃ ¬A — MP из 5 и 2.
7) (¬B ⊃ ¬A) ⊃ ((¬B ⊃ A) ⊃ B) — аксиома 3.
8) ((¬B ⊃ A) ⊃ B) — MP из 6 и 7.
9) B — MP из 4 и 8.
Таким образом A, ¬A ` B. Тогда по теореме о дедукции, ¬A ` A ⊃ B
и ` ¬A ⊃ (A ⊃ B).
Остальные пункты утверждения предлагаются читателю для
самостоятельного доказательства.
¤
2.2.5 Теорема о полноте исчисления высказываний
Лемма 2.2.6 . Аксиомы теории L являются тавтологиями.
Доказательство. 1)
(A ⊃ (B ⊃ A)) = A ∨ B ∨ A = 1.
2)
((A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C))) =
= A ∨ B ∨ C ∨ A ∨ B ∨ A ∨ C = ABC ∨ AB ∨ A ∨ C =
= (AB ∨ C)(C ∨ C) ∨ (A ∨ A)(B ∨ A) = AB ∨ C ∨ B ∨ A =
= (A ∨ A)(B ∨ A) ∨ C ∨ B = B ∨ A ∨ C ∨ B = 1
3)
((¬B ⊃ ¬A) ⊃ ((¬B ⊃ A) ⊃ B) = B ∨ A ∨ B ∨ A ∨ B =
= BA ∨ B A ∨ B = B(A ∨ A) ∨ B = B ∨ B = 1.
135
¤
Лемма 2.2.7 . Любая теорема теории L является тавтологией.
Доказательство. Пусть для формулы A теории L существует вывод A
1
,
A
2
, ..., A
n
= A. Докажем по индукции, что A
i
— тавтология, i = 1, n . По
определению вывода, A
1
является аксиомой и по лемме 2.2.6 она является
тавтологией.
Пусть формулы A
i
— тавтология, ∀i = 1, k. Рассмотрим A
k+1
:
она является аксиомой, или получена по правилу вывода modus po-
nens из предыдущих формул. Если A
k+1
— аксиома, то она является
тавтологией по лемме 2.2.6. Пусть A
k+1
получена по правилу modus
ponens из формул A
i
и A
j
= A
i
⊃ A
k+1
, i, j ≤ k. По индукционному
предположению, A
i
и A
j
— тавтологии. Пусть, на некотором наборе
значений пропозициональных букв формула A
k+1
принимает значение 0.
Тогда на этом наборе
A
j
= A
i
⊃ A
k+1
= 1 ⊃ 0 = 0. ?!
Противоречие. Следовательно A
k+1
— тавтология. Следовательно A —
тавтология.
¤
Пусть A — формула, в которую входят пропозициональные буквы B
1
,
B
2
, ..., B
k
. Когда нам будет необходимо подчеркнуть, от каких значений
рассматривается A, будем писать A(α
1
, α
2
, ..., α
k
), имея в виду, что вместо
пропозициональной буквы B
i
подставляется значение α
i
, i = 1, k.
Как и раньше, будем использовать знак степени для обозначения
наличия или отсутствия отрицания:
B
σ
=
½
B, σ = 1,
¬B, σ = 0.
Лемма 2.2.8 . Пусть B
1
, B
2
, ..., B
k
— все пропозициональные буквы,
которые входят в формулу A, и пусть σ
1
, σ
2
, ..., σ
k
— логические
константы. Тогда
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k
k
` A
A(σ
1
,σ
2
,...,σ
k
)
.
136
Доказательство. Докажем по индукции по числу j логических связок
в формуле A.
1) Пусть j = 0. Тогда A = B
1
, A(σ
1
) = σ
1
, A
A(σ
1
)
= B
σ
1
1
.
B
σ
1
` B
σ
1
= A
A(σ
1
)
.
2) Пусть утверждение верно для любого j < n. Докажем для случая
n логических связок в A. Формула A, в зависимости от своей последней
логической связки, может быть одного из двух видов: A = ¬A
1
или
A = (A
1
⊃ A
2
).
a) Пусть A = ¬A
1
. Рассмотрим два варианта
Пусть A
1
(σ
1
, ..., σ
k
) = 0. По индукционному предположению
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k
k
` ¬A
1
. ¬A
1
= A = A
¬A
1
(σ
1
,...,σ
k
)
= A
A(σ
1
,...,σ
k
)
. Следова-
тельно,
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k
k
` A
A(σ
1
,σ
2
,...,σ
k
)
.
Пусть A
1
(σ
1
, ..., σ
k
) = 1.
A
A(σ
1
,...,σ
k
)
= A
¬A
1
(σ
1
,...,σ
k
)
= ¬A = ¬¬A
1
.
По индукционному предположению B
σ
1
1
, B
σ
2
2
, ..., B
σ
k
k
` A
1
. Построим
вывод:
1. A
1
⊃ ¬¬A
1
— пункт 2 из леммы 2.2.5.
2. A
1
— посылка.
3. ¬¬A
1
— MP из 2 и 1.
Таким образом, A
1
` ¬¬A и
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k
k
` ¬¬A
1
= A
A(σ
1
,σ
2
,...,σ
k
)
.
b) Пусть A = (A
1
⊃ A
2
). Рассмотрим несколько вариантов.
Пусть A
1
(σ
1
, ..., σ
k
) = 0, A
2
(σ
1
, ..., σ
k
) = 0. Тогда
B
σ
1
1
, ..., B
σ
k
k
` ¬A
1
, B
σ
1
1
, ..., B
σ
k
k
` ¬A
2
.
A
A(σ
1
,...,σ
k
)
= A
0⊃0
= A = (A
1
⊃ A
2
).
Рассмотрим вывод:
1. ¬A
1
— посылка.
137
2. ¬A
1
⊃ (A
1
⊃ A
2
) — пункт 3 из леммы 2.2.5.
3. (A
1
⊃ A
2
) — MP из 1 и 2.
Таким образом, ¬A
1
` (A
1
⊃ A
2
) = A
A(σ
1
,...,σ
k
)
⇒
B
σ
1
1
, ..., B
σ
k
k
` A
A(σ
1
,...,σ
k
)
.
Пусть A
1
(σ
1
, ..., σ
k
) = 0, A
2
(σ
1
, ..., σ
k
) = 1. Тогда
B
σ
1
1
, ..., B
σ
k
k
` ¬A
1
, B
σ
1
1
, ..., B
σ
k
k
` A
2
.
A
A(σ
1
,...,σ
k
)
= A
0⊃1
= A = (A
1
⊃ A
2
).
Рассмотрим вывод:
1. ¬A
1
— посылка.
2. ¬A
1
⊃ (A
1
⊃ A
2
) — пункт 3 из леммы 2.2.5.
3. (A
1
⊃ A
2
) — MP из 1 и 2.
Таким образом, ¬A
1
` (A
1
⊃ A
2
) = A
A(σ
1
,...,σ
k
)
⇒
B
σ
1
1
, ..., B
σ
k
k
` A
A(σ
1
,...,σ
k
)
.
Пусть A
1
(σ
1
, ..., σ
k
) = 1, A
2
(σ
1
, ..., σ
k
) = 0. Тогда
B
σ
1
1
, ..., B
σ
k
k
` A
1
, B
σ
1
1
, ..., B
σ
k
k
` ¬A
2
.
A
A(σ
1
,...,σ
k
)
= A
1⊃0
= A
0
= ¬(A
1
⊃ A
2
).
Рассмотрим вывод:
1. A
1
— посылка.
2. ¬A
2
— посылка.
3. A
1
⊃ (¬A
2
⊃ ¬(A
1
⊃ A
2
)) — пункт 6 из леммы 2.2.5.
4. ¬A
2
⊃ ¬(A
1
⊃ A
2
) — MP из 1 и 3.
5. ¬(A
1
⊃ A
2
) — MP из 2 и 4.
Таким образом, A
1
, ¬A
2
` ¬(A
1
⊃ A
2
) = A
A(σ
1
,...,σ
k
)
⇒
B
σ
1
1
, ..., B
σ
k
k
` A
A(σ
1
,...,σ
k
)
.
Пусть A
1
(σ
1
, ..., σ
k
) = 1, A
2
(σ
1
, ..., σ
k
) = 1. Тогда
B
σ
1
1
, ..., B
σ
k
k
` A
1
, B
σ
1
1
, ..., B
σ
k
k
` A
2
.
A
A(σ
1
,...,σ
k
)
= A
1⊃1
= A = (A
1
⊃ A
2
).
138
Рассмотрим вывод:
1. A
2
— посылка.
2. A
2
⊃ (A
1
⊃ A
2
) — аксиома 1.
3. (A
1
⊃ A
2
) — MP из 1 и 2.
Таким образом, A
2
` (A
1
⊃ A
2
) = A
A(σ
1
,...,σ
k
)
⇒
B
σ
1
1
, ..., B
σ
k
k
` A
A(σ
1
,...,σ
k
)
.
Утверждение доказано.
¤
Пример 2.2.4 . Пусть, A = B
1
⊃ B
2
. Если σ
1
= 1, σ
2
= 0, то
A(σ
1
, σ
2
) = 0. Следовательно, по лемме 2.2.8,
B
1
, ¬B
2
` ¬(B
1
⊃ B
2
).
Покажем, что это действительно так. Вывод:
1) B
1
⊃ (¬B
2
⊃ ¬(B
1
⊃ B
2
)) — лемма 2.2.5 пункт 6.
2) B
1
— посылка.
3) ¬B
2
— посылка.
4) (¬B
2
⊃ ¬(B
1
⊃ B
2
)) — MP из 2 и 1.
5) ¬(B
1
⊃ B
2
) — MP из 3 и 4.
Что и требовалось доказать.
Теорема 2.2.9 (о полноте исчисления высказываний). Формула
A формальной теории L есть тавтология тогда и только тогда, когда
A — теорема теории L.
Доказательство. Достаточность следует из леммы 2.2.7.
Покажем необходимость. Пусть A — тавтология. Пусть B
1
, B
2
, ..., B
k
— все пропозициональные буквы, которые входят в формулу A, и пусть
σ
1
, σ
2
, ..., σ
k
— логические константы. По лемме 2.2.8
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−1
k−1
, B
σ
k
k
` A
A(σ
1
,σ
2
,...,σ
k
)
.
Поскольку A — тавтология, A
A(σ
1
,σ
2
,...,σ
k
)
= A для любых наборов σ
i
.
Тогда,
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−1
k−1
, B
k
` A,
139
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−1
k−1
, ¬B
k
` A.
По теореме о дедукции,
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−1
k−1
` B
k
⊃ A,
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−1
k−1
` ¬B
k
⊃ A.
Построим вывод:
1) B
k
⊃ A — посылка.
2) ¬B
k
⊃ A — посылка.
3) (B
k
⊃ A) ⊃ ((¬B
k
⊃ A) ⊃ A) — теорема 7 из леммы 2.2.5.
4) ((¬B
k
⊃ A) ⊃ A) — MP из 1 и 3.
5) A — MP из 2 и 4.
Следовательно,
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−1
k−1
` A.
Таким образом, мы избавились от B
k
в списке посылок для вы-
вода формулы A. Повторяя процесс, мы можем показать, что
B
σ
1
1
, B
σ
2
2
, ..., B
σ
k−2
k−2
` A и так далее, пока не получим, что ` A.
¤
Замечание 2.2.5 . Формальная теория L является разрешимой,
поскольку для любой формулы мы можем проверить, является ли она
тавтологией и, следовательно, теоремой L.
Определение 2.2.11 . Формальная теория T с операцией ¬
непротиворечива, если в ней не существует такой формулы A, что
`
T
A и `
T
¬A.
Следствие 2.2.10 . Формальная теория L непротиворечива.
Доказательство. Если ` A, то A — тавтология. Тогда ¬A не является
тавтологией и по теореме 2.2.9: 6` ¬A.
¤
2.2.6 Независимость аксиом исчисления высказываний
Определение 2.2.12 . Пусть B — множество аксиом формальной
теории T . Тогда X ⊆ B — независимое множество аксиом, если
140