Устройство для
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
287408
Союз Советских
Социалистических
Республик
Зависимое от авт. свидетельства М—
Заявлено 25.1Х.1968 (№ 1273125118-24) с присоединением заявки ¹â€”
Приоритет—
Опубликовано 19.Х1.1970. Бюллетень ¹ 35
Дата опубликования о1писагипя 1-.II.1971
Кл. 42m, 15!34
Комитет по делам изобретений и открытий при Совете Министров
СССР.л!ПК G 06f
УДК 681.323.056 (088.8) Авторы изобретения
А. H Пивоваров, В. Ф. Акимов и А. М. Егоров
Заявитель
УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ СУЩЕСТВЕННЫХ
ПЕРЕМЕН НЫХ
Изобретение относится к специализированным вычислительным устройствам для минимизации булевых функций.
Известные устройства основаны на принципе перебора, который является очень громоздким и требует больших затрат времени.
Целью данного изобретения является сокращение количества операций перебора прп анализе и синтезе булевых функций и сокращение затрат времени.
Указанные цели были достигнуты благодаря тому, что в данном устройстве, содер>кащем 2 " переключателей выбора конституент единицы и 1(2 индикаторов, соответствующих К двоичным переменным булевой фучткции, каждый т-й переключатель выбора конституент единицы своим нормально разомкнутым контактом соединен с общей шиной
Всех индикаторов т-ой конституенты, а нормально замкнутые контакты m-ro переключателя соединены со входами индикаторов соответствующих переменным, по которым llf-на 1 конституента является соседней с другими конституентами, При анализе и синтезе булевых функций производится попарное «склеивание» произведений логических переменных, что приводит к последовательному сокращению числа переменных в произведениях до тех пор, пока такое сокращение возможно, т е. до тех пор, пока сокращенное произведение удовлетворяет зада1гной функции Полученные таким образом сокращенные члены (первичные импликанты) могут быть подразделены на три группы, 1. Существенные 1смп.113канты, входящие в состав любой минимальной дизыонктивной нормальной формы, которые образ3 ют ядро дизьюнктнвной формы.
1о 2. Несущественные импликанты, которые могут входить в составе различных минимальных нормаль!Iblx форм. Ооразуют разветвлсние дизъюнктивн11х нормаль.1ых форм.
3. Избыточные первичные нмпликанты, ко15 Topblp не входят llil В одну из мини ма 7bklbtx тупиковых диз7 юнктпвных 1юрмальных форм, Каждая конституента единицы заданной функции может накрываться одной илн более чем одной первнч11ой импликантой. Если конституента накрывается только одной первичной импликантой, TI; эта импликанта является существенной, а все переменные. входящие в ее состав, называют существенными переменными данной конституенты.
Ec IH 1
Номер конституентвь по которой склеивае!с» дан а» по переменной
Значение функ!(ии (р
Конститз ента
- з, Лз
45! (1 з Л з X! Xo
1
3
5
7
9
11
12
0
0
1
0 (!
Х3 Хз Х! Ло
Хз Хз Л! Хо
Х,Х,Х, Ло
ХзМ, Х! Хо
Х,ХЗ X! Xo х,х,х х
Хз Хз Х! Хо
50
2 о
0
12
14
3
12
1 1
14
9
15
10
8
11
13
0
ХзХ,Х! Хо
Хз Х2 Х! Хо
Х,Х,Х! Хо хз хз х! Ло
Лз Хз Х! Хо
ХЗХ,X! Хо
) 8
1
0
1
15
12
15
14 !
ХЗХ Х, Х!
Л -Х Х,Х
3 2 о
14 менные, входящие II первичные импликанты, называются несущественными. 1хроз!е того, в конституенте могут иметься такие переменные, которые не входят ни в одну первичную импликапту, накрывающую данную конституенту, Такие переменные по аналогии с избыточными первичными импликантами будут называться здесь из!быточнь!3!и переменньгми.
Пример Пусть булевая функция четырех переменных, заданная в cGIIepIIIeIIIIGII дизъюнктивной нормальной форме.
+ == Х з Х -Х! Хо + Хз Хо Х! Х„- — Хз Х2 Х! Хо +
+ - 13 Х2 Х! (О . ХЗХ2 Х! 3Х2. ХО + ХЗХ2Х! (О
Вы!полияя последовательно операции попарного склеивания, получим полную систему первичных импликант
@ = Лз Х2 Х! Хо + Хз Х2 Хо + Х2 Х! Хо + Хз Х! °
Проанализировав импликантную таблицу, можно сделать вывод о том, что первичная импликанта Х2Х,Х0 является избыточной, а остальные импликанты и их логическая сумма представляют собой единственную тупиковую минимальную дизъюнктивную форму.
Булевая функция может быть представлена в виде таблицы (см таблицу), где коггституенты располагаются в порядке возрастающих но<меров. Иначе говоря, каждой конституенте соответствует некоторое десятичное число.
В каждой конституенте переменные могут быть заменены номерами соседних конституент состояний, как это показано в таблице. Соседние конституенты m-иая и (т+2 ) склеиваются по переменной Х;. Для самой переменной берется знак минус, для ее отрицания — знак плюс, Таким образом, для любой конституенты можно определить весь ряд десятичных чисел, .которые являются номерами соседних конституент, Например, для ко!нституенты по:I номером 10 соответствующие десятичные числа будут следующие:
РГ - т —,2 — 10 — - 1 =11
РI — — — m — — 2 =10--2= 8
Р" — m -+ 2 - = 10 + 4 = — 14
Р(30 m 2з =-10 8=
Это означает, что конституента под номером 10 склеивается с конституентой под !номером 11 ло переменной Х„а также с конституентой и!о,д номером 8 — по переменной Х! и т. д, Такая таблица отображения переме!шых в конституентах ггомерами конститувнт легко может быть построена для любого числа переменных
К по указа!н!ному выше правилу.
Для рассматриваемого примера булевой функции в каждой конституенте «1» подчеркну ты снизу чертой ее существенные переменные.
Неотмеченные переменные в конституентах «1» являются либо, несущественными, либо избыточными переменными.
B этом случае легко увидеть, что существенными будут только переменные, соответст вующие номерам конституент нуля в строках таблицьг, на которых функция принимает значе ия единицы (.в конституентах «1»).
Из числового представления таблицы видно, что для выявления существенных переменных в кан<дой конституенте может быть построено логическое устройство, с помощью которого определяются в один этап все существенные перемен!ные булевой функции, На фиг. 1 приведена схема устройства для определения существенных переменных в комституентах булевых функций для К переменных. Оио содержит 2 позиционных переключателей, каждый из которых содержит один замыкающий контакт (на схеме 0---2 " — 1)) и
К размыкающих контактов, На размыкающих контактах указаны номера переключателей конституент, к которьгм эти контакты относятся.
Л
Кроме того, это устройство содери<ит 27" групп индикаторов по К в каждой группе.
1<аждый индикатор в определенной группе соответствует двоичной переменной:в конституенте булевой функции
Замыкающий контакт каждого переключателя коммутирует общие шины индикаторов одной группы (конституепты), а размыкающи" контакты коммутируют раздельные цепи ин;IHKBTopGH, расположеннь!х в конституентах, соседних с рассматриваемой конституентой
В случае применения разделительных диодов или пороговых элементов К размыкающих контактов в кагкдом из переключателей могут быть заменены одним размыкающим контактом.
287408
На фиг. 2 показана схема устройства на три переменных с разделительными диодами.
Для определения существенных переменных булевой функции переключатели номеров конституент, при которых функция принимает з начения «1», ставятся в положение « включено».
При этом подключаются общие шины рядов индикаторов выбранных конституент. Одновременно размыкаются размыкающие контакты, соответствующие номерам конституент 1. Таким образом визуально по светящимся индикаторам определяются существенные переменные заданной булевой функции.
Как видно из таблицы 1, существенные переменные в конституентах под номерами 1, 4 и 14 (15) образуют .существенные импликанты, логическая сумма которых представляет собой единственную тупиковую минимальную дизъюнктивную форму.
B данном устройстве за один этап одновременно выделяются все существенные переменные, анализируя которые, при некотором навыке, визуально с помощью этого устройства легко можно определять и все существенные и несущественные импликанты, входящие в тупиковые дизъюнктнвные формы.
Предмет изобретения
Устройство для определения существенных переменных в конституентах булевых функций, содержащее 2 переключателей выбора конP
10 ституент единицы и К 21 индикаторов, соответствующих К двоичным переменным булевой функции, от.гичающееея тем, что с целью сокращения количества операций перебора при анализе и синтезе булевых функций первый
15 зажим источника питания через замыкающий контакт каждого т-го переключателя выбора конституент единицы соединен с каждой оощей шиной всех индикаторов т-й конституенты, а второй зажим источника питания через
20 размыкающие контакты m-ro переключателя соединен со входами индикаторов, соответствующих переменным, по которым nz-ная конституента является соседней с другими конституентамн.
287408
Фиг 2
Составитель И. В. Долгушева
Корректор T. А. Уманец
Редактор Н. С. Коган
Заказ 830/4 Тираж 480 Подписное
Ц11ИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР
Москва, Ж-35, Раушская наб., д. 4/5
Тип.. .арьк. фил. пред, «Патент»
