Мінімізація функцій. Карти Карно. Цифрова техніка // EG Lab [14:20]
Мінімальна діз'юнктівная нормальна форма (МДНФ) для логічної функції - це диз'юнкція з мінімальним числом елементарних кон'юнкція з мінімальним числом аргументів (або самих, або їх заперечень) даної функції. При цьому таблиці істинності для логічної функції та її МДНФ збігаються.
Мінімальна діз'юнктівная нормальна форма для логічної функції з числом аргументів до чотирьох може бути побудована за допомогою карт Карно. Для цього одиниці карти Карно послідовно покриваються прямокутниками 4 × 2, 2 × 4, 2 × 2, 4 × 1, 1 × 4, 2 × 1, 1 × 2 і 1 × 1. Потім будуються елементарні Кон'юнктів МДНФ.
n - число аргументів функції;
k - число прямокутників на карті Карно;
argj (i, l) - значення аргументу xj в наборі аргументів для клітини (i, l);
[Math] f_ (x_1, x_2, \ ldots, x_n) = \ bigcup \ limits_ ^ k \ bigcap \ limits_ \ arg_j \ left [P_t (x_1, x_2, \ ldots, x_n) = 1 \ right] = 1 \ Text \\\ arg_j \ left [P_t (x_1, x_2, \ ldots, x_n) = 1 \ right] = 0 \ End> y_j, [/ math] де [math] y_j = \ beginx_j, \ text \ \ arg_j \ left [P_t (x_1, x_2, \ ldots, x_n) = 1 \ right] = 1 \\ \ bar_j, \ text \ \ arg_j \ left [P_t (x_1, x_2, \ ldots, x_n) = 1 \ right] = 0 \ end [/ math] [math] \ arg_j \ left [P_t (x_1, x_2, \ ldots, x_n) = 1 \ right] = \ begin1, \ text \ \ forall (i, l) \ in P_t (x_1, x_2, \ ldots, x_n), \ arg_j (i, l) = 1 \\ 0, \ text \ \ forall (i, l) \ in P_t (x_1, x_2, \ ldots, x_n), \ arg_j (i, l) = 0 \ end [/ math]
Приклади побудови МДНФ
Будуємо карту Карно для функції трьох змінних:
Одиниці карти Карно мінімально покриваються одним прямокутником виду 1 × 2 і двома прямокутниками виду 2 × 1, що відповідає трьом елементарних кон'юнкція двох аргументів. Зауважимо, що два неповних прямокутника виду 2 × 1 відповідають одному повного прямокутника покриття.
Будуємо карту Карно для функції чотирьох змінних:
Одиниці карти Карно мінімально покриваються трьома квадратами виду 2 × 2, що відповідає трьом елементарних кон'юнкція двох аргументів. Зауважимо, що чотири кутових неповних квадрата відповідають одному повного квадрату покриття.
Будуємо тривимірну карту Карно для функції п'яти змінних:
Одиниці тривимірної карти Карно мінімально покриваються паралелепіпедами виду 2 × 2 × 2, 2 × 2 × 1 (два), 1 × 4 × 1, 1 × 2 × 2, що відповідає одній елементарної кон'юнкції двох аргументів і чотирьох елементарних кон'юнкція трьох аргументів. Зауважимо, що крайні по сторонам і кутові фігури об'єднуються.