B, A (A Ù B) дедукция

11 · Г, B, A (A Ù B) расширение посылок

12 · Г, А, В C силлогизм(3, 11)

13 · Г, А (В ® C) дедукция

14 · Г (А ® (В ® C)) дедукция

Правила удаления конъюнкции: .

1 · Г (A Ù B) дано

2 · (A Ù B) ® A (К1)

3 · Г A МР(1, 2)

 

Второе правило докажите самостоятельно.

Правила введения конъюнкции: .

1 · Г A дано

2 · Г В дано

3 · Г, А В расширение посылок

4 · Г (A ® В) дедукция

5 · ((А ® A) ® ((A ® B) ® (A ® (A Ù B))))(К3)(А := А, В := А, С := В)

6 · (A ® A) доказуема

7 · ((A ® B) ® (A ® (A Ù B))) МР(5, 6)

8 · Г (A ® (A Ù B)) МР(4, 7)

9 · Г (A Ù B) МР(1, 8)

Правила введения дизъюнкции:.

1 · Г A дано

2 · (A ® (A Ú B)) (Д3)

3 · Г (A Ú В) МР(1, 2)

Второе правило докажите самостоятельно.

Правило modus tollens: .

1 · Г, А В дано

2 · Г (А ® В) дедукция

3 · Г дано

4 · ((A ® B) ® (® )) (О3)

5 · Г (® ) МР(2, 4)

6 · Г МР(3, 5)

Правило контрапозиции: .

1 · Г, А В дано

2 · Г (А ® В) дедукция

3 · ((A ® B) ® (®)) аксиома (О3)

4 · Г (® ) МР(2, 3)

5 · Г, дедукция

Правило опровержения: .

1 · Г, А В дано

2 · Г, А, А Врасширение посылок

3 · Г, А дано

4 · Г, А modus tollens(2, 3)

5 · Г, А А 2⁰

6 ·Г, А (А Ù )введениеÙ

7 · (А Ù ) А (К1)

8 · (А Ù ), Арасширение посылок

9 · (А Ù ) (К2)

10 · (А Ù ) modus tollens(8, 9)

11 · ® (О2)

12 · (А Ù ) силлогизм(10,11)

13 · контрапозиция(10)

14 · (A ® A) ® (О1)

15 · (A ® A) дедукция

16 · (A ® A) силлогизм(13, 15)

17 · (A ® A) ® дедукция

18 · (A ® A) доказуема

19 · МР(17, 18)

20 · Г расширение посылок

21 · Г modus tollens(6, 20)

4. Основные равносильности ИВ.Две формулы А и В исчисления высказываний назовём равносильными и будем писать А ~ В, если доказуемы обе формулы А ® B и B ® A. Это понятие, конечно, аналогично понятию равно­сильности º формул, изученному в главе I, и как будет показано далее, на самом деле совпадает с ним.

Докажем формально самые важные из знакомых основных равносильностей.