Карти карно, дискретна математика, приклади рішень завдань

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

Карти Карно були винайдені в 1952 Едвардом В. Вейч і вдосконалені в 1953 Морісом Карно, фізиком з «Bell Labs», і були покликані допомогти спростити цифрові електронні схеми. В карту Карно булеві змінні передаються з таблиці істинності і упорядковуються за допомогою коду Грея, в якому кожне наступне число відрізняється від попереднього тільки одним розрядом.

Карта Карно може бути складена для будь-якої кількості змінних, однак зручно працювати при кількості змінних не більше п'яти. По суті Карта Карно - це таблиця істинності складена в 2-х вимірному вигляді. Завдяки використанню коду Грея в ній верхній рядок є сусідній з нижньої, а правий стовпець сусідній з лівим, таким чином вся Карта Карно згортається в фігуру тор (бублик). На перетині рядка і стовпця проставляється відповідне значення з таблиці істинності. Після того як Карта заповнена, можна приступати до мінімізації.

• Якщо необхідно отримати мінімальну ДНФ, то в Карті розглядаємо тільки ті клітини які містять одиниці, якщо потрібна КНФ, то розглядаємо ті клітини, які містять нулі.

Алгоритм мінімізації по методу карт Карно:

1.Метод Карно заснований на представленні вихідної функції, заданої у формі СДНФ, у вигляді карти такого вигляду:

2. Об'єднуємо суміжні клітини, що містять одиниці, в область так, щоб одна область містила 2 n (тобто 2, 4, 8, і т.д.) клітин (пам'ятаємо про те, що крайні рядки і стовпці є сусідніми між собою), в області не повинно знаходитися клітин, що містять нулі, області можуть перетинатися, можливо кілька варіантів покриття.

3. Далі беремо першу область і дивимося, які змінні не змінюються в межах цієї області, виписуємо кон'юнкцію цих змінних; якщо незмінний змінна нульова, проставляємо над нею інверсію. Беремо наступну область, виконуємо те ж саме, що і для першої, і т. Д. Для всіх областей.

4. кон'юнкції областей об'єднуємо диз'юнкція.

Приклад. Методом Карно мінімізувати функцію:

$$ y = f # 92; left (A, B, C # 92; right) = # 92; bar # 92; bar # 92; bar # 92; vee # 92; barB # 92; bar # 92; vee A # 92; bar # 92; bar # 92; vee A # 92; barC $$

1.Задать функцію представимо за допомогою карти Карно:

2. Потім проводиться об'єднання 2-х, 4-х або 8-ми одиниць. В даному випадку об'єднання двох одиниць по горизонталі відповідає операції склеювання над констітуентамі $ # 92; bar # 92; bar # 92; bar $ і $ # 92; bar B # 92; bar $. в результаті якої виключається змінна B і отримана импликанта $ # 92; bar # 92; bar $. Об'єднання двох одиниць по вертикалі відповідає операції склеювання над констітуентамі $ A # 92; bar # 92; bar $ і $ A # 92; barC $. в результаті якої виключена змінна $ З $ і буде отримана импликанта $ A # 92; bar $.

3. Отже, мінімальна форма заданої функції прийме наступний вигляд: $$ y = # 92; bar # 92; bar # 92; vee A # 92; bar $$.