borisenko_o_a_diskretna_matematika

Борисенко О.А.

Відповідь. Імплікантою є функція ер, оскільки вона дорівнює нулю на тих наборах, де функція Р також дорівнює нулю. Функція 2 не є імплікантою функції Р, оскільки на наборі 4 функція 2 = 1, а функція Р = 0.

лише на одному наборі змінних. А оскільки ДДНФ логічної функції Р складається з диз'юнкції конституент одиниці, то одиничне значення будь-якої конституента одиниці, що належить до ДДНФ, збігається з одним із значень одиниці логічної функції Р. Решта значень конституенти одиниці, як відомо, буде дорівнювати нулю. Тобто неможливо, щоб імиліканга набула значення одиниці, а відповідне їй значення функції дорівнювало нулю. Тому конституента одиниці, що належить до ДДНФ, є її імплікантою.

Теорему доведено.

Теорема 2. Константа нуля є імплікантою будь-якої логічної функції.

Доведення. Дійсно, функція константа нуля за означенням дорівнює нулю на всіх її можливих наборах значень, і тому обов'язково дорівнює нулю на всіх тих наборах, на яких функція Р дорівнює нулю. Цього досить для того, щоб константа нуля мала всі ознаки імпліканти.

Теорему доведено.

Кожна логічна функція є імплікантою самої себе. Це випливає з того, що ця функція збігається сама з собою й, відповідно, дорівнює нулю на тих наборах значень, де вона вже дорівнювала нулю раніше ще до того, як проводився її аналіз щодо належності до імпліканти, і ніде не дорівнює одиниці, де функція дорівнює нулю. Саме це і є ознакою імпліканти.

Теорема 3. Будь-яка логічна функція є імплікантою константи одиниці.

Доведення. Константа одиниці не дорівнює нулю на жодному наборі. Це означає, що в будь-якої логічної функції, на яких наборах не стояли б у неї одиниці, існуватиме відповідність її одиничних

82

Дискретна математика

значень до одиничних значень константи одиниці, і ніде не можливий набір, для якого логічна функція дорівнюватиме одиниці, а константа одиниці в цей час дорівнюватиме нулю.

Теорему доведено.

2. Прості імпліканти

Означення 2. Елементарний добуток, одержаний шляхом виключення з початкового добутку однієї або кількох змінних, називається власною частиною останнього.

Приклад 2. Нехай елементарний добуток - хуг. Тоді його власними частинами будуть добутки

ху, уг, хг, х, у, г.

Означення 3. Елементарні добутки, які самі належать даній функції в ДДНФ, але ніяка їх власна частина самостійно їй не належить, називаються простими імплікантами.

Приклад 3. Припустимо, що добугки (р ~~ш Х^Х-уХ^Хл 1 X-}X^

самостійно до неї не входять. Тоді добуток х2 х4 буде простою імплікантою функції Р, оскільки х2х4 с ер с. Р , а х2 <Х Р і х4 <£ Р. Разом з тим добуток (р не буде простою імплікантою, оскільки його власна частина х2х4 с Р.

Якщо добуток належить даній функції, то з появою в ньому додаткових змінних новий добуток також буде належати цій функції, оскільки він перетворюється на нуль завжди, коли вихідний добуток дорівнює нулю, незалежно від того, дорівнюють чи не дорівнюють нулю додаткові змінні. Це випливає з того, що добуток 0 з будь-якою змінною дорівнює 0.

3. Подання логічних функцій у скорочених ДНФ

Означення 4. Диз'юнкція простих імплікант називається

скороченою ДНФ.

83

Борисенко О.А.

Теорема 4. Будь-яку логічну функцію Р можна подати у вигляді скороченої ДНФ, тобто диз 'юнкції простих імплікант.

Доведення. Оскільки прості імпліканти належать самостійно функції Р, то вони повинні дорівнювати нулю на тих самих наборах, що й функція Р. Якщо це не так і проста імпліканта дорівнює одиниці

знайтись хоча б одна проста імпліканта, що дорівнює одиниці, інакше

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

Це означає, що функція Р після всіх можливих поглинань врешті-решт буде складатися з одних простих імплікант.

Теорему доведено.

З метою подання логічної функції Р у вигляді скороченої ДНФ розглянемо операції повного і неповного склеювання, а також поглинання і розгортання в ДНФ.

Операція повного склеювання визначається співвідношенням

ху V ху = X.

Це випливає з того, що

ху V ху = х(у V у) = X А 1 = X

Склеювання добутків ху і ху відбувається в цьому разі за змінною у.

Операція неповного склеювання має вигляд:

ху V ху - X V ху V ху.

84

Дискретна математика

Це можливе тому, що логічне додавання змінної х з виразом ху V ху ніяк не впливає на останній. Він залишається незмінним, скільки б разів змінна х до нього не додавалась.

Операція поглинання визначається з рівностей

XV ху = X І XV ху —х.

У цьому випадку х поглинає весь вираз. Це випливає з того, що

X V ху = X (1 V у) = X.

Відповідно

X V ху = X ( 1 V у ) = X.

Оскільки далеко не завжди вихідна логічна функція подається в ДДНФ, розглянемо операцію її розгортання. Вона перетворює будьяку просту імпліканту в диз'юнкцію конституент одиниці.

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

цього одержимо ДДНФ вихідної логічної функції.

Від часів греків говорити "математика" означає говорити "доведення".

Н. Бурбакі

85

Борисенко О.А.

Лекція 14 ДОСКОНАЛІ КОН'КЖТИВНІ НОРМАЛЬНІ ФОРМИ

1. Елементарні суми Означення 1. Логічна сума кількох різних змінних, узятих із

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

Теорема 1. Елементарна сума, або диз'юнкція, дорівнює нулю тоді і лише тоді, коли її змінним із запереченням присвоєна одиниця, а змінним без заперечення - нуль.

Доведення теорем туг і в лекції 15 не подаються, оскільки вони аналогічні доведенням відповідних теорем у лекціях 13, 14.

Наслідок. Кожній елементарній сумі відповідає один і лише один набір значень змінних, що належать до неї, на якому вона дорівнює нулю.

86

Дискретна математика

2. Конституенти нуля

Означення 3. Логічна функція п змінних, що приймає значення, яке дорівнює нулю, лише на одному їх наборі, називається

констшпуентою нуля.

Теорема 3. Елементарна сума (диз'юнкція) усіх п змінних, що належать до функції Р, є конституентою нуля.

Теорема 4. Число конституент нуля п змінних дорівнює 2".

Згідно з теоремою 1, щоб подати конституенту нуля від п змінних, що дорівнює 0 на т-му наборі, погрібно подати число т у вигляді «-розрядного двійкового числа і в диз'юнкції всіх змінних узяти із запереченням лише ті змінні, яким у двійковому числі відповідають одиниці.

Приклад 3. Записати конституенту нуля 17-го набору. Розв'язання. Подамо десяткове число 17 у двійковому вигляді:

1 7 ^ = 10001^. Запишемо диз'юнкцію 5 змінних: х: V х2 V х3 V х4 V х5.

Візьмемо із запереченням ті змінні, яким у двійковому коді відповідають одиниці: х, V х2 V х} V х4 V х5. Одержаний результат с конституентою нуля 17-го набору.

3. Подання логічних функцій у ДКНФ

Означення 4. Кон'юнкція конституент нуля, що дорівнює нулю на тих самих наборах, що й задана функція, називається досконалою конюнктивною нормальною формою (ДКНФ) логічної функції.

Теорема 5. Будь-яка логічна функція, крім конституенти одиниці, може бути подана в ДКНФ, до того ж єдиним способом.

Виходячи з теореми 5, розглянемо алгоритм подання логічних функцій в ДКНФ.

З цією метою треба скласти добуток тих конституент нуля, що дорівнюють нулю на тих самих наборах, що й задана функція, за таким алгоритмом:

а) виписати за числом нулів у логічній функції диз'юнкції всіх аргументів від першого до п-го й по'єднати їх знаками кон'юнкції;

87

Борисенко О.А.

б) записати під кожним аргументом його значення у відповідному до даного добутку наборі, яке дорівнює одиниці або нулю, і над аргументами, що дорівнюють одиниці, поставити знаки заперечення.

Даний алгоритм носить назву запису логічної функції в досконалій кон'юктивній нормальній формі або за нулями.

Приклад 4. Подати у ДКНФ логічну функцію п'яти аргументів Р = Р(хі, Хг, ху, х4, х5), що дорівнює нулю на наборах з номерами 5, 14, 16, 31 і одиниці - на решті наборів.

Розв'яжемо цю задачу за наведеним вище алгоритмом:

1. Випишемо чотири суми аргументів і поєднаємо їх знаками

2. Під кожною сумою поставимо подані у двійковому вигляді числа 5, 14, 16, 31 і розставимо заперечення над змінними, які відповідають одиниці.

Тоді отримаємо ДКНФ

У математиці сила невідомого незмірна.

Наполеон

88

Дискретна математика

Лекція 15 СКОРОЧЕНІ КОН'ЮНКТИВНІ НОРМАЛЬНІ ФОРМИ

1. Імпліценти логічної функції

ДКНФ є найбільш загальною формою подання логічної функції у кон'юнктивній формі і тому містить найбільше можливе кількість літер. Розглянемо питання зменшення їх числа.

Означення 1. Якщо деяка логічна функція ер (в окремому випадку - елементарна сума) дорівнює одиниці на всіх тих наборах, на яких дорівнює одиниці інша функція Р, то функція <р називається імпліцентою функції Р. Кажуть, що функція ер належить функції Р. При цьому функція (р може дорівнювати одиниці і на тих наборах, на яких Р = 0, але не навпаки - не може дорівнювати нулю на наборах, де функція Р дорівнює одиниці.

Приклад 1. У в табл. 2.21 подані функції

Р = Р (х,, х2, х3), ер = <р (х,, х2, х3), 2 = 2(хі,Х2, ХЗ).

Відповідь. Ані функція ір, ані функція 2 не є імпліцентами функції Р, оскільки перша дорівнює нулю на наборах 2 і 6, а друга - на наборах 0, 2, 3 і 6. На цих наборах функція Р дорівнює одиниці, що суперечить означенню імпліценти.

89

Борисенко О.А.

Теорема 1. Будь-яка конституента нуля, що належить до ДКНФ логічної функції Р, є її імпліцентою.

2. Прості імпліценти Означення 2. Елементарна сума, одержана виключенням з

вихідної суми однієї або кількох змінних, називається власною частиною останньої.

Приклад 2. Нехай є елементарна сума х + у+г. Тоді її власними частинами будуть суми:

х + у; у+ х + г; х; у; г.

Означення 3. Елементарні суми, які самі належать даній функції, але жодна їх власна частина не належить, називається

простими імпліцентами.

Приклад 3. Припустимо, що сума (р = х\ + х2 + х3 + х4 і її частина х2 + х4 належать як самостійні члени функції Р = Р (х\, х2, х}, х4), а змінні х2 і х4 не належать. Тоді сума х2 + х4 буде простою імпліцентою функції Р, оскільки (х2 + х4) с <р с Р, а хг ф Р і х4 Р. У той же самий час сума <р не буде простою імпліцентою, оскільки (х2 + Х 4 ) с Р.

Якщо будь-які елементарні суми належать даній функції, то при додаванні до них будь-яких змінних нова сума також буде належати цій функції, оскільки вона перетворюється в одиницю разом з початковою сумою.

3. Подання логічних функцій у скорочених КНФ Означення 4. Кон'юнкція простих імпліцент називається

скороченою КНФ.

90

Дискретна математика

Теорема 4. Будь-яку логічну функцію Р можна подати у вигляді скороченої КНФ, тобто кон'юнкції простих шпліцент.

З метою подання логічної функції Р у вигляді скороченої КНФ розглянемо операції повного і неповного склеювання, а також поглинання і розгортання в КНФ.

Операція повного склеювання визначається співвідношенням

(х + у)(х + у) = х.

Це випливає з того, що

(х + у)(х +-у) = х + ху + ху + уу = X + х(у + V) = X.

Склеювання сум х + у і х + у відбувається в цьому випадку за змінною у.

Операція неповного склеювання мас вигляд

(х + у)(х + у) - х{х + у)(х + у).

Операція поглинання визначається з рівностей х(х + у) = х і х(х + у)- х. У цьому випадку х поглинає весь вираз. Це випливає з того, що х(х + у) = х + ху = х(1 + у) = х.

Відповідно

х(х + у) = х + ху = х(1 + у) = X.

Операція розгортання перетворює будь-яку просту імпліценту в диз' юнкцію конституент нуля.

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

X + у = (х + у) + 22 = (х + у + 2)(х + у + І ) = = ((х + у + г) + ий)фс + у + І ) + ии) =

= (х + у + 2 + и) (х + у + г + її) (х + у + 1 + и)(х + у +1 + її).

91