ГРАФІЧНИЙ МЕТОД МІНІМІЗАЦІЇ

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

Структура карт Карно

Карта Карно для логічних функцій від М змінних Y = F (X M Х т, ..., Х 0 ) має форму прямокутника або квадрата, який містить I м пронумерованих клітин (рис. 3.7). Номер клітини складається з М-розрядної двійкового числа Х м, ... Хт ... Х0, при цьому старшими розрядами нумеруються рядки, молодшими - стовпці.

Подання логічних функцій за допомогою карт Карно

Карту Карно для функції Y можна ототожнити з таблицею істинності. Кожній клітці карти Карно відповідає рядок таблиці істинності. Тому якщо для km набору змінних Х м _ v ..., Х т Х0 значення функції У * = 1, то в клітку з номером k заноситься 1, в іншому випадку - 0 або клітина залишається порожньою. Клітини, заповнені одиницями, будемо називати одиничними клітинами, а заповнені нулями, або порожні клітини - нульовими клітинами.

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

 
< Попер   ЗМІСТ   Наст >