16.2. Мінімізація булевих функцій методом карт Карно

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

Для функції двох змінних структура карти Карно має вигляд

x y	0	1
0
1

Стовпчики карти Карно відповідають значенням змінної x, рядки – змінної y. Кожна комірка відповідає конституентам одиниці у вигляді формул з абстрактними змінними.

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

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

x y	0	1
0	A
1

x y	0	1
0		B
1

x y	0	1
0
1	C

x y	0	1
0
1		D

Приклад 1. Для функції карта Карно має вигляд.

x y	0	1
0	1	1
1	1

Для функцій трьох змінних структура карти Карно має вигляд

xy z	00	01	11	10
0
1

Стовпчики карти Карно для функції трьох змінних відповідають словам значень перших двох змінних x і y, сусідні слова мають відрізнятися значенням тільки однієї змінної. Звідси порядок слів 00, 01, 11, 10. Ряди карти Карно відповідають значенням змінної z. У комірках карти вказані відповідні конституенти одиниці із абстрактними змінними.

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

Приклад 2. Карта Карно для функції має вигляд

xy z	00	01	11	10
0	1
1	1	1	1

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

xy z	00	01	11	10		xy z	00	01	11	10
0						0
1		A				1				B

сусідні комірки комірки А (зафарбовані) ; сусідні комірки комірки В;

xy z	00	01	11	10		xy z	00	01	11	10
0						0				D
1	C					1

сусідні комірки комірки С ; сусідні комірки комірки D.

Для функції чотирьох змінних структура карти Карно має вигляд

xy zt	00	01	11	10
00
01
11
10

Кожна комірка карти Карно для функції чотирьох змінних має чотири сусідні комірки. Наприклад.

B

A

C

F

D

E

Для функції п`яти змінних має два шари. Перший шар має слова для яких п`ята змінна , другий – :

xy zt	00	01	11	10		xy zt	00	01	11	10
00						00
01						01
11						11
10						10

Кожна комірка має п’ять сусідів. Наприклад:

xy zt	00	01	11	10		xy zt	00	01	11	10
00						00
01						01
11		A				11
10						10

xy zt	00	01	11	10		xy zt	00	01	11	10
00						00
01						01
11						11
10	B					10

xy zt	00	01	11	10		xy zt	00	01	11	10
00						00
01				C		01
11						11
10						10

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

1. Побудувати карту Карно для даної функції.

2. Об’єднати комірки в групи, що позначають операції склеювання. В об`єднанні беруть участь комірки, в яких записані одиниці. В групу можуть об`єднуватися комірок, . При цьому групи повинні бути прямокутними або квадратом..

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

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

5. Диз`юнкція всіх одержаних імплікант і є мінімальною ДНФ.

Приклад 3. Знайти мінімальну ДНФ для функції

Виконання. Заповнюємо карту Карно

xy z	00	01	11	10
0	1
1	1	1	1

Об’єднуємо комірки з одиницями в групи

xy z	00	01	11	10
0	1
1	1	1	1

B

A

Одержали дві максимальні групи A, B, яким відповідають мінімальні імліканти A, B:

,

.

Схематично ці імпліканти представити так:

, ,

(підкреслені співпадаючі значення реальних змінних)

Об’єднуємо диз’юнкцією мінімальні імпліканти і одержимо МДНФ заданої функції;

.

Приклад 4. Знайти МДНФ для функції

.

Виконання.

xy z	00	01	11	10
0		1	1
1	1		1

, , .

МДНФ:

Приклад 5. Знайти МДНФ для функції

.

Виконання.

xy z	00	01	11	10
0	1	1	1	1
1	1		1	1

, , .

МДНФ :

Приклад 6. Знайти МДНФ для функції

Виконання.

xy zt	00	01	11	10
00	1			1
01	1			1
11	1	1		1
10			1

, , , .

МДНФ :

Приклад 7. Знайти МДНФ для функції

Виконання.

xy zt	00	01	11	10		xy zt	00	01	11	10
00	1	1	1	1		00		1	1
01						01
11	1		1			11
10			1	1		10

,, ,

,.

МДНФ : .