2020-04-20
169
При проектуванні цифрових машин широко використовуються методи мінімізації булевих функцій, які дозволяють отримати рекомендації для побудови економічних схем цифрових машин. Загальна задача мінімізації булевих функцій формулюється так: знайти аналітичне вираження булевої функції в формі, що містить мінімально можливе число букв. Слід відмітити, що в загальній постановці дана задача поки що не розв’язана, але достатньо добре досліджена в класі диз’юнктивно-кон’юктивних нормаьних форм.
|
Визначення: Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій.
Визначення: Мінімальною диз’юнктивною нормальною формою булевої функції називається ДНФ, що містить найменше число букв.
Визначення: Булева функція 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 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 | 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 |
Її ДДНФ має вигляд
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 -лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:
