МААТЛОГИКА
.pdf
Доведення леми очевидне.
Íàñëiäîê 9. Повна система булевих функцiй мiстить хоча б одну нелiнiйну функцiю.
Мiркування аналогiчнi до мiркувань аналогiчних лем попереднiй пунктiв, тому ми ¨х опуска¹мо. Зауважимо лише, що iснують нелiнiйнi булевi функцi¨, наприклад, iмплiкацiя (див. стор. 26).
Ëåìà 8. З нелiнiйно¨ функцi¨ констант 0; 1 i функцiй x; x;¹ y суперпозицi¹ю можна отримати кон'юнкцiю двох логiчних змiнних.
Доведення. Îñêiëüêè f(x1; : : : ; xn) ¹ нелiнiйна функцiя, то в полiномi Жегалкiна,
який ¨¨ зображу¹, iсну¹ одночлен, який мiстить добуток двох логiчних змiнних, скажiмо, x1x2. Далi, всi одночлени полiнома розiб'¹мо на чотири групи:
Iякi мiстять одночасно x1 i x2;
II якi мiстять x1, але не мiстять x2; III якi не мiстять x1, але мiстять x2; IV якi не мiстять нi x1, íi x2.
Функцiя f(x1; : : : ; xn) в результатi такого групування буде мати вигляд:
f(x1; : : : ; xn) = x1x2ª1(x3; : : : ; xn) © x1ª2(x3; : : : ; xn) © x2ª3(x3; : : : ; xn) © ª4(x3; : : : ; xn):
Очевидно, ª1(x3; : : : ; xn) 6´0, iнакше f(x1; : : : ; xn) була б лiнiйною функцi¹ю. Отже, знайдеться такий такий набiр значень змiнних x3; : : : ; xn, наприклад, ~a = (a3; : : : ; an), ùî ª1(a3; : : : ; an) = 1. Розглянемо функцiю
»(x1; x2) = x1x2 © ®x1 © ¯x2 © °;
äå ® = ª2(a3; : : : ; an), ¯ = ª3(a3; : : : ; an), ° = ª4(a3; : : : ; an). За допомогою цi¹¨ функцi¨ побуду¹мо функцiю F (x; y) òàê:
F (x; y) = »(x © ¯; y © ®) = (x © ¯)(y © ®) © ®(x © ¯) © ¯(y © ®) © ° =
=xy © ®x © ¯y © ®¯ © ®x © ®¯ © ¯y © ®¯ © ° =
=xy © (®¯ © °);
тобто F (x; y) = xy © (®¯ © °). |
|
à) ßêùî ®¯ © ° = 0, òî F (x; y) = xy. |
|
á) ßêùî ®¯ © ° = 1, òî F (x; y) = xy © 1 = xy, |
|
òîìó xy = F (x; y). Отже, нами побудована кон'юнкцiя логiчних змiнних x i y. |
¤ |
31
5. Теорема про функцiональну повноту.
Теорема 16 (Post E.). Для того щоб система булевих функцiй ff1; f2; : : : ; fng була повною, необхiдно i достатньо, щоб вона мiстила:
²хоча б одну функцiю, яка не зберiга¹ константу 0;
²хоча б одну функцiю, яка не зберiга¹ константу 1;
²хоча б одну несамодво¨сту функцiю;
²хоча б одну немонотонну функцiю;
²хоча б одну нелiнiйну функцiю.
Доведення. Необхiднiсть умов теореми виплива¹ iз наслiдкiв 5, 6, 7, 8, 9. Для доведення достатностi припустимо, що виконуються всi п'ять умов теореми i нехай ff0; f1; fs; fm; flg ¹ пiдсистема системи ff1; f2; : : : ; fng òàêà, ùî f0 íå çáåðiã๠0, f1 íå
çáåðiã๠1, fs несамодво¨ста, fm немонотонна, fl нелiнiйна функцiя. Розглянемо довiльну булеву функцiю f(x1; : : : ; xn) i покажемо, що ¨¨ можна подати
як суперпозицiю функцiй f0; f1; fs; fm; fl; x1; : : : ; xn. Перш за все, побуду¹мо константи 0 i 1. Вiзьмемо f0 i x1, i далi побуду¹мо функцiю g(x1) = f0(x1; : : : ; x1). Îñêiëüêè f0 íå çáåðiã๠0, òî g(0) = f0(0; : : : ; 0) = 1, тобто g(0) = 1.
à) ßêùî g(1) = 1, тодi, очевидно, g(x1) ´ 1, тобто g(x1) ¹ константа 1. Далi, пiдставляючи g(x1) â f1 отрима¹мо функцiю ¾(x1) = f1(g(x1); : : : ; g(x1)). Ìà¹ìî
¾(0) = f1(g(0); : : : ; g(0)) = f1(1; : : : ; 1) = 0; ¾(1) = f1(g(1); : : : ; g(1)) = f1(1; : : : ; 1) = 0;
òîìó ¾(x1) ´ 0, тобто ¾(x1) ¹ константа 0.
á) ßêùî æ g(1) = 0, то, очевидно, g(x1) = x¹1. Äàëi, ç fs i x¹1 за лемою 4 буду¹мо
якусь константу. Iншу константу отриму¹мо iз побудовано¨ в результатi ¨¨ пiдстановки |
|||||||
â x¹1. Таким чином, константи |
0 i 1 нами побудованi. |
|
|||||
Ïîòiì |
çà |
лемою |
6 ç |
fm, |
0 i |
1 буду¹мо заперечення змiнно¨ x¹1. Пiсля цього, |
|
за лемою |
8 |
ç fl, 0, |
1, x¹1, x1, x2 |
áóäó¹ìî êîí'þíêöiþ x1x2. Вiдомо, що функцiя |
|||
f(x1; : : : ; xn) |
ìîæå |
áóòè |
задана |
формулою, яка |
записана лише за допомогою |
||
x1; : : : ; xn, заперечення i кон'юнкцi¨. Але оскiльки останнi операцi¨ виражаються через f0; f1; fs; fm; fl; x1; : : : ; xn, òî f(x1; : : : ; xn) також може бути задана суперпозицi¹ю функцiй f0; f1; fs; fm; fl; x1; : : : ; xn. Отже, ми показали, що система f0; f1; fs; fm; fl повна,
а значить система ff1; f2; : : : ; fng також повна. |
¤ |
||||||||
|
Приклад 1. Дослiдити на повноту систему булевих функцiй f»; Ã!g. |
||||||||
¹ |
Дослiдження |
äàíî¨ |
системи функцiй викона¹мо за теоремою Поста. Ма¹мо |
||||||
= 1 |
. Îòæå, |
» |
не зберiга¹ константу |
0 |
, тому перша умова теореми 16 викону¹ться. |
||||
0 |
|
, òîìó |
|
|
|
. Друга умова теореми 16 викону¹ться |
|||
Аналогiчно ¹ |
|
» |
не зберiга¹ константу |
||||||
|
|
1 |
= 0 |
|
|
|
|
1 |
|
також. Далi ма¹мо 0 Ã! 0 = 1 i 1 Ã! 1 = 1, òîìó Ã! ¹ несамодво¨ста функцiя.
Отже, третя умова теореми викону¹ться. Оскiльки |
|
, àëå ¹ |
¹, òî |
|
0 < 1 |
0 |
= 1 > 0 = 1 |
32
»
x¹ = x © 1, x Ã! y = x © y © 1, що говорить про те, що обидвi функцi¨ лiнiйнi. Таким чином, п'ята умова теореми не ма¹ мiсця. Отже, дана система булевих функцiй неповна.
Приклад 2. Дослiдити на повноту систему булевих функцiй f©; ¡!g.
Дослiдження дано¨ системи функцiй викона¹мо знову за теоремою Поста. Ма¹мо 0©0 = 0, òîìó © зберiга¹ константу 0. Розглянемо тепер iмплiкацiю. Ма¹мо 0 ¡! 0 = 1.
Îòæå, ¡! не зберiга¹ константу 0. Таким чином, перша умова теореми викону¹ться. Далi, 1©1 = 1, це означа¹, що © не зберiга¹ константу 1. Отже, друга умова теореми
викону¹ться.
Перевiримо тепер чи iсну¹ несамодво¨ста функцiя. Розглянемо значення булево¨ функцi¨ © на протилежних двiйкових наборах (0; 0) i (1; 1). Ìà¹ìî 0 © 0 = 0 i
1 © 1 = 0. Таким чином, знайшлась пара протилежних двiйкових наборiв, на яких функцiя прийма¹ однаковi значення. Отже, © несамодво¨ста булева функцiя. Це
означа¹, що третя умова теореми також викону¹ться. Перевiряти чи буде iмплiкацiя |
||
несамодво¨стою вже нема¹ потреби. |
|
|
Покажемо далi, що iсну¹ немонотонна булева функцiя. Розглянемо спочатку суму |
||
по модулю два ©. Ма¹мо двiйковi набори ~a = (1; 0) |
i ~ |
~ |
b = (1; 1). Зрозумiло, що ~a Á b, |
||
àëå 1 © 0 = 1 i 1 © 1 = 0, òîìó 1 © 0 > 1 © 1. Таким чином, © ¹ немонотонна булева
функцiя. Iмплiкацiю вже не перевiря¹мо. Отже, четверта умова теореми Поста також викону¹ться.
I нарештi, знайдемо полiноми Жегалкiна для © i ¡!. Для суми по модулю два
полiном Жегалкiна буде такий: x © y. Îòæå, © лiнiйна булева функцiя, тому треба
ще подивитись, який буде полiном Жегалкiна для iмплiкацi¨. Ранiше на стор. 26 була доведена рiвнiсть x ¡! y = xy © x © 1, це означа¹, що ¡! ¹ нелiнiйна булева функцiя.
Отже, п'ята умова теореми викону¹ться.
Таким чином, всi умови теореми мають мiсце, а тому згiдно з теоремою Поста про функцiональну повноту система булевих функцiй f©; ¡!g ¹ повною.
33
2 Числення висловлень
2.1 Числення висловлень. Теорема дедукцi¨
Поняття про формальну аксiоматичну теорiю. Вивiднiсть iз гiпотез та ¨¨ властивостi. Аксiоми числення висловлень. Лема ` A ¡! A. Теорема
дедукцi¨.
1. Таблицi iстинностi дозволяють вiдповiсти на багато важливих питань математично¨ логiки, в тому числi, i на питання: чи буде дана формула тавтологi¹ю, протирiччям або нi тим та не iншим, чи виплива¹ вона логiчно з iншо¨ формули тощо. Однак бiльш складнi питання математично¨ логiки, про якi пiде мова пiзнiше, вже не можуть бути вирiшенi за допомогою таблиць iстинностi. Для ¨х розв'язання iсну¹ iнший метод, а саме, метод формальних теорiй.
Формальна аксiоматична теорiя T вважа¹ться визначеною, якщо виконанi наступнi умови:
1.Задана деяка зчисленна множина символiв теорi¨ T (ця множина назива¹ться алфавiтом теорi¨ T). Скiнченнi послiдовностi символiв теорi¨ T називаються
виразами теорi¨ T.
2.Видiлена пiдмножина виразiв теорi¨ T, елементи яко¨ називаються формулами.
Звичайно iсну¹ правило, що дозволя¹ для деякого виразу визначати, чи ¹ воно формулою чи нi.
3.Видiлена деяка пiдмножина формул теорi¨ T, елементи яко¨ називаються аксiомами теорi¨ T. Часто вимага¹ться лише ефективно з'ясувати, чи ¹ дана
формула теорi¨ T аксiомою. чи нi; в цьому випадку теорiя T назива¹ться
ефективно аксиоматизованою або аксiоматичною теорi¹ю.
4.Задана деяка скiнченна множина ½1; : : : ; ½n вiдношень мiж формулами теорi¨
T, якi називаються правилами виведення. Нехай ½i ¹ mi-àðíå вiдношення, A1; : : : ; Ami¡1; B формули теорi¨ T òàêi, ùî (A1; : : : ; Ami¡1; B) 2 ½i, тодi формула
B назива¹ться безпосереднiм наслiдком формул A1; : : : ; Ami¡1 за правилом ½i.
Досить часто правило виведення записують так:
A1; : : :B; Ami¡1 (½i):
Доведенням в теорi¨ T (або виведенням) назива¹ться кожна скiнченна послiдовнiсть
A1; : : : ; An формул цi¹¨ теорi¨ така, що для довiльного i = 1; : : : ; n формула Ai ¹ àáî àêñiîìà òåîði¨ T, або безпосереднiй наслiдок з деяких попереднiх формул за
одним з правил виведення. Формула A òåîði¨ T назива¹ться теоремою теорi¨ T (i öå
познача¹ться `T A або просто ` A), якщо iсну¹ таке доведення в теорi¨ T, ùî A ¹ в ньому останньою формулою. Це доведення назива¹ться доведенням формули A.
Вiдмiтимо, що для поняття теореми може i не iснувати алгоритму, який дозволя¹ пiзнавати за даною формулою, чи iсну¹ доведення в теорi¨ T цi¹¨ формули або нi.
Теорiя, для яко¨ такий алгоритм iсну¹, назива¹ться розв'язною, в iншому випадку вона
34
назива¹ться нерозв'язною.
2. Формула A назива¹ться наслiдком в теорi¨ T множини формул ¡ (ÿêi
називаються гiпотезами) тодi i тiльки тодi, коли iсну¹ така скiнченна послiдовнiсть формул A1; : : : ; An, ùî An ¹ A, i для кожного i = 1; : : : ; n формула Ai ¹ àáî àêñiîìà,
або елемент множини ¡, або безпосереднiм наслiдком деяких формул, що ¨й передують, за одним iз правил виведення. Твердження "A ¹ íàñëiäîê ¡"символiчно познача¹ться
через ¡ ` A. ßêùî æ ¡ = fB1; : : : ; Bng, то пишемо B1; : : : ; Bn ` A, ÿêùî æ ¡ = ?, òî çàìiñòü ? ` A пишемо ` A. Останн¹, як не важко бачити, означа¹, що A ¹ теорема
òåîði¨ T.
Вiдмiтимо деякi властивостi вивiдностi iз гiпотез:
1.ßêùî ¡ ½ ¢ i ¡ ` A, òî ¢ ` A.
2.¡ ` A тодi i тiльки тодi, коли iсну¹ скiнченна пiдмножина ¢ ½ ¡ òàêà, ùî ¢ ` A.
3.ßêùî ¢ ` A i ¡ ` B для довiльного B 2 ¢, òî ¡ ` A.
3.Розглянемо тепер формальну аксiоматичну теорiю L для числення висловлень.
1.Символами L ¹ »; ¡!; (; )i ëiòåðè p1; q1; r1; s1; p2; q2; r2; s2; : : : Символи » i ¡!
називаються логiчними зв'язками, а лiтери pi; qi; ri; si логiчними змiнними.
2.Формули L визначаються так:
(a)Всi логiчнi змiннi ¹ формули.
(b)ßêùî A i B формули, то вирази (» A) i (A ¡! B) також формули.
3.Якi б не були формули A; B; C òåîði¨ L наступнi формули ¹ аксiоми L:11
A1: (A ¡! (B ¡! A));
A2: ((A ¡! (B ¡! C)) ¡! ((A ¡! B) ¡! (A ¡! C)));
A3: (((» B) ¡! (» A)) ¡! (((» B) ¡! A) ¡! B)).
4. ™диним правилом виведення ¹ правило modus ponens: B ¹ безпосереднiй наслiдок A i A ¡! B, тобто
(modus ponens або скорочено MP):
Вiдмiтимо, що зовнiшнi дужки ми будемо опускати, якщо це не буде приводити до непорозумiнь. Наша мета: побудувати теорiю L таким чином, щоб клас всiх ¨¨ теорем
спiвпадав з класом всiх тавтологiй.
Iншi логiчнi зв'язки введемо за допомогою таких означень: D1: (A ^ B) означа¹ » (A ¡! (» B));
11 Зауважимо, що вирази A1, A2 i A3 ¹, так званi, схеми аксiом, кожна з яких визнача¹ нескiнченну множину аксiом, тобто пiдставляючи в данi схеми конкретнi формули, ми будемо кожний раз отримувати конкретнi аксiоми.
35
D2: (A _ B) означа¹ (» A) ¡! B;
D3: (A Ã! B) означа¹ (A ¡! B) ^ (B ¡! A).
Ëåìà 9. Для довiльно¨ формули A òåîði¨ L ì๠ìiñöå ` A ¡! A.
Доведення.
1. |
(A ¡! ((A ¡! A) ¡! A)) ¡! ((A ¡! (A ¡! A)) ¡! (A ¡! A)) (пiдстановка в |
|
|
схему аксiом A2) |
|
2. |
A ¡! ((A ¡! A) ¡! A) (пiдстановка в схему A1) |
|
3. |
(A ¡! (A ¡! A)) ¡! (A ¡! A) (ç 1 i 2 ïî MP) |
|
4. |
A ¡! (A ¡! A) (схема аксiом A1) |
|
5. |
A ¡! A (ç 3 i 4 ïî MP) |
¤ |
4. В математичних мiркуваннях часто деяке твердження B доводять в припущеннi справедливостi iншого твердження A, пiсля чого роблять висновок, що справедливе
твердження "якщо A, òî B". Для системи L цей засiб обгрунтову¹ться наступною теоремою.
Теорема 17 (Метатеорема дедукцi¨). ßêùî ¡ множина формул теорi¨ L, A i B формули L i ¡; A ` B, òî ¡ ` A ¡! B.
Доведення. Нехай B1; : : : ; Bn ¹ доведення формули B ç ¡ [ fAg, äå Bn = B. За допомогою метода математично¨ iндукцi¨ доведемо, що ¡ ` A ¡! Bi для кожного i = 1; : : : ; n. Для формули B1 можливi такi випадки: а) B1 àêñiîìà, á) B1 2 ¡, â) B1 ¹ формула A. За схемою A1 ми можемо записати ` B1 ¡! (A ¡! B1), тому у випадках а) i б) за МР отриму¹мо ¡ ` A ¡! B1. У випадку ж в) за лемою 9 ма¹мо
òîìó ¡ ` A ¡! B1. Îòæå, ïðè i = 1 теорема справедлива.
Припустимо, що теорема справедлива для довiльного k < i, тобто ¡ ` A ¡! Bk äëÿ âñiõ k < i. Для формули Bi ¹ чотири можливостi: а) Bi àêñiîìà; á) Bi 2 ¡; â) Bi ¹ формула A; ã) Bi виводиться за МР з Bj i Bm = Bj ¡! Bi, äå j < i i m < i. У випадках а), б) i в) за допомогою таких же мiркувань, як i при i = 1, показу¹мо ¡ ` A ¡! Bi.Ó випадку ж г) за схемою A2
` (A ¡! (Bj ¡! Bi)) ¡! ((A ¡! Bj) ¡! (A ¡! Bi)):
Але згiдно iндуктивного припущення ¡ ` A ¡! Bj i ¡ ` A ¡! (Bj ¡! Bi). Отже, по МР отриму¹мо спочатку ¡ ` (A ¡! Bj) ¡! (A ¡! Bi), а далi знову по МР отриму¹мо ¡ ` A ¡! Bi. Отже, згiдно методу математично¨ iндукцi¨ ¡ ` A ¡! Bi äëÿ âñiõ
i = 1; : : : ; n, òîìó ¡ ` A ¡! Bn, що означа¹ ¡ ` A ¡! B. |
¤ |
Íàñëiäîê 10. ßêùî A ` B, òî ` A ¡! B. |
|
36
Приклад 1. Користуючись теоремою дедукцi¨ довести, що
|
A ¡! B; B ¡! C ` A ¡! C: |
(2.1.1) |
|
Доведемо спочатку, що |
A ¡! B; B ¡! C; A ` C: |
(2.1.2) |
|
Îòæå, ìà¹ìî: |
|||
|
|
||
|
1: A (гiпотеза) |
|
|
|
2: A ¡! B (гiпотеза) |
|
|
|
3: B (ÌÐ, 1, 2) |
|
|
|
4: B ¡! C (гiпотеза) |
|
|
|
5: C (ÌÐ, 3, 4) |
|
Таким чином, ми довели (2.1.2). Застосувавши тепер до (2.1.2) теорему дедукцi¨, |
|
отрима¹мо (2.1.1), що i треба було довести. |
¤ |
Приклад 2. Користуючись теоремою дедукцi¨ довести, що |
|
A ¡! (B ¡! C); B ` A ¡! C: |
(2.1.3) |
Доведемо спочатку, що
A ¡! (B ¡! C); B; A ` C: (2.1.4)
Îòæå, ìà¹ìî:
1: A |
(гiпотеза) |
2: A ¡! (B ¡! C) (гiпотеза) |
|
3: B ¡! C (ÌÐ, 1, 2) |
|
4: B |
(гiпотеза) |
5: C |
(ÌÐ, 3, 4) |
Таким чином, ми довели (2.1.4). Застосувавши тепер до (2.1.4) теорему дедукцi¨, |
|
отрима¹мо (2.1.3), що i треба було довести. |
¤ |
37
2.2 Повнота, несуперечнiсть i незалежнiсть аксiом числення висловлень
Деякi теореми числення висловлень. Теорема про повноту. Несуперечнiсть числення висловлень. Незалежнiсть аксiом числення висловлень. Iншi аксiоматики числення висловлень.
äàëi.1. Доведемо деякi формальнi теореми числення висловлень, якi нам будуть потрiбнi
Ëåìà 10. Для довiльних формул A i B наступнi формули ¹ теоремами теорi¨ L:
(a) »» B ¡! B; |
(e) (A ¡! B) ¡! (» B ¡!» A); |
(b) B ¡!»» B; |
(f) A ¡! (» B ¡!» (A ¡! B)); |
(c) » A ¡! (A ¡! B); |
(g) (A ¡! B) ¡! ((» A ¡! B) ¡! B): |
(d) (» B ¡!» A) ¡! (A ¡! B); |
|
Доведення.
(a) `»» B ¡! B.
1: (» B ¡!»» B) ¡! ((» B ¡!» B) ¡! B) 2: » B ¡!» B
3: (» B ¡!»» B) ¡! B
4: »» B ¡! (» B ¡!»» B) 5: »» B ¡! B
(b) ` B ¡!»» B.
1: (»»» B ¡!» B) ¡! ((»»» B ¡! B) ¡!»» B) 2: »»» B ¡!» B
3: (»»» B ¡! B) ¡!»» B 4: B ¡! (»»» B ¡! B)
5: B ¡!»» B
(c) `» A ¡! (A ¡! B).
1: » A
2: A
3: A ¡! (» B ¡! A)
4: » A ¡! (» B ¡!» A) 5: » B ¡! A
6: » B ¡!» A
7: (» B ¡!» A) ¡! ((» B ¡! A) ¡! A) 8: (» B ¡! A) ¡! B
9: B
( схема аксiом A3 ) ( ëåìà 9 )
( 1, 2, (2.1.3) )
( схема аксiом A1 ) ( 3, 4, (2.1.1) )
( схема аксiом A3 )
( пункт (а), доведений вище ) ( 1, 2 MP )
( схема аксiом A1 ) ( 3, 4, (2.1.1) )
( гiпотеза ) ( гiпотеза )
( схема аксiом A1 ) ( схема аксiом A1 ) ( 2, 3, MP )
( 1, 4, MP )
( схема аксiом A3 ) ( 6, 7, MP )
( 5, 8, MP )
38
Îòæå, çãiäíî 1 9, » A; A ` B. Тому, за теоремою дедукцi¨, » A ` A ¡! B i, за цi¹ю теоремою, `» A ¡! (A ¡! B).
(d) ` (» B ¡!» A) ¡! (A ¡! B). |
|
1: » B ¡!» A |
( гiпотеза ) |
2: A |
( гiпотеза ) |
3: (» B ¡!» A) ¡! ((» B ¡! A) ¡! B) |
( схема аксiом A3 ) |
4: A ¡! (» B ¡! A) |
( схема аксiом A1 ) |
5: (» B ¡! A) ¡! B |
( 1, 3, MP ) |
6: A ¡! B |
( 4, 5, (2.1.1) ) |
7: B |
( 2, 6, MP ) |
 ñèëó 1 7, » B ¡!» A; A ` B, пiсля чого, двiчi застосовуючи теорему дедукцi¨, отрима¹мо потрiбний результат.
(e) ` (A ¡! B) ¡! (» B ¡!» A).
1: A ¡! B |
( гiпотеза ) |
2: »» A ¡! A |
( пункт (а) ) |
3: »» A ¡! B |
( 1, 2, (2.1.1S) ) |
4: B ¡!»» B |
( пункт (b) ) |
5: »» A ¡!»» B |
( 3, 4, (2.1.1) ) |
6: (»» A ¡!»» B) ¡! (» B ¡!» A) |
( пункт (d) ) |
7: (» B ¡!» A)) |
( 5, 6, MP ) |
 ñèëó 1 7, A ¡! B `» B ¡!» A, звiдки (е) отриму¹ться за теоремою дедукцi¨.
(f)` A ¡! (» B ¡!» (A ¡! B)).
Очевидно, A; A ¡! B ` B. Застосувавши двiчi теорему дедукцi¨, отриму¹мо ` A ¡! ((A ¡! B) ¡! B). Згiдно пункту (е) ма¹мо
` ((A ¡! B) ¡! B) ¡! (» B ¡!» (A ¡! B)):
Нарештi, застосувавши (2.1.1), отриму¹мо
`A ¡! (» B ¡!» (A ¡! B)):
(g)` (A ¡! B) ¡! ((» A ¡! B) ¡! B).
1: A ¡! B |
( гiпотеза ) |
2: » A ¡! B |
( гiпотеза ) |
3: (A ¡! B) ¡! (» B ¡!» A) |
( пункт (е) ) |
39
4: » B ¡!» A |
( 1, 3, MP ) |
5: (» A ¡! B) ¡! (» B ¡!»» A) |
( пункт (е) ) |
6: » B ¡!»» A |
( 2, 5, MP ) |
7: (» B ¡!»» A) ¡! ((» B ¡!» A) ¡! B) |
( схема аксiом A3 ) |
8: (» B ¡!» A) ¡! B |
( 6, 7, MP ) |
9: B |
( 4, 8, MP ) |
Îòæå, A ¡! B; » A ¡! B ` B. Застосовуючи далi два рази теорему дедукцi¨ отриму¹мо (g).
Твердження 1. Кожна теорема числення висловлень ¹ тавтологiя.
Справдi, легко бачити, що кожна з аксiом числення висловлень ¹ тавтологiя. Вiдомо, що МР, застосований до тавтологiй, знову приводить до тавтологi¨, звiдки виплива¹ справедливiсть твердження.
Ëåìà 11. Нехай A ¹ формула числення висловлень, а p1; : : : ; pk ëîãi÷íi çìiííi, якi входять в A. Нехай заданий деякий розподiл iстинностних значень для p1; : : : ; pk.
Нехай далi p0 |
означа¹ p |
, ÿêùî |
j |
p |
ij |
= 1, i p0 означа¹ |
» |
p |
, ÿêùî |
p |
ij |
= 0. Аналогiчно, A0 |
i |
i |
|
|
i |
i |
|
j |
|
||||
¹ A ïðè jAj = 1 i A0 ¹ » A ïðè jAj = 0. Тодi справедливе |
|
|
|
|
||||||||
|
|
|
|
|
|
p10 ; : : : ; pk0 ` A0: |
|
|
|
|
|
(2.2.1) |
Доведення. Доведення проводиться iндукцi¹ю по числу n входжень в A ëîãi÷íèõ
çâ'ÿçîê. ßêùî n = 0, òî A явля¹ собою деяку логiчну змiнну, скажiмо, p1. В цьому випадку твердження леми зводиться до p1 ` p1, àáî äî » p1 `» p1, що ¹ справедливим â ñèëó ëåìè 9. Îòæå, ïðè n = 0 твердження (2.2.1) ма¹ мiсце. Припустимо, що (2.2.1)
справедливе для кожного i < n.
|
|
Випадок 1. Формула A ма¹ вигляд заперечення » B, де число входжень логiчних |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
зв'язок в формулу B меньше n. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
а) Нехай при даному розподiлi iстинностних значень jBj = 1, òîäi jAj = 0, òîìó |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
B0 = B i A0 = |
» |
|
A. Згiдно припущення p0 |
|
; : : : ; p0 |
` |
B, але за лемою 10 (b) |
` |
B |
¡!»» |
B, |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|||||||||||
тому по МР отриму¹мо p0 |
; : : : ; p0 |
`»» |
B, àëå |
|
»» |
B = |
» |
A = A0, çâiäêè p0 |
; : : : ; p0 |
|
A0 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
б) Нехай тепер |
|
B |
|
|
|
1 |
|
|
|
|
k |
|
|
|
|
|
|
|
|
B i A0 |
|
|
|
1 |
|
|
|
|
|
|
k ` |
|
|
|
|
|||||||||||||||||||||||||||
|
|
j |
j |
|
= 0, òîäi |
|
j |
A |
j |
= 1, çâiäêè B0 = |
» |
= A. За припущенням |
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
||||||
p0 |
; : : : ; p0 |
` |
B0, тобто p0 |
|
; : : : ; p0 |
|
|
|
B, àëå |
» |
B = A = A0, òîìó p0 |
; : : : ; p0 |
|
|
A0 |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
1 |
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
k `» |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
k ` |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
Випадок 2. Нехай A ì๠âèä B ¡! C, тодi число входжень логiчних. çâ'ÿçîê â B i C |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
меньше, нiж в A, тому за припущенням p10 ; : : : ; pk0 ` B0 i p10 ; : : : ; pk0 ` C0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
à) ßêùî |
j |
B |
j |
|
= 0, òî |
|
j |
A |
j |
= 1, îòæå, B0 |
= |
» |
B, A0 |
= A. Îòæå, p0 |
; : : : ; p0 |
|
`» |
B, |
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
k |
|
|
|
|
|||||||||
але за лемою 10 (c) |
`» |
B |
|
¡! |
(B |
¡! |
|
C), òîìó ïî ÌÐ p0 |
; : : : ; p0 |
` |
B |
¡! |
C, тобто |
|||||||||||||||||||||||||||||||||||||||||||||||||||
p10 ; : : : ; pk0 ` A0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
k |
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
á) ßêùî |
j |
C |
j |
|
= 1, òî |
j |
A |
j |
= 1, çâiäêè C0 = C i A0 = A. Ìà¹ìî, p0 ; : : : ; p0 |
|
` |
C, à çà |
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
k |
|
|
|
|
. |
|||||||||
схемою A |
` |
|
C |
|
|
¡! |
|
(B |
¡! |
C), òîìó ïî ÌÐ p0 |
|
; : : : ; p0 |
|
B |
¡! |
C, тобто p0 ; : : : ; p0 |
` |
A0 |
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
k ` |
|
|
|
|
|
1 |
|
|
|
|
|
|
k |
|
|
|
|
|||||||||||||||||
|
|
â) ßêùî æ jBj = 1, jCj = 0, òî jAj = 0, òîìó B0 = B, C0 =» C, A0 =» A =» |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(B |
|
¡! |
C). За припущенням p0 |
; : : : ; p0 |
|
` |
B |
i p0 ; : : : ; p0 |
|
`» |
C. За лемою 10 (f) ма¹мо |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
B |
( |
|
C |
|
|
|
|
|
|
|
|
(B |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
k |
|
|
|
|
1 |
|
k |
|
|
|
(B |
|
|
|
|
C) i äàëi ïî |
|||||||||||||||||||||
` |
¡! |
» |
|
¡!» |
|
¡! |
C)), çâiäêè ïî ÌÐ p0 ; : : : ; p0 |
`» |
C |
¡!» |
¡! |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 . |
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
ÌÐ p0 ; : : : ; p0 |
|
|
`» |
(B |
¡! |
C), тобто p0 |
; : : : ; p0 |
|
|
A0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
1 |
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
k ` |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
Таким чином, (2.2.1) справедливе для n, тому за методом математично¨ iндукцi¨ |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(2.2.1) викону¹ться для довiльного натурального n. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
¤ |
|||||||||||||||||||||||||||||||||||||||||||
40