Математическая логика и теория алгоритмов. Сергиевская И.М. - 21 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

26
Запишем
A
¬ . Каждая формула из множества
Γ
и формула
A
¬ независимо
преобразуются во множество предложений. В этом множестве нужно найти
резольвируемые предложения и применить к ним правило резолюций. Резольвенты
добавляются во множество предложений до тех пор, пока не будет получено пустое
предложение. Возможны два случая:
•
Среди множества предложений нет резольвируемых. Вывод: теорема
опровергнута, и формула
A
не выводима из множества формул
Γ
.
•
Получено пустое предложение. Теорема доказана. Имеет место выводимость
Γ
├
A
.
Примеры. 1. Методом резолюций доказать теорему ├ )(
B
A
A
→→¬ .
Доказательство. Запишем инверсию исходной формулы:
()()
BAA →→¬¬ .
Заменим все импликации по соответствующей формуле:
()()
=→→¬¬ BAA
()()
BAA ∨¬∨¬¬
¬
.
Применим закон двойного отрицания и закон де Моргана:
()()
=→→¬¬ BAA
()()
(
)
=
∨
¬
¬
∧
¬
=
∨¬∨
¬
BAABAA
B
A
A
B
A
A
¬∧∧
¬
=¬∧¬¬∧¬= .
Получаем предложения:
A
¬ ,
A
,
B
¬
. Резольвируем их:
1.
A¬ – предложение.
2.
A – предложение.
3.
B
¬ – предложение.
4.
.
R
1, 2.
2. Методом резолюций доказать теорему
├
()
BABA ∧→→ .
Доказательство. Запишем инверсию исходной формулы:
()()
BABA ∧→→¬ .
Заменим все импликации по соответствующей формуле:
()()
=
∧→→¬ BABA
()()
BABA
∧
∨¬∨¬¬ .
Применим закон двойного отрицания и закон де Моргана:
()()
=
∧→→¬ BABA
(
)()
=
∧
∨¬¬∧¬¬ BABA
()
=∧¬∧∧= BABA
()
BABA
¬
∨¬∧∧ .
Получаем предложения:
A
,
B
,
B
A
¬
∨
¬
.
1.
A
– предложение.
2.
B
– предложение.
3.
B
A
¬∨¬ – предложение.
4.
B
¬
.
R
1, 3.
5.
.
R
2, 4.
В
Содержание. 
      Запишем ¬A . Каждая формула из множества Γ и формула ¬A независимо
преобразуются во множество предложений. В этом множестве нужно найти
резольвируемые предложения и применить к ним правило резолюций. Резольвенты
добавляются во множество предложений до тех пор, пока не будет получено пустое
предложение. Возможны два случая:
• Среди множества предложений нет резольвируемых. Вывод: теорема
   опровергнута, и формула A не выводима из множества формул Γ .
• Получено пустое предложение. Теорема доказана. Имеет место выводимость
   Γ ├ A.

     Примеры. 1. Методом резолюций доказать теорему ├ ¬A → ( A → B) .
     Доказательство. Запишем инверсию исходной формулы:
¬(¬A → ( A → B )) .
     Заменим все импликации по соответствующей формуле:
¬(¬A → ( A → B )) = ¬(¬¬A ∨ (¬A ∨ B )).
     Применим закон двойного отрицания и закон де Моргана:
¬(¬A → ( A → B )) = ¬( A ∨ (¬A ∨ B )) = ¬A ∧ ¬(¬A ∨ B ) =
= ¬A ∧ ¬¬A ∧ ¬B = ¬A ∧ A ∧ ¬B .
     Получаем предложения: ¬A , A , ¬B . Резольвируем их:
1. ¬A – предложение.
2. A – предложение.
3. ¬B – предложение.
4. .           R 1, 2.

      2. Методом резолюций доказать теорему
├ A → (B → A ∧ B ) .
      Доказательство. Запишем инверсию исходной формулы:
¬( A → (B → A ∧ B )) .
      Заменим все импликации по соответствующей формуле:
¬( A → (B → A ∧ B )) = ¬(¬A ∨ (¬B ∨ A ∧ B )) .
      Применим закон двойного отрицания и закон де Моргана:
¬( A → (B → A ∧ B )) = ¬¬A ∧ ¬(¬B ∨ ( A ∧ B )) =
= A ∧ B ∧ ¬( A ∧ B ) = A ∧ B ∧ (¬A ∨ ¬B ) .
      Получаем предложения: A , B , ¬A ∨ ¬B .
1. A – предложение.
2. B – предложение.
3. ¬A ∨ ¬B – предложение.
4. ¬B .             R 1, 3.
5. .                R 2, 4.

В Содержание.




                                      26

Страницы