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

Страницы работы

Содержание работы

Напомним, что процесс нахождения определяющих элементов итеративен. Например, в начале процесса   элемент у81  не может быть  признан  определяющим,  так как он совместим с элементами у14 и у85, которые   не    совместимы между собой. Однако после  того, как элемент у14 войдет в подмножество совместимых элементов, определяемое элементом у46,,  элемент у81    становится  определяющим.

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

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


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


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

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

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


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

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

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


В этом случае


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

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


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

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

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

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

Похожие материалы

Информация о работе