Материал: Ответы на экзаменационные вопросы по математической логике
( )! (4)
5)Тогда из формул (3) и (4) по правилу . . выводится нужная формула:
!
4.Доказать, исходя из свойств выводов, аксиом ИВ и правила вывода ИВ
следующие свойства выводов ИВ
2) Если , то , .
. . , !
По свойству №3 («лишняя формула не мешает») и №2 («порядок формул не имеет значения») — добавляем в начало:
, , !
По свойству №4 («удаление выводимой формулы») — так как по условию выводима из , то её можно убрать как выводимую:
, !
3) Если и , то .
. . , !
По свойству №3 («лишняя формула не мешает») и №2 («порядок формул не имеет значения») — добавляем в начало:
, , !
По свойству №4 («удаление выводимой формулы») — так как по условию ивыводимы из , то их можно убрать как выводимые:
!
4) Если и — любая формула ИВ, то .
. . , ( ) ( )!
По свойству №3 («лишняя формула не мешает») и №2 («порядок формул не имеет значения») — добавляем в начало:
, , ( ) ( )! (1)
Так как ( ) — аксиома А1, то (аксиома следует из любых формул):
( )!
По свойству №3 («лишняя формула не мешает») — добавляем :
( )!
Из (1) по свойству №4 («удаление выводимой формулы») — так как по условиюи ( ), то их можно убрать как выводимые:
!
5. Теорема дедукции
Если из формул и выводится формула , то из формул выводится формула
(«если , , то »). (Дедукция — переход от общего к частному.) Метод математической индукции (индукция — это переход от частного к общему):
1.Проверяют истинность утверждения для = 1 ( = 0) — база индукции.
2.Предполагают, что утверждение верно для = — индуктивное предположение.
3.Доказывают, что тогда оно верно и для = + 1 — индуктивный переход.
Доказательство (методом математической индукции по числу — длине вывода). Пусть 1, … , есть вывод из и (то есть 1, … , ).
База индукции. Пусть = 1. Тогда совпадает с 1. Согласно определению вывода возможны 3 случая:
1) — аксиома |
2) — формула из |
3) совпадает с |
Если 1 — аксиома, то по свойству №3 («лишняя |
Значит совпадает с . |
|
формула не мешает») — добавляем , а если 1 — |
По свойству ИВ №1 ( |
|
формула из , то ничего не добавляем: в любом из |
!) и свойству №3 («лишняя |
|
этих двух случаев можно вывести . |
формула не мешает»): |
|
! ( 1!) |
! |
|
Тогда, по свойству ИВ №4: |
То есть получили |
|
если и — любая формула ИВ, то |
(где совпадает с ). |
|
|
|
|
Допустим теперь, что если длина вывода формулы меньше , то утверждение теоремы верно, и докажем, что тогда теорема верна для длины вывода, равного . При этом возможны 4 случая:
1) — аксиома |
|
2) — формула из |
|
3) совпадает с |
|||
Доказательство такое же, как при = 1 |
|||||||
|
|||||||
4) получена по правилу . . из , ( ), где , < |
|||||||
то есть , |
|
( имеет вид ) |
|||||
|
|
|
|
|
|
|
|
Отбрасывая последние − формулы из 1, … , , получаем вывод , . Отбрасывая последние − формулы из 1, … , , получаем вывод , . Длины этих выводов меньше и мы имеем:
, ! (1)
, ! ( , )! (2)
Индуктивное предположение (верно для и ):
! (1)
! ( ( ))! (2)
Далее следует индуктивный переход к .
По аксиоме А2:
( ( )) (( ) ( ))!
Имеем ( → , → , свойство №3: «лишняя формула не мешает» — добавляем ):
( ( )) (( ) ( ))! (3) . . к секвенциям (2) и (3):
( ) ( )! (4)
После этого, применяя все то же правило . . к секвенциям (1) и (4) получаем:
!
То есть !
Таким образом, индукция проведена, и теорема дедукции доказана.
6.Свойство транзитивности импликации. Доказать секвенцию: ( ),
Транзитивность импликации (правило силлогизма).
, ?
По свойству ИВ №2 («если , то , ») и свойству №2 («порядок формул не имеет значения»):
, , ?
По свойству №5 («если из формул выводится , а из набора формул , выводится формула , то из набора формул , выводится формула »):
{ |
|
, |
|
, |
|
Получаем («если из формул , выводится , а из формул , выводится формула , то из формул , , выводится формула »):
. . , |
, , ! |
{. . , |
По свойству №2 («порядок формул не имеет значения») и теореме дедукции («если
, , то »):
, !
Доказать секвенцию: ( ), .
( ), ?
По свойству ИВ №2 («если , то , »):
( ), , ?
По свойству №2 («порядок формул не имеет значения»):
( ), , ?
По теореме дедукции («если , , то »):
( ), ?
По теореме дедукции («если , , то »):
( ) ( )?
По свойству №1 (, или ):
( ) ( )!
По свойству ИВ №2 («если , то , »):
( ), !
По свойству ИВ №2 («если , то , »):
( ), , !
По свойству №2 («порядок формул не имеет значения»):
( ), , !
По теореме дедукции («если , , то »):
( ), !
7. Противоречивые формулы
Доказать:
1)Если и ¬ , то («из ложного следует всё, что угодно»).
Пусть — любая формула. Тогда из двух данных секвенций по свойству ИВ №4 («если и — любая формула ИВ, то ») следует, что ¬ и¬ ¬. По аксиоме А3 (заметим, что аксиома следует из любых формул):
(¬ ¬) ((¬ ) )!
По свойству №3 («лишняя формула не мешает») — добавляем :
(¬ ¬ ) ((¬ ) )!
Тогда применяя 2 раза свойство ИВ №2 («если , то , »), получим:
, (¬ ¬), (¬ ) !
По свойству №4 («удаление выводимой формулы») — так как ¬ ¬ и ¬ , то выводимые формулы (¬ ¬) и (¬ ) можно убрать:
!
2)Если , то , ¬ .
По условию:
!
По свойству №3 («лишняя формула не мешает») — добавляем ¬:
, ¬ !
Следующее утверждение также справедливо, так как по свойству №1 (¬ ¬) и по свойству №3 («лишняя формула не мешает») — добавляем :
, ¬ ¬ !
По уже доказанному выше утверждению («если и ¬, то ») — так как
, ¬ и , ¬ ¬, то получим: , ¬ !
8. Обоснование доказательства от противного: доказать, что если , ¬ , то
Доказательство «от противного» — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса.
Доказательство утверждения проводится следующим образом. Сначала принимают предположение, что утверждение неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение , которое заведомо неверно.
Из определения импликации следует, что, если ложно, то формула ¬ истинна тогда и только тогда, когда ¬ ложно, следовательно утверждение истинно.
Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение ¬¬ , которое по закону двойного отрицания равносильно утверждению .
Доказательство №1 (если , ¬ , то ).
Так как , ¬ , то есть из и ¬ выводима любая формула, то, в частности, выводима и формула : , ¬ . Значит, ¬ по теореме дедукции.
По свойству ИВ №1 ( ) из любых формул (в частности, из формул ) выводится ¬ ¬, а по свойству №3: «лишняя формула не мешает»: ¬ ¬.
Сдругой стороны, по аксиоме А3:
(¬ ¬ ) ((¬ ) )!
Имеем ( → , свойство №3: «лишняя формула не мешает» — добавляем ):
(¬ ¬ ) ((¬ ) )!
Применяя 2 раза свойство ИВ №2 («если , то , »), получим:
, (¬ ¬ ), (¬ ) !
По свойству №4 («удаление выводимой формулы») — так как ¬ и ¬ ¬, то, удаляя выводимые формулы ¬ и ¬ ¬, получим: !
Доказательство №2 (если , , то ¬).
В самом начале докажем, что если — любая формула, то , ¬ . По свойству №1 ( ):
!
По свойству №3 («лишняя формула не мешает») — добавляем ¬:
¬ , !
Следующее утверждение также справедливо, так как по свойству №1 (¬ ¬) и по свойству №3 («лишняя формула не мешает») — добавляем :
¬ , ¬ !
То есть ¬ , и ¬ , ¬ — по уже доказанному в 7-ом вопросе утверждению («если и ¬, то ») и свойству №2 («порядок формул не имеет значения»):
, ¬ !
Теперь перейдём к основному доказательству («если , , то ¬»).
Так как по доказанному выше («если — любая формула, то , ¬ ») и свойству №2 («порядок формул не имеет значения»), то имеем:
¬¬ , ¬ !
Так как по доказательству №1 («если , ¬ , то »), то:
¬¬ !
Кроме того, формулы и по условию противоречивы (, ). Тогда по свойству №3 («лишняя формула не мешает») — будут противоречивы 3 формулы:
, ¬¬ !
Как уже было написано, ¬¬ ! — значит по свойству №4 («удаление выводимой формулы») можно удалить выводимую формулу :
, ¬¬ !
Тогда по доказательству №1 («если , ¬ , то ») получаем ¬.