ам Вейча) при невеликому числі змінних виконується просто і наочно.
Введемо поняття подкуба, яке використовується в теорії ПФ і їх мінімізації. Подкуб - це сукупність 2 i сусідніх клітин карти Карно, заповнених одиницями (нулями), для яких принаймні одна змінна в координатах всіх цих 2 i клітин має неоднакові значення (0 і 1). З визначення випливає, що подкуб можуть утворити 2, 4, 8, 16 і т.д. сусідніх клітини карти.
Кожен 2 i -клітинний подкуб дозволяє при мінімізації виключити i змінних - 1,2,3,4 і т.д. Дійсно, подкуб, що складається з двох клітин, сусідніх по горизонталі або вертикалі (рис.2, а, б, в, г) характеризується тим, що координати його клітин розрізняються значенням однієї змінної, а інші змінні мають однакове значення. br/>В
Мінлива, значення якої для цих клітин різні (0 і 1), відповідно до закону склеювання зникає. Четирехклеточний подкуб містить клітини, координати яких розрізняються значеннями двох змінних (рис.3, а, б, в), отже, четирехклеточний подкуб дозволяє виключити дві змінні. Восьмиклітинного подкуб дозволяє виключити три змінні (рис.3, г, д).
В
Всі минтермов (макстерми), ввійшли в подкуб, склеюються за один прийом. Результатом склеювання таких клітин є отримання кон'юнктивній терма (якщо склеюються поодинокі клітини) або диз'юнктивного терма (якщо склеюються нульові клітини).
Контерм (кон'юнктивний терм) - результат склеювання сусідніх минтермов, що входять до подкуб (сусідніх одиничних клітин). У алгебраїчному поданні контерм - є кон'юнкція змінних, що мають незмінне значення в координатах рядків і стовпців всіх поєднуваних клітин; якщо незмінне значення змінної в координатах дорівнює 1, то в кон'юнкції вона записується без інверсії, якщо дорівнює 0 - то з інверсією.
На рис.2, а, б, в наведено приклади запису контермов для двухклеточного подкубов, а на рис.3, а, б, в, г, д - четирехклеточних () і восьмиклітинного ().
МДНФ - є диз'юнкція контермов.
Приклад: МДНФ для ПФ y 9 (рис.3, е) як результат мінімізації за одиничними значенням функції має вигляд:
. (5)
Дізтерм (диз'юнктивний терм) - результат склеювання сусідніх макстермов, що входять до подкуб (сусідніх нульових клітин). У алгебраїчному поданні дізтерм - є диз'юнкція змінних, що мають незмінне значення в координатах рядків і стовпців всіх поєднуваних клітин; якщо незмінне значення змінної в координатах дорівнює 1, то в диз'юнкції вона записується з інверсією, якщо дорівнює 0 - то без інверсії.
Для ПФ y 9 (рис.3, ж) побудовані подкуби мають наступні дізтерми:
МКНФ - є кон'юнкція дізтермов.
Приклад: МКНФ для ПФ y 9 (рис.3, ж) як результат мінімізації за нульовими значенням функції має вигляд:
() () (). (6)
Ранги контермов або дізтермов, які входять в логічне рівняння МДНФ або МКНФ перемикальної функції, в загальному випадку не однакові.
Загальні правила мінімізації функцій, справедливі для будь-якого числа логічних змінних:
- прямокутні області карти Карно, складові подкуби, можуть складатися з 1, 2, 4, 8, 16 і т.д. тільки одиничних клітин (при отриманні МДНФ) або тільки нульових клітин (при отриманні МКНФ);
- для подкубов вибирається мінімальний варіант їх побудови на карті Карно, при якому число подкубов мінімально, а їх розміри максимальні;
- клітини карти Карно можуть неодноразово входити в різні подкуби, якщо це необхідно для збільшення їх розмірів і зменшення їх кількості.
При мінімізації неповністю певних функцій факультативні клітини, позначені на карті знаком, можуть включатися до подкуби сусідніх клітин в тих випадках, коли дозволяють сформувати
подкуб або більшого розміру, або такий, який охопить клітини, раніше не включені ні в один подкуб. Включення клітин зі знаком в подкуби відповідає доопределение функції на відповідних цим клітинам наборах.
В
Формування подкубов з включенням до них факультативних клітин дозволяє отримувати більш прості, як правило, структурні формули МДНФ або МКНФ. Мінімізація функції, наведеної на мал.4, а, що відрізняється від функції (рис.3, е) тільки наявністю факультативних клітин, показує, що включення клітин зі знаком в подкуби дозволяє отримати вираз функції:
, (7)
яке істотно простіше, ніж (5) або (6). Істотна відмінність у складності формул може мати місце і при мінімізації неповністю певної логічної функції при використанні одиничних клітин і нульових клітин (МДНФ і МКНФ). Для функції, наведеної на рис.4, б, об'єднання нульових клітин в подкуби і дає мінімізоване вираз (МКНФ): = () (). МДНФ для функції (рис. 4, в) складніше: =.
6. Нормальні форми логічних рівнянь. Перетворення логічних рівнянь до заданого базису
Якщо при проектуванні логі...
