Сжатие булевой матрицы. Методы сканирования булева пространства, страница 5

Поскольку последовательность наборов строго упорядочена, т. е. каждый набор однозначно определен местом, занимаемым им в таблице, то их можно и не показывать, что и делается при представлении минимизируемой функции в ЭВМ, когда набор отождествляется с адресом — номером ячейки памяти, куда помещается соответствующее значение функции  f (отсчет начинается с начального набора 0 0 ... 0). Таким образом, чтобы узнать, какое значение функция f принимает, например, на наборе 110100, достаточно извлечь содержимое ячейки с этим номером 110100, заданным в двоичной системе счисления (точнее говоря, с номером  k + 110100, где k — номер ячейки, с которой начинается размещение в памяти таблицы значений функции   f ).

Несложно выясняются значения функции f и на соседних элементах булева пространства. Например, если нас интересует значение, принимаемое функцией  f  на наборе, соседнем некоторому набору а по переменной x₂, то, как нетрудно сообразить, чтобы получить адрес ячейки, где находится искомое значение, надо изменить значение второй компоненты набора а. Аналогично находится набор, ортогональный заданному сразу по нескольким компонентам.

Чем меньше соседей в множестве М¹ имеет некоторый элемент этого множества, тем меньшему, как правило, числу различных максимальных интервалов он принадлежит. Учитывая это обстоятельство, описываемый метод начинает построение интервального покрытия множества М¹ с поиска интервалов для покрытия элементов с минимальным числом соседей — в этом случае конструирование покрытия будет более целенаправленным.

Прежде всего строится таблица соседей, в которой для каждого элемента характеристического множества М¹ показывается, по каким переменным этот элемент имеет соседей в множестве М¹, а также показывается общее число соседей. Эту таблицу удобно совместить с таблицей значений функции  f , заполняя прочерком соответствующие позиции для элементов множества М⁰.

Например, для булевой функции  f , заданной матрицей будет получена табл. 5 описанного типа.

Заметим, что порядок перечисления аргументов в показанных в таблице наборах в принципе безразличен, он должен лишь всюду быть одним и тем же. В данном случае мы принимаем, что аргументы представлены в наборах слева направо, в порядке их номеров: левая компонента поставлена в соответствие аргументу x₁, следующая направо — аргументу x₂  и т. д.

Элементов, не имеющих соседей, в множестве М¹ не оказывается, поэтому мы начинаем с рассмотрения элементов, имеющих по одному соседу. Таких элементов два:   00000   и   01011.  Первый из них имеет соседа по переменной x₁, откуда  следует обязательность интервала  - 0 0 0 0,  принимаемого в качестве первого элемента решения.  Аналогично находится обязательный интервал, определяемый вторым  элементом: 0 1 - 11. Все четыре элемента, принадлежащие найденным интервалам, исключаются из дальнейшего рассмотрения. 

Выбираем далее среди остальных элементов множества М¹ элементы с двумя соседями. Первым из них оказывается элемент 01100, имеющий соседей по переменным x₁ и x₅. Он окажется определяющим, если множеству М¹ будет принадлежать также элемент, ортогональный ему по этим переменным (и только по ним). Убеждаемся  в выполнении этого условия, выясняя значение функции f   на  наборе  11101,  и  включаем  в решение обязательный  интервал -110- , определяемый элементом 01100. Аналогичному рассмотрению подвергается имеющий двух соседей элемент 10110, определяющий, как оказывается, обязательный интервал 1 - 1 1 -. Все элементы множества М¹, принадлежащие полученным интервалам, также исключаются из дальнейшего рассмотрения.           

Анализируя элемент 11000, также обладающий двумя соседями, в данном случае по переменным x₂ и x₃, мы находим, что он не определяет однозначно некоторый обязательный интервал, так как на элементе 10100, ортогональном рассматриваемому элементу по переменным x₂ и x₃, функция f принимает значение 0. Однако в текущей ситуации любой содержащий его максимальный интервал будет допустим, поскольку в минимальном интервале, поглощающем этот элемент с его соседями, все элементы множества М¹, кроме самого элемента 11000, оказываются уже покрытыми выбранными ранее интервалами. Примем поэтому в качестве очередного элемента решения допустимый интервал 1 - 0 0 0 .