Мінімізація за картами Карно

Комірки з одиницями на карті називаються Р-клітинками.

Дві сусідні одиниці утворюють одномірний р-підкуб або 1-куб. Одновимірний р-підкуб відповідає добутку, у якому завжди відсутній один первинний терм.

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

Приклад 17.3. Зобразити функцію на карті Карно.

Розв’язок. Відзначимо одиничні значення функції на карті, помістивши їх у другу й третю комірки (рис. 17.5).

Рисунок 17.5 – Одновимірний р-подкуб або 1-куб

При цьому видно, що дві одиниці попадають у сусідні комірки й утворюють 1-куб. Вони обводяться мінімізуючим контуром. Отже, зображення функції буде таким: .

Чотири сусідні одиниці утворюють двовимірний р-підкуб (2-куб), що відповідає добутку без двох первинних термів. Ті змінні, які не зберігають постійне значення на цьому підкубі, не вказуються.

Приклад 17.4. Знайти аналітичний вираз, що відповідає 2-кубу на карті Карно (рис. 17.6).

Рисунок 17.6 – Двовимірний р-підкуб або 2-куб на карті Карно 4-х змінних

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

Тривимірні р-підкуби містять по 8 одиниць (3-куб).

Приклад 17.5. Блок з 8-ми одиниць підлягає склеюванню з одержанням 3-кубу (рис. 17.7).

Рисунок 17.7 – Тривимірний р-підкуб або 3-куб

При цьому мінімальна форма функції описується виразом, якому відповідає єдиний превинний терм: .

Одновимірний р-підкуб відповідає ребру, що має дві сусідні вершини. Двовимірний р-підкуб відповідає двовимірному підкубу n-вимірного куба.

Правила мінімізації:

1) Дві сусідні комірки на карті утворюють 1-куб.

2) Несуттєва координата для двох кубів позначається символом X. Наприклад: .

3) Чотири комірки поєднуються та утворюють 2-куб:

.

4) У загальному випадку можуть поєднуватися сусідні комірки, число яких дорівнює , тобто 2, 4, 8, 16, 32,..., з утворенням k-кубів, де – кількість змінних функції.

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

17.4 Контрольні запитання

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

2. Чим відрізняються карти Карно від таблиць істинності?

3. Яке основне призначення карт Карно?

4. Як установлюється зв'язок між двійковими наборами й комірками карти Карно двох (трьох, чотирьох) змінних?

5. Які комірки карти є сусідніми?

6. Як подається функція на карті?

7. У чому полягає спрощений стандарт карт Карно?

8. Які властивості мають карти Карно?

9. Що таке р-клітинки?

10. Які основні правила склеювання за картами?

11. Як виконується мінімізація за картами Карно?

12. Що являють собою мінімізуючі контури?

18 ВИСНОВКИ ДО РОЗДІЛУ «БУЛЕВА АЛГЕБРА»

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

19 ПОЗНАЧЕННЯ ДО РОЗДІЛУ «БУЛЕВА АЛГЕБРА»

Символ	Розшифровка
	Диз’юнкція (логічне додавання)
	Кон’юнкція (логічне множення)
−	Заперечення
	Імплікація
	Сума за модулем два, XOR
	Еквівалентність
	Штрих Шефера
	Стрілка Пірса (функція Веба)
	Істина (істиннісне значення булевої змінної або булевої функції)
	Хибність (хибне значення булевої змінної або булевої функції)
,	Двійковий набір (вектор)
	Первинний терм
	Елементарна кон’юнкція
	Елементарна диз’юнкція
	Диз’юнктивна нормальна форма (ДНФ)
	Кон’юнктивна нормальна форма (КНФ)
	Досконала ДНФ (ДДНФ)
	Досконала КНФ
	Складність форми булевої функції
	Складність форми булевої функції за Квайном, - число кон’юнктивних термів функції
	Граничне диз’юнктивне розкладання функції за Шенноном (ДДНФ)
	Граничне кон’юнктивне розкладання функції за Шенноном (ДКНФ)
AND	AND-Оператор (І)
OR	OR-Оператор (АБО)
NOT	NOT-Оператор (НІ)
Х	Незалежна координата
0-куб	Точка (вершина одиничного куба)
1-куб	Відрізок (ребро одиничного куба)
2-куб	Площина (грань одиничного куба)
	Комплекс 0-кубів
	Комплекс 1-кубів
	Клас функцій, що зберігають константу нуль
	Клас функцій, що зберігають константу одиниця
	Клас самодвоїстих функцій
	Клас монотонних функцій
	Клас лінійних функцій
	Поліном Жегалкіна, де та , є або 1, або змінна, або кон’юнкція різних змінних
	Поліном першого ступеня, де
()	Передування (порівнянність) двійкових наборів
	Двоїста функція
	Одинична залишкова функція
	Нульова залишкова функція
	Булева похідна першого порядку за змінною
	Змішана похідна k-го порядку булевої функції
	Похідна k-го порядку