Ще раз про мінімізації булевих функцій

У попередній статті я розповів, як симетричні карти дозволяють досить просто і швидко мінімізувати булеві функції, але не висвітлив два моменти: отримання різних варіантів мінімального рішення і автоматизацію самого алгоритму мінімізації. Розповім тут про це більш докладно.



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

Отже, у прикладі з попередньої статті, можна знайти ядро функції для наступної симетричної карти:

image

Воно дорівнює:

!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)(5 V 2 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)(5 V 2 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)(5 V 2 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 на прикладі, представленому нижче:

image

Результат роботи програми espresso:

espresso -Dexact -oeqntott test.txt

image

Результат роботи програма apssymmap:

image

Видно, що програма 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 змінних, тобто на дві менше. В якості висновку можна зробити висновок, що симетричні карти є не тільки більш зручним методом при ручній мінімізації булевих функцій, але і перевершують інші методи при вирішенні цієї задачі на комп'ютері.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.