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

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

Матрица простых  совокупностей.

Продолжая минимизацию рассматриваемой булевой функции, можно получить в явном виде характеристическое множество , удалить из него элементы, покрываемые найденной допустимой совокупность A⁺, построить матрицу бинарного отношения принадлежности оставшихся элементов интервалам из множества A* и приступить к поиску ее кратчайшего покрытия. Однако при большом числе элементов в множествеэтот метод оказывается трудоемким, а строящаяся матрица — громоздкой.

Опишем в связи с этим другой метод, основанный на использовании матрицы простых совокупностей.

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

а) в множестве М¹ существует некоторый элемент, принадлежащий каждому из интервалов совокупности , и не принадлежащий более ни одному из максимальных интервалов;

б) не существует другой совокупности , содержащейся в  и обладающей свойством а.

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

Сформулируем следующее правило, позволяющее находить простые совокупности непосредственно в множестве А простых импликант, задаваемых соответствующими максимальными интервалами множества М¹.

Подмножество , множества А представляет собой простую совокупность в том и только в том случае, когда:

а) пересечение всех интервалов из А  не содержится в объединении интервалов из А \ ;

б) в множестве A не существует другого подмножества , содержащегося в  и обладающего свойством а.

Это правило легко переносится на случай, когда множество А задано троичной матрицей U.

Известно, что пересечение любых интервалов, если только оно не пусто, также представляет собой интервал, причем представляющий его вектор получается из векторов,  представляющих пересекающиеся интервалы, следующим образом: в компонентах, где все векторы-аргументы имеют значение «—», он также получает значение «—», а остальным компонентам присваивается значение 0 или 1, совпадающее со значением одноименных компонент некоторых векторов-аргументов (остальные имеют там значение «—»). Например, пересечение интервалов  0 1 — 0 — — — ,   — 1 — — 0 — 1 и 0 1 — 0 0 — 1 образует интервал 0 1 — 00 — 1.

Подмножество  взаимно неортогональных строк матрицы U является простой совокупностью в том и только том случае, когда а) минор, образованный пересечением тех из остальных строк матрицы U, которые неортогональны каждой из строк подмножества  со столбцами, в которых все строки подмножества имеют значение «—», не вырожден, б) не существует другого подмножества строк Uj, содержащегося в , и обладающего свойством а.

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

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

Если из множества А простых импликант предварительно выделены (неважно, каким методом) некоторая допустимая совокупность А⁺ и соответствующий ей текущий остаток А*, то поиск простых совокупностей ограничивается множеством А*: анализу подвергаются только подмножества этого множества. Однако при построении соответствующих миноров используются строки как матрицы U*, так и матрицы   .

Именно на такой ситуации мы остановились в решаемом примере, поскольку она оказалась тупиковой для примененного итеративного метода конструирования допустимой совокупности.

Итак, будем искать простые совокупности в полученной ранее 24-строчной матрице U*, представляющей текущий остаток A*.