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

А матрица совместимости - значение

C₅ =

Последняя матрица имеет особенность — столбец с одной единицей. Это позволяет  редуцировать текущую ситуацию: интервал а расширяется так, чтобы он поглотил элемент 8, после чего в матрице совместимости вновь возникает столбец' с одной единицей, и расширению  подвергается интервал Ь, поглощающий при этом элемент 10. Оба интервала а и Ь выходят из игры, а интервал с, оказывающийся совместимым с каждым из остающихся в остатке элементов  3, 7 и 9, последовательно расширяется, поглощая все эти элементы. Так мы находим решение состоящее х интервалов, сообща покрывающих все элементы множества М¹.

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

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

В данном случае такой матрицей будет служить матрица покомпонентной ортогональности рассматриваемого интервала элементам множества М°. Столбцы этой матрицы соответствуют тем компонентам расширяемого вектор-интервала, которые имеют значение 0 или 1, а строки поставлены в соответствие строкам матрицы Uy и показывают (единицами), по каким из компонент последние ортогональны интервалу. Находя кратчайшее столбцовое покрытие матрицы покомпонентной ортогональности, мы находим тем самым некоторую минимальную совокупность компонент             вектор-интервала, значения которых следует сохранить, чтобы он остался ортогональным множеству М°.

Всем остальным компонентам присваивается значение «—».

Например, отношение покомпонентной ортогональности полученного интервала а :

-  - - 1 1 0 0 1 - - 1

элементам множества М°, т. е. строкам матрицы

U₀ =