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

Каждая строка этой матрицы задает некоторое максимальное интервально-поглощаемое подмножество из М¹, показывая единицами, какие именно элементы множества М¹ принадлежат ему. Например, первая строка этой матрицы задает совокупность трех строк матрицы , с номерами 4, 8 и 10. Минимальный поглощающий интервал для них получается достаточно просто:

01011001101       (4)  

01011001111       (8)

00100011100       (10)

0- - - -011- Так же просто выясняется, что этот интервал не пересекается с множеством М°. Он сравнивается по очереди с каждым элементом этого множества, в результате чего оказывается, что ни один из этих элементов не принадлежит данному интервалу. Нетрудно проверить, что при добавлении в рассматриваемое подмножество любого другого из остальных элементов множества М¹ соответствующий интервал будет пересекаться с множеством М°.

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

(соответствующие строки покрываемо     й матрицы отмечены знаком +)