Устройство для

ОП ИСАНИЕИЗОБВЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 287408 Союз Советских Социалистических РеспубликЗависимое от авт. свидетельства М явлено 25.1 Х,1968 ( 1273125118-24) з, 421 п" 153 с присоединением заявки хо -Комитет по деламобретений и открытри Совете МинистреСССР(088.8) 970, Бюллетень хЪ 35 Опубликован ния списания 15.11.19 Дата опублик Авторы 1 зобретенияЗаявитель А. Н, Пивоваров, В. Ф, Акимов горов УСТРОЙСТВО ОПРЕДЕЛЕНИЯ СУЩЕСТВЕННПЕРЕМЕННЫХ оулевь еивани х, что нию ч тех по и синтезепарное склх переменнь му сокраще ведениях до х ф нкццц е произветриводит к исла перер, пока таализе С 51 ПО ески льно роцз При ан производит дений логи последоват меццых в п Изобретение относится к специализированным вычислительным устройствам для минимизации булевых функций.Известные устройства основаны на принципе перебора, который является очень громоздким и требует больших затрат времени.Целью данного изобретения является сокращение количества операций перебора прц анализе и синтезе булевых функций и сокращение затрат времени.Указанные цели были достигнуты благодаря тому, что в данном устройстве, содеркащем 2" переключателей выбора конституецт единицы и К 2 индикаторов, соответствующих К двоичным переменным булевой фу 51 кции, каждый т-й переключатель выбора коцстцтуент единицы своим нормально разомкнутым контактом соединен с общей шиной ьсех индикаторов т-ой конституенты, а нормально замкнутые контакты пт-го переключателя соединены со входами индикаторов соответствующих переменным, по которым и-на 1 конституента является соседнец с другими конституентами,кое сокращение возможно, т. е. до тех пор, пока сокращенное произведение удовлетворяет задацтной функции Полученные таким образом сокращенные члены (первичцые импликанты) могут быть подразделены на трц группы,1. Существенные 1 смпликанты, входящие всостав любой минимальной дизыонктивной нормальной формы, которые образ ют ядро дцзьюцктцвцой формы.1 о 2. Несущественные цмплцканты, которыемогут входить в составе различных минимальных цормальцых форм. Ооразуют разветвлсцце дизъюнктивць 1 х цормаль 11 ых форм,3. Избыточные первичные цмплцканты, ко торые це входят цц В одну цз мини х 1 альныхтупиковых дизъюнктпвцых 1 юрмальцых форм,Каждая конституента единицы заданнойфункции может накрываться одной нлц более чем одной первичной имплцкантой. Если конституецта цакрывастся только одной первичной цмпликантой, тс эта имплцкацта является существенной, а все переменные, входящие в ее состав, называют существецш 1 мц перемеш 1 ымц даццой констцтуецты.Ес 11 и конституента накрыв 11 ется дв 1 я цлцоольшим числом первичных цмплцкацт, то существец 1 ымц переменць 1 мц оудут те, которые содеркатся во всех первичцых цмпликантах (т, е. являются общими для них), накрываю- ЗП щцх даццу 1 о коцституецту. Остальные пере287408 40 Номер конституентвь по которой скгеиваетсн данная по перемен- ной Значениефункииф Конститз ента-з, Ли 45 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 0 1 1 0 О 0 3 ХзХз Х Ло ХзХз М Мо Х,Х,Х Хо ХзМ,Х Хо Хз Хз Х Хо Х,Х,Х, Хо Хзхз Х Хо 10 50 2 о 4 7 0 1 6 7 12 13 14 2 3 12 11 14 15 8 9 1 О 11 15 55 10 9 8 11 1 О 13 12 Х,Х,Х,Х, ХзХ,Х Х, 1Хз Хз Х Хо Хзхо Х, Ло Мз Хз Х Хо ХзХ,Х, Хо 8 9 141 1 0 0 1 1 60 15 12 13 15 14Хз Хз Х, Хо 1 о Х. Х Х, Х3 2о 14 меццые, входящие в первичные имплцкацты,Базываются несущественными, 1 хроме того, вкоцституецте могут иметься такие переменные, которые це входят ци в одну первичнуюимпликацту, накрывающую данную коцститу.енту,Такие переменные по аналогии с избыточными перви пгьоги импликацтами будут цазываться здесь избыточцыми переменными.П р и м е р. Пусть булевая функция четырех переменных, заданная в совершецойдизъюцктивцой цормальцой форме.ф = Х 3 Хз Л 1 Хо + Хз Хз Х Хо Хз Х 2 Х Хо ++ Хз Хзо Лз Хз Х ХоХз Л 2 Л Ло Хз Х 2 Х ЛоВыполняя последовательно операции попарного склеивания, получим полцую систему цервичцых импликантФ = Лз Х, Х, Хо + Хз Хз Хо + Хо Х Хо + Хз Х.,Проанализировав импликацтцую таблицу,можно сделать вывод о том, что первичнаяимпликацта ХзХХо является избыточной, аостальцые импликапты и их логическая суммапредставляют собой единственную тупиковуюминимальную дизъюцктивцую форму.Булевая фуцкция может быть представленав виде таблицы 1 см таблицу), где коцституецты располагаются в порядке возрастающих номеров. Ицаче говоря, каждой коцституецте соответствует некоторое десятичное число.В каждой коцституепте переменные могутбыть заменены цомерами соседних коцституецтсостояний, как это показано в таблице. Соседцие коцституецты пг-цая и (и+2) склеиваются по перемецггой Х,. Для самой перемецпойберется знак минус, для ее отрицания - знакплюс, Таким образом, для любой коцституецты можно определить весь ряд десятичцых чиселкоторые являются номерами соседнихкоцституецт. Например, для коцституецты подномером 10 соответствующие десятичные чис,габудут следующие: Р ,": т + 2 - 10 + 1 = 11 Ро и 2 1 О э Я Р з - и + 2 з = 10 4 = 14 зо т -2 =-1 О - 8= 2Это означает, что коцституецта под номером 10 склеивается с коцституецтой под номером 11 ло переменной Ха также с коцституецтой пзо,д номером 8 - по переменной Х и т. д, Такая таблица отображения перемешых в конституецтах гиомерами коцститусцт легко может быть построена для любого числа перемецных К по указацному выше правилу.Для рассматриваемого примера булевой функции в каждой конституенте 1 подчеркпу ты снизу чертой ее существенные переменные. Неотмечеццые переменные в коцституецтах 1 являются либо, несущественными, либо избыточными переменными. 10 15 20 25 30 35 В этом случае легко увидеть, что существеццыюи будут только переменные, соответст вующие номерам коцституегцт нуля в строках таблицьг, ца которых функция принимает значения единицы 1 в коцституецтах 1),Из числового представления таблицы видцо, что для выявления существенных переменцых в каждой конституецте может быть построецо логическое устройство, с помощью которого определяются в один этап все существеццые перемеццые булевой функции,На фиг. 1 приведена схема устройства для определения существенных перемеццых в коцституецтах булевых функций для К переменцых. Оцо содержит 2 позициоццых переключателей, каждый из которых содержит один замыкающий контакт ца схеме 021" - 1)1 и К размыкающих контактов, На размыкающих контактах указаны номера переключателей коцституецт, к которьгм эти контакты отцосятся.Кроме того, это устройство содержит 2 групп индикаторов по К в каждой группе 1 хаждый индикатор в определенной группе соответствует двоичной переменной в коцституецте булевой функции.Замыкающий контакт каждого переключателя коммутирует общие шины ицдикаторов одной группы 1 конституепты), а размыкающие контакты коммутируют раздельные пепи ицдикаторов, расположеццых в коцституецтах, соседних с рассматриваемой коцституецтой В случае применения разделительцых диодов или пороговых элементов К размыкающих контактов в каждом из переключателей могут быть заменены одним размыкающим контактом.На фиг. 2 показана схема устройства на три переменных с разделительными диодами, Для определения существенных переменных булевой функции переключатели номеров конституент, при которых функция принимает значения 1, ставятся в положение включено. При этом подключаются общие шины рядов индикатор ов вы бр а нных конституент. Одновременно размыкаются размыкающие контакты, соответствующие номерам конституент 1. Таким образом визуально по светящимся индикаторам определяются существенные переменные заданной булевой функции.Как видно из таблицы 1, существенные переменные в конституентах под номерами 1, 4 и 14 (15) образуют существенные импликанты, логическая сумма которых представляет собой единственную тупиковую минимальную дизъюнктивную форму,В данном устройстве за один этап одновременно выделяются все существенные переменные, анализируя которые, при некотором навыке, визуально с помощью этого устройства легко можно определять и все существенные и несущественные импликанты, входящие в тупиковые дизъюнктнвные формы,Предмет изобретенияУстройство для определения существенныхпеременных в конституентах булевых функций,содержащее 2 переключателей выбора конРго ституент единицы и К 21 индикаторов, соответствующих К двоичным переменным булевойфункции, отличающееся тем, что с целью сокращения количества операций перебора прианализе и синтезе булевых функций первый15 зажим источника питания через замыкающийконтакт каждого т-го переключателя выбораконституент единицы соединен с каждой общей шиной всех индикаторов пг-й конституенты, а второй зажим источника питания через20 размьпсающие когнтакты ггг-го переключателясоединен со входами индикаторов, соответствующих переменным, по которым ггг-ггая конституента является соседней с другими конституентамн,287408Фиг 2 Составитель И. В. ДолгушеваКорректор Т, А. Уманеи Редактор Н. С. КоганЗаказ 830/4 Тираж 480 Подписное Ц 11 ИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 4/5Типарьк. фил. пред, Патент