1.2 Мінімізація логічних функцій.

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

1. Проведемо мінімізацію функції за допомогою елементарних булевих перетворень:

- задана функція

1. 

2. 

3. 

За дистрибутивним законом та аксіомою: ( )

Виконуємо перевірку:

1*0*0 v 0*0 v 1 v 0*1 v 0*1 = 0

1*0*1 v 0*0*0 v 0*1 v 0*1= 0;

1*1*0 v 0*0*1 v 0*0 v 0*0= 0;

1*1*1 v 0*0*0 v… = 1 ;

1v0v0 v 0*1*1 v 0*1 v 1*1 = 1;

1*0*1 v 0*1*0 v 0*1 v 1*1 = 1;

1*1*0 v 0*1*1 v 0*0 v 1*0 = 0;

1*1*1 v … = 1;

0*0*0 v 1*0*1 v 1*1 v 0*1 = 1;

0*0*1 v 1*0*0 v 1*1 v 0*1 = 1;

0*1*0 v 1*0*1 v 1*0 v 0*0 = 0;

0*1*1 v 1*0*0 v 1*0 v 0*0 = 0;

0*0*0 v 1*1*1 v …= 1;

0*0*1 v 1*1*0 v 1*1 v … = 1;

0*1*0 v 1*1*1 v … = 1;

0*1*1 v 1*1*0 v 1*0 v 1*0 = 0.

По результатам проведеної перевірки можна стверджувати, що мінімізація була проведена вірно.

1.3. Мінімізація логічної функції за допомогою карт Карно.

Другий метод мінімізації функції є метод мінімізації за допомогою карт Карно (КК).

Цей метод відноситься до табличних методів мінімізації логічних функцій. Карти Карно графічно представляють таблиці істинності логічних функцій. Вони представляють собою таблиці, які містять по 2ⁿ прямокутних комірок, де n – число логічних змінних. КК розрізняються системою

координат, які відповідають значенням вихідних змінних. Комірки КК, які представляють функцію, містять стільки одиниць, скільки елементарних

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

зростання двійкових кодів, а у порядку: 00, 01, 11, 10. Це зроблено для того, щоб сусідні набори, які відрізняються між собою лиш цифрою одного розряду, були сусідніми у геометричному сенсі.

Послідовність процесу мінімізації:

1. Формуються прямокутники по 2^к комірок, к = 0,1,2… У прямокутнику об’єднуються сусідні комірки з одиницями. Це об’єднання ведеться по горизонталі чи вертикалі.

2. Складається вираз в вигляді ДНФ для обраного покриття.

а) Виписуються координати всіх точок, що входять у прямокутник.

б) Всі змінні, які не змінюють свого значення у межах прямокутника включаються у елементарний добуток один раз.

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

		Х1Х0
		00	01	11	10
Х3Х2	00	0	0	1	0
	01	1	1	1	0
	11	1	1	0	1
	10	1	1	0	0

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

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

х3	х2	х1	х0
1	1	0	0
1	1	0	1
1	0	0	0
1	0	0	1

х3	х2	х1	х0
0	1	0	0
0	1	0	1
1	1	0	0
1	1	0	1

х3	х2	х1	х0
1	1	0	0
1	1	1	0

х3	х2	х1	х0
0	0	1	1
0	1	1	1

Рис.1.2 Мінімізація здобутого покриття карти Карно для функції чотирьох змінних

Якщо перемінна має в межах прямокутника незмінне значення «1», вона входить в елементарний твір без інверсії. У протилежному випадку (при незмінному значення перемінної «0») – включається з інверсією.

Після вищезазначених перетворень аналітична функція приймає вигляд:

Y =

Даний вираз повністю співпадає із виразом отриманим з використанням формул алгебри логіки.

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

За допомогою логічних елементів, побудуемо структурну схему мінімізованої логічної функції.

&

1

&

1

Y

1

&

1

&

Рис.1.3 Структурна схема мінімізованої логічної функції