Page 65 - 4570

64

2. Усі пропозиційні букви А і є формулами. Якщо А і В – формули, то A ,
A  B також формули теорії L.
3. Для будь-яких формул А, В, С теорії L формули:
А 1) A  (B  ) A ;
А 2) ((A (B  C )))  ((A  ) B  (A  C ));
А 3) ( B   ) A  (( B  ) B  ) B

є аксіомами теорії L.
4. Єдиним правилом виведення служить правило modus ponens (MP), за
допомогою якого із формули А і A  B виводиться В:
, A A  B ├ B.
Необхідно зазначити, що нескінченна множина аксіом теорії L задана за
допомогою лише трьох схем аксіом А 1, А 2, А 3, кожна з яких породжує
нескінченну множину аксіом. Для будь-якої формули логіки висловлювань
легко перевірити, є вона аксіомою чи ні, а звідси випливає, що теорія L є
ефективно аксіоматизованою теорією.
Інші зв’язки в аксіоматичній теорії L можна ввести за допомогою вже
відомих формул:
A &B   (A   ) B ; A B   A  B ; A  B  (A  B )&(B  ) A

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

Теорема дедукції дає нове правило виведення у логіці висловлювань, і
тому вона є важливою під час доведення теорем і різних висловлювань.
Теорема 2.3 (дедукція). Якщо Г – множина формул, А і В – формули і Г,
A ├ В, то Г ├ A  B . Зокрема, якщо A ├ В, то ├ A  B .
Доведення. Нехай В 1, В 2,…, В n – виведення із Г  { }A формули В, тобто

В n = В. Доведення будемо проводити індукцією по і – довжині виведення
(1 i n  ) формули В.
При і = 1 В 1 повинне бути або:
а) елементом Г;
б) аксіомою;
в) самою формулою А.
У випадках «а» і «б» теорема випливає з того, що за схемою А 1 маємо

B  (A  B ) . Звідси за МР отримаємо, що Г  (A  B ).
1 1 1
У випадку «б», тобто коли A  B , із доведеного вище маємо, що A ├ А ─
1
теорема. Отже, Г ├ A  A і випадок і =1 цим вичерпано.
Нехай тепер Г ├ A  B справедливе для всіх k  i . Покажемо, що
K
Г ├ A  B . У цьому випадку можливі такі варіанти:
i
а) B є аксіомою;
i
б) B є елементом Г;
i
в) B  A ;
i