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

UptoLike

ВУЗ: 

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

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

Рубрика: 

21
Таким образом, нам нужно доказать, что из формул
A
B
¬→
¬
и
A
выводима
формула
B
. Составим вывод формулы
B
. В каждой строке вывода записывается
только одна формула. В правой части страницы удобно указывать комментарий, –
что собой эта формула представляет. Возможны варианты:
• гипотеза,
• аксиома (может быть, с какими-то подстановками),
• ранее доказанная теорема,
• формула получена из предыдущих формул по правилу Modus ponens.
Вначале мы запишем гипотезы.
1.
A
B
¬→¬ – гипотеза.
2.
A
– гипотеза.
Формулу
B
удобно получить из аксиомы А3. Поэтому запишем эту аксиому:
3.
()()()
BABAB →→¬→¬→¬ А3.
К формулам 1 и 3 можно применить правило вывода Modus ponens (что мы и
отметим в комментарии). Порядок номеров формул существенен (первой
указывается посылка).
4.
()
BAB →→¬ . МР 1, 3.
Посылку в формуле 4 можно получить из аксиомы А1, если заменить
B
на
B
¬ :
5.
()
ABA →¬→ . А1 с подстановкой вместо
B
–
B
¬
.
Далее дважды применяем правило Modus ponens:
6.
A
B
→¬ . МР 2, 5.
7.
B
. МР 6, 4.
Вывод построен, и применением теоремы дедукции мы доказали выводимость
первоначальной формулы.
Отметим, что вывод может быть неединственным, в частности, формулы
могут быть записаны в другом порядке. Решение данной задачи может быть
оформлено следующим образом:
├
()()
BAAB →→¬→¬ .
По теореме, обратной теореме дедукции,
A
B
¬→¬ ├
B
A
→ .
A
B
¬→¬ ,
A
├
B
.
1.
A
B
¬→¬ – гипотеза.
2.
A
– гипотеза.
3.
()
ABA →¬→ . А1,
B
:
B
¬
.
4.
A
B
→¬ . МР 2, 3.
5.
()()()
BABAB →→¬→¬→¬ . А3.
6.
()
BAB →→¬ . МР 1, 5.
7.
B
. МР 4, 6.
Пример. Данный пример более прост, но достаточно показателен. Обратите
внимание, что здесь не используются ни аксиомы, ни теоремы. Доказательство
теоремы ├
()()
(
)()
BCACBA →→→→→ строится только на основании правила
МР. 
       Таким образом, нам нужно доказать, что из формул ¬B → ¬A и A выводима
формула B . Составим вывод формулы B . В каждой строке вывода записывается
только одна формула. В правой части страницы удобно указывать комментарий, –
что собой эта формула представляет. Возможны варианты:
• гипотеза,
• аксиома (может быть, с какими-то подстановками),
• ранее доказанная теорема,
• формула получена из предыдущих формул по правилу Modus ponens.
       Вначале мы запишем гипотезы.
1. ¬B → ¬A – гипотеза.
2. A – гипотеза.
       Формулу B удобно получить из аксиомы А3. Поэтому запишем эту аксиому:
3. (¬B → ¬A) → ((¬B → A) → B )                            А3.
       К формулам 1 и 3 можно применить правило вывода Modus ponens (что мы и
отметим в комментарии). Порядок номеров формул существенен (первой
указывается посылка).
4. (¬B → A) → B .                                     МР 1, 3.
       Посылку в формуле 4 можно получить из аксиомы А1, если заменить B на
¬B :
5. A → (¬B → A).           А1 с подстановкой вместо B – ¬B .
       Далее дважды применяем правило Modus ponens:
6. ¬B → A .                                          МР 2, 5.
7. B .                                               МР 6, 4.
       Вывод построен, и применением теоремы дедукции мы доказали выводимость
первоначальной формулы.
       Отметим, что вывод может быть неединственным, в частности, формулы
могут быть записаны в другом порядке. Решение данной задачи может быть
оформлено следующим образом:
├ (¬B → ¬A) → ( A → B ) .
   По теореме, обратной теореме дедукции,
¬B → ¬A ├ A → B .
 ¬B → ¬A , A ├ B .
1. ¬B → ¬A – гипотеза.
2. A – гипотеза.
3. A → (¬B → A).                                 А1, B : ¬B .
4. ¬B → A .                                          МР 2, 3.
5. (¬B → ¬A) → ((¬B → A) → B ) .                      А3.
6. (¬B → A) → B .                                    МР 1, 5.
7. B .                                               МР 4, 6.

     Пример. Данный пример более прост, но достаточно показателен. Обратите
внимание, что здесь не используются ни аксиомы, ни теоремы. Доказательство
теоремы ├ ( A → B ) → ((C → A) → (C → B )) строится только на основании правила
МР.


                                      21

Страницы