Матрица простых совокупностей. Оптимальная реализация слабо определенных булевых функций, страница 7

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

Данный метод может быть рекомендован, когда мощности множеств М¹ и М° сравнительно невелики. Особенно критичным метод оказывается к числу элементов в множестве М¹, становясь весьма трудоемким уже при двух-трех десятках элементов в этом множестве. При дальнейшем увеличении мощности множества М¹ целесообразно перейти к описываемому ниже приближенному методу.

 Метод конкурирующих интервалов. Так был назван метод, идея которого заключается в параллельном «выращивании» интервалов, из которых в результате образуется решение.

Будем считать, что в текущей ситуации получено некоторое частичное решение Vi — совокупность интервалов множества ,не обязательно максимальных, покрывающих некоторую часть множества М¹, и обозначим через непокрытый остаток, образуемый теми элементами множества М¹, которые не принадлежат ни к одному из интервалов частичного решения. На очередном, (г+ 1)-м шаге частичное решение Vi преобразуется в новое частичное решение ., причем так, чтобы непокрытый остаток сократился по крайней мере на один элемент. Элементарными операциями такого преобразования могут служить лишь расширение некоторого из интервалов частичною решения в множестве и введение нового интервала

Конкретизация операции на очередном шаге производится на основе информации, заключенной в булевой матрице Ci отношения совместимости элементов из  с интервалами частичного решения, первые из которых ставятся в соответствие строкам матрицы, а вторые — столбцам При этом элемент а считается совместимым с интервалом и, если в множестве  существует интервал, поглощающий как а, так и u. Очевидно, что необходимое и достаточное условие совместимости можно сформулировать следующим образом: минимальный интервал, поглощающий а и u, должен содержаться в множестве . Получается такой интервал аналогично минимальному поглощающему интервалу для элементов булева пространства' компоненты троичного вектора, представляющего этот интервал, принимают значения соответствующих компонент векторов-аргументов при их совпадении, и значение «—» — в противном случае.

Например,

0 1 0 0 1 0 1 1 1 0          a

          - 1 0 – 0 0 0 –  1 0         u

      - 1 0 -  - 0 -  -   1 0    

Выбор очередного шага производится следующим образом.

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

Если в матрице С_i существует столбец без единиц, то это означает, что соответствующий интервал частичного решения не может быть расширен так, чтобы покрыть какой-либо из элементов множества М_i*. В этом случае он произвольно расширяется, если это возможно, на множествеи принимается в качестве одного пз элементов окончательного решения.