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

ОЮЗ СОВЕТСНИХ ОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 09 у И а 06 Г 7/00 АНИЕ ИЗОБРЕТЕНИЯ/00,проразрядов реверсла счета соотвеса реверсивногоса подключен к1 мента И узла сче вного счетчика узственно, вход сбросчетчика узла сбро выходу второго элеТдГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ К АВТОРСКОМ,К СВИДЕТЕЛЬСТВ(54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ .БУЛЕВЫХ ФУНКЦИЙ) содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, триггеры и узел счета, причем информационный вход устройства подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход первого триггера является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет реализации скобочных форм булевых функций, представленных в виде алгебраических уравнений, уст" ройство содержит элементы И, первые входы первого, второго и третьегоэлементов И подключены к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и к управляющему входу устройства, выходэле; мента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен кпервому входу четвертого элемента И, выход которого подключен к нулевому входу первого триггера, единичный вход которого подключен к выходу первого элемента И, второй вход которого подключен к выходу узла счета и к второму входу второго элемента И, выход которого подключен к .единичному входу второго триггера, нулевой вход которого подключен к выходу третьего элемента И, второй вход которого подключен к выходу первого триггера, второй вход четвертого элемента И подключен к выходу второго триггера, выходы триггеров подключены к информационным входам узла счета, управляощий вход которого подключен к управляющему входу устройства, при этом узел счета содержит элементы И,реверсивный счетчик и дешифратор, инверсный выход которого подключен к первому входу первого элемента И узла счета, второй вход которого подключен к управляющему входу узла счета и к входу сложения . реверсивного счетчика узла счета,вход вычитания которого подключен к выходу первого элемента И узла счета, входы второго элемента И узла счета подключены к информационным входам узла счета, выход которого подключен к прямому выходу дешифратора узла счета входы которого подключены к выходам98 2жит элементы И, первые входы первого, второго и третьего элементов И подключены к второму входу элемента ИСКЛЮЧАЮ ЩЕЕ ИЛИ и к управляющему входу. устройства, выход элемента ИСКЛЮЧАЮЩЕЕ .ИЛИ подключен к первому входу четвертого элемента И, выход которого подключен к нулевому входу первого триггера, единичный вход которого подклю"чен к выходу первого элемента И; второй вход которого подключен к выходу узла счета и к второму входу второго элемента И, выход которого подключен к единичному входу второго триггера, нулевой вход которого подключен к выходу третьего элемента И,второй вход которого подключен к выходу первого триггера, второйвход четвертого элемента И подключен к выходу второго триггера, выходы триггеров подключены к информационным входам узла счета, управляющий вход которого подключен к управляющему входу устройства, при этом узел счета содержит элементы И,реверсивный счетчи и дешифратор, инверсный выход которого подключен к первому входу первого элемента И узла счета, второй вход которого подключен к управляющему вхо ду узла счета и к входу сложения реверсивного счетчика узла счета, входвычитания которого подключен к выходу первого элемента Иузла счета,1входы второго элемента И узла счетаподключены к информационным входамузла счета выход которого подключен к пря мому выходу дешифратора узл а счет а, входы котооого подключены к выходам разрядов ревер сивного счетчика узла счета соответственно, вход сброса реверсивного . счетчика узла сброса подключен к выходу второго элемента И узла счета.1Устройство позволяет использовать дпя вычисления булевых функций алгебраическихуравнений знак дизъюнкции "+", открывающие и закрывающие скобки, что дает возможность реализовать скобочные формы булевых функций, пред ставленные в виде алгебраических урав нений, При этом отпадает необходимость в разработке принципиальных электрических схем за счет того, что . программирование производится .непосредственно по уравнению, а не по электрической схеме. Максимально облег чается труд программиста, так как любое уравнение является и программой . 1 01198еИзобретение относится к автомати,ке, в чзстйости к программному управлению технологическим оборудованием,и может быть использовано в программируемых системах управления технологическими объектами, алгоритм управления которых описывается с помощью булевых функций, в частности епрограммируемых контроллерах и управляющих вычислительных машинах, 10Устройства для вычисления булевыхфункций позволяют вычислять скобочные формы булевых функций, представленных в виде лестничной диаграммы. Наряду с такой формой представления булевых функций в технике используется представление булевых функ-ций в виде компактной записи и в форме алгебраических уравнений, Приэтом существует необходимость создания устройства, реализующего любуюсколь-угодно сложную булевую функцию, представленную в. форме алгебраицеского уравнения.Известно устройство для вычисления булевых функций, содержащее триггер, триггер результата, элемент И,элемент ИЛИ, первый и второй узлы инвертирования 1,Недостатком его является невозмож-.З 0ность вычисления скобочных форм булевых функций,Наиболее близким к изобретениюпо технической сущности является устройство для вычисления булевых функций, содержащее триггер, блок проверки на нечетность, блок определения конфигурации диаграммы, включающий ячейку памяти, распределитель,узел счета числа ответвления диаграм мы 21.Недостатком его является невозможность реализации скобочных форм булевых функций, представленных в видеалгебраических уравнений. . 45Цель изобретения - расширение обла-сти применения за счет реализациискобоцных форм булевых функций, представленных в виде алгебраических урае-.мнении,50Поставленная, цель достигается тем,1 что устройство для вычисления булевыхфункций, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, триггеры и узел счета,причем информационный вход устройства 55подключен к первому входу элементаИСКЛЮЧАЮЩЕЕ ИЛИ, выход первого триггера является выходом устройства, содер1 Оч 9898 4 3его решеыия, поэтому для программирования достаточно просто "перепи-.сать" это уравнение в память устройства без каких-либо преобразований.Кроме того, программирование по .урав .нению позволяет автоматизировать ,ввод программы (например, вводить программу от вычислительной машины).Решить булевое уравнение - значит. найти его значение на данном наборе 1 О аргументов. Для любого булевого уравнения вычисление ведут в порядке естественной записи аргументов,т.е.слева направо.Пример уравнения 15Х, Х+ХХ 4) 5 ХЬ(,Хт ХВЯ Х 4Х,=У. (1) Индексы при аргументах определяют20порядок вычисления. В начале вычисления устанавливают значение функции равное 1. Решают уравнение, вычисляя по порядку аргументы.в следующем порядке. Обозначают единицей значение аргумента, указан" ное в уравнении, если -этот аргумент записан без знака инверсии (аргументы Х 1, Хд, Хд, Х 5, Х, Хр Х и Х 10 в уравнении (1), и соответственно обоз начают нулем, если этот аргумент записан со знаком инверсии (аргументы Х и Х в уравнении (1. При таком обозначении совпадение действительного значения аргумента и значе ния аргумента, указанного в уравнении, означает, что аргумент истинен (т.е. его вычисленное значение равно единице), несовпадение этих значений означает, что аргумент ложен 40 (т.е. его вычисленное значение равно нулю). Составляют таблицу по результатам этих рассуждений. Как видно из таблицы для выцисления аргумента можно использовать элемент проверки на четность (ИСКЙОЧАРЩЕЕ ИЛИ с инверсией). Если на входы элемента подавать сигналы действительного значения аргумента и значения, указанного в уравнении то на выходе получают вычисленное значение аргумента. В процессе вычисления уравнения, существует два условных перехода:.когда вычисленный аргумент истинен и, после него стоит знак дизъюнкции "+";когда вычисленный аргумент ложен и после него нет знака дизъюнкции (т.е.стоит знак конъюнкции).В примере (уравнение (1 знакдизъюнкции стоит после аргументов Х,Хдю Х 5 ф Хт и Хд.В первом случае процедура условного перехода такова: функции присваивается значение 1, накладывается запрет на вычисление остальных слагаемыхдизъюнкций до отыскания последнегоаргумента, входящего в данную дизьюнкцию, после чего вычисление продол"жается. Очевидно что если уравнениезаканчивается последним членом этойдизъюнкции, то результатом решенияэтого уравнения будет единица,Во втором случае функции присваива-,ется значение О, накладывается запрет.на вычисление остальных сомножителейданной конъюнкции до отыскания последнего аргумента, обнаруживается дизьюнктивный член к той .части функции,вкоторую входит только чти вычисленнаяконъюнкция, функции присваиваетсязначение 1 и вычисление продолжается. Очевидно, что если уравнение заканчивается последним членом даннойконъюнкции,то результатом решения этого уравнения будет О.Эти правила вытекают из предложеЗначениеаргумента,указанноев уравнении Действительное значение аргумента Вычисленноезначение артгумента. 501О55 ний булевой алгебры: если в дизъюнкции хотя бы один из слагаемых равен единице, то вся дизъюнкция равна единице; если в конъюнкции хотя бы один из сомножителей равен нулю, то вся конъюнкция обращается в нуль.Уславливаюсь правило для отыскания последнего аргумента дизъюнкций при первом условном переходе. Дпя этого рассматривают дизъюнкцию Х +Х +Х +Х= У (2)Если эта дизъюнкция входит в состав более сложного аргумента, то она должна быть заключена в скобкиХ+ Х 14 ХФ,+ ХпХ 1 (3)ИЛИХпХ,ФМ 2 ХЗ,мХя) +Хпя =Ч(4)5где ХП 1 и Х 0,- любые сколь-угодно сложные агрументы.Из уравнений (3) и (4) видно, что окончание дизъюнкции определяется налицием закрывающей скобки. Однако. любой член дизъюнкции может быть сложным аргументОм, в свою очередь содержащим скобки, Например, Х 2= 9 4(Я+ + 3) у тогда уравнение (3) примет вид 15Я (агф Я 4 Д,Х) Хп-Ори этом по ходу вычисления, если, например, Х= 1, имеется закрывающая скобка после аргумента Я д, которая не характеризует окончание данной дизъюнкции. Такие скобки, принадлежащие сложным аргументам, характеризуются тем, что каждой закрывающей скобке соответствует открываю 25 щая скобка и лишь последняя закрывающая скобка, указывающая на конец дизьюнкции, оказывается нескомпенсированной открывающей скобкой. Поэтому правило для отыскания последнего члена дизъюнкции можно трактовать так: по ходу вычисления подсчитывается количество открывающих и закрывающихскобок и тот наиболее близкий шаг вычислений, в котором число зак рывающих скобок хотя бы на одну больше числа открывающих скобок, указы-вает на конец дизъюнкции.Устанавливают правило для отыскания последнего аргумента конъюнкциипри втором условном переходе, Дляэтого. рассматривают конъюнкциюХ, ХХ Х=(6)Если эта конъюнкция входит в составболее сложного аргумента, то посленее должен стоять знак дизъюнкции,с помощью которого к ней присоединяется в общем случае любой, сколь-угодно сложный аргумент,50Х, Х,"ХХ+ Х,=1Из уравнения (7) видно, что окончание конъюнкции определяется наличием знака дизъюнкции "+", Однако каждый 55 из аргументов Х,Хя может быть сколь-угодно сложным, содержащим в свою очередь знаки дизъюнкции,НаприХ : я, + ф, Такие аргументы заключаются в скобки Тогда перед каждым знаком дизъюнк"ции, входящим в сомножитель вычисляемой конъюнкции, должна быть открывающая скобка и лишь в том случае, когда все открывающие скобки скожпенсированы закрывающими скобками, знакдизъюнкции "+" является указаниемна окончание конъюнкции. Тогда правило для отыскания последнего членаконъюнкции можно трактовать так: походу вычисления подсчитывается количество открывающих и закрывающих скобок , причем закрывающие скобки считаются лишь тогда, если имеется хотябы одна открывающая скобка, Если разность между числом открывающих и закрывающих скобок равна нулю, то наиболее близкий по ходу вычисления знакдизъюнкции "+" указывает на оконча,ние конъюнкции.На фи г. 1 представлена схема устройства; на фиг. 2 - схема узла счета,Устройство содержит элемент ИСКЛОЧАЮЩЕЕ ИЛИ 1 (схема проверки нанечетность), триггер 2, триггер 3узел 4 счета, элементы И 5-8. Узел4 счета содержит элементы И 9 и 10,реверсивный счетчик 11 и дешифратор 12.Элемент" ИСКЛЮЧАЮЩЕЕ ИЛИ 1 служитдля вычисления аргумента (в данномслучае для удобства построения схемы взят элемент ИСКЛЮЧАЮЩЕЕ ИЛИ , ане ИСКЛЮЧАЮЩЕЕ ИЛИ с инверсией, какдано в пояснении). Триггер 2 служитдля хранения текущего и вычисленного значений функции, Выход триггера 2 является выходом устройства.Сигнал, снимаемый с этого выхода,есть вычисленное значение функции.Установка триггера 2 в нулевое состосние определяет начало второго условного перехода, Триггер 3 служит дляфиксации первого условного перехода,установка триггера 3 в нулевое состояние определяет начало первого условного перехода,Узел 4 счета служит для подсчета открывающих и закрывающих скобокуравнения в процессе условных переходов.фа первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 через управляющий вход7;:164,Э устройства подается сигнал "Значенйе. аргумента, указанное в уравнении",.На второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 подается сигнал действительного значения аргумента, Выход элемента 5 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 соединен с первым входом .элемента И 5.Вход элемента И 5соедияен с выходом триггера 3, а вы" ход элемента И 5 соединен .с входом(вход установки нуля) триггера 2. На 10 вход элемента Иб подается через управляющий вход устройства сигнал "Дизъюнкция "+". Вход элемента Иб соединен с выходом узЛа 1 счета, а выход элемента Иб соединен с входом 15(вход установки единицы) триггера 2, На вход элемента И 7 через управляющий вход устройства подается сигнал "Закрывающая скобка ")", вход элемента И 7 соединен с выходом узла ,20 1 счета, а выход элемента И 7 соединен с входом (вход установки единицы),триггера 3. На вход элемента И 8 через управляющий вход устройства подается сигнал "Дизъюнкция "+", вход 25 элемента И 8 соединен с выходом триг- " гера 2, а выход элемента И 8 соединен с входом (вход установки нуля ) триггера 3. На вход узла 1 счета через управляющий вход устройства подаются З 0 сигналы "Открывающая скобка "(" и "Закрыеаоцая скобка" )" , вход узла 1 счета соединен с выходом триггера 3 а другой вход узла Мсчета соедйнен с выходом триггера 2, З 5Узел ч счета может, например,состоять иэ двоичного реверсивного счетцика 11 и дешифратора 12,Пример выполнения узла счета дан на фиг.2, Двоичный реверсивный счетчик 11 име ет вход "Сложение", вход "Вычитание" и вход установки нуля. Если выходы триггера через элемент И соединить с входом установки нуля счетчика, то перевод любого из двух 45триггеров в нулевое состояние будет, являться сигналом для начала подсчета открывающих и закрывающих скобок. При этом, если на вход "Сложение" подавать сигнал "Открываю щая скобка "(", а на вход "Вычита"ние" подавать сигнал "Закрывающая скобка ")" и начинать подсчет закрывающих скобок, если счетчик не находится в нуле, т.е, когда была подсчитана хотя бы одна открываоцая скобка, то нулевое состояние счетчика всег-, да определяет, что по ходу еыцисления все открывающие скобки скомпенсированы закрывающими. При этом можно использовать дешифратор числай =О. Единичный сигнал на выходе этого дешифратора и наличие по ходу вычисления закрывающей скобки определяют окончание первого условного перехода, В этом случае на обоих входах элемента И 7 будут единичные сигналы, и триггер 3 переведется в единичноесостояние. Единичный сигнал на выходе дешифратора и наличие по ходу вычисления знака "Дизъюнкция "+" определяют окончание второго условного перехода, при этом на обоих входах элемента Иб будут единичные сигналы, и триггер 2 переведется в единичное состояние.Устройство работает следующим образом.В нацале вычисления триггеры 2 и 3 устанавливаются в единичное состояние. В процессе вычисления через управляющий вход устройства на вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 подается сигнал "Значение аргумента, указанное в уравнении", на входы элементов Иб и И 8,подается сигнал "Диэъюнкция "+", на вход элемента И 7 подается сигнал "Закрывающая скобка ")" и на вход узла 1 счета подаются сигналы "Открывающая,скобка "(" и "Закрывающая скобка ")", Эти сигналы подаются в том порядке, как они записаны в уравнении; При подаче на один вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 сигнала "Зна,чение аргумента, указанное в уравнении", на другой вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 подается действительное значение аргумента. Если эти значения совпадают, т.е, на обоих входах будут либо нули, либо единицы то на выходе элемента будет нуль, и триггер 2 останется в единичном состоянии. Если после этого аргумента нет знака диэъюнкции,то вводится следующий аргумент, т.е. вычисление аргументов продолжается. Если же после этого аргумента есть знак дизъюнкции, то триггер 3 переведется в нулевое состояние, так как на обоих входах элемента, И 8 будут вдиничные сигналы. При этом накладывается запрет на вычисление последуоцих аргументов, так как на входе элемента И 5, соединенном с выходом триггера 3 будет нулевой сигнал. Одновременйо узел Й счета подготавли10 Й 98 аказ 8127/ Подписно ВНИИ Тира филиал П .ужгород Патент",Проектная,вается к отсчету открывающих и звкрывающих скобок. Если по ходу вычисления все открывающие скобки будут скомпенсированы закрывающими скобками и имеется лишняя закрывающая скобка ( частный случай, когда между знаком дизьюнкции и закрывающей скобкой .нет ни одной открывающей скобки ), то на обоих входах элемента И 7 будут единицы и триггер ) через вход установки едиО ницы будет переведен в единичное состояние.Если действительное значение аргумента и "Значение аргумента, указанное в уравнении" не совпадают,то 5 на выходе элемента ИСКЛ 10 ЧА 10 ЩЕЕ ИЛИ 1, будет единица, и по входу установки нуля триггер 2 переведется в нулевое состояние. При этом узел 1 счета будет подготовлен к отсчету открывающих 20 и закрывающих скобок, Если по ходу вычисления все открывающие скобки будут скомпенсированы закрывающими и имеется знак "Дизъюнкция "+" (част 98 10ный случай когда после вычисленного аргумента сразу же стоит знак дизъюнкции),то на обоих входах элементов Иб будут единицы, и триггер 2 будет переведен в единичное состояниеи вычисление продолжается.После вычисления последнего аргумента уравнения значение функции (О ; или 1) снимается с выхода первого триггера 2, это значение является результатом. решения уравнения. Предлагаемое устройство для вычисления булевых функций позволяет реализовать скобочные формы булевых функций, представленных в виде алгебраиеских уравнений, при этом отпадает необходимость в разработке принципиальных электрических схем за счет того, что программирование производится непосредственно по уравнению, а не по электрической схеме. Это снижает материальные затраты и ускоряет проектирование.