МААТЛОГИКА
.pdf1.2 Логiчне слiдування в логiцi висловлень
Логiчний наслiдок в логiцi висловлень. Властивостi логiчного слiдування. Доведення в логiцi висловлень. Правила виведення. Методи доведення теорем.
1. Нехай A1; A2; : : : ; An i B деякi формули логiки висловлень.
Означення 1 Висловлення B |
назива¹ться логiчним наслiдком висловлень |
A1; A2; : : : ; An (це познача¹ться |
ÿê A1; A2; : : : ; An j= B), якщо для кожного |
розподiлення iстинностних значень, якi приписуються логiчним змiнним, що входять хоч би в одну з формул A1; A2; : : : ; An i B , формула B отриму¹ значення 1,
як тiльки кожне Ai отриму¹ значення 1.
Надалi ми називатимемо формули A1; A2; : : : ; An посилками, а формулу B наслiдком. Якщо викону¹ться A1; A2; : : : ; An j= B, то ще кажуть, що B логiчно виплива¹ з посилок A1; A2; : : : ; An, i говорять, що дане мiркування ¹ коректним с точки зору логiки. Доведемо, наприклад, що A; B; C ^ A ¡!» B j=» C. Для цього складемо таблицю iстинностi:
A |
B |
C |
A |
B |
C ^ A ¡!» B |
» C |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
|
Ми бачимо, що в четвертому рядку всi посилки приймають значення 1 i значення наслiдку також дорiвню¹ 1. Згiдно означення це означа¹, що наслiдок » C ëîãi÷íî
виплива¹ з посилок A; B; C ^ A ¡!» B. Ма¹ мiсце така очевидна теорема:
Теорема 4. Для довiльних формул A1; A2; : : : ; An i B ì๠ìiñöå A1; A2; : : : ; An j= B òîäi i òiëüêè òîäi, êîëè j= A1 ^ A2 ^ : : : ^ An ¡! B.
Íàñëiäîê 1. A j= B òîäi i òiëüêè òîäi, êîëè j= A ¡! B для довiльних формул логiки висловлень.
Íàñëiäîê 2. Для довiльних формул A1; A2; : : : ; An i B ì๠ìiñöå A1; A2; : : : ; An j= B òîäi i òiëüêè òîäi, êîëè A1; A2; : : : ; An¡1 j= An ¡! B. В бiльш загальнiй формi A1; A2; : : : ; An j= B òîäi i òiëüêè òîäi, êîëè j= A1 ¡! (A2 ¡! (: : : (An ¡! B) : : :)).
2.Вiдмiтимо двi очевиднi властивостi логiчного слiдування:
1.A1; A2; : : : ; An j= Ai для кожного i = 1; 2; : : : ; n.
2. ßêùî A1; A2; : : : ; An j= Bj äëÿ j = 1; 2; : : : ; p i ÿêùî B1; B2; : : : ; Bp j= C, òî A1; A2; : : : ; An j= C.
11
Доведення властивостей легко проводиться, якщо скористатись теоремою 4.
3. Нехай формула B ¹ логiчним наслiдком з посилок A1; A2; : : : ; An, тодi можна побудувати так зване доведення (або iнакше виведення) формули B з вказаних посилок, яке визнача¹ться означенням 2.
Означення 2 Доведенням формули B з посилок A1; A2; : : : ; An назива¹ться
скiнченна послiдовнiсть формул логiки висловлень, останньою з яких ¹ формула B, причому наявнiсть кожно¨ формули E в цiй послiдовностi обгрунтову¹ться
застосуванням одного з наступних правил: 4
²Правило посилки (правило p): формула E ¹ посилка.
²Правило наслiдку (правило t): формулi E в послiдовностi передують такi
формули A; : : : ; C, ùî j= A ^ : : : ^ C ¡! E.
²Правило умовного вiдокремлення (правило cp): формула B ¡! C
виправдана в доведеннi, посилками якого слугують формули A1; A2; : : : ; An, ÿêùî встановлено, що C ¹ логiчний наслiдок формул A1; A2; : : : ; An; B.
Приклад 1. Довести, що A _ B; A ¡! C; B ¡! D j= C _ D, пiсля чого побудувати доведення формули C _ D з посилок A _ B; A ¡! C; B ¡! D.
Доведення. Згiдно теореми 4 розглянемо формулу
(A _ B) ^ (A ¡! C) ^ (B ¡! D) ¡! (C _ D) |
(1.2.1) |
i покажемо, що вона ¹ тавтологiя. Припустимо, що це не так, тобто
j(A _ B) ^ (A ¡! C) ^ (B ¡! D) ¡! (C _ D)j = 0;
òîìó jA _ Bj = 1, jA ¡! Cj = 1, jB ¡! Dj = 1, jC _ Dj = 0. З останньо¨ рiвностi ма¹мо, що jCj = 0 i jDj = 0, òîìó jA ¡! 0j = 1 i jB ¡! 0j = 1. Таким чином, jAj = jBj = 0, òîìó jA _ Bj = 0, що протирiччить рiвностi jA _ Bj = 1. Отже, формула (1.2.1) ¹ тавтологiя, а це означа¹ згiдно теореми 4, що формула C _ D ¹ ëîãi÷íèì íàñëiäêîì
формул A _ B; A ¡! C; B ¡! D.
Нижче дано доведення формули C _ D
1.
2.
3.
4.
5.
6.
A ¡! C
A _ B ¡! C _ B (правило t, рядок 1, тавтологiя 11)
B ¡! D
C _ B ¡! C _ D (правило t, рядок 3, тавтологiя 11)
A _ B ¡! C _ D (правило t, рядки 2, 4, тавтологiя 7)
A _ B
4 Такi правила називають в математичнiй логiцi правилами виведення.
12
7. C _ D (правило t, рядки 5, 6, тавтологiя 1) |
|
Приклад 1 розглянуто повнiстю. |
¤ |
Багато теорем в математицi мають форму iмплiкацi¨, причому припущеннями слугують аксiоми теорi¨, що розгляда¹ться. У символiчнiй формi така теорема ма¹ наступний вид:
A1; A2; : : : ; An j= B ¡! C;
де формули A1; A2; : : : ; An àêñiîìè, à B ¡! C наслiдок, який доводиться. Звичайний спосiб доведення тако¨ теореми поляга¹ в тому, що B приймають як ще
одну посилку, яку називають гiпотезою, а потiм виводять C ÿê ëîãi÷íèé íàñëiäîê. Ïðè
цьому використову¹ться той факт, що A1; A2; : : : ; An j= B ¡! C òîäi i òiëüêè òîäi, êîëè
A1; A2; : : : ; An; B j= C, що обгрунтову¹ться наслiдком 2 теореми 4, тобто користуються правилом умовного вiдокремлення.
Приклад 2. Довести, що A ¡! (B ¡! C); » D _ A; B j= D ¡! C.
1. |
A ¡! (B ¡! C) (правило p) |
|
2. |
» D _ A (правило p) |
|
3. |
B |
(правило p) |
4. |
D |
(гiпотеза, правило p) |
5. |
A (правило t, рядки 2, 4, тавтологiя 3) |
|
6. |
B ¡! C (правило t, рядки 1, 5, тавтологiя 1) |
|
7. |
C (правило t, рядки 3, 6, тавтологiя 1) |
|
8. D ¡! C (правило cp, рядки 4, 7, див. властивiсть 1 на стор. 11)
Теорема 5. Нехай A1; : : : ; An; B формули логiки висловлень i T довiльна тавтологiя, тодi A1; : : : ; An j= B, ÿêùî i òiëüêè ÿêùî T; A1; : : : ; An j= B.
Доведення. Справдi, згiдно теореми 4 твердження A1; : : : ; An j= B означа¹, що j= A1 ^ : : : ^ An ¡! B. Îñêiëüêè j= T , то очевидно jA1 ^ : : : ^ Anj = jT ^ A1 ^ : : : ^ Anj,
à òîìó j= T ^ A1 ^ : : : ^ An ¡! B, що означа¹ T; A1; : : : ; An j= B. ¤
Теорема 5 дозволя¹ в доведення за правилом p вводити довiльну тавтологiю.
На практицi крiм вказаних вище трьох правил виведення користуються й iншими додатковими правилами виведення, що значно полегшу¹ доведення багатьох теорем. Нижче наведенi найбiльш вживанi правила виведення:
²Модус поненс (ÌÏ): A; A ¡! B j= B (див. тавтологiю 1).
²Модус толленс (ÌÒ): » B; A ¡! B j=» A (див. тавтологiю 2).
²Введення кон'юнкцi¨ (ÂÊ): A; B j= A^B (згiдно тавт. 4 i наслiдку 2 теореми 4).
13
²Знищення кон'юнкцi¨ (ÇÊ): A ^ B j= A àáî A ^ B j= B (див. тавтологiю 5).
²Введення диз'юнкцi¨ (ÂÄ): A j= A _ B àáî B j= A _ B (див. тавтологiю 6).
² Знищення диз'юнкцi¨ (ÇÄ): » A; A _ B j= B àáî » B; A _ B j= A (äèâ. òàâò. 3).
² Правило силогiзму (ÏÑ): A ¡! B; B ¡! C j= A ¡! C (див. тавтологiю 7).
² Правило контрапозицi¨ (ÏÊ): A ¡! B j=» B ¡!» A (див. тавтологiю 20).
Пiдсумовуючи сказане вище, ми можемо дати таке означення доведення:
Означення 3 Доведенням формули B з посилок A1; A2; : : : ; An назива¹ться
скiнченна послiдовнiсть формул логiки висловлень, останньою з яких ¹ формула B, причому наявнiсть кожно¨ формули E в цiй послiдовностi обгрунтову¹ться
застосуванням одного з наведених вище правил виведення до деяких формул, що передують ¨й у цiй послiдовностi, або ж формула E ¹ тавтологi¹ю.
Приклад 3. Побудувати доведення теореми: A _ B ¡! C ^ D; D _ E ¡! F; A j= F .
1. |
A (посилка) 5 |
2. |
A _ B (ÂÄ, 1) |
3. |
A _ B ¡! C ^ D (посилка) |
4. |
C ^ D (ÌÏ, 2, 3) |
5. |
D (ÇÊ, 4) |
6. |
D _ E (ÂÄ, 5) |
7. |
D _ E ¡! F (посилка) |
8. |
F (ÌÏ, 6, 7) |
4. |
Розглянемо тепер деякi методи доведення теорем. Припустимо, що нам потрiбно |
|||
довести теорему: |
A1 |
; A2; : : : ; An j= B: |
(1.2.2) |
|
|
|
|||
Якщо ми буду¹мо доведення цi¹¨ теореми, користуючись означеннями 2 або 3, тобто з посилок A1; A2; : : : ; An виводимо формулу B, то таке доведення назива¹ться прямим. В
розглянутих вище трьох прикладах нами були побудованi прямi доведення теорем. Крiм прямого доведення часто на практицi користуються непрямими доведеннями, оскiльки в багатьох випадках вони значно полегшують процес доведення теореми. Ми розглянемо зараз три методи непрямих доведеíü:
5 Надалi ми будемо писати просто слово "посилка" замiсть слiв правило p .
14
Доведення вiд супротивного поляга¹ в тому, що до посилок при¹дну¹ться, так звана, гiпотеза » B. Пiсля цього, користуючись означеннями 2 або 3 буду¹ться
пряме доведення формули виду H^ » H, äå H деяка формула. Неважко бачити, що формула H^ » H ¹ протирiччям. Отже, насправдi ми буду¹мо пряме доведення
твердження |
A1 |
; A2; : : : ; An; » B j= H^ » H; |
(1.2.3) |
|
але стверджу¹мо, що нами доведене твердження (1.2.2). Останн¹ поясню¹ться таким чином. Твердження (1.2.3) згiдно теореми 4 означа¹
j= (A1 ^ A2 ^ : : : ^ An)^ » B ¡! H^ » H:
Îñêiëüêè jH^ » Hj = 0, то очевидно j(A1 ^ A2 ^ : : : ^ An)^ » Bj = 0 для всiх значень логiчних змiнних, якi входять в данi формули. Отже,
j=» ((A1 ^ A2 ^ : : : ^ An)^ » B):
Таким чином, згiдно тавтологi¨ 27 ма¹мо твердження (1.2.2). |
|
Доведення за правилом гiпотези застосову¹ться тодi, коли наслiдок, |
ÿêèé |
виплива¹ з посилок, ма¹ вид iмплiкацi¨, тобто теорема ма¹ таку форму: |
|
A1; A2; : : : ; An j= B ¡! C: |
(1.2.4) |
В цьому випадку до посилок при¹дну¹ться, так звана, гiпотеза B. Пiсля цього,
користуючись означеннями 2 або 3 буду¹ться пряме доведення формули C.
Даний метод грунту¹ться на застосування правила умовного вiдокремлення, тобто правила cp. Отже, щоб довести твердження 1.2.4, ми буду¹мо пряме доведення для
твердження
Доведення методом частинних випадкiв застосову¹ться тодi, коли наслiдок, який |
|
виплива¹ з посилок, ма¹ вид диз'юнкцi¨, тобто теорема ма¹ таку форму: |
|
A1; A2; : : : ; An j= B _ C: |
(1.2.5) |
В цьому випадку до посилок при¹дну¹ться, так звана, гiпотеза » B (àáî » C).
Пiсля цього, користуючись означеннями 2 або 3 буду¹ться пряме доведення формули C (àáî âiäïîâiäíî B), тобто доводиться твердження
A1; A2; : : : ; An; » B j= C |
(1.2.6) |
àáî âiäïîâiäíî A1; A2; : : : ; An; » C j= B: Обгрунту¹мо тiльки-що сказане. Дiйсно, твердження (1.2.5) згiдно теореми 4 означа¹
j= A1 ^ A2 ^ : : : ^ An ¡! B _ C:
Приймаючи до уваги тавтологiю 33, ми отриму¹мо
j= A1 ^ A2 ^ : : : ^ An^ » B ¡! C;
що означа¹ (1.2.6).
15
Продемонстру¹мо тепер вказанi методи доведень на прикладах. Приклад 4. Побудувати доведення теореми:
(A ¡! B) ^ (C ¡! D); (B ¡! E) ^ (D ¡! F ); » (E ^ F ); A ¡! C j=» A:
Доведення проведемо методом вiд супротивного.
1. |
»» A |
(гiпотеза) |
|
|
2. |
»» A ¡! A |
(тавтологiя) |
||
3. |
A (ÌÏ, 1, 2) |
|
||
4. |
A ¡! C (посилка) |
|
||
5. |
C (ÌÏ, 3, 4) |
|
||
6. |
(A ¡! B) ^ (C ¡! D) |
(посилка) |
||
7. |
C ¡! D (ÇÊ, 6) |
|
||
8. |
D (ÌÏ, 5, 7) |
|
||
9. |
(B ¡! E) ^ (D ¡! F ) |
(посилка) |
||
10. |
D ¡! F (ÇÊ, 9) |
|
||
11. |
F (ÌÏ, 8, 10) |
|
||
12. |
» (E ^ F ) |
(посилка) |
|
|
13. |
» (E ^ F ) ¡!» E_ » F |
(тавтологiя) |
||
14. |
» E_ » F |
(ÌÏ, 12, 13) |
||
15. |
F ¡!»» F |
(тавтологiя) |
||
16. |
»» F |
(ÌÏ, 11, 15) |
|
|
17. |
» E |
(ÇÄ, 14, 16) |
|
|
18. |
B ¡! E (ÇÊ, 9) |
|
||
19. |
» B |
(ÌÒ, 17, 18) |
|
|
20. |
A ¡! B (ÇÊ, 6) |
|
||
21. |
» A |
(ÌÒ, 19, 20) |
|
|
22. |
A^ » A (ÂÊ, 3, 21) |
¤ |
||
16
Приклад 5. Побудувати доведення теореми:
|
» A _ B; C ¡!» B j= A ¡!» C: |
|
Доведення будемо проводити за правилом гiпотези: |
|
|
1. |
A (гiпотеза) |
|
2. |
» A _ B (посилка) |
|
3. |
A ¡!»» A (тавтологiя) |
|
4. |
»» A (ÌÏ, 1, 3) |
|
5. |
B (ÇÄ, 2, 4) |
|
6. |
B ¡!»» B (тавтологiя) |
|
7. |
»» B (ÌÏ, 5, 6) |
|
8. |
C ¡!» B (посилка) |
|
9. |
» C (ÌÒ, 7, 8) |
¤ |
Приклад 6. Побудувати доведення теореми:
X _ Y; X ¡! Z; Y ¡! W j= Z _ W:
Доведення проводимо методом частинних випадкiв: 1. » Z (гiпотеза)
2. |
X ¡! Z (посилка) |
|
|
3. |
» X |
(ÌÒ, 1, 2) |
|
4. |
X _ Y |
(посилка) |
|
5. |
Y (ÇÄ, 3, 4) |
|
|
6. |
Y ¡! W (посилка) |
|
|
7. |
W (ÌÏ, 5, 6) |
¤ |
|
17
1.3Рiвносильнiсть формул логiки висловлень. Нормальнi форми
Визначення рiвносильностi формул. Список основних рiвносильностей. Елементарнi кон'юнкцi¨ та диз'юнкцi¨. Нормальнi форми. Досконалi нормальнi форми. Теореми про зображення булевих функцiй за допомогою досконалих нормальних форм. Релейно-контактнi схеми.
1.Нехай A i B ¹ двi формули логiки висловлень. Будемо казати, що вони рiвносильнi i позначати цей факт A ´ B, якщо i тiльки якщо для довiльного розподiлу iстинностних
значень логiчних змiнних, що входять хоча б в одну з цих формул, данi формули приймають однаковi iстинностнi значення. Наприклад, покажемо, що формула » p _ q
рiвносильна формулi p ¡! (q _ s) ^ (s ¡! q).
p q s 
» p » p _ q 
q _ s s ¡! q (q _ s) ^ (s ¡! q) p ¡! (q _ s) ^ (s ¡! q)
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
В таблицi ми бачимо, що стовпцi, якi вiдповiдають даним формулам однаковi, що означа¹ Рiвносильнiсть формул. Неважко також бачити, що вiдношення рiвносильностi мiж формулами ¹ вiдношення еквiвалентностi, тобто воно рефлексивне, симетричне i транзитивне.
Теорема 6. Для довiльних формул A i B логiки висловлень A ´ B òîäi i òiëüêè òîäi, êîëè j= A Ã! B.
Доведення. Дiйсно, для довiльного розподiлу iстинностних значень логiчних змiнних, що входять хоча б в одну з формул A; B (тобто якi входять в формулу
A Ã! B), формули A i B приймають однаковi значення, тобто jAj = jBj, що означа¹ згiдно означення еквiвалентностi, що jA Ã! Bj = 1. Таким чином, j= A Ã! B. ¤
Теорема 7. Якщо формули A, B, C, D òàêi, ùî A ´ B i D отриму¹ться з формули C пiдстановкою B замiсть одного або бiльшого числа входжень A, òî C ´ D.
Доведення теореми очевидне.
Òåîðåìà 8. В логiцi висловлень мають мiсце такi рiвносильностi: 1. A ´ A закон подвiйного заперечення, 6
2. (AB)C ´ A(BC) асоцiативнiсть кон'юнкцi¨, 7
6 Нагада¹мо, що A означа¹ » A.
7 AB означа¹ кон'юнкцiю A ^ B.
18
3. (A _ B) _ C ´ A _ (B _ C) асоцiативнiсть диз'юнкцi¨, 4. AB ´ BA комутативнiсть кон'юнкцi¨,
5. A _ B ´ B _ A комутативнiсть диз'юнкцi¨, 6. AA ´ A iдемпотентнiсть кон'юнкцi¨,
7. A _ A ´ A iдемпотентнiсть диз'юнкцi¨,
8. A(B _ C) ´ AB _ AC перший закон дистрибутивностi,
9. A _ BC ´ (A _ B)(A _ C) другий закон дистрибутивностi, 10. AB ´ A _ B перший закон де Моргана,
11. A _ B ´ A B другий закон де Моргана, 12. A ¡! B ´ A _ B,
13. A Ã! B ´ (A ¡! B)(B ¡! A),
14. A _ A ´ 1 закон виключеного третього, 15. A A ´ 0 закон протирiччя,
16. A 1 ´ A, A _ 1 ´ 1, A 0 ´ 0, A _ 0 ´ A дi¨ з константами, 17. A ¡! B ´ B ¡! A закон контрапозицi¨.
Рiвносильностi 1 17 доводяться за допомогою таблиць iстинностi i |
|||||||||||||||||||||||||||||||||||||||||
використовуються для спрощення формул логiки висловлень. |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
Приклад 1. Спростити формулу (A ¡! B)(A _ BC)(A ¡! C) _ |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
C: |
|
||||||||||||||||||||||||||||||||||||||||
Ìà¹ìî |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
(A ¡! B)(A _ BC)(A ¡! C) _ C ´ (A _ B)(A _ BC)(A ¡! C) _ C ´ |
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
´ (A _ B)(A _ BC)(A _ C) _ C ´ (A _ B)(A _ C)(A _ BC) _ C ´ |
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
16 |
|
|
|
|
|
|
||||
´ (A _ BC)(A _ BC) _ C ´ (AA _ BC) _ C ´ (0 _ BC) _ C ´ |
|
||||||||||||||||||||||||||||||||||||||||
|
|
9 |
|
|
|
|
14 |
|
|
|
16 |
|
|
5 |
|
|
12 |
|
|
|
|
|
|
¤ |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
´ BC _ C ´ (B _ C)(C _ C) ´ (B _ C) 1 ´ B _ C ´ C _ B ´ C ¡! B: |
|||||||||||||||||||||||||||||||||||||||||
2. Елементарною кон'юнкцi¹ю назива¹ться кожна кон'юнкцiя скiнченного числа попарно рiзних логiчних змiнних, взятих iз запереченням або без нього. Наприклад, xyz, xyz¹ u¹, x1x¹2x¹3x¹4x5 ¹ елементарнi кон'юнкцi¨, а xxy¹ , xyzy¹ такими не будуть.
Елементарною диз'юнкцi¹ю назива¹ться диз'юнкцiя скiнченного числа попарно рiзних логiчних змiнних, взятих iз запереченням або без нього. Наприклад, x _ y _ z, x¹ _ y _ z¹,
x1 _ x¹2 _ x3 _ x¹4, à x _ y _ x¹ вже не ¹ елементарною диз'юнкцi¹ю.
19
Зафiксу¹мо деяку множину X логiчних змiнних. Елементарнi кон'юнкцi¨, якi мiстять всi змiннi з X, будемо називати конституентами одиницi над X,
вiдповiдно елементарнi диз'юнкцi¨, якi задовольняють подiбну властивiсть, назвемо
конституентами нуля над X. Наприклад, якщо X = fx; y; z; ug, òî xyz¹ u¹, xyzu¹
конституенти одиницi над X, x¹ _ y _ z _ u¹ конституента нуля над X. Неважко
бачити, що кожна конституента одиницi (вiдповiдно, конституента нуля) тiльки на одному, ¹диному для не¨, двiйковому наборi прийма¹ значення 1 (вiдповiдно, значення
0). В цьому випадку говорять, що конституента вiдповiда¹ даному двiйковому набору. Наприклад, якщо X = fx; y; zg, òî xy¹z¹ вiдповiда¹ двiйковому набору (1; 0; 0), xyz¹ набору (0; 1; 1), x _ y _ z¹ âiäïîâiä๠(0; 0; 1), à x¹ _ y _ z (1; 0; 0).
Означення 4 Диз'юнктивною (кон'юнктивною) нормальною формою назива¹ться диз'юнкцiя (кон'юнкцiя) скiнченного числа попарно рiзних елементарних кон'юнкцiй (диз'юнкцiй).
Наприклад, xy_x¹_yz¹_yzu, xyz¹_u ¹ диз'юнктивнi нормальнi форми (скорочено ДНФ), а (x_y)(¹x_u¹_z), (x_y¹_z)x кон'юнктивнi нормальнi форми (скорочено КНФ). Надалi
елементарнi кон'юнкцi¨ в ДНФ будемо називати доданками, а елементарнi диз'юнкцi¨¨ в КНФ множниками.
ДНФ (КНФ) назива¹ться досконалою, якщо всi ¨¨ доданки (множники) ¹ конституенти одиницi над множиною всiх ¨¨ логiчних змiнних. Досконалу ДНФ (КНФ) ми будемо скорочено позначати як ДДНФ (ДКНФ). Наприклад, xyz¹ _ xy¹ z¹ ¹ ÄÄÍÔ,
à (x _ y¹ _ z)(x _ y _ z¹)(¹z _ y¹ _ z¹) ДКНФ. Вiдмiтимо, що за допомогою очевидно¨
рiвносильностi
(1.3.1)
äå A довiльна формула, а x логiчна змiнна, кожна ДНФ може бути зведена до ДДНФ, а з допомогою рiвносильностi
(A _ x)(A _ x¹) ´ A |
(1.3.2) |
кожна КНФ може бути зведена до ДКНФ.
Приклад 2. Звести формулу xy _ xz¹ äî ÄÄÍÔ.
Ма¹мо, згiдно формули (1.3.1): xy _ xz¹ ´ xyz _ xyz¹ _ xz¹ ´ xyz _ xyz¹ _ xyz¹ _ xy¹z¹ ´
xyz _ xyz¹ _ xy¹z:¹ |
¤ |
Приклад 3. Звести формулу (x _ y)y äî ÄÊÍÔ. |
|
Згiдно формули (1.3.2) ма¹мо: (x _ y)y ´ (x _ y)(x _ y)(¹x _ y) ´ (x _ y)(¹x _ y): |
¤ |
На завершення вiдмiтимо, що ДДНФ тавтологi¨, що буде доведено пiзнiше, мiстить точно 2n доданкiв, де n число всiх логiчних змiнних дано¨ тавтологi¨. Це да¹ нам ще
один спосiб перевiрки формули на тавтологiчнiсть. Наприклад, доведемо, що формула x(x ¡! y) ¡! y ¹ тавтологiя. Отже, ма¹мо: x(x ¡! y) ¡! y ´ x(¹x _ y) ¡! y ´
x(¹x _ y) _ y ´ x¹ _ x¹ _ y _ y ´ x¹ _ xy¹ _ y ´ xy¹ _ x¹y¹ _ xy¹ _ y ´ xt¹ _ x¹y¹ _ xy¹ _ xy _ xy¹ ´
20