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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, триггеры и узел счета , причем информационный вход усТ ройства подключен к первому входу элемента ИСК/ЮЧАЮЩЕЕ ИЛИ, выход первого триггера является выходом устройства , отличающееся тем, что, с целью расширения области применения за счет реализации скобочных форм булевых функций, представленных в виде алгебраических уравнений, устройство содержитэлементы И, первые входы первого, второго и третьего элементов И подключены к второму входу элемента ИСКЛОЧАЮЩЕЕ ИЛИ и к управляющему входу устройства,выходэлег мента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к первому входу четвертого элемента И, выход которого подключен к нулевому входу первого триггера, единичный вход которого подключен к выходу первого элемента И, второй вход которого подключен к выходу узла счета и к второму входу второго элемента И, выход которого подключен к единичному входу второго триггера , нулевой вход которого подключен к выходу трет;ьего элемента И, второй вход которого подключен к выходу пер .вого триггера, второй вход четвертого элемента И подключен к выходу второго триггера, выходы триггеров подключены к информационным входам узла счета, управляющий вход которого подключен к управляющему входу устройства , при этом узел счета содержит i элементы И,реверсивный счетчик и дешифратор , инверсный выход которого (Л подключен к первому входу первого элемента И узла счета, второй вход которого подключен к управляющему входу узла счета и к входу сложения . реверсивного счетчика узла счета,вход вычитания которого подключен к выходу первого элемента И узла счета, входы второго элемента И узла счета со подключены к информационным входам уз- . 00 ла счета, выход которого подключен к со прямому выходу дешифратора узла счета, СХ) входы которого подключены к выходам разрядов реверсивного счетчика узла счета соответственна, вход сброса реверсивного счетчика узла сброica подключен к выходу второго эле1мента И узла счета.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ .

РЕСПУБЛИК (19) (И) а 06 Г 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

t

К АВТОРСКОМ,К СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

1 (21) 3408255/18-24, (22) 01.02.82 (46) 23.10.83. Бюл. 11 39(72) Ю. M. Футерман, Н. К. Подставкин, А. И. Мариночкин и T.À.Ðàêóëü (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР и 6 10104, кл.. G 06 F 7/00, .1976.

2. Авторское свидетельство СССР и 813413, кл. G 06 F 7/00,. 1979 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

БУЛЕВЫХ ФУНКЦИЙ) содержащее элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ, триггеры и узел счета, причем информационный вход устройства подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход первого триггера является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет реализации скобочных форм булевых функций, представленных в виде алгебраических уравнений, уст" ройство содержит элементы И, первые входы первого, второго и третьего элементов И подключены к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и к управляющему входу устройства, выход эле; мента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к первому входу четвертого элемента И, выход которого подключен к нулевому входу первого триггера, единичный вход которого подключен к выходу первого элемента И, второй вход которого подключен к выходу узла счета и к второму входу второго элемента И, выход которого подключен к .единичному входу второго тригге-. ра, нулевой вход которого подключен к выходу третьего элемента И, второй вход которого подключен к выходу первого триггера, второй вход четвертого элемента И подключен к выходу вто рого триггера, выходы триггеров подключены к информационным входам узла счета, управляющий вход которого подключен к управляющему входу устройства, при этом узел счета содержит элементы И,реверсивный счетчик и де- Я шифратор, инверсный выход которого подключен к первому входу первого элемента И узла счета, второй вход которого подключен к управляющему вхо- ду узла счета и к входу сложения . реверсивного счетчика узла счета, вход вычитания которого подключен к выходу первого элемента И узла счета, входы второго элемента И узла счета 4 подключены к информационным входам уз-, ла счета, выход которого подключен к прямому выходу дешифратора узла счета, входы которого подключены к выходам разрядов реверсивного счетчика узI ла счета соответственно., вход сброса реверсивного счетчика узла сбро,са подключен к выходу второго эле1мента И узла счета. 3>

98 2 жит элементы И, первые входы первого, второго и третьего элементов И подключены к второму входу элемента ИСКЛЮЧАЮ

ЩЕЕ ИЛИ и к управляющему входу устройства, выход элемента ИСКЛЮЧАЮЩЕЕ .

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

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

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

E 10498 а

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

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

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

Недостатком его является невозмож-.З0 ность вычисления скобочных форм булевых функций.

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

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

Цель изобретения - расширение обла- I сти применения за счет реализации скобочных форм булевых функций, представленных в виде алгебраических урав-.

1 нении.

Поставленная, цель достигается тем, что устройство дпя вычисления булевых функций, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, триггеры и узел счета,причем информационный вход устройства 55 подключен к первому входу элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ, выход первого триггера является выходом устройства, содер1049898 4 з

его решеыия, поэтому для программирования достаточно просто "nepenu-. !

cBTb это уравнение в память устройства без каких-либо преобразований. Кроме того, программирование по .урав.нению позволяет автоматизировать ,ввод программы (например, вводить программу от вычислительной машины).

Решить булевое уравнение - значит. найти его значение на данном наборе 10 аргументов. Для любого булевого уравнения вычисление ведут в порядке естественной записи аргументов,т.е. слева направо.

Пример уравнения 15

Х, (Х + Х Хф .(3(> i X+(X+4 Х8Я-Х 4

Ф Х40 Y. (1) Индексы при аргументах определяют 20 порядок вычисления.

В начале вычисления устанавливают значение функции равное 1. Решают уравнение, вычисляя по порядку аргументы.в следующем порядке.Обозначают единицей значение аргумента, указан" ное в уравнении, если -этот аргумент записан без знака инверсии (аргумен-.

Tbl Xg» Xg» X4, Xg» Xg» Х8» Xq и Х,0 в уравнении (1), и соответственно обоз- З0 начают нулем, если этот аргумент записан со знаком инверсии (аргументы

Х» и Х6 в уравнении (1)). При таком обозначении совпадение действительного значения аргумента и значения аргумента, указанного в уравнении, означает, что аргумент истинен (т.е. его вычисленное значение равно единице), несовпадение этих значений означает, что аргумент ложен 40 (т.е. его вычисленное значение равно нулю). Составляют таблицу порезультатам этих рассуждений.

Как видно иэ таблицы для вычисления аргумента можно использовать элемент проверки на четность (ИСКЙОЧАРЩЕЕ ИЛИ с инверсией). Если на входы элемента подавать сигналы действительного значения аргумента и значения, укаэанного в уравнении,, то на выходе получают вычисленное значение аргумента.

В процессе вычисления уравнения, существует два условных перехода: . когда вычисленный аргумент мстинен и . после него стоит знак дизъюнкции "+"; когда вычисленный аргумент ложен и после него нет знака дизъюнкции (т.е. стоит знак конъюнкции).

В примере (уравнение (1)) знак дизъюнкции стоит после аргументов Х, ХЭ» Х5» ХТ v Хд.

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

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

Эти правила вытекают из предложеЗначение аргумента,указанное в уравнении

Действительное значение аргумента

Вычисленное значение арт гумента . 50

0

0 55 ний булевой алгебры: если в диэъюнкции хотя бы один из слагаемых равен единице, то вся диэъюнкция равна единице; если в конъюнкции хотя бы один из сомножителей равен нулю, то вся конъюнкция обращается в нуль.

Уславливаюсь правило для отыскания последнего аргумента дизъюнкций при первом условном переходе. Дпя этого рассматривают дизъюнкцию Х +Х +Х +...+

+Х„= У (2)

Если эта дизъюнкция входит в состав более сложного аргумента, то она должна быть заключена в скобки

1ОИ 9898.(Х<+ Х Ф Х +,„+ Xó)) ° Ч (3)

ИЛИ

) п, (Х,+М21ХЗ+,... Хя) +Хп+я =Ч,(4)

5,, (х,+Я,(а,+ Я,)+х>i,,iõ.) х„„= (5) .

При этом по ходу вычисления, если, например, Х = 1, имеется закрывающая скобка после аргумента Я д, которая не характеризует окончание данной дизъюнкции. Такие скобки, принадлежащие сложным аргументам, характеризуются тем, что каждой закрывающей скобке соответствует открываю25 щая скобка и лишь последняя закрывающая скобка, указывающая на конец дизьюнкции, оказывается нескомпенсированной открывающей скобкой. Поэтому правило для отыскания последнего члена дизъюнкции можно трактовать так: по ходу вычисления подсчитывается количество открывающих и закрывающих скобок и тот наиболее близкий шаг вычислений, в котором число зак- 35 рывающих скобок хотя бы на одну больше числа открывающих скобок, указывает на конец дизъюнкции.

Устанавливают правило для отыска- 40 ния последнего аргумента конъюнкции при втором условном переходе, Для этого. рассматривают конъюнкцию

Х, Х Х ... Х„= (e)

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

50 (7) Х1 Х X>... Х„+ Х„,„= Y

Из уравнения (7) видно, что окончание конъюнкции определяется наличием знака дизъюнкции "+", Однако каждый 55 из аргументов Х,...Хя может быть сколь-угодно сложным, содержащим в

csoe очередь знаки дизъюнкции.Напри. где Х» 1 и ХрФХ- л бые сколь-угодно сложные агрументы.

Из уравнений (3) и (4) видно, что окончание дизъюнкции определяется на-10 личием закрывающей скобки. Однако любой член дизъюнкции может быть сложным аргументОм, в свою очередь содержащим скобки . Например, Х2= h (Я +

+ 11 ), тогда уравнение (3) примет вид15 мер, Х = A + Я . Такие аргументы заключаются в скобки

Х1 (31+ Я l) Х3> -<<ë Хп (, (8)

Тогда перед каждым знаком дизъюнк" ции, входящим в сомножитель вычисляемой конъюнкции, должна быть открывающая скобка и лишь в том случае, когда все открывающие скобки сковпенсированы закрывающими скобками, знак дизъюнкции "+" является указанием на окончание конъюнкции ° Тогда правило для отыскания последнего члена конъюнкции можно трактовать так: по ходу вычисления подсчитывается количество открывающих и закрывающих скобок, причем закрывающие скобки считаются лишь тогда, если имеется хотя бы одна открывающая скобка. Если разность между числом открывающих и закрывающих скобок равна нулю, то наиболее близкий по ходу вычисления знак дизъюнкции "+" указывает на оконча,ние конъюнкции.

На фи г. 1 представлена схема устройства; на фиг. 2 - схема узла счета, Устройство содержит элемент ИСКЛОЧАЮЩЕЕ ИЛИ 1 (схема проверки на нечетность), триггер 2, триггер 3 „ узел 4 счета, элементы И5-8. Узел

4 счета содержит элементы И 9 и 10, реверсивный счетчик 11 и дешифратор 12.

Элемент" ИСКЛЮЧАЮЩЕЕ ИЛИ 1 служит для вычисления аргумента (в данном случае для удобства построения схемы взят элемент ИСКЛЮЧАЮЩЕЕ ИЛИ., а не ИСКЛЮЧАЮЩЕЕ ИЛИ с инверсией, как дано в пояснении). Триггер 2 служит для хранения текущего и вычисленного значений функции, Выход триггера 2 является выходом устройства °

Сигнал, снимаемый с этого выхода, есть вычисленное значение функции.

Установка триггера 2 в нулевое состосние определяет начало второго условного перехода. Триггер 3 служит для фиксации первого условного перехода, установка триггера 3 в нулевое состояние определяет начало первого условного перехода, Узел И счета служит для подсчета открывающих и закрывающих скобок уравнения в процессе условных переходов.

)la первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 через управляющий вход

7 .164 устройства подается сигнал "Значенйе аргумента, указанное в уравнении",.На второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ1 подается сигнал действительного значения аргумента. Выход элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ1 соединен с первым входом .элемента И5.Вход элемента И5 соедияен с выходом триггера 3, а вы" ход элемента И5 соединен .с входом (вход установки нуля) триггера 2. На 10 вход элемента Иб подается через управляющий вход устройства сигнал

"Дизъюнкция "+". Вход элемента И6 соединен с выходом узла 4 счета, а выход элемента Иб соединен с входом 15 (вход установки единицы) триггера

2. На вход элемента И7 через управляющий вход устройства подается сигнал "Закрывающая скобка ")", вход элемента И7 соединен с выходом узла .20

4 счета, а выход элемента И7 соединен с входом (вход установки единицы),триггера 3. На вход элемента

И8 через управляющий вход устройства подается сигнал "Дизъюнкция "+", вход25 элемента И8 соединен с выходом триггера 2, а выход элемента И8 соединен с входом (вход установки нуля ) триггера 3. На вход узла 4 счета через управляющий вход устройства подаются З0 сигналы "Открывающая скобка "(" и "Закрывающая скобка" )", вход узла 4 счета соединен с выходом триггера 3» а другой вход узла 4 счета соедйнен с выходом триггера 2. З5

Узел 4 счета может, например,состоять из двоичного реверсивного счетчика 11 и дешифратора 12.Пример выполнения узла счета дан на фиг.2.

Двоичный реверсивный счетчик 11 име- 40 ет вход "Сложение", вход "Вычитание" и вход установки нуля. Если выходы триггера через элемент И соединить с входом установки нуля счетчика, то перевод любого из двух 45 триггеров в нулевое состояние будет, являться сигналом для начала подсчета открывающих и закрывающих скобок. При этом, если на вход "Сложение" подавать сигнал "Открываю- 50 щая скобка "(", а на вход "Вычита" ние" подавать сигнал "Закрывающая скобка ")" и начинать подсчет закрывающих скобок, если счетчик не находится в нуле, т.е. когда была подсчи- 55 тана хотя бы одна открывающая скобка, то нулевое состояние счетчика всег-, да определяет, что по ходу вычисления есе открывающие скобки скомпенсированы закрывающими. При этом можно использовать дешифратор числа и =0. Единичный сигнал на выходе этого дешифратора и наличие по ходу вычисления закрывающей скобки определяют окончание первого условного перехода. В этом случае на обоих входах элемента И7 будут единичные сигналы, и триггер 3 переведется в единичное состояние. Единичный сигнал на выходе дешифратора и наличие по ходу вычисления знака "Дизъюнкция "+" определяют окончание второго условного перехода, при этом на обоих входах элемента Иб будут единичные сигналы, и триггер 2 переведется в единичное состояние.

Устройство работает следующим образом.

В начале вычисления триггеры 2::и

3 устанавливаются в единичное состояние. В процессе вычисления через управляющий вход устройства на вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 подается сигнал "Значение аргумента, указанное в уравнении", на входы элементов Иб. и И8,подается сигнал "Диэъюнкция "+", на вход элемента И7 подается сигнал

"Закрывающая скобка ")" и на вход узла 4 счета подаются сигналы "Открывающая,скобка "(" и "Закрывающая скобка ")". Эти сигналы подаются в том порядке, как они записаны в уравнении; При подаче на один вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ1 сигнала "Зна,чение аргумента, указанное в уравнении", на другой вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ1 подается действительное значение аргумента. Если эти значения совпадают, т.е. на обоих входах будут либо нули, либо единицы то на выходе элемента будет нуль, и триггер 2 останется е единичном состоянии. Если после этого аргумента нет знака диэъюнкции,то вводится следующий аргумент, т.е. вычисление аргументов продолжается.

Если же после этого аргумента есть знак дизъюнкции, то триггер 3 переведется в нулевое состояние, так как на обоих входах элемента, И8 будут вдиничные сигналы. При этом накладывается запрет на вычисление последующих аргументов, так как на входе элемента И5, соединенном с выходом триггера 3> будет нулевой сигнал.

Одновременйо узел 4 счета подготавли10498 вается к отсчету открывающих и закрывающих скобок. Если по ходу вычисления все открывающие скобки будут скомпенсированы закрывающими скобками и имеется лишняя закрывающая скобка (частный случай, когда между знаком дизьюнкции и закрывающей скобкой .нет ни одной открывающей скобки ), то на обоих входах элемента И7 будут единицы и триггер 3 через вход установки еди-10 ницы будет переведен в единичное состояние.

Если действительное значение аргумента и "Значение аргумента, указанное в уравнении" не совпадают,то 15 на выходе элемента ИСКЛ1ОЧАВЩЕЕ ИЛИ1, будет единица, и по входу установки нуля триггер 2 переведется в нулевое состояние. При этом узел 4 счета будет подготовлен к отсчету открывающих 20 и закрывающих скобок. Если по ходу вычисления все открывающие скобки. будут скомпенсированы закрывающими и имеется знак ндизъюнкция "+" (част98 10 ный случай, когда после вычисленного аргумента сразу же стоит знак дизъюнкции),то на обоих входах weментов Иб рудут единицы, и триггер 2 будет переведен в единичное состояние,,и вычисление продолжается.

После вычисления последнего аргумента уравнения значение функции (О

; или 1) снимается с выхода первого триггера 2, это значение является результатом. решения уравнения.

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

ФАР

ВНИИПИ Заказ 8427/46

Тираж 706 Подписное филиал ППП "Патент", r.Ужгород,ул.Проектная,4