Подання логічних функцій нормальними формами

Приклад 2.7 засвідчує, що одну й ту саму ЛФ описують різні логічні вирази (формули). У загальному випадку, зробивши низку еквівалентних перетворень деякої ЛФ згідно з законами алгебри логіки, можна дістати різні подання цієї ЛФ, наприклад:

= .

Тому, розглядаючи низку ЛФ, треба переконатися в тому, що вони відрізняються одна від одної, аби не виконувати непотрібної роботи. У зв’язку з цим постає потреба вибирати таку форму зображення логічних функцій, коли кожній функції відповідатиме одна і тільки одна формула і навпаки, кожній формулі має відповідати єдина Лф. Такі форми зображення логічних функцій називають канонічними (стандартними).

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

Означення 2.12. Логічний добуток будь-якого скінченного числа змінних, взятих із запереченням чи без нього не більш як один раз, називається елементарною кон’юнкцією (елементарним добутком).

Наприклад, логічні добутки є елементарними кон’юнкціями, а , – ні.

Означення 2.13. Логічна функція, що подається диз’юнкцією елементарних кон’юнкцій, називається диз’юнктивною нормальною формою (ДНФ).

Наприклад, функція є диз’юнктивною нормальною формою.

Означення 2.14. Логічна сума будь-якого скінченного числа змінних, взятих із запереченням чи без нього не більш як один раз, називається елементарною диз’юнкцією (елементарною сумою).

Наприклад, логічні суми є елементарними диз’юнкціями, а , – ні.

Означення 2.15. Логічна функція, що подається кон’юнкцією елементарних диз’юнкцій, називається кон’юнктивною нормальною формою (КНФ).

Наприклад, функція є кон’юнктивною нормальною формою.

Означення 2.16. Розв’язуваною називається формула, яка не є тотожно хибною або тотожно істинною.

Елементарні кон’юнкції (диз’юнкції) завжди розв’язу-вані. Це забезпечується тим, що в них кожна змінна зустрічається лише один раз, із запереченням або без нього (немає випадків одночасної наявності змінної та її інверсії). Унаслідок цього жодна елементарна кон’юнкція (диз’юнкція) у ДНФ (КНФ) не може бути тотожно хибною (істинною) і тому не може бути виключеною із числа доданків (співмножників) без порушення умови рівносильності вихідної ЛФ та перетвореної у ДНФ (КНФ).

Як відмічалося вище, можна будь-яку логічну формулу перетворити в інші, рівносильні формули. Аналогічно, будь-яку ЛФ можна подати різними, рівносильними ДНФ і КНФ. Це означає, що поданням ЛФ у вигляді ДНФ або КНФ однозначність нормальних форм ще не досягається. Способом вирішення цієї проблеми є приведення ДНФ (КНФ) до стандартної (канонічної) форми. Такі стандартні форми подання ЛФ називають досконалими.

Означення 2.17. Упорядкована множина (кортеж) аргументів логічної функції називається її базою.

Означення 2.18. Рангом елементарної кон’юнкції або диз’юнкції називають кількість змінних, які вона містить.

Очевидно, максимальне значеня рангу елементарної кон’юнкції (диз’юнкції) дорівнює кількості аргументів ЛФ.

Означення 2.19. Якщо в елементарну кон’юнкцію (диз’юнкцію) входить кож­на змінна із бази логічної функції, причому лише один раз, то во­на називається конституентою одиниці (нуля).

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

Конституента одиниці j приймає значеня 1 лише у тому випадку, коли в ній всі змінні без заперечення та з запереченням мають значення, відповідно, 1 та 0. Враховуючи, що серед 2ⁿ наборів логічної функції n змінних немає однакових, можемо стверджувати, що тільки на одному з цих наборів j =1. На всіх інших наборах буде j =0, оскільки серед співмножників кон’юнкції j буде не менше одного зі значенням 0.

З іншого боку, кожний з наборів однозначно задає відповідну до нього конституенту одиниці j, яка має значення 1 на даному наборі за умови, що значенню 1 (0) змінної x_i , iÎ{1, …, n} у даному наборі відповідає змінна x_i ( ) в кон’юнкції j. Побудована за таким правилом кон’юнкція j є єдиною, що має значення 1 на даному наборі. Всі інші кон’юнкції, які можна скласти з n змінних, відрізняються від кон’юнкції j наявністю змінної x_i замість або замість x_i , принаймі для одного iÎ{1, …, n}. внаслідок цього конституента одиниці j¢, що відмінна від конституенти j, на даному наборі, буде мати значення 0, оскільки вона містить принаймі один співмножник зі значенням 0.

Проведемо аналогічні міркування щодо властивостей конституент нуля. Конституента нуля y приймає значення 0 лише у тому випадку, коли в ній всі змінні без заперечення та з запереченням мають значення, відповідно, 0 та 1. Тому тільки на одному з 2ⁿ наборів логічної функції n змінних виконуються умови рівності y =0. На всіх інших наборах буде y =1, оскільки серед доданків диз’юнкції y буде не менш одного зі значенням 1. Кожний з 2ⁿ наборів однозначно задає відповідну до нього конституенту нуля y, яка має значення 0 на даному наборі за умови, що значенню 0 (1) змінної x_i , iÎ{1, …, n} у даному наборі відповідає змінна (x_i) в диз’юнкції y. Побудована за таким правилом конституента нуля y є єдиною, що має значення 0 на даному наборі. Всі інші диз’юнкції, які можна скласти з n змінних, відрізняються від диз’юнкції y наявністю змінної x_i замість або замість x_i , принаймі для одного iÎ{1, …, n}. внаслідок цього конституента нуля y¢, що відмінна від конституенти y, на даному наборі буде мати значення 1, оскільки вона містить принаймі один доданок зі значенням 1.

З наведених прикладів легко помітити, що конституенти одиницы та нуля, пов’язані відношенням взаємної однозначності з одним набором, взаємно інверсні (читачеві рекомендується довести цей факт за допомогою законів де Моргана).

Отже, кожному із 2ⁿ наборів логічної функції n змінних відповідає єдина конституента одиниці (нуля), що має значення 1 (0) на даному наборі, і навпаки, будь-якій з конституент одиниці (нуля) відповідає єдиний із 2ⁿ наборів, на якому ця конституента має значення 1 (0). Це означає, що існує взаємно-однозначна відповідність між кожним набором логічної функції і конституентою одиниці (нуля), що має на даному наборі значення 1 (0). Відношення взаємної однозначності між конституентою одиниці (нуля) та єдиним набором (x₁…x_n) логічної функції n змінних забезпечується тим, що в цієї конституенті всі змінні без заперечення та з запереченням пов’язані з даним набором таким правилом: у конституенті одиниці (нуля) значенню 1 змінної x_i, iÎ{1, …, n} даного набора відповідає змінна x_i ( ), а значенню 0 змінної x_i – змінна (x_i).

Оскільки розв’язувана ЛФ не є тотожно хибною або істинною (як це відмічалося вище), то очевидно, що вона приймає кожне зі значень 1 і 0 не менш як на одному з наборів її аргументів. Це означає, враховуючи взаємно-однозначну відповідність між наборами ЛФ і конституентами одиниці (нуля), які мають на цих наборах значення 1 (0), що кількість конституент одиниці (нуля) строго дорівнює кількості наборів, на яких ЛФ приймає значення 1 (0). Ця обставина наводить на думку про те, що згадану вище стандартизацію виду ДНФ (КНФ) буде досягнено, якщо цю нормальну форму подати у вигляді логічної суми (логічного добутку) всіх її конституент одиниці (нуля).

Означення 2.20. Логічна функція, що подається диз’юнкцією всіх її конституент одиниці, називається досконалою диз’юнктивною нормальною формою (ДДНФ).

Наприклад, функція трьох аргументів, яка приймає значення 1 тільки на наборах (100), (001) та (111), є досконалою ДНФ.

Формула логічної функції у вигляді ДДНФ містить всі ті і тільки ті доданки, які є конституентами одиниці цієї функції, надлишкових доданків немає. Цим гарантується можливість подання у ДДНФ будь-якої ЛФ, крім функції “Константа нуль” (див. п. 2.4), тому що остання має значення 0 на всіх наборах.

Якщо при поданні ЛФ у вигляді ДДНФ задати будь-який набір з числа 2ⁿ наборів цієї функції, то її значення дорівнюватиме визначеному для цього набора. Правильне відтворення значень ЛФ для кожного з наборів забезпечується тим, що на наборі, якому відповідає задане значення 1 логічної функції, ДДНФ обов’язково містить один з доданків зі значенням 1, а на наборі, якому відповідає задане значення 0 логічної функції, всі доданки мають значення 0.

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

Наприклад, досконалою КНФ є функція трьох аргументів , яка приймає значення 0 тільки на наборах (011), (110) та (000).

Формула логічної функції у вигляді ДКНФ містить всі ті і тільки ті співмножники, які є конституентами нуля цієї функції, надлишкових співмножників немає. Цим гарантується можливість подання у ДКНФ будь-якої ЛФ, крім функції “Константа одиниця” (див. п. 2.4), тому що остання має значення 1 на всіх наборах.

Правильне відтворення значень ЛФ для кожного з наборів забезпечується тим, що на наборі, якому відповідає задане значення 0 логічної функції, ДКНФ обов’язково містить один з співмножників зі значенням 0, а на наборі, якому відповідає задане значення 1 логічної функції, всі співмножники мають значення 1.

Саме ДДНФ і ДКНФ вважаються стандартними формами аналітичного подання логічних функцій. Підкреслимо основні властивості ДДНФ (ДКНФ): у ній немає двох однакових доданків (співмножників); жодний доданок (співмножник) не містить двох однакових співмножників (доданків); жодний доданок (співмножник) не містить деякої змінної разом з її запереченням; кожен доданок (співножник) містить в якості співмножників (доданків) всі аргументи ЛФ, деякі або всі з котрих можуть бути із запереченням.

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

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

Вихідна ЛФ не завжди подається у ДНФ або КНФ. У таких випадках ЇЇ перетворюють у ДНФ або КНФ, використовуючи закони алгебри логіки, що не викликає складнощів. Наступним кроком є виконання операції розгортання отриманої ДНФ (КНФ), результатом якої буде одержання ДДНФ (ДКНФ) вихідної ЛФ. Операція розгортання елементарної кон’юнкції (диз’юнкції) дозволяє перетворити її у диз’юнкцію (кон’юнкцію) повних кон’юнкції (диз’юнкції), які є конституентами одиниці (нуля), якщо перетворенню піддається ДНФ (КНФ). Розглянемо сутність операцій розгортання елементарних кон’юнкції та диз’юнкції на наступних прикладах.

ДДНФ і ДКНФ є найбільш застосовними аналітичними формами подання ЛФ. Однак, вони містять найбільш можливе число символів у їхньому напису. Розглянувши ДДНФ і ДКНФ одної ЛФ, треба з’ясувати, яка з цих форм простіше (має менше символів у формулі). Можна припустити, що коли таблиця істинності містить більше нульових значень, ніж одиничних, то ДДНФ простіше, і навпаки. Остаточний висновок можна зробити, лише спростивши ЛФ в тій чи іншій формі (якщо це виявиться можливим).

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

Означення 2.22. Якщо функція j має значення 0 (1) принаймі на тих наборах, на яких має значення 0 (1) інша функція f, то вона називається імплікантою (імпліцентою) функції f.

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

Поставимо питання: чи є конституенти одиниці (нуля) імплікантами функції f, поданої у ДДНФ (ДКНФ)? Нагадаємо, що кожна з конституент одиниці (нуля) є логічною функцією з такою ж базою, що й сама ЛФ. Конституента одиниці (нуля) має значення 1 (0) тільки на одному з наборів, на яких ЛФ також має значення 1 (0), а на всіх інших наборах вона має значення 0 (1). Тому можемо стверджувати, що будь-яка конституента одиниці (нуля) логічної функції, поданої у ДДНФ (ДКНФ), є імплікантою (імпліцентою) цієї ЛФ. Більш того, всі доданки ДДНФ (конституенти одиниці) є імплікантами, а всі співмножники ДКНФ (конституенти нуля) є імпліцентами вихідної ЛФ.

Вихідну ЛФ можна подати як ДНФ (КНФ), доданки (співмножники) якої є логічними функціями, що носять назву елементарної кон’юнкції (диз’юнкції). Якщо база елементарної кон’юнкції (диз’юнкції) містить не всі змінні із бази вихідної ЛФ, то ця кон’юнкція (диз’юнкція) не є конституентою одиниці (нуля). Незалежно від того, чи є елементарна кон’юнкція (диз’юнкція) конституентою одиниці (нуля), завжди знайдється такий набір (можливо, не єдиний) аргументів ЛФ, на якому ця елементарна кон’юнкція (диз’юнкція) одночасно з самою ЛФ приймає значення 0 (1). Отже, всі елементарні кон’юнкції (диз’юнкції) як доданки (сумножники) ДНФ (КНФ) є імплікантами (імпліцентами) вихідної ЛФ, поданої у ДНФ (КНФ). При цьому слід пам’ятати, що ДДНФ і ДКНФ є частковими випадками подання ЛФ у ДНФ і КНФ. Це положення ілюструють наступні приклади.

Означення 2.23. Елементарна кон’юнкція (диз’юнкція), що одержана шляхом виключення однієї або кількох змінних із вихідній кон’юнкції (диз’юнкції), називається власною частиною останньої.

Наприклад, власними частинами елементарної кон’юнкції x₁× ×x₃ будуть кон’юнкції x₁× , x₁×x₃, ×x₃, x₁, , x₃, а власними частинами елементарної диз’юнкції x₁+ +x₃ будуть диз’юнкції x₁+ , x₁+x₃, +x₃, x₁, , x₃.

Означення 2.24. Елементарні кон’юнкції (диз’юнкції), які є доданками (сумножниками) ДНФ (КНФ) за умови, що ніякі їх власні частини не є самостійними доданками (сумножниками) цієї ДНФ (КНФ), називаються простими імплікантами (імпліцентами).

Наприклад, елементарні кон’юнкції x₁× ×x₃ та x₁× є доданками деякій ДНФ, а змінні x₁ та самостійно у склад ДНФ не входять як елементарні кон’юнкції. Тоді кон’юнкція x₁× буде простою імплікантою цієї ДНФ. Разом з цим елементарна кон’юнкція x₁× ×x₃ не буде простою імплікантою, оскільки вона містить кон’юнкцію x₁× як власну частину. Аналогічно, якщо елементарні диз’юнкції x₁+ +x₃ та x₁+ є співмножниками деякої КНФ, а змінні x₁ та самостійно у склад КНФ не входять як елементарні диз’юнкції, то диз’юнкція x₁+ буде простою імпліцентою цієї КНФ. Разом з цим елементарна диз’юнкція x₁+ +x₃ не буде простою імпліцентою, оскільки вона містить диз’юнкцію x₁+ як власну частину.

Проста імпліканта (імпліцента) не склеюється (за законом неповного склеювання, табл. 2.1) з жодною іншою імплікантою (імпліцентою) у складі ДНФ (КНФ), оскільки вона не є власною частиною цих імплікант (імпліцент). Це означає, що скорочення кількості символів у ДНФ (КНФ) шляхом застосування операцій склеювання імплікант (імпліцент) неможливо, якщо вони всі є простими.

Означення 2.25. Якщо всі імпліканти (імпліценти) ДНФ (КНФ) є простими, то ця ДНФ (КНФ) називається скороченою.

Будь-яка логічна функція може бути подана у вигляді скороченої ДНФ (СДНФ) або скороченої КНФ (СКНФ). Цей факт стверджується наступною теоремою.

Теорема 2.1 (Теорема Квайна).Якщо в ДДНФ (ДКНФ) логічної функції здійснити всі операції неповного склеювання, а потім всі операції поглинання та видалення дублюючих членів, то буде одержана скорочена ДНФ (КНФ) цієї функції, тобто диз’юнкція (кон’юнкція) всіх її простих імплікант (імпліцент).

Доведення. Нехай функція f(x₁,…,x_n) подана у ДДНФ (це завжди можливо). Припустимо, що після здійснення всіх операцій неповного склеювання, а потім всіх операцій поглинання одержана ДНФ, яка містить елементарну кон’юнкцію j, яка не є простою імплікантою. Це означає, що (згідно до означення 2.25 простої імпліканти) ДНФ містить, крім імпліканти j, деяку її частину n, яка є простою імплікантою функції f, тобто ДНФ містить диз’юнкцію j+n, а імпліканта j має вигляд j=n×m, де m деяка кон’юнкція. Тоді імпліканта j, згідно до рівності j+n=n×m+n=n, поглинатиметься простою імплікантою n. Таким чином, ДНФ складатиметься тільки з простих імплікант, тобто вона буде скороченою ДНФ.

Тепер розглянемо випадок подання функції f у ДКНФ. Припустимо, що після здійснення всіх операцій неповного склеювання, а потім всіх операцій поглинання одержана КНФ, яка містить елементарну диз’юнкцію j, яка не є простою імпліцентою. Це означає, що КНФ містить, крім імпліценти j, деяку її частину n, яка є простою імпліцентою функції f, тобто КНФ містить кон’юнкцію j×n, а імпліцента j має вигляд j=n+m, де m деяка диз’юнкція. Тоді імпліцента j, згідно до рівності j×n=(n+m)×n=n, поглинатиметься простою імпліцентою n. Таким чином, КНФ складатиметься тільки з простих імпліцент, тобто вона буде скороченою КНФ. Теорему доведено.

Для одержання СДНФ (СКНФ) логічної функції, поданої в довільній ДНФ (КНФ), спочатку треба перетворити її в ДДНФ (ДКНФ) шляхом розгортання вихідної ЛФ та видалення дублюючих членів, як у прикладах 2.15 і 2.16. Після цього необхідно, згідно до методу Квайна, послідовно виконати перетворення ЛФ наступними кроками.

1) У ДДНФ (ДКНФ) логічної функції f(x₁,…,x_n) виконують всі операції неповного склеювання конституент одиниці (нуля). При цьому слід мати на увазі, що кожна конституента одиниці (нуля) може склеюватись з кількома іншими (за різними змінними), тому після першого склеювання її не поглинають, а використовують для чергових операцій склеювання (у цьому є суть операції неповного склеювання). В результаті одержана таким чином ДНФ (КНФ) містить збережені конституенти одиниці (нуля) та імпліканти (імпліценти) рангу n–1, причому серед останніх можут бути і прості імпліканти (імпліценти).

2) Виконують поглинання імплікантами (імпліцентами) всіх конституент одиниці (нуля), які брали участь у неповному склеюванні. Ці конституенти поглинаються обов’язково, оскільки кожна з них містить у своєму складі власну частину, яка дорівнює однієї з одержаних на першому кроці імплікант (імпліцент). Конституент одиниці (нуля), які не брали участь в операціях неповного склеювання, не можуть поглинатися, вони являють собою прості імпліканти (імпліценти) рангу n. Після цього проводять видалення дублюючих членів.

3) Виконують операції неповного склеювання імплікант (імпліцент) рангу n–1 і наступного їх поглинання імплікантами (імпліцентами) рангу n–2 за аналогією з операціями по кроках 1) і 2). Ця процедура повторюється з одержанням імплікант (імпліцент) низших рангів доти, поки операції неповного склеювання залишаються можливими, а після проведення операцій поглинання у формулі ДНФ (КНФ) залишаться тільки прості імпліканти (імпліценти), тобто буде одержано СДНФ (СКНФ).

Якщо вихідну ЛФ задано повною (за всіма наборами) таблицєю істинності або формулою, що дозволяє побудувати повну таблицю істинності, то ця ЛФ є повністю визначеною. У таких випадках задану ЛФ можна, шляхом відповідних перетворень, подати у ДДНФ або ДКНФ і далі одержати СДНФ або СКНФ.

При вербальному описі вихідна ЛФ може бути задана як неповністю визначена (див. означення 2.5). Приведення її до повністю визначеної здійснюється присвоєнням їй довільних значень із множини {0, 1} на тих наборах, на яких вона не визначена. Зокрема, довизначення ЛФ може бути здійснено присвоєнням ій значень 0 або 1 на всіх цих наборах, якщо ми маємо намір подати повністю визначену ЛФ відповідно у ДДНФ або ДКНФ. Після цього, з метою одержання СДНФ або СКНФ з меншою кількістю символів, можна змінити деякі значення ЛФ з числа доданих для збільшення числа склеюваних конституент, як це показано у наступному прикладі.

Досконала та скорочена нормальні форми подання логічних функцій не є единими нормальними формами. Доповнимо перелік останніх ще двома їх видами.

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

Наприклад, ЛФ (2.11) з прикладу 2.22 є тупиковою ДНФ вихідної функції (2.9). У цьому читач може переконатись шляхом проведення випробувань функції (2.11) при виключенні з неї імплікант ×x₄ та x₁×x₂×x₃.

Кількість можливих тупикових ДНФ вихідної функції (2.9) дорівнює одиниці, у чому можна переконатись, виконавши випробування СДНФ (2.10) при виключенні з неї по черзі всіх простих імплікант ×x₄, x₁×x₂×x₃ та x₂×x₃×x₄. У загальному ж випадку логічна функція може мати декілька різних тупикових нормальних форм (ДНФ і КНФ), що відрізняються кількістю символів (у п. 2.7 ми зустрінимось з такими випадками). Це означає, що існує тупикова нормальна форма (ДНФ або КНФ) логічної функції з мінімальної кількістю символів в її формулі.

Означення 2.27. Тупікова нормальна форма логічної функції, яка має мінімальну кількість символів, називається мінімальною (МДНФ, МКНФ).

При постановці задачі мінімізації кількості символів у формулі ЛФ, з метою спрощення її технічної або програмної реалізації, необхідно провести процедуру мінімізації ЛФ, базуючись на її поданні у вигляді СДНФ або СКНФ. Метод випробувань, застосований у прикладі 2.22, незручний через його трудомісткість, особливо при великої кількості простих імплікант (імпліцент) у складі СДНФ (СКНФ). Більш зручні методи мінімізації логічних функцій, які широко застосовуються на практиці, розглядаються у пп. 2.7, 2.8.