В предыдущей статье я рассказал, как симметричные карты позволяют достаточно просто и быстро минимизировать булевые функции, но не осветил два момента: получение разных вариантов минимального решения и автоматизацию самого алгоритма минимизации. Расскажу здесь об этом более подробно.



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

Итак, в примере из предыдущей статьи, можно найти ядро функции для следующей симметричной карты:



Оно равно:

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