Устройство для вычисления булевых функций Советский патент 1983 года по МПК G06F7/00 

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

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

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

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

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

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

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

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

Устройство noзвoляet использовать

для вычисления булевых функций алгебраическихг.уравнений знак дизъюнкции +, открывающие и закрывающие скобки, что дает возможность реализовать скобочные формы булевых функций, пред ставленные в виде алгебраических урав нений. При этом отпадает необходимость в разработке принципиальных электрических схем за счет того, что программирование производится .непосредственно по уравнению, а не по электрической схеме. Максимально облег чается труд программиста, так как любое уравнение является и программой . его решения, поэтому для программир вания достаточно просто перепй сать это уравнение в память устрой ства без каких-либо преобразований. Кроме того, программирование по ура нению позволяет автоматизировать (ВВОД программы (например, вводить программу от вычислительной машины) Решить булевое уравнение - значи найти его значение на данном наборе аргументов. Для любого булевого ура нения вычисление ведут в порядке естественной записи аргументов,т.е. слева направо. Пример уравнения. X,-iX2+X34X4VU5 b() «И ло- Индексы при аргументах определяют порядок вычисления. В начале вычисления устанавливают значение функции равное 1. Решают уравнение, вычисляя по порядку аргументы, в следующем порядке.Обозначают единицей значение аргумента, указанное в уравнении, если -этот аргумент записан без знака инверсии (аргумеиты Х, Хд Х, Хз, Х-, Xg, Xg и X уравнении (1), и соответственно обоз начают нулем, если этот аргумент записан со знаком инверсии (аргументы Х2 и Xg в уравнении (1)). При таком обозначении совпадение действительного значения аргумента и значения аргумента, указанного в уравнении, означает, что аргумент истинен (т.е. его вычисленное значение равно единице), несовпадение этих значений означает, что аргумент ложен (т.е. его вычисленное значение равно нулю).Составляют таблицу по результатам этих рассуждений. Как видно из таблицы для вычисления аргумента можно использовать элемент проверки на четность (ИСКЛЮЧАЮЩЕЕ ИЛИ с инверсией).Если на входы элемента подавать сигналы действительного значения аргумента и значения, указанного в уравнении, то на выходе получают вычисленное значение аргумента. В процессе вычисления уравнения существует два условных перехода: когда вычисленный аргумент истинен и после него стоит знак дизъюнкции когда вычисленный аргумент ложен и после него нет знака дизъюнкции (т.е. стоит знак конъюнкции). В примере (уравнение (1)) знак дизъюнкции стоит после аргументов Х2, Xg Xg, Xf и Xrt. В первом случае процедура условного перехода такова: функции присваивается значение 1, накладывается запрет на вычисление остальных слагаемых дизъюнкций до отыскания последнего аргумента, входящего в данную дизъюнкцию, после чего вычисление продолжается. Очевидно, что если уравнение заканчивается последним членом этой дизъюнкции, то результатом решения этого уравнения будет единица. Во втором случае функции присваива- . ется значение О, накладывается запрет на вычисление остальных сомножителей данной конъюнкции до отыскания последнего аргумента,обнаруживается дизъюнктивный член к той части функции,в которую входит только что вычисленная конъюнкция, функции присваивается значение 1 и вычисление продолжается. Очевидно, что если уравнение заканчивается последним членом данной конъюнкции,то результатом решения этого уравнения будет 0. Эти правила вытекают из предложений булевой алгебры: если в дизъюнкции хотя бы один из слагаемых равен единице. То вся дизъюнкция равна единице; если в конъюнкции хотя бы один из сомножителей равен нулю, то вся конъюнкция обращается в нуль. Уславливают правило для отыскания последнего аргумента дизъюнкций при первом условном переходе. Для этого рассматривают дизъюнкцию X.+X-+X,-f...+ X, Y(2) Если эта дизъюнкция входит в состав более сложного аргумента, то она должна быть заключена в скобки |X,4Xj4X,4,...4XnVX,,,-V (3) . ()-Хп + 2,(/) . где и Xqij- любые сколь-угодно сложные агрументы. Из уравнений (3) и С) видно, что окончание дизъюнкции определяется на личием закрывающей скобки. Однако любой член дизъюнкций может быть сло ным аргументам, в свою очередь содер жащим скобки. Например, п 5(Я«+ + 113), тогда уравнение (З) примет ви V l + )-V,-,n) (5) , При этом по ходу вычисления, если |цапример, Х( V, имеется закрывающая скобка после аргумента Л з торая не характеризует окончание данной дизъюнкции. Такие скобки, при надлежащие сложным аргументам,характеризуются тем, что каждой закрывающей скобке соответствует открывающая скобка и лишь последняя закрывающая скобка,указывающая на конец дизъюнкции, оказывается иескомпенсирован ной открывающей скобкой. Поэтому правило для отыскания последнего члена дизъюнкции можно трактовать так: по ходу вычисления подсчитывает ся количество открывающих и закрывающих скобок и тот наиболее близкий шаг вычислений, в котором число закрывающих скобок хотя бы на одну боль ше числа открывающих скобок, указывает на конец дизъюнкции. Устанавливают правило для отыскания последнего аргумента конъюнкции при BtopoM условном переходе. Для этого рассматривают конъюнкцию Х,... (6) Если эта конъюнкция входит в состав более сложного аргумента, то после нее должен стоять знак дизъюнкции, с помощью которого к ней присоединяется в общем случае любой, сколь-уго но сложный аргумент. .Хз... X,,, Y Из уравнения (7) видно, что оконч ние конъюнкции определяется наличием знака дизъюнкции +. Однако каждый из аргументов Х4,...Хп может быть сколь-угодно сложным, содержащим в свою очередь знаки дизъюнкции.Например, Xj Я,+. ;. Такие аргументы заключаются в скобки (,).К5,...х„4Хп,у. (8); Тогда перед каждым анаком дизъюнкции , входящим в сомножитель вычисляемой конъюнкции, должна быть открывающая скобка и лишь в том случае, когда все открывающие скобки скомпенсированы закрывающими скобками, знак дизъюнкции + является указанием на окончание конъюнкции. Тогда правило для отыскания последнего члена конъюнкции можно трактовать так; по ходу вычисления подсчитывается количество открывающих и закрывающих скобок , причем закрывающие скобки считаются лишь тогда, если имеется хотя бы одна открывающая скобка. Если разность между числом открывающих и закрывающих скобок равна нулю, то наиболее близкий по ходу вычисления знак дизъюнкции + указывает на оконча,ние конъюнкции. На фиг. 1 представлена схема устройства; на фиг. 2 - схема узла счета. Устройство содержит элемент ИСКЛЮМДЮЩЕЕ ИЛИ 1 (схема проверки на нечетность), триггер 2. триггер 3 узел счета, элементы И5-6. Узбл k счета содержит элементы И 9 и 10, реверсивный счетчик 11 и дешифратор 12. Элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 1 служит для вычисления аргумента (в данном случае для удобства построения схемы взят элемент ИСКЛЮЧАЮЩЕЕ ИЛИ , а не ИСКШЧАЮЩЕЕ ИЛИ с инверсией, как дано в пояснении). Триггер 2 служит для хранения те кущего и вычисленного значений функции. Выход триггера 2 является выходом устройства. Сигнал, снимаемый с этого вь)хода, есть вычисленное значение функции. Установка триггера 2 в нулевое срстосние определяет начало второго условного перехода. Триггер 3 служит для фиксации первого условного перехода, установка триггера 3 в нулевое состояние определяет начало первого условного перехода. Узел k счета служит для подсчета открывающих и закрывающих скобок уравнения в процессе условных переходов. }4а первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 через управляющий вход устройства пбдается сигнал Значение аргумента, указанное в уравнений. второйвход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подается сигнал действительного зна чения аргумента. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ1 соединен с первым входом элемента ИЗ.Вход элемента И5 соединен с выходом триггера 3, а вы ход элемента И5 соединен с входом (вход установки нуля) триггера 2. Н вход элемента Иб подается через управляющий вход устройства сигнал Дизъюнкция +. Вход элемента Иб соединен с выходом счета, а выход -элемента Иб соединен с входом (вход установки единицы) триггера 2. На вход элемента И7 через управляющий вход.устройства подается сиг нал Закрывающап скобка )Ч вход эл мента Иу соединен с выходом узла счета, а выход элемента И7 соединен с входом (вход установки единицы),триггера 3. На вход элемента И8 через управляющий вход устройств подается сигнал Дизъюнкция +, вх элемента И8 соединен с выходом триг гера 2, а выход элемента И8 соедине с входом (вход установки нуля ) три гера 3. На вход узла А счета через у равлякзщий вход устройства подаются сигналы Открывающая скобка ( . и Закрываю1цая скобка ) , вход узла счета соединен с выходом триггера 3i а другой вход узла h счета соединен с выходом триггера 2 Узел Ц счета может,например,состоять из двоичного реверсивного счетчика 11 и дешифратора 12.Пример выполнения узла счетадан на фиг.2. Двоичный реверсивный счетчик 11 имеет вход Сложение, вход Вычитание и вход установки нуля. Если выходы триггера через элемент И соединить с входом установки нуля учетчика, то перевод любого из двух триггеров в нулевое состояние будет, являться сигналом для начала подсчета открывающих и закрывающих скобок. При этом, если на вход Сложение подавать сигнал Открывающая скобка (, а на вход Вычитание подавать сигнал Закрывающая скобка ) и начинать подсчет закрывающих скобок, если счетчик не нах дится в нуле, т.е. когда была подсчи тана хотя бы одна открываю1цая скобка то нулевое состояние счетчике всегда определяет, что по ходу вычисления все открывающие скобки скомпенсированы закрывающими. При этом можно использовать дешифратор числа N 0. Единичный сигнал на выходе этого дешифратора и наличие по ходу вычисления закрывающей скобки определяют окончание первого условного перехода. В этом случае на обоих входах элемента И7 будут единичные сигналы, и триггер 3 переведется в единичное состояние. Единичный сигнал на вы-ходе дешифратора и наличие по ходу вычисления знака Дизъюнкция определяют окончание второго условного перехода, при этом на обоих входах элемента Иб будут единичные сигналы, и триггер 2 переведется в единичное состояние. Устройство работает следующим образом. . . В начале вычисления триггеры 2;;и 3 устанавливаются в единичное состояние. В процессе вычисления через управляющий вход устройства на вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ1 подается сигнал Значение аргумента, указанное в уравнении, на входы элементов Иб и И8 .подается сигнал Дизъюнкция +, на вход элемента И7 подается сигнал Закрывающая скобка ) и на вход узла k счета подаются сигналы Открывающая . скобка ( и Закрывающая скобка ). Эди сигналы подаются в том порядке, как они записаны в уравнении; При подаче на один вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ сигнала Зна(Чение аргумента, указанное в уравнении, на другой вход элемента ИСКШЧАЮЩЕЕ ИЛИ1 подается действительное значение аргумента. Если эти значения совпадают, т.е. на обоих входах будут либо нули, либо единицы у то на выходе элемента будет нуль, и триггер 2 останется в единичном состоянии. Если после этого аргумента нет знака дизъюнкции,то вводится следующий аргумент, т.е. вычисление аргументов продолжается. Если, же после э.того аргумента есть знак дизъюнкции, то триггер 3 переведется в нулевое состояние, так как на обоих входах элемента. И8 будут единичные сигналы. При этом накладывается запрет на вычисление последующих аргументов, так как на входе элемента И5, соединенном с выходом триггера 3i будет нулевой сигнал. Одновременно узел k счета подготавливается к отсчету открывающих и закрывающих скобок. Если по ходу вычисления все открывающие будут скомпенсированы закрывающими скобками и имеется лишняя закрывающая скобка s ( частный случай, когда между знаком дизъюнкции и закрывающей скобкой нет ни одной открывающей скобки ), то на обоих входах элемента И7 удут единицы и триггер 3 через вход установки еди-Ю ницы будет переведен в единичное состояние.

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

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

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

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