Метод Квайна мінімізації логічних функцій

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

Крок 1. Перетворюють ДДНФ (ДКНФ) логічної функції у СДНФ (СКНФ), базуючись на теоремі Квайна (теорема 2.1, приклади 2.19, 2.20).

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

Крок 3. Визначають перелік конституент одиниці (нуля), які не покриваються ядерними імплікантами (імпліцентами). Поняття “покриття” пояснюється при розгляді наступних прикладів. Якщо таких конституент немає або налічує тільки одна неядерна імпліканта (імпліцента), то тупикова ДНФ (КНФ) є єдиною і мінімальною. У першому випадку складовими мінімальної ДНФ (КНФ) є тільки всі ядерні імпліканти (імпліценти), а у другому випадку – всі ядерні та едина неядерна імпліканти (імпліценти).

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

Крок 4. Складають формули всіх тупікових ДНФ (КНФ) і вибірають з них мінімальну за кількістю символів.

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

Для кожної конституенти перевіряється, чи є вона такою, що покривається тільки одною імплікантою. З таблиці 2.9 бачимо, що такими є конституенти Ù Ù Ùx₄, Ù Ùx₃Ùx₄, Ùx₂Ù Ùx₄ та x₁Ùx₂Ù Ù Імпліканти Ùx₄ та x₁Ùx₂Ù , що покривають ці конституенти, називають ядерними, вони складають “ядро” імплікант.

Крок 3. У нашому прикладі ядерні імпліканти покривають всі конституенти одиниці, крім x₁Ùx₂Ùx₃Ùx₄. Ця конституента має покриватися одною із двох неядерних імплікант: x₁Ùx₂Ùx₃ або x₂Ùx₃Ùx₄. Це означає, що кількість тупикових ДНФ дорівнює 2.

У загальному випадку, коли кількості неядерних імплікант і конституент, що не покриваються ядерними імплікантами, більше одиниці, для виявлення варіантів покриття цих конституент зручно скористатися скороченою (спрощеною) імплікантною таблицею. Складання скороченої імплікантної таблиці (табл. 2.10) здійснюється шляхом видалення із повної імплікантної таблиці (табл.2.9) рядків, що відповідають імплікантам ядра, і стовпців, що відповідають конституентам одиниці, які покриваються імплікантами ядра.

У цьому прикладі побудова скороченої імплікантної таблиці не є необхідною. Ми навели таблицю 2.10 лише для ілюстрації принципів складання таких таблиць.

Крок 4. Очевидно, що логічна сума всіх ядерних імплікант має бути складовою частиною будь-якої тупикової ДНФ. Додаваючи до неї варіативно кожну з імплікант x₁×x₂×x₃ і x₂×x₃×x₄, одержимо формули тупикових ДНФ: f(x₁,x₂,x₃,x₄) = Ùx₄Úx₁Ùx₂Ùx₃Úx₁Ùx₂Ù ; (2.14) f(x₁,x₂,x₃,x₄) = Ùx₄Úx₁Ùx₂Ù Úx₂Ùx₃Úx₄. (2.15)

Обидві тупикові функції (2.14) і (2.15) мають однакову кількість символів (букв, знаків диз’юнкції, кон’юнкції та заперечення), тому будь-яка з них може бути прийнятою за мінімальну (ще одна особливість даного прикладу).

Формалізацію метода Квайна, орієнтовану на можливість програмної реалізації процедур мінімізації логічних функцій, запропонував Мак-Класкі. Формалізація полягає в тому, що у формулі елементарної кон’юнкції (диз’юнкції) змінна без заперечення (із запереченням) замінюється числом 1 (0), а змінна із запереченням (без заперечення) – числом 0 (1), на місцях відсутніх змінних ставляться дефіси (таку формалізацію ми вже застосовували у прикладі 2.14). Такі позначення елементарних кон’юнкцій (диз’юнкцій) називаються узагальненими кодами. У прикладі 2.23 таблиця 2.9 з формалізованими за Мак-Класкі позначеннями конституент одиниці та простих імплікант матиме вигляд таблиці 2.11. По суті, позначення конституент одиниці заміняються двійковими номерами наборів, на яких ці конституенти мають значення 1, а в позначеннях простих імплікант дефісами позначаються ліквідовані розряди наборів, відповідних конституентам, що покриваються цими імплікантами.

Помітимо, що напис функцій (2.12) і (2.13) також може бути подано в узагальнених кодах (читач може зробити це самостійно, за аналогією з прикладом 2.14).

На підставі таблиці 2.11 одержуються тупикові ДНФ в узагальнених кодах: f(x₁,x₂,x₃,x₄) = 0--1Ú111-Ú11-0; (2.16) f(x₁,x₂,x₃,x₄) = 0--1Ú11-0Ú-111. (2.17)

Шляхом переходу від узагальнених кодів до позначень змінних буквами із (2.16) і (2.17) одержуються, відповідно, функції (2.14) і (2.15).