МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ

МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ

1. Індекс простоти

2. Скорочена форма

3. Тупикові нормальні форми

4. Карти Карно. Діаграми Вейча

5. Індекс простоти

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

Найзрозумілішим є алгоритм, що грунтується на переборі, тобто перегляді всіх можливих ДНФ і КНФ функції. Проте ним не можна скористатися практично вже при и=3, а при и= 1 та п=2 проблема є тривіальною. Спочатку знаходять конкретну функцію алгебри логіки, визначену для будь-яких наборів значень аргументів. Після цього функцію подають у будь-якій з двох досконалих форм. Потім здійснюють низку спрощень, що досягається за допомогою різних тотожних перегворень з метою здобуття формули, еквівалентної початковій, але яка реалізується простіше.

При оцінюванні складності приймають коефіцієнт простоти.

Розглянемо функцію

А = (х, АГ, А Х3 ) V (х( АГ; АХ3) А Х2 АХ,) у(х, ЛХ2 АГ, АХ,) еквівалентну формулі

В = А = (рС^ЛXі)VX^.

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

Найчастіше зустрічаються такі типи коефіцієнтів простоти:

• І 1(А) - число символів змінних, які зустрічаються в запису ДНФ. Якщо проаналізувати формули А та В, то можна встановити, що Ь\(А) = 15, а Ь\(В) = 3, тобто функція В є простішою;

• Ь2(А) - число елементарних кон’юнкцій, що входять у функцію А. Для ДНФ А та В очевидно, що Ь2(А) = 5, а І2(В) = 2, тобто функція В теж є простішою за цим критерієм;

• ЬЗ(А) - число символів інверсій, які зустрічаються в запису ДНФ. Для ДНФ А та В ІЗ (А) = 7, а ІЗ(В) = 2, тобто функція В за цим критерієм є також простішою.

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

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

Деякі булеві функцію мають кілька мінімальних ДНФ (КНФ).

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

Означення. Мінімізацією називаються перетворення функції, яке веде до зменшення числа символів, а отже, числа змінних.

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

1. Скорочена форма

Уведемо поняття накриття для булевих функцій.

Означення. ФункціяДхі,...дгп) накриває функцію £(хі,... д:т) (и<т) на наборі аргументів (аі,...,ап), якщох„+і,...дт : §(аи...,а„,хп+],...х„) =Даи...,а„).

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

Означення. Якщо деяка булева функція £ дорівнює нулю в тих наборах, у яких дорівнює нулю інша функція / то говорять, що функція £ входить у функцію / тобто функція £ входить у функцію /

тоді, кола вона накриває нулями всі нулі функції/ а одиниці функції/можуть бути накриті як нулями, так і одиницями функції £. Отже, функція £ має не меншу кількість нулів, ніж функція /

Означення. Функцію £, що входить у задану функцію/ називають її імплікантою.

Означення. Функція Називається імплікантою функції /(х„), якщо на будь-якому наборі значень змінних х,,х2,...,хп виконується умова <р{хп)< /(*„).

Наведемо два твердження (без доведення), які є корисними при отриманні мінімальних ДНФ:

1. диз’юнкція будь-якого числа імплікант булевої функції /також є імплікантою цієї функції;

2. будь-яка булева функція / еквівалентна диз’юнкції всіх своїх імплікант; така форма подання булевої функції називається скороченою ДНФ.

Простими імплікантами логічної функції / називають такі елементарні кон’юнкції, які самі входять до даної функції, тобто є імплікантами функції Г, але ніяка їх власна частина не є імплікантою функції /

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

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

Застосування терміна “імпліканта” пов’язано з булевої функцією імплікації. Можна пересвідчитись, що функція £-»/ тотожно дорівнює 1, тобто завжди є істинною тоді, коли функція £ входить у /

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

Означення. Простими імплікантами булевої функції називаються елементарні кон’юнкції, що самі входять у задану функцію/ але ніяка власна частина їх у функцію/не входить.

Прості імпліканти є найкоротшими елементарними кон’юнкціями, що входять у задану булеву функцію.

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

Теорема. Будь-яка булева функція дорівнює диз’юнкції всіх своїх простих імплікант.

, * Означення. Диз’юнкція всіх простих імплікант називається скороченою ДНФ булевої функції.

1. Тупикові нормальні форми

Нехай функція /х1,...рси) має довільну ДНФ вигляду. А = А'чК або А - А’ч(ал.К'), де К - елементарна кон’юнкція, А' - ДНФ, утворена з інших кон’юнкції, що входять в А (залишок); а- деякий множник з АГ; К' - кон’юнкції! інших множників з АГ.

Існують два основних типи перетворень (операцій) ДНФ.

1. Операції! вилучення елементарних кон’юнкцій. Перехід від А до А' - перетворення, яке здійснюється виключенням елементарних кон’юнкцій АГ, що можливо при А=А'.

2. Операції! вилучення множника, тобто перехід від А до ДНФ вигляду (А'чК') вилученням множника. Це перетворення можливо тільки при А = А' \гК'.

Означення. ДНФ, яку не можна спростити за допомогою перетворень 1 та 2 (їх не можна застосувати), називають тупиковою ДНФ.

Можна сформулювати один з алгоритмів утворення тупикових ДНФ (алгоритм спрощення, тобто алгоритм найшвидшого спуску):

1. Функціїо подають у ДДНФ.

2. Упорядковують ДДНФ (записують співмножники так, щоб було зручно здійснювати перетворення).

3. До ДДНФ застосовують операціїо вилучення елементарних кон’юнкцій, а потім операціїо вилучення співмножників.

Теорема. ДНФ, утворена після застосування алгоритму найшвидшого спуску, є тупиковою.

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

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

Карти Карно для функцій трьох змінних Р(х,, х2, х3).

00

01

11

10

0

000

001

011

010

1

100

101

пі

110

00

01

її

10

0

X, Х2 Х3

н

1

1

X, Х2 X,

х, х2 х3

1

Хх х2 Х3

X, х2 х3

X, Х2 Х3

х1 х2 х3

[endif]-- є

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

Тупикові форми, що містять найменшу кількість символів, будуть мінімальними.

Теорема. Будь-яка мінімальна ДНФ булевої функції є тупиковою.

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

4. Карти Карио. Діаграми Вейча

Важливим етапом проектування цифрових пристроїв є мінімізація булевих функцій, тобто знаходження їхніх виражень з мінімальним числом букв.

Мінімізація забезпечує побудову економічних схем цифрових автоматів. Для мінімізації функцій із числом букв п<, 6 застосовують карти Карно. їх будують у вигляді таблиць з 2" кліток з розміткою рядків і стовпчиків змінними.

Для мінімізації булевих функцій використовують також діаграми Вейча, які аналогічні картам Карно і відрізняються від них способом розмітки замість символів 0 і 1 використовують булеві аргументи - х,, х,, х2 та інші.

Х2

Х2

XI

11

10

хї

01

00

\^3*4

00

01

11

10

00

0000

0001

0011

0010

01

0100

0101

0111

0110

11

1100

1101

1111

1110

10

1000

1001

1011

1010

Х4 Х4 Х4

Приклад. Спростити логічний вираз з використанням діаграм Вейча. у = х: А х2 А Х3 V X] А х2 А Х3 V X! Л Х2 А Х3 V X) А Х2 А х3 V Х} А х2 А Х3 Діаграма Вейча згідно заданого виразу буде мати вигляд:[endif]-- Діаграма Вейча для 2- х змінних.

Діаграма Вейча для 3- х змінних.

Х2

Х2

XI

по

111

100

100

XI

010

011

000

000

хз

хз хз

Діаграма Вейча для 4- х змінних.

Х2 Х2

,

1100

1101

1001

1000

1110

1111

1011

1010

0110

0111

Ооп

0010

0100

0101

0001

0000

< ■-.... •>

<----------------------- >

4;--------

Спрощений вираз мас вигляд:

У = Х[ А Х2 V X, А Х3 V Х1 А Х3 .

![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--

#вдохновение #успех