Классические методы минимизации булевых функций. Сжатие булевой матрицы

Напомним, что процесс нахождения определяющих элементов итеративен. Например, в начале процесса   элемент у⁸₁  не может быть  признан  определяющим,  так как он совместим с элементами у¹₄ и у⁸₅, которые   не    совместимы между собой. Однако после  того, как элемент у¹₄ войдет в подмножество совместимых элементов, определяемое элементом у⁴₆,,  элемент у⁸₁    становится  определяющим.

Отыскивая  максимальные   единичные миноры для найденных определяемых  подмножеств и дополняя их найденным ранее парным минором, мы приходим в 

Рис. 38.   Синтезирован-    конечном результате к следующему решению:            

ный генератор заданной

На рис. 38 показана матричная схема, реализующая найденный оператор T^Ñ.

14. Классические методы минимизации булевых функций

Познакомившись с элементарными матричными схемами, рассмотрим теперь чуть более сложные схемы, получаемые из элементарных легко реализуемой сверткой выходного вектора у по операции дизъюнкции или конъюнкции. Такие схемы описываются суперпозициями ÚB^Ú, ÙВ^Ù,ÙВ^Ú ,ÚT^D,ÚT^Ñ ,ÙT^Dи ÙT^Ñ. Это разнообразие можно свести к двум суперпозициям ÚB^Ú и ÚT^D, которые и стоит изучить более подробно.

Р е а л и з а ц и я    м о н о т о н н ы х    б у л е в ы х   функций. Как это следует из (3.6), составной оператор  \/В^ задает уравнение

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

Например, структура схемы ПЛМ, изображенной на рис. 39, описывается булевой матрицей

В этом случае

Легко видеть, что схемы данного типа реализуют функции, оказывающиеся монотонными: если некоторый аргумент меняет свое значение с 0 на 1, а значения остальных аргументов остаются прежними, то функция не может при этом изменить значение с 1 на 0. Нетрудно также показать, что любая монотонная булева функция реализуется некоторой схемой с оператором \/В^.

Рассматривая некоторую конкретную булеву матрицу В, можно поставить вопрос: а нельзя ли как-то упростить ее или найти другую более простую матрицу С, порождающую оператор ÚC^Ù, эквивалентный по действию оператору ÚB^ — в этом случае будет выполняться отношение равносильности ÚC^Ù =ÚB^Ù. При этом за критерий простоты можно принять число строк в матрице или число единиц в ней.

Чтобы ответить на этот вопрос, найдем сначала троичную матрицу U, представляющую булеву функцию f, реализуемую оператором ÚB^Ù. Для этого достаточно соответственно преобразовать структурную матрицу B, заменив в ней нули значением «—». В рассматриваемом примере это приводит к следующему результату:

Строки матрицы U интерпретируются при этом как элементарные конъюнкции, а матрица в целом — как дизъюнкция этих конъюнкций. Возможна и другая интерпретация, в определенном смысле эквивалентная первой, но оказывающаяся в ряде случаев более удобной. Она имеет теоретико-множественный характер и основана на замене булевой функции f (x₁, x₂, … , x_n) ее характеристическим множеством М¹, составленным из тех элементов булева пространства М значений переменных   x₁, x₂, … , x_n , на которых функция f принимает значение 1 (в то время как пространство М в целом содержит все 2ⁿбулевых вектора с п компонентами). Каждая строка матрицы U рассматривается при этом как интервал пространства М — множество булевых векторов, получаемых из данной строки всевозможными заменами значения «—» на 0 или 1. Этот интервал представляет собой характеристическое множество соответствующей элементарной конъюнкции. Матрица U в целом рассматривается как объединение интервалов, задаваемых отдельными строками, т. е. как характеристическое множество функции f. Очевидно, что все заданные в матрице U интервалы являются подмножествами характеристического множества М¹, в связи с чем их можно называть интервалами из М¹ или интервалами множества М¹.

На языке последней интерпретации поставленная задача упрощения оператора ÚB^Ù , реализующего булеву функцию f, будет звучать так: найти минимальную совокупность интервалов из М¹, объединение которых равно  М¹. При такой формулировке за критерий оптимальности принимается число строк в искомой матрице C, в основном и определяющее сложность матричной схемы, реализующей функцию f. Назовем эту задачу задачей о кратчайшем интервальном покрытии множеств  М¹

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