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

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

Очевидно, что задача синтеза оптимальной схемы, реализующей заданную частичную булеву функцию /, тесно связана с оптимальным доопределением этой функции или'оптимальным выбором среди полностью определенных булевых функций, реализующих функцию /. Определение оптимальности булевой функции будет при этом зависеть от типа схем, в пределах которого ищется схемная реализация частичной булевой функции. В частности, при реализации функции на ПЛМ оптимальной -следует считать такую булеву функцию, у которой кратчайшая ДНФ содержит минимальное число членов. Нахождение такой функции и одновременное получение ее кратчайшей ДНФ составляет содержание задачи мини-ми з ации частичной булевой функции .

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

Для решения этой задачи может быть применен описанный ранее метод, в основе которого лежит предварительное получение множества всех максимальных интервалов. В данном случае метод модифицируется следующим образом: обязательному покрытию подлежит лишь множество М¹, а интервалы, которым могут принадлежать элементы этого множества, выбираются среди максимальных интервалов множества . Однако будучи ограниченной по мощности множеств М¹ и М°, слабо определенная булева функция может обладать большим числом аргументов и вследствие этого весьма большим числом максимальных интервалов множества . Конечно, можно было бы ограничиться рассмотрением «полезных» интервалов, как мы назовем те из максимальных интервалов множества , которые пересекаются с множеством М¹, однако и их число может оказаться чрезмерно большим.

Изложим в связи с этим другой подход к решению данной задачи.

Нахождение кратчайшей ДНФ слабо определенной булевой функции. Задача сводится к разбиению множества М¹ на минимальное число подмножеств так, чтобы каждое из них содержалось в некотором максимальном интервале множества . Назовем такие подмножества интервально-поглощаемллми. Очевидно, что некоторое подмножество множества М¹ интервально-поглощаемо в том и только том случае, когда поглощающий его минимальный интервал содержится в множестве , т. е. не пересекается с множеством М°. Очевидно также, что при поиске указанного минимального разбиения множества М ⁱ есть смысл ограничиться рассмотрением максимальных интервально-поглощаемых подмножеств этого множества, т. е. таких подмножеств из М¹, которые интервально-поглощаемы, но перестают быть такими при добавлении в них любого из остальных элементов характеристического множества М¹.

Каждое из максимальных интервально-поглощаемых подмножеств Mi задает некоторый класс максимальных интервалов в множестве , а именно таких интервалов, проекции которых на множество М¹ равны между собой и совпадают с множеством Mi. Рассмотрение максимальных интервалов заменяется рассмотрением их классов, и поэтому чем больше различных максимальных интервалов содержится в каждом классе, тем эффективнее оказывается применение данного подхода.

Именно эти соображения и положены в основу предлагаемого метода минимизации слабо определенных булевых функций.

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

Продемонстрируем работу метода на конкретном примере, когда множества М¹ и М°, характеризующие частичную булеву функцию /, заданы соответственно матрицами