Мінімізація булевих функцій

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

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

Карти Карно для функцій трьох змінних .

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

Загальні правила мінімізації.

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

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

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

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

Розмітка карт Карно для функцій чотирьох змінних.

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