Минимизация системы булевых функций. Синтез ПЛМ с заданной выходной матрицей

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

Получение кратчайшей ДНФ системы F сводится к нахождению кратчайшего строчного покрытия матрицы К.

После его нахождения не составляет особого труда найти для каждого элемента покрытия соответствующий интервал пространства M. Для этого достаточно расщепить все пары (m_j,k), принадлежащие некоторому рассматриваемому максимальному интервально поглощаемому подмножеству P_t (элементу найденного покрытия), на элементы m_j и k и образовать из  элементов некоторое множество Q_t , а из вторых элементов — множество S_t , затем найти для множества Q_t минимальный покрывающий интервал пространства М и, если возможно, расширить его, но так, чтобы он не пересекся ни с одним из множеств М_K⁰, для которых kÎS_t .

Уточним этот метод для случая, когда система F задана парой булевых матриц Х и Y. Специфика этого случая заключается в том, что области определения всех функций f_i , системы F совпадают, будучи равны множеству М_f вектор-столбцов матрицы X, причем число элементов этого множества, как правило, сильно ограничивается. Каждое максимальное интервально поглощаемое подмножество P_t совпадает теперь с прямым произведением множеств q_tи S_t , представляя собой множество всевозможных пар, первый элемент которых выбирается из множества Q_t , а второй — из множества S_t , и это произведение представляется некоторым единичным минором матрицы У. Поэтому каждое из множеств P_t , Q_t и S_t однозначно определяет два других.

Отсюда следует, что поиск максимальных интервально поглощаемых множеств P_t можно заменить поиском соответствующих множеств Q_t , которые мы будем называть существенными для рассматриваемой системы (X, Y). Таким образом, громоздкий перебор подмножеств из множества Р, производимый при поиске максимальных интервально поглощаемых подмножеств, заменяется теперь на менее трудоемкий перебор подмножеств на множестве m_F, при котором отыскиваются все существенные подмножества.

Отсюда следует также, что множество всех существенных подмножеств из M_F может быть получено следующим путем.

Найдем сначала независимо для каждой функции f_i , системы F все максимальные интервально поглощаемые подмножества множества M_i¹ , а затем образуем всевозможные различные пересечения тех из них, которые соответствуют различным функциям f_i . Получаемое в результате множество подмножеств из M_F и будет являться множеством всех существенных подмножеств.

Пример. Пусть

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