Аналоговая модель для минимизации булевых функций

 

643897 "й.,х к первому входу соответствующего дополнительного обратимого инвертора, подключенного вторым входом через соответствующий ограничивающий диод к соответствующему истохтнику опорного напряжения и через ключ к соответствующему входу выходного обратимого сумматора, и входов каждого из N дополнительных обратимых сумматоров подключены через ! ограничивающие диоды к соответствующим 1О источникам опорных напряжений и через соответствующие обратимые инверторы и ключи — к одному из входов соответствующего основного обратимого сумматора.

На фиг. 1 приведен упрощенный вари- 35

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

2 показан граф функции.

Модель (фиг. 1) состоит из обратимых сумматоров 1 10, обратимых инверторов 20

1 1-30, диодов 31-50, источников опорных напряжений 51-70, ключей 71-90, блоков индикации 91 и 92.

Теоретическое обоснование анягоговой модели состоит в следующем. ?5

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

Очевидно, что задача нахождения наименьmего покрытия основного графа и задача определения оптимального покрытия гг — 40 мерного куба максимальными интервалами эквивалентны. Наименьшее покрытие графа, можно определить путем нахождения экстремальной величины потока в сети.

Пля этой цели положим, что булевая 45 функция задана совершенной диэъюнк тинной нормальной функцией и разобьем булевую функцию на два подмножества в одно из которых (A) входят конституенты с четным числом отрицательных перемен- 5О ных, в другое( — нечетным, и построим граф, в котором соединены соседние конституенты из обеих подмножеств. Йополнив полученный граф булевой функции до

55 расширенного введением источника Н и сток К (фиг. 2), положим, что пропускные способности pe6epHA;(A;A/A)) и Ц Кф б(Я ) больше или равны едиф нице, я гропускные способности ребер

8> равны или больше нуля. Тогда, если некоторую функцию g поставить в соответствие количеству вещества, гротекающего (в единицу времени) по ребру

4 3> or А < К 3>, причем; если это количество превьппа ет пропускную способность ребра А< З, го в ка адой вершине А количество притекающего вещест - ва равно количеству вытекакчцего. Число (p выражает количество притекающего на выход К вещества и называется потоком.

В случае, если величина потока (p > Q определена множеством ребер сети и принимает целочисленное значение, то при наименьшем потоке (р ребра, для которых

LP > О > образуют наименьшее покрытие графа (см. фиг. 2).

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

Вариант модели, приведенной на фиг.

1, работает следующим образом.

Функция, предназначенная для упрощения, представляется в виде двудольного графа, одни вершины которого соответствуют конституентам с четным числом огрицательных переменных (A), а другиеконституентам единицы с нечетным числом оерннаеепепых переменных (В н набирается при помощи ключей 71-74 и

87-90. Соседние конституенты единицы, отличающиеся одной переменной, соединены через ключи 75-86 ребрами, Основной граф дополнен до расширенного введением начальной Н и конечной К вершин (фиг. 2). В качестве моделей вершин графа используются обратимые суммагоры, а моделями ребер служат обратимые инверторы. Схема модели удовл е твор яе т со о т нош ени ям задачи о минимальном потоке, т.е. удовлетворяются принципы непрерывности и ограничения по гока. i

0ля выходных сигналов { -ro сумма-. тора имеется зависимость

Z.лр;;+ Ед;; -(.), где ф -величина потока, что соответствует,условию непрерывности потока. Ограничители напряжения 4диоды 31-50 и источ ники опорных напряжений 51-70) устанавливаются пропорционально пропускной способности соответствующего ребра и моделируют зависимость ограничения потока в ребрах. Наличие обратимых инверторов 11-30 в каждом ребре вызвано