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

Начнем с поиска двухэлементных простых совокупностей (одноэлементные уже найдены и включены в допустимую совокупность А*). При этом прежде Всего проверяется условие неортогональности строк анализируемой пары, а затем строится соответствующий минор и выясняется, вырожден ли он. В ходе этого процесса выявляются также пары, составленные из неортогональных строк, но не являющиеся простыми совокупностями. Из этих пар формируются затем трехэлементные подмножества, рассмотрением которых можно ограничиться при поиске трехэлементных простых совокупностей.  Подобным образом совершается переход к поиску четырехэлементных простых совокупностей и т. д. В данном случае процесс заканчивается на рассмотрении трехэлементных подмножеств. Результат представляется булевой матрицей (с. 204), столбцы которой соответствуют строкам матрицы U*, а строки задают найденные простые совокупности. Легко находится кратчайшее столбцовое покрытие этой матрицы, состоящее из десяти столбцов: 1, 3, 4, 9, 11, 13, 15, 19, 23 и 24. Присоединяя соответствующие строки матрицы U* к допустимой совокупности , получаем кратчайшую ДНФ рассматриваемой булевой функции.

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

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

Частичная булева функция задает разбиение булева пространства М на три части М¹, М° и , представляющие собой множества наборов, на которых функция принимает соответственно значения 1, 0 или не определена. Рассматривая две частичные булевы функции f и g, будем говорить, что функция f реализует функцию g. если  и , т. е. если можно так доопределить функцию g, сменив некоторые из ее значений «—» на 1 или 0, что она совпадет с функцией /.

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

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