Визначення. Импликанта g булевої функції f. що є елементарною кон'юнкцією, називається простий, якщо ніяка частина імпліканти g не є импликантой функції f.
З прикладу видно, що імпліканти і. є простими импликантами функції f. Імпліканти g1. g2. g4. g6 не є простими, так як їх частини є импликантами функції f. наприклад g5 є частиною g1. Наведемо без доведення два твердження, корисні при отриманні мінімальної ДНФ.
1. Диз'юнкція будь-якого числа импликант булевої функції f також є импликантой цієї функції.
2. Будь-яка булева функція f еквівалентна диз'юнкції всіх своїх простих импликант. Така форма подання булевої функції називається скороченою ДНФ.
Перебір всіх можливих импликант для булевої функції f з розглянутого прикладу дає можливість переконатися, що простих импликант всього дві: g3 і g5 .Отже, скорочена ДНФ функції f має вигляд:
Як видно з табл. 1, імпліканти g3. g5 в сукупності покривають своїми одиницями все одиниці функції f. Отримання скорочених ДНФ є першим етапом відшукання мінімальних форм булевих функцій. Як уже зазначалося, в скорочену ДНФ входять всі прості імпліканти булевої функції. Іноді з скороченою ДНФ можна прибрати одну або кілька простих импликант, не порушуючи еквівалентності вихідної функції. Такі прості імпліканти назвемо зайвими. Виняток зайвих простих импликант зі скорочених ДНФ - другий етап мінімізації.
Визначення. Скорочена ДНФ булевої функції називається тупикової, якщо в ній відсутні зайві прості імпліканти.
Усунення зайвих простих импликант зі скороченої ДНФ булевої функції не є однозначним процесом, т. Е. Булева функція може мати кілька тупикових ДНФ.
Затвердження. Тупикові ДНФ булевої функції f. що містять мінімальну кількість букв, є мінімальними. Мінімальних ДНФ теж може бути кілька.
Розглянемо кілька методів мінімізації. Всі вони практично розрізняються лише на першому етапі - етапі отримання скороченою ДНФ. Слід зазначити, що, на жаль, пошук мінімальної ДНФ завжди пов'язаний з деяким перебором рішень. Існують методи зменшення цього перебору, проте він завжди залишається.
Метод Квайна грунтується на застосуванні двох основних співвідношень.
1. Співвідношення склеювання
де А - будь-який елементарне твір.
2. Співвідношення поглинання
Справедливість обох співвідношень легко перевіряється. Суть методу полягає в послідовному виконанні всіх можливих склеюванні і потім всіх поглинань, що призводить до скороченої ДНФ. Метод застосуємо до досконалої ДНФ. Зі співвідношення поглинання слід, що довільне елементарне твір поглинається будь-якій його частиною.
Для доказу досить показати, що довільна проста импликанта може бути отримана. Справді, застосовуючи до р операцію розгортання (зворотний операції склеювання):
за всіма відсутньою змінним вихідної функції f, отримуємо сукупність S констітуєнт одиниці. При склеюванні всіх констітуєнт з S отримаємо импликантами р. Останнє очевидно, оскільки операція склеювання обратна операції розгортання. Безліч S констітуєнт обов'язково присутній в досконалої ДНФ функції f оскільки р - її импликанта.
Приклад. Нехай є булева функція, задана таблицею істинності (табл. 9.12). Її СДНФ має вигляд:
Для зручності викладу позначимо кожну конституенту одиниці з СДНФ функції f яким-небудь десятковим номером (довільно). Виконуємо склеювання. Конституента 1 склеюється тільки з конституентов 2 (по змінної) і з конституентов 3 (по змінної), конституента 2 з конституентов 4 і т. Д.
В результаті отримуємо
Зауважимо, що результатом склеювання є завжди елементарне произве-дення, що представляє собою загальну частину, що склеюються констітуєнт.
Далі виробляємо склеювання одержуваних елементарних творів. Склеюються тільки ті твори, які містять однакові змінні. Має місце два випадки склеювання:
з появою одного і того ж елементарного твори Подальші склею-вання неможливі. Провівши поглинання (з отриманої ДНФ викреслюємо всі поглинаються елементарні твори), отримаємо скорочену ДНФ:
Переходимо до другого етапу. Для отримання мінімальної ДНФ необхідно прибрати зі скороченої ДНФ всі зайві прості імпліканти. Це робиться за допомогою спеціальної импликантной матриці Квайна. Рядки такої матриці відзначаються простими импликантами булевої функції, т. Е. Членами скороченою ДНФ, а стовпці - констітуентамі одиниці, т. Е. Членами СДНФ булевої функції.
Приклад (продовження). Импликантной матриця має вигляд (табл. 3).
Як уже зазначалося, проста импликанта поглинає деяку конституенту одиниці, якщо є її власною частиною. Соот-ветствующим клітина импликантной матриці на перетині рядка (з розглянутої простий импликантой) і стовпці (з конституентов одиниці) відзначається хрестиком (табл. 3). Мінімальні ДНФ будуються по импликантной матриці наступним чином:
1) здійснюється пошук стовпці импликантной матриці, мають тільки один хрестик. Відповідні цим хрестиками прості імпліканти називаються базисними і складають так зване ядро булевої функції. Ядро обов'язково входить в мінімальну ДНФ.
2) розглядаються різні варіанти вибору сукупності простих импликант, які накриють хрестиками інші стовп-ці импликантной матриці, і вибираються варіанти з
мінімальним сумарним числом букв в такій сукупності імплікант.
Приклад (продовження). Ядром нашої функції є імпліканти; .Імпліканта - зайва, так як ядро накриває все стовпчики импликант-ної матриці. Тому функція має єдину тупикову і мінімальну ДНФ:
Слід зазначити, що число N хрестиків в одному рядку завжди є ступенем 2. Більш того, читач може легко переконатися в тому, що
,де k - число букв, що містяться в простій импликанте.
Зауважимо також, що використовуючи різні співвідношення, можна розширити "область застосування методу Квайна за межі досконалої ДНФ.
Приклад. Мінімізувати булеву функцію f методом Квайна:
1. Позбавляємося від заперечень і дужок, використовуючи наведені співвідношення
2. Відновлюємо СДНФ функції f, застосовуючи операцію розгортання
3. Знайдемо скорочену ДНФ функції f, виробляючи в СДНФ всі можливі склеювання
4. Шукаємо мінімальну ДНФ функції f по импликантной матриці (табл. 4). Ядро булевої функції:. .Мінімальние ДНФ: