Аналіз теорії цифрових автоматів (стр. 6 из 7)
Визначення: Мінімальною диз’юнктивною нормальною формою булевої функції називається ДНФ, що містить найменше число букв.
Визначення: Булева функція g (x1,x2,…,xn) називається імплікантою булевої функції f (x1,…,xn), якщо для будь-якого набору змінних, на якому g=1, справедливе f=1.
Визначення: Імпліканта g булевої ф-ції f, що є елементарною кон’юнкцією, називається простою, якщо ніяка частина імпліканти g не є імплікантою функції f.
Приведемо без доведень два твердження, корисні при отриманні мінімальної ДНФ.
Дизьюнкція будь-якої кількості імплікант булевої ф-ції f також є імплікантою цієї функції.
Будь-яка булева функція f еквівалентна диз’юнкції всіх своїх простих імплікант. Така форма представлення булевої ф-ції називається скороченою ДНФ.
Отримання скорочених ДНФ є першим етапом відшукання мінімальних форм булевих функцій. В скорочену ДНФ входять всі прості імпліканти булевої функції. Іноді з скороченої ДНФ можна забрати одну, або декілька простих імплікант, не порушуючи еквівалентності початкової функції. Такі прості імпліканти називаються лишніми. Виключення лишніх простих імплікант з скорочених ДНФ - другий етап мінімізації.
Визначення: Скорочена ДНФ булевої ф-ції називається тупіковою, якщо в ній відсутні лишні прості імпліканти.
Виключення лишніх простих імплікант в скорочених ДНФ булевої функції не є однозначним поцесом, тобто булева функція може мати декілька тупікових ДНФ.
Твердження. Тупікові ДНФ булевої функції f, що містять мінімальну кількість букв, являються мінімальними. Мінімальних ДНФ також може бути декілька.
Розглянемо декілька методів мінімізації. Всі вони практично відрізняються тільки на першому етапі - етапі отримання скорочених ДНФ. Слід відмітити, що, на жаль, пошук мінімальної ДНФ завжди зв’язаний з деяким перебором рішень. Існують методи зменшення цього перебору, проте він завжди залишається.
Метод квайна оснований на використанні двох основних співвідношень:
Співвідношення склеювання:
Ax
A 
=A,де А - любе елементарне походження.
Співвідношення поглинання:
А
А=А, 
{x, }.Справедливість обидвох співвідношень легко перевіряється. Суть методу в послідовному виконанні всіх можливих склеювань і потім всіх поглинань, що приводять до скороченої ДНФ.
Приклад. Нехай є булева ф-ція, задана таблицею істиності (табл.1).
Таблиця 1
| x1 x2 x3 x4 | F |
| 0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1 | 1001101110000010 |
Її ДДНФ має вигляд
f=
Для зручності помітимо кожну конституєнту одиниці з ДДНФ ф-ції f яким-небудь десятковим номером (довільно). Виконаємо склеювання. Конституєнта 1 склеюється тільки з конституєнтою2 (по змінній х3) і з конституєнтою 3 (по змінній х2), конституєнта 2 з конституєнтою 4. В результаті отримуємо
1-2:
; 3-4: 
;1-3:
; 4-6: 
;2-4:
; 5-6: 
.Далі проводимо склеювання отриманих елементарних перетворень. Склеюються тільки ті перетворення, які містять одинакові змінні. Має місце два випадки склеювання:
= 
; 
= ,з появою одного і того ж
.Подальші склеювання неможливі. Провівши поглинання, отримаємо скорочену ДНФ
.Переходимо до наступного етапу. Для отримання мінімальної ДНФ необхідно забрати з скороченої ДНФ всі лишні прості імпліканти. Це робиться за допомогою спеціальної імплікантної матриці Квайна. Рядки такої матриці відмічаються простими імплікантами булевої ф-ції, тобто членами скороченої ДНФ, а стовбці - конституєнтами одиниці, тобто членами ДДНФ булевої ф-ції. Приклад (продовження). Імплікантна маириця має вигляд (табл.2)
Таблиця 2.
| Прості імпліканти | Конституенти одиниці | |||||
 |  |  |  |  |  | |
 |    |  |  | |||
| x2 x3 x4 |  |  | ||||
| x1 x2 x3 |  | |||||
Відповідна клітка імплікантної матриці на перетині рядка (з розглядуваною простою імплікантою) і стовбця (з конституєнт одиниці) відмічається хрестиком (табл.2). Мінімальні ДНФ будуються по імплікантній матриці наступним чином:
1. Шукаються стовбці матриці, які мають тільки один хрестик. Відповідні цим хрестикам прості імпліканти називаються базисами і складають так зване ядро булевої ф-ції. Ядро обов’язково входить в мінімальну ДНФ.
2. Розглядаються різні варіанти вибору сукупності простих імплікант, які накриють хрестиками решту стовбців матриці, і вибираються варіанти з мінімальним сумарним числом букв в такій сукупності імплікант.
Ядром нашої ф-ції є імпліканти x1x2x3. Імпліканта x2x3x4 -лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:
Метод квайна-мак-класкі
Метод представляє собою формалізований на етапі знаходження простих імплікант метод Квайна. Формалізація проводиться таким чином: