Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. V2: Предельные теоремы теории вероятностей
  2. Амплитудная селекция
  3. Беседа как метод обучения детей дошкольного возраста диалогической речи (лекция).
  4. Вводная лекция
  5. Вводная лекция
  6. ВЕРОЯТНОСТЬ СЛОЖНЫХ СОБЫТИЙ. ТЕОРЕМЫ СЛОЖЕНИЯ И УМНОЖЕНИЯ ВЕРОЯТНОСТЕЙ. УСЛОВНАЯ ВЕРОЯТНОСТЬ
  7. Вопрос 1.Лекция.
  8. Вопрос 6.Зависимые и независимые события. Условная вероятность. Теоремы умножения вероятностей.
  9. Воскресная лекция Шрилы Радханатхи Свами в Киеве о Бхакти Тиртхе Свами
  10. Временная селекция

Рассмотрим основные свойства выводимости, в которых 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

∨ Aim − 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 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.028 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав