Читайте также:
|
|
Рассмотрим основные свойства выводимости, в которых 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) по правилу коммутативности.
Свойство доказано.
По существу мы установили
СВОЙСТВО 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 = A 1 ∨ A 2 · · · ∨ An, у кото-
рой выводим один из ее членов Ai, где i = 1, 2 ,..., n. Тогда выводима
формула A.
Доказательство. Если i = n, то применим несколько раз правило рас-
ширения. Получим
_ An− 1 ∨ An, _ An− 2 ∨ An− 1 ∨ An,..., _ A 1 ∨ A 2 ∨... ∨ An,
т.е. _ A. Если i _ = n, то рассмотрим C = Ai +1 ∨... ∨ An. Как и выше
получаем
_ Ai ∨ C, _ Ai ∨ Ai +1 ∨ C,..., _ A 1 ∨ A 2 ∨... ∨ An,
т.е. _ A. Свойство доказано.
СВОЙСТВО 6 Пусть дана формула A = A 1 ∨ A 2 ,..., ∨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 = A 2 ∨ A 3 ,..., ∨An содержит члены Ai, Aj,
причем _ Ai ∨ Aj. Тогда по индукции _ B и по правилу расширения _ A.
Пусть i = 1. Тогда _ A 1 ∨ Aj. Если при этом j = 2, то _ A 1 ∨ A 2.
Обозначим C = A 3 ,..., ∨An. По правилу расширения _ (A 1 ∨ A 2) ∨ C.
По правилу ассоциативности _ A = A 1 ∨ (A 2 ∨ C), что и нужно.
Пусть j > 2. По индукции получаем _ A 1 ∨ C для C = A 3 ∨ · · · ∨ An.
Тогда
1. _ C ∨ A 1 (по коммутативности),
2. _ (C ∨ A 1) ∨ A 2 (по правилам расширения и коммутативности),
3. _ C ∨ (A 1 ∨ A 2) (по ассоциативности),
4. _ (A 1 ∨ A 2) ∨ C (по коммутативности),
5. _ A 1 ∨ (A 2 ∨ C) (по свойству 3),
т.е. _ A.
Свойство доказано.
СВОЙСТВО 7 Пусть дана формула A = A 1 ∨ A 2 ∨ · · ·∨ An, причем
для некоторых ее членов Ai 1, Ai 2 ,..., Aim выводима формула
Ai 1
∨ Ai 2
∨ · · · ∨ Aim. (18)
Тогда выводима даннаяформула A.
Доказательство проводим индукцией по числу m. Пусть A — контрпри-
мер с наименьшим m. По свойствам 5 и 6 имеем m > 2.
Нам дана выводимая формула Ai 1
∨ Ai 2
∨ · · · ∨ Aim, т.е. формула
Ai 1
∨ (Ai 2
∨ · · · ∨ (Aim− 1
∨ Aim)), по соглашению о правосторонней рас-
становке скобок. Рассмотрим другую формулу
(Ai 1
∨ Ai 2) ∨ Ai 3
∨ · · · ∨ Aim. (19)
Она выводима по правилу ассоциативности и с учетом выводимости фор-
мулы (18). Она содержит m − 1 членов следующего вида:
один член Ai 1
∨ Ai 2и m − 2 членов Ai 3 ,..., Aim. (20)
По индукции, если выводима формула, составленная из этих m− 1 чле-
нов, то выводима формула F, содержащая эти члены. Рассмотрим в ка-
честве F формулу
(Ai 1
∨ Ai 2) ∨ A. (21)
Формула (19) составлена из из ее m − 1 членов формулы (21) и выво-
дима. Поэтому по индукции выводима формула (21). Тогда
1. _ (Ai 2
∨ A) ∨ Ai 1 (по ассоциативности),
2. _ (Ai 2
∨ A) ∨ A (по предыдущему свойству),
3. _ Ai 2
∨ (A ∨ A) (по ассоциативности),
4. _ (A ∨ A) ∨ Ai 2(по коммутативности),
5. _ (A ∨ A) ∨ (A ∨ A) (по предыдущему свойству),
6. _ A ∨ A (по правилу сокращения),
7. _ A (по правилу сокращения).
Свойство доказано.
Замечание. Из данного свойства следует, что перестановка членов в
формуле A = A 1 ∨A 2 ∨· · ·∨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.
По правилу сечения
A ∨
_
C ∨ ¬ (A ∨ B)
_
, ¬A ∨ C _
C ∨¬ (A ∨ B)
_
∨ C
получаем _
_
C ∨ ¬ (A ∨ B)
_
∨ C. Из членов этой выводимой формулы
составлена формула ¬ (A ∨ B) ∨ C. По свойству 6 она сама выводима.
Свойство доказано.
Лекция 6. Совпадение классов выводимых и тожде-
Дата добавления: 2015-01-12; просмотров: 28 | Поможем написать вашу работу | Нарушение авторских прав |