У попередній статті я розповів, як симетричні карти дозволяють досить просто і швидко мінімізувати булеві функції, але не висвітлив два моменти: отримання різних варіантів мінімального рішення та автоматизацію самого алгоритму мінімізації. Розповім тут про це більш детально.
Нагадаю, що завдання мінімізації - для кожної одиниці знайти найбільше покриття. Якщо таке покриття знайдено і воно єдине, то воно записується в так зване ядро функції, а всі одиниці, що їм покриваються вибувають з подальшого розгляду. Однак, якщо максимальне покриття не єдине, виникають варіанти рішення, які можливо використовувати, наприклад, для обліку будь-яких додаткових вимог. Крім того, як я покажу далі, відкидання варіантів призводить до того, що отримане рішення може виявитися не мінімальним.
Отже, у прикладі попередньої статті можна знайти ядро функції для наступної симетричної карти:
Воно дорівнює:
!X1*X5 V X2*X3*X4 V X1*!X2*!X5
Можна знайти, що одиниця в рядку з індексом 0 і стовпчику з індексом 4 може бути покрита двома способами:
!X1*X3*!X4 (1)
X3*!X4*!X5 (2)
Аналогічно, одиниця в рядку з індексом 10 і стовпчику з індексом 4 може бути покрита чотирма способами:
!X1*X3*!X4 (1)
X3*!X4*!X5 (2)
!X1*X2*X3 (3)
X2*X3*!X5 (4)
Зауважимо, що при покритті різних одиниць зустрічаються однакові імпліканти, позначені тут однаковими цифрами.
Далі, одиниця в рядку з індексом 30 і стовпчику з індексом 4 може бути покрита трьома способами:
X3*!X4*!X5 (2)
X1*X3*!X5 (5)
X2*X3*!X5 (4)
І одиниця в рядку з індексом 20 і стовпчику з індексом 1 може бути покрита двома способами:
X1*!X2*!X3*!X4 (6)
!X2*!X3*!X4*X5 (7)
Оскільки в остаточному рішенні повинні бути покриті всі одиниці, запишемо такий вираз у вигляді твору варіантів для кожної одиниці:
(1 V 2)(1 V 2 V 3 V 4)(2 V 5 V 4)(6 V 7)
Розкриємо перші дві дужки:
(1*1 V 1*2 V 1*3 V 1*4 V 2*1 V 2*2 V 2*3 V 2*4)(2 V 5 V 4)(6 V 7)
Оскільки імпліканта, будучи помножена сама на себе дає ту ж імпліканту, першу дужку можна переписати в наступному вигляді:
(1 V 1*2 V 1*3 V 1*4 V 2*1 V 2 V 2*3 V 2*4)(2 V 5 V 4)(6 V 7)
Далі, оскільки варіант з однією імплікантою дає краще рішення, ніж з двома, можна переписати рішення у вигляді:
(1 V 2)(2 V 5 V 4)(6 V 7)
Розкриваючи дужки далі і використовуючи подібні скорочення, отримуємо остаточне рішення, яке вже не можна скоротити:
2(6 V 7)
Перший множник 2 - єдина імпликанта в групі і повинна бути довавлена в ядро функції (так зване розширене ядро функції):
X3*!X4*!X5
А дужка дає два варіанти:
X1*!X2*!X3*!X4
і
!X2*!X3*!X4*X5
Можна вибрати будь-який з них.
Природно, виникає питання про автоматизацію даного алгоритму. Для цього мною була написана програма apssymmap, яку можна знайти на моєму сайті:
http://andyplekhanov.narod.ru/soft/soft.htm
Є інтерес порівняти результати застосування даного методу з іншими відомими методами. Порівняємо результати роботи програми apssymmap з відомою програмою espresso на прикладі, представленому нижче:
Результат роботи програми espresso:
espresso -Dexact -oeqntott test.txt
Результат роботи apssymmap:
Видно, що програма apssymmap видає 8 різних варіантів замість одного у espresso. Однак, більш цікавим фактом є те, що результат espresso не є оптимальним. Якщо відкинути всі загальні частини в цих рішеннях, можна побачити, що у espresso залишиться дві імпліканти:
!X7*!X5*!X4*X2*X1
і
X7*!X6*X5*X4*X3*X1
що містять відповідно 5 і 6 змінних, а в рішенні apssymmap будуть імпліканти
!X5*X3*X2*X1
і
X7*!X6*X3*X2*X1
містять 4 і 5 змінних, тобто на дві менше. Як висновок можна зробити висновок, що симетричні карти є не тільки більш зручним методом при ручній мінімізації бульових функцій, але і перевершують інші методи при вирішенні цього завдання на комп'ютері.