2.2. Теорема дедукції

Теорема дедукції дає нове правило виведення у логіці висловлювань, і тому вона є важливою під час доведення теорем і різних висловлювань.

Теорема дедукції 2.2.1. Якщо Г – множина формул, А і В – формули і Г, ├ В, то ├ . Зокрема, якщо ├ В, то ├ .

Доведення. Нехай В₁, В₂,…, В_n – виведення із формули В, тобто В_n = В. Доведення будемо проводити індукцією по і – довжині виведення формули В.

При і = 1 В₁ повинне бути або: а) елементом Г; б) аксіомою; в) самою формулою А.

У випадках “а” і “б” теорема випливає з того, що за схемою А1 маємо . Звідси за МР отримаємо, що .

У випадку “б”, тобто коли , із доведеного вище маємо, що ├ А ─ теорема. Отже, ├ і випадок і =1 цим вичерпано.

Нехай тепер ├ справедливе для всіх . Покажемо, що ├ . У цьому випадку можливі такі варіанти:

а) є аксіомою; б) є елементом Г;

в) ; г) є наслідком за правилом МР деяких формул і , і має вигляд .

Доведення випадків “а” - “в” нічим не відрізняється від доведення цих випадків для і =1.

У випадку “г”, використовуючи принцип індукції, маємо ├ і ├ .

За схемою аксіом А2 маємо Отже, за правилом МР отримаємо ├ і знову за правилом МР ─ , що й потрібно було довести.

Теорема 2.2.2. Довести, що ├ .

Доведення. За означенням теорії L

1) ─ гіпотеза;

2) ─ гіпотеза;

3) А ─ гіпотеза;

4) використовуючи МР із 1 і 3, отримаємо В;

5) використовуючи МР із 2 і 4, отримаємо С.

Отже, ├ С і за теоремою дедукції маємо ├ що й потрібно було довести.

Теорема 2.2.3. Довести, що В├

Доведення. За означенням теорії L

1. ─ гіпотеза;

2. В ─ гіпотеза;

3. А ─ гіпотеза;

4. використовуючи МР із 1 і 3, отримаємо ;

5. використовуючи МР із 2 і 4, отримаємо С.

Отже, ├ С, і за теоремою дедукції маємо В ├ , що й потрібно було довести.

Теорема 2.2.4. Для будь-яких формул А і В такі формули є теоремами формальної теорії L:

а) ; д) ;

б) ; є) ;

в) ; ж) ;

г) .

Доведення а) ├ .

1) – схема аксіом А3;

2) – теорема 2.1.1;

3) – теорема 2.2.3;

4) – схема аксіом А1;

5) – за MP із 3 і 4.

Доведення б) .

1) – схема аксіом А3;

2) – теорема 2.2.4 а;

3) – за МР із 1 і 2;

4) – схема аксіом А1;

5) – теорема 2.2.2 і за МР із 3 і 4.

Зіставляючи теореми 2.2.4 а і 2.2.4 б, отримаємо теорему

,

що виражає відомий нам із алгебри логіки закон подвійного заперечення.

Доведення в) ├

1) – гіпотеза;

2) – гіпотеза;

3) – схема аксіом А1;

4) – схема аксіом А1;

5) – за МР із 2, 3;

6) – за МР із 1, 4;

7) – схема аксіом А3;

8) – за МР із 6, 7;

9) – за МР із 5, 8.

Отже, використовуючи 1 ─ 9, маємо, що ├ В і за теоремою дедукції отримаємо ├ .

Доведення г) ├

1) – гіпотеза;

2) – гіпотеза;

3) – схема аксіом А3;

4) – схема аксіом А1;

5) – за МР із 1, 3;

6) – теорема 2.2.2;

7) – за МР із 2, 6.

Отже, використовуючи 1─7, маємо, що ├ В і, двічі застосувавши теорему дедукції, отримаємо ├

Доведення д) .

1) – гіпотеза;

2) – теорема 2.2.4 а;

3) – теорема 2.2.2;

4) – теорема 2.2.4 б;

5) – теорема 2.2.2;

6) – теорема 2.2.4 д;

7) – за МР із 5, 6.

Отже, використовуючи 1─7, маємо

├ і за теоремою дедукції отримаємо

├

Порівнюючи теореми 2.2.1 г і 2.2.1 д, отримаємо теорему

на якій ґрунтується метод доведення тверджень, відомий під назвою метод доведення від супротивного.

Доведення е) ├ .

Оскільки А, ├ В, то за теоремою дедукції отримаємо

За теоремою 2.2.4 д маємо

├

Використовуючи теорему 2.2.2, отримаємо

├

Доведення є)

1) – гіпотеза;

2) ─ гіпотеза;

3) ─ теорема 2.2.4 д;

4) ─ за МР із 1, 3;

5) ─ теорема 2.2.4. д;

6) ─ за МР із 2,5;

7) ─ схема аксіом АЗ;

8) ─ за МР із 6, 7;

9) ─ за МР із 4, 8.

Отже, , ├ , і, застосувавши двічі теорему дедукції, отримаємо

├ .