УСТРОЙСТВО для Советский патент 1970 года по МПК G06G7/32 

Изобретение относится к спепиализированным вычислительным устройствам для минимизации булевых функций. Известные устройства основаны на принципе перебора, который является очень громоздким и требует больших затрат времени. Целью данного изобретения является сокращение количества операций перебора при аналкзе и €И1нтезе булевых функций и сокращение затрат времени. Указанные цели -были достигнуты благодаря тому, что В данном устройстве, содержащем 2 переключателей выбора кОНституент единицы и /С 2 индикаторов, соответствующих К двоичным переменным булевой функции, каждый т-н переключатель выбора конституент единицы своим нормально разомкнутым контактом Соединен с общей шиной всех индикаторов т-ой конституенты, а нормально замкнутые контакты г-го переключателя соединены со входам-и и;Нди.каторов, соответствующих неременным, по которым т-нач конституента является соседней с другими конституентамикое сокращеиие возможно,, т. е. до тех пор, пока сокращенное произведение удовлетворяет заданной функции. Полученные таким образом сокращенные члены (первичные импликанты) могут быть подраз.делены на три групны. 1.Существенные импликанты, входящие в cccTSiB любой минимальной дизъвонктивной нормальной формы, которые образуют ядро дизъюнктивной формы. 2.Несущественные импликанты, которые могут входить В составе различных минимальных нор альных форм. Образуют разветвление дизъюнктивных нормальных форм. 3.Избыточные первичные импликанты, которые не входят ни в одну из :минимальных туииковых дизъюнктивных нормальных форм. Каждая конституента единицы заданной функции может накрываться одной или более чем одной нервичпой импликантой. Если конституента накрывается только одной первичной имнликантой, тс эта импликанта является существенной, а все переменные, входящие в ее состав, называют существенными переменными данной хонституенты. Если конституента накрывается двумя или большим числом иервичиых импликант, то существенными переменнымп будут те, которые содержатся во всех первичных импликантах (т. е. являются общими для них), накрывающих данную конституенту. Остальные переменыые, входящие и первичные импликанты, Называются несуплествеиными. Кроме того, в конституенте могут иметься такие переменные, которые не входят «и в одну первичную импликанту, накрывающую данную конституенту.

Такие неременные но аналогии с избыточными первичными импликантами будут называться здесь избыточными переменньгми.

При м е р. Пусть булева я фупкния четырех неременных, заданная в совершешюй дизъюнктивной нормальной форме,

Ф - АЗ Х Xi Хо Ч- Xz Х Xi --- Xz Xz Xi Ao -b лз A2 1 0 : 3 Xy X АО

- АЗ Xz X 1 АО + Х$ Xz X XQ

Вьшолняя последовательно операции попарного акленва;ния, получим нолную систему первичных импликант Ф АЗ Л2 л 1 X(j + АзА2Ао + л л АО + АЗ Х.,

Проа:нализи рОВав имнликантную таблицу, сделать Вывод о том, что первичная импликанта является избыточной, а остальные импликанты н их логическая сумма предстаВляют собой единственную тупиковую минимальную дизъюнктивную форму.

Булевая функния может быть представлена в внде таблицы (см- таблину), где конституенты располагаются в порядке возрастающих номеро,в. Иначе говоря, каждой конституенте соответствует некоторое десятичтюе число. В каждой констнтуенте переменные могут быть заменены номерами соседних конституепт состояний, как это показано ъ таблице. Соседние конституепты т-ная и (/п±2) оклеиваются но 1переменно4| А ,-. Для самой неремешюй берется знак минус, для ее отрицания - зпак плюс. Таким образом, для любой конституанты можно определить весь ряд десятичных чисел, .которые являются номерами соседних конституент. Панример, для коиституенты под номером /Осоответствующие десятичпые числа будут следующие:

P{;.-:m-f 2..:104-1

11

от-12 10-2 8 Pi:--- m + +

Рз° -те --2 10-8 2

Это означает, что конституента нод номером 10 склеивается с конституентой под номером // по переменной Ао, а также с конституентой под номером 8 - но неременной Х и т. д. Такая таблица отображения переменных в конституентах номерами конституент легко может быть построена для любого чнсла неременных /С по указанному выше правилу.

Для рассматриваемого примера булевой функции в каждой конституенте «1 подчеркнуты снизу чертой ее существенные переменные. Неотмеченные переменные в конституентах «1 являются либо несущественными, либо избыточными переменными.

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

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

На фиг. 1 приведена схема устройства для определения существенных переменных в конституентах булевых функций для К. неременных. Оно содержит 2 позиционных переключателей, каждый из которых содержит однн замыкающий контакт на схеме О---2 -I) и /С размыкающих контактов. На размыкающих контактах указаны номера переключателей конституент, к которым эти контакты относятся.

Кроме того, это устройство содержит 2 групп индикаторов по К в каждой группеКаждый индикатор в оиределенной груцпе соответствует двоичной неремешюй в конституенте булевой функции.

Замыкающий конта кт каждого переключателя коммутирует общие щииы индикаторов одной групны (констнтуенты), а размыкающие контакты коммутируют раздельные цени индикаторов, расположенных в конституентах, соседних с рассматрнвае.мой конституентой В случае нри.менения разделительных диодов или пороговых элементов /С размыкающих контактов в каждом из переключателей могут быть заменены одним размыкающим контактом.

45 На фиг. 2 показана схема устройства на три переменных с раздатительными диодами. Для определения существенных переменных булевой функции переключатели номеров конституент, при которых функция принимает значения «1, ставятся в положение «включено. При этом подключаются общие шины рядов индикаторов выбранных ко«ституент. Одновремеино размыкаются размыкающие контакты, соответствующие номерам конституент /. Таким образом вивуально но светящимся индикаторам определяются существенные переменные заданной булевой функции.

Как видно из таблицы /, существенные переменные в конституантах под номерами /, 4 и 14 (15) образуют существенные импликанты, логическая сумма которых представляет собой единственную тупиковую минимальную дизъюнктивную форму.

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

Предмет изобретения

Устройство для определения существенных переменных в конституентах булевых функций, содержащее 2 переключателей выбора копституент единицы и К. 2 индикаторов, соответствующих К двоичным переменным булевой функции, отличающееся тем, что с целью сокращения количества операций перебора при анализе и синтезе булевых функций первый

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

размыкающие контакты т-го переключателя соединен со входами индикаторов, соответствующих переменным, по которым иг-ная конституента является соседней с другими конституентами.

i,2 i-- -а

0.

ФФ:Ф:

Ы

и

/г

-tt2

з

-0--6/774;

-о-в-

Ci

- «J:--