Устройство для вычисления булевых функций

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 594 С 06 Р ПИСАНИЕ ИЗОБРЕТЕНИА ВТОРСКОМУ СВИДЕТЕЛЬСТВУ мобильный зав А, И. Андерсо(57) Изобретениетельной техникевычисления булевленных в виде ал слиотносится к вычпредназначенож функций, преебраических ур авне ОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССРУ 610104, кл, С 06 Р 7/00, 1975.Авторское свидетельство СССРУ 1049898, кл, С 06 Р 7/00, 1982Авторское свидетельство СССРВ 1160391, кл, С 06 Р 7/00, 1983ДЛЯ ВЫЧИСЛЕНИЯ БУ ЯО 1 24292 ний. Цель изобретения - расширениеобласти применения устройства за счетвычисления скобочньж форм булевыхфункций, представленных в виде алгебраических уравнений. Устройство содержит сумматор по модулю два, триггер, группу коммутаторов, реверсивный счетчик. На входы команды устройства подаются сигналы "Значениеаргумента, указанное в уравнении,Дизъюнкция, "Открывающая скоба" и"Закрывающая скоба". На информационный вход устройства подаются действительные значения аргументовуравнения. Вычисление булевого уравнения ведется в порядке естественнойзаписи аргументов. После вычисленияпоследнего аргумента полученное значение функции считывается с выходатриггера. 4 ил., 1 табл.Изобрететне ) )10" и гт.я к вытислительетой техник- ., я бслее кснкре)ес кпрограммному упрявлецик) технологическим 06 ОЕ)удоваептем.Цель теэоб)ретеетия - рясццрение обЛЯ С ТИ 11 ) МОЕЕЕИ Я 3 Я СЧЕТ БЬЧИСЛЕЕИ 51скобочных форм булевых функций, представлен;Еьех и вице ялгебракческихуравнений,51 а фИГ, Е ПрИВЕцЕца СтпуКтурцая)схема. устройства,цля 5)ычисленкя бут)евых функций; ня фит 2 - пример реализации устройства на уровне стандартных функциональных элсмееетов;на фиг. 3 - временная диаграмма работы устройства; ця фиг 4 - япгорить раооты уст 1)отстгтэустройство (фиг., 1 к 2) соцержктсумматор 1 по моду.п два, триггер 2,груг:пу 3 1 оммутятог)ов, реверсивныйсчетчик 4. )-руппу входов 5 команды,информацконный вход б и вьходПервый коммутатор Группы 3 (фиг. 2)может быть выголнен в виде элементаЗАПРЕТ 8, второй коммутатор можетбыть Выпоетнее на элементе НГ-ИЛИ 9 кэлементе (24)И-.2 ИЛИ 10, установкаустройства Б исходпое состояние исинхрон 1 зяция ОсупеРствляются ПОвходу )1 устян 01)ки В исходное состоя"ние и синхровходу 12.Ия фие ) прке)едена Временна)е ди -аграмма рябо.гы усройства где показано взаимное расположение сигналовна информационном входе 6, Входе 5команды к синхровходе 12 устройстга,ВЬГХОдаХ С.ут 15 ятОр)я: 110 МОдуЛЕО,Ц)3 а )триггера 2) г:ервого и второго коммутаторов Группы 3 и вь.хода реверсивного счетчикаф:; )кг)-Р,) т ф 1)мОГч ) псг)Ркхтючятьс 5; ) наг)риме 1) . ЛО )те"реднему фронту ст) Гня:а поступяеотпего на синхровхо, 12 у)1:ойст)3 я, С прихс)- ДОМ СИЕХР)оцтЗ)РУЮГЕГО КМПУЛЬСЯ ИРИодинаковых уров).ях,";игических игналов 1 я входах Обре тес)ГО и пряьт)ЗГОтС:С ттткЕ; тЦЕ ИЗ) РЕПГ ГО СОС)тОЯЦКЯ, Сттн)ГРОЕИэтРУЮ)дкй КМ- пульс поцяе-ся ца ицхровход 12 устройства когда сигналы ня входах элементов устройства принимают )стя-. НОВИВЕЛЕЕЕ СЯ ЗНЯЧР НИ 5 .,Ситнял устянсг)ки стройства Б ис- ХОДНОЕ СОСТО 511Р, 7)ЕРЕЕ)ЭЕ)ЯЕЕ)5)тй СЧРТ чкк 4 в состояние "0 я триггер 2 в состояние "1, ттоткгетс 51 асинхронно на вход 11 установя"1 в исходное сс стоят)не ус ТЕ)ой.тц; 1 еред каждьгм циклом вычяспецкя очередной 6 ут)евойфунк)ии,11 я фиг 4 пре;стявлен алгоритм работы устройсе:за, логические блоки110 тот) О Г 0 ) ьп 10. тня т с:,.РЕуез)це д ей с тееи 51; блэк- устяпо 13 кть состояниетт т)СЧ Е Г ЧИК а т, О я ЗНО Е 0И С О С т О яНИ Ет рк г г е р а .". разное " 1 "," бл о к 2 - л р О 111 верить состо)тн 13 Р счетчика 4 на равенство 0" блох 3 - проверить состоят)цие триггера 2 ца равенство 0блок 4 - проврить, сов 1 адяет лиЧЕЙСГВИТЕЛ-.ЕЕ)Е ЗнаЧРЦИЕ ЯвгтгРЕЕТЯ СОзначением) указацным в уравтенин;блое; 5 - проверить, имеется,тгк знактт )т,состояние триггера 2 раве:ое 0бЛОК- ует,а)СВИТЬ СОСтОВНИЕ трИГ) .-Рря 2 равноз "1", блок 8 - прове")ить имеется ли зякрывяюпЕа 5 скобат) , ")Л)3)К 3 - ПРОВЕРИТЬ, ИМЕЕТСЯ ЛИоткре)е)яеопс).я скоба("; блок 10),вепичить содержимое счегчика 4 цаблок ) 1 - умень)тить содержимоесчетчика - ня 1У)тройство использует для вычислеЕвкя б-;тл)ЗВЫХ ф )НКцКй яЛГЕбраКЧЕСКИХ, 15,)тОбот с 6 тлРВОГО утавиация вы --")еле)кя )Еег.;,Г в ееор 5 дке естественнойЗЯПКСИ ЯРЕ Ут)ецтОЬ) СЛЕВа НЯТЭаВО.,1 т 5 тт) Рттец).; (1 ) КЕ.ЕПЕКСЬЕ Етрк ат) -ГУМЕН) ЯХ Олт)ЕЦЕЛЯЮТ ПОРЯДОК ЗЫЧИСЛЕ -пия,В начале вычисления устанавлквакт значение Ь),еекь)ки рагное 1 . Ре ткогда вычисленный аргумент истинени после него стоит знак дизъюнкции"+ , когда вычисленный аргумент ложен и после него нет знака цизъюнкции(т.е, стоит знак конъюнкции).В примере (уравнение ) знакдизъюнкции стоит после аргументовХ 2, ХЗ, Х 5, Х 7 и Х 9.В первом случае процедура условного перехода такова: функции присваивается значение единицы", накладывается запрет на вычисление остальныхслагаемых дизъюнкции до отысканияпоследнего аргумента, входящего вданную дизъюнкцию, после чего вычисление продолжается.Очевидно, если уравнение заканчивается последним членом этой дизъюнкции, то результатом, решения этогоуравнения будет "1",Во втором случае функции присваивается значение нольнакладываетсязапрет на вычисление остальных сомножителей данной конъюнкции до отыскания последнего аргумента, обнаруживается диэъюнктивный член к этойчасти функции, в которую входит только что вычисленная конъюнкция, функции присваивается значение "1" ивычисление продолжается. Очевидночто если уравнение заканчиваетсяпоследним числом данной конъюнкции,то результатом решения этого уравнения будет "О". Для отыскания послед в .него аргумента дизъюнкции при первомусловном переходе рассмотрим дизъюнкцию видаХ 1+Х 2+ХЗХп=У (2)Если эта дизъюнкция входит в состав более сложного аргумента, тоона должна быть заключена в скобки(Х 1+Х 2+ХЗ+Х)хХ+1=7 (3)илиХ+1(Х 1+Х 2+ХЗХ)+Х+2=7 (4)где Х+1 и Х+2 - любые сколь угодносложные аргументы.Из уравнений (3) и (4) видно, что окончание дизъюнкции определяется наличием закрывающей скобки. Однако любой член дизъюнкции может быть в свою очередь сложным аргументом и .содержать скобки. Например Х 2=В 1(В 2+ +ВЗ), тогда уравнение (3) принимает вид(Х 1+В 1 (В 2+В 3) +ХЗ+ Х ) Х+1 =У (5)При этом по ходу вычисления, если, например, действительное значение Х равно "1" и совпадает со значени 25 30 Для отыскания последнего аргумента конъюнкции при втором условном переходе рассмотрим конъюнкциюХ 1 хХ 2 хХЗХ =У (6)Если эта конъюнкция входит в состав более сложного аргумента, топосле нее должен стоять знак дизъюнкции, с помощью которого к нейприсоединяется в общем случае любой,сколь угодно сложный аргумент Х 1 хХххХЗХ+Х+=У (7) .Из уравнения (7) видно, что окон 50 55 5 1 О 15 20 ем, указанным в уравнении, то результат операции "ИСКЛЮЧАЮЩЕЕ ИЛИ" надсигналами "Действительное значениеаргумента" и "Значение аргумента,указанное в уравнении" равен "О".Зто означает, что аргумент Х 1, являющийся членом дезъюнкции, истинен,так как после Х стоит знак дизъюнкции "+", то и вся дизъюнкция истинна.Для продолжения вычислений необходимонайти последний член этой дизъюнкции,Однако закрывающая скобка после аргумента ВЗ не характеризует окончаниеданной дизъюнкции. Такие скобки, принадлежащие сложным аргументам, характеризуются тем, что каждой закрывающей скобке соответствует открывающая скобка и лишь последняя закрывающая скобка, указывающая на конецдизъюнкции, оказывается нескомпенсированной открывающей скобкой. Поэтому правило для отыскания последнего члена дизъюнкции можно трактоватьтак: по ходу вычисления подсчитывается количество открывающих и закрывающих скобок и тот наиболее близкий .шаг вычислений, в котором число закрывающих скобок хотя бы на однубольше числа открывающих скобок, указывает на конец дизъюнкции. чание конъюнкции определяется наличием знака дизъюнкции "+. Однако как и при первом условном переходе, каждый из аргументов может быть сколь угодно сложным, содержащим в своюочередь знак дизъюнкции и скобки.Например Х 2 х(В+В 2)хХЗХ+Х++=У (8) . Тогда перед каждым знаком диэъюнкции, входящим в сомножитель вычисляемой конъюнкции, должна быть открывающая скобка и лишь в том .случае, когда все открывающие скобки скомпенсированы закрывающими, знак диэъюнкции + является указанием на окончание конъюнкции.Тогда правило для отысканияпоследнего члена коцьюнкции можнотрактовать так: по ходу вычисленияподсчитывается количество открывающих и закрывающих скобок, причемзакрывающие скобки считаются лишь 1",тогда, когда имеется хотя бы однаоткрывающая скобка. Если разностьмежду числом открывающих и закрывающих скобок равна нулю, то наиболееблизкий по ходу вычисления знакдизъюнкции + указывает на окончаниеконъюнкции.Устройство работаетследующим 15образом (фиг. 1 - 4).В начале вычислений счетчик 4 устанавливается в состояние "ноль(значение его выходного сигнала равно "единице), а триггер 2 - в состояние 11 единица . В процессе вычисленийпоследовательно по шагам для каждогоаргумента булевого уравнения сумматор 1 по модулю два проверяет совпадение сигналов "Действительное значение аргумента (на информационномвходе) и "Значение аргумента, указанное в уравнении". Если для какоголибо аргумента его действительноесостояние совпадает со значением, 30указанным в уравнении, то на выходесумматора 1 по модулю два появляетсясигнал логический "ноль"Если к тому же имеется знак дизъюнкциито выполняются условия для первогоусловного перехода и сигнал +" (через второй коммутатор группы 3) увеличивает на единицу значение содержимого счетчика 4,Когда содержимое счетчика 4 отличается от исходного, то значениеего выходного сигнала принимает состояние равное нулю , при этом нак,ладывается запрет на вычисление последующих аргументов и изменение состояния триггера 2,Начинается подсчет счетчиком 4 открывающих и закрывающих скобок.При этом коммутаторы группы 3 функционируют таким образом, что на вход обратного приращения счетчика подается сигнал Закрывающая скоба , а на вход прямого приращения сигнал "Открывающая скоба". Когда количество закрывающих скобок хотя бы на одну 55 больше числа открывающих скобок,счетчик 4 устанавливается в исходное состояние 110", а его выходной сигнал принимает значение 1 , и вычисленияпродолжаются.Если для какого-либо аргумента егодействительное состояние не совпадает со значением, указанным в уравнении, то на выхоце сумматора 1 по модулю два появляется сигнал логическая11 1 11Если отсутствует знак дизъюнкции+ , то выполняются условия для в торого условного перехода . Триггер 2сбрасывается в состояние " О " , а наег о выходе 7 устанавливается эн ач ениевыходного сигнала (функции) равное" О " . Счетчик 4 подготовлен к о тсч ету открывающих и закрывающих скобок ,причем закрывающие скобки и одсчи тываются лишь тогда , когда имеется хотябы одна открывающая скобка , Если находу вычисления в се открывающие скобки скомпенсированы закрывающими ( состояние счетчика 4 равно " О" ) и имеется знак дизъюнк ции " + " , то триггер2 устанавливается в исходное состояние , равное " 1 " , и вычисления и родолжают с я ,После проверки всех аргументовре алиэуемой булевой функции , представленной в виде алгебраическогоуравнения , энач ени е функции "О " или" 1 " снима ется с выхода 7 триггера 2 ,Это значение является результатомрешения уравнения .Рассмотрим в качестве примера работу устройства. при вычислении уравн ения ( 1 ) . Для определенности предйоложим , например , ч то аргументы Х 1 ,ХЗ , Х 7 , Х 1 О находятся в состояниилогической единицы , а остальныеаргументы в состоянии логическогонуляСоставим та 1 блицу, характеризующую состояние устройства в процессе вычисления.Формула изобретенияУстройство дпя вычисления булевых Функций, содержащее сумматор по модулю два, триггер, группу коммутаторов и реверсивный счетчик, входы обратного и прямого приращения и синхровход которого соединены соответственно с выходами первого и второго коммутаторов группы и синхро1242928 О Есть ХЗ Х 4 Есть е О 2 Нет О Х т О 2 НетЕсть О . Х е- номер условного перехода. Вычисленное значение функцииданном случае равно "единице". входом устройства, входы сумматора по модулю два соединены с информационным входом устройства и входом команды "Значение аргумента, указанное в уравнении" устройства, о т - л и ч а ю щ е е с я . тем, что с целью расширения области применения устройства за счет вычисления скобочных форм булевых функций, представленных в виде алгебраических уравнений, первый коммутатор состоит из элемента ЗАПРЕТ, второй коммутатор группы состоит из элемента НЕ-ИЛИ и элемента (2-4)ИИЛИ, причем выход признака нуля реверсивного счетчика соединен с инверсным входом элемента ЗАПРЕТ, первым входом элемента НЕ-ИЛИ, первым прямым входом первой группы входов элемента (2-4)ИИЛИ, первым входом первой .группы входов установки единицы и первым прямым входом группы входов установки нуля триггера, второй вход первой группы входов установки единицыи инверсный вход группывходов установкинуля которого соединен с входом команды "Дйзьюнкция" устройстваи вторым прямым входом первой группывходов элемента (2-4)ИИЛИ, третийпрямой вход первой группы входовкоторого соединен с выходом триггера,.выходом устройства и вторым входомэлемента НЕ-ИЛИ, выход которого соединен с первым входом второй группы 1 О входов элемента (2-4)ИИЛИ, второйвход второй группы входов которогосоединен с входом команды Открывающая скоба" устройства, вход команды"Закрывающая скоба" которого соеди нен с прямым входом элемента ЗАПРЕТ,инверсный вход первой группы входовэлемента (2-4)ИИЛИ соединен с, выходом сумматора по модулю два и вторым прямым входом группы входов уста новки нуля триггера, синхровход ивход начальной установки которогосоединены соответственно с синхровходом и входом установки в исходноесостояние устройства, вход сброса 25 реверсивного счетчика соединен свходом установки в исходное состояние устройства.1242928 Информационный Аодб Вход Х коман.ды Гинсройод диод суммапюрапа модуласдыяод триггера Р Выход коммугоащороо группы Яо -/"Рыгоо коммунагпороо еруппыЭГосударств ам изобрет осква, ЖТираж 671нного комитета СССРний и открытийРаушская наб., д.