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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в программируемых системах управления технологическими объектами, алгоритм управления которых описывается с помощью булевых функций, в частности в программируемых контроллерах и управляющих вычислительных машинах. Цель изобретения - расширение об-, ласти применения устройства за счет реализации любых скобочных форм булевьпс функций, представленных в виде алгебраических уравнений. Устройство содержит элементы И, элемент ИСКЛЮЧАВДЕЕ ИЛИ, первый и второй триггеры, узел счета скобок. В процессе вычисления на информационный вход подаются действительные значения аргументов, на управляющие входы - сигналы Значение аргумента , указанное в уравнении, Дизъюнкция, Закрывающая скобка, Открывающая скобка. Эти сигналы подаются в том порядке, в котором соответствующие им символы записаны в уравнении. После вычисления последнего аргумента уравнения значение функции снимается с выхода первого триггера. Изобретение дополнительное к авт.св. № 1049898. 3 ил, 2 табл. (Л с § 1C СХ) со а

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

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

РЕСПУБЛИН

09) (11).

I дую G 06 F 7/00

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

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

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

Н ABTOPCHQMY СВИДЕТЕЛЬСТВУ (61) 1049898 (21) 3786899/24-24 (22) 04.09.84 (46) 15.03.86. Бюл. У 10 (71) Московский автомобильный завод им. И.А. Лихачева (72) О.В. Катков, А.И. Андерсон и В.И. Хохлов (53) 681.3(088.8) (56) Авторское свидетельство СССР .Ф 1049898, кл. G 06 Г 7/00, 1982. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в программируемых системах управления технологическими объектами алгоритм управления которых описывается с помощью булевых функций, в частности в программируемых контроллерах и управляющих вычислительных машинах.

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

Устройство содержит элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй триггеры, узел счета скобок. В процессе вычисления на информационный вход подаются действительные значения аргументов, на управляющие входы — сигналы "Значение аргумента, указанное в уравнении", "Дизъюнкция", "Закрывающая скобка", "Открывающая скобка". Эти сигналы подаются в том порядке, в котором соответствующие им символы записаны в уравнении. После вычисления последнего аргумента уравнения значение функции снимается с выхода первого триггера. Изобретение дополни" тельное к авт.св. 9 1049898.

3 ил, 2 табл. проверить состояние счетчика 11 на равенство нулю; блок 12 — инкрементировать содержимое счетчика 11; блок

13 — декрементировать содержимое счетчика 11 блок 14 — установить триггер 3 в единичное состояние, блок 15 — проверить состояние тригГера 2 на равенство нулю, блок 16— проверить состояние счетчика 11 на

10 равенство нулю, блок 17 — проверить наличие знака дизъюнкции "+"," блок

18 — установить триггер 2 в единичное состояние.

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

35 (например вводить программу от вычислительной машины).

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

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

45 Х1 » (Х2 + ХЗ + Х4) » (Х5 + Х6«

«(Х7 + Х8)) Х9 + Х10 = Y (1)

Индексы при аргументах определяют порядок вычисления.

В начале вычисления устанавливают значение функции, равное 1. Решают уравнение, вычисляя последовательно аргументы в следующем порядке. Обозначают единицей значение аргумента, указанное в уравнении, если этот аргумент записан для знака инверсии (аргументы Х1, Х 3, Х4, Х5, Х7, Х8, Х9, Х10 в уравнении (1), и соответственно обозначают нулем, 4 1218376 2

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

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

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

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

IIa фиг. 1 представлена схема устройства; на фиг. 2 — схегга узла счета . на фиг. 3 — блок-схема алгоритма работы устройства.

Устройство содержит элемент

11СКЛ10ЧЛОЩЕЕ ИЛИ 1, триггеры 2 и 3, узел 4 счета, элементы И 5-8.

Узел счета содержит элементы

И 9-10, реверсивный счетчик 11 и дешифратор 12.

Нлоки блок-схемы алгоритма работы устройства выполняют следующие дейстгил: блок 1 — установить состояние триггеров 2 и 3 равное единице, блок ? — проверить состояние триггера 2 на равенство едшшце, блок 3 проверить состояние триггера 3 »а равенство единице; блок 4 — проверить совпадает ли действительное значение аргумента со значением аргумента, указанным в управлении; блоки 5 и 6проверить наличие знака дизъгонкции

"+"; блок 7 — установить состояние трш гера 3 равное нулю, блок 8— установить состояние триггера 2 равное ну«но; блок 9 — проверить наличие знака "Закрьвагощая скобка" ")"; блок 10 — проверить наличие знака

"Открывающая скобка" "("; блок 11

1218376

1О

15 конъюнкция, функции присваивается

Действительное значеЗначение

Вычисленное значеаргумента, указанное ние аргумента ние аргумента в уравнении

0

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

Составляют табл. 1 по результатам этих вычислений

Таблица 1

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

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

В процессе вычисления уравнения существует два условных перехода: когда вычисленный аргумент истинен и после него стоит знак дизъюнкции

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

В примере — уравнение (1) знак дизъюнкции стоит после аргументов Х2, XÇ, Х5, Х7, Х9.

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

50 данную дизъюнкцию, после чего вычисление продолжается.

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

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

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

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

Для этого рассматривают дизъюнкцию

Х1+Х2+ХЗ... +Хп = Y (2).

Если эта дизъюнкция входит в состав более сложного аргумента, то она должна быть заключена в скобки /Х1+Х2+ХЗ+... +Хп/ а Xn+1=Y (3) или Хп+1 /Х1+Х2+ХЗ+... +Xn/* Xn+2=Y (4) где Хп+1 и Хп+2 — любые, сколь угодР но сложные аргументы.

Иэ уравнении (3) и (4) видно, что окончание дизъюнкции определяется наличием закрывающей скобки.

Однако любой член дизъюнкции может быть сложным аргументом, в свою очередь содержащим скобки..Например, Х2 = Л /A, + Л /, тогда уравнение (3) примет вид /Х1+ Л/Л +Л„ /+ХЗ+...+

+Хп/Хп+1 = Y (5) .

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

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

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

Х1 Х2 ХЗ ...Xn = Y (6).

1О!

45

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

Х1» Х2» X3 ...Хп+Хп+1 X=Y (7)

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

Такие аргументы заключаются в скобки

Х1 "/Л, + Л, / ХЗ...Xn + Xn+1=Y (8)

Тогда перед каждым знаком дизъюнкции, входящим в сомножитель

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

55 окончание конъюнкции.

Элемент HCIUIIO×ÀIOÙEÊ ИЛИ 1 (фиг. 1) устройства служит для вычисления аргумента. Триггер 2 служит для хранения текущего и вычисленного значения функции. Выход триггера 2 является выходом устрой ства. Сигнал, снимаемый с этого вы хода, есть вычисленное значение функции. Установка триггера 2 в нулевое состояние определяет начало второго условного перехода.

Триггер 3 служит для фиксации первого условного перехода, установка триггера 3 в нулевое состояние определяет начало первого условного перехода.

Узел 4 счета служит для подсчета открывающих и закрывающих скобок уравнения в процессе условных переходов. Узел 4 счета (фиг. 2) может, например, состоять из двоичного реверсивного счетчика 11 и дешифратора 12. Двоичный реверсивный счетчик имеет входы "Сложение" и "Вычитание", а также входы установки нуля и синхронизации. Если выходы триггеров 2 и 3 через элемент И 10 соединить с входом установки нуля счетчика, то перевод любого из триггеров в нулевое состояние будет сигналом для начала подсчета открывающих и закрывающих скобок. При этом, если на вход "Сложение" подавать сигналы "Открывающая скобка"

")", а на вход "Вычитание" подавать сигналы "Закрывающая скобка" "1" и начинать подсчет закрывающих скобок, если счетчик не находится в нуле, т.е. когда была подсчитана хотя бы одна открывающая скобка, то нулевое состояние счетчика всегда определяет, что по ходу вычисления, все открывающие скобки скомпенсированы закрывающими. При этом можно использовать дешифратор числа = О.

Единичный сигнал на выходе этого дешифратора и наличие по ходу вычисления закрывающей скобки определяют окончание первого условного перехода. В этом случае на обоих входах элемента И 8 будут единичные сигналы и триггер 3 переведется в единичное состояние. Единичный сигнал на выходе дешифратора и наличие по ходу вычисления знака и и

Дизъюнкция определяют окончание второго условного перехода, при этом на обоих входах элемента И 7 будут единичные сигналы и триггер 2 переведется в единичное состояние.

1218376

Входы установки единицы триггеров

- 2 и 3 имеют приоритет над входами установки нуля.

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

Перед каждым циклом вычисления подается сигнал "Установка устройства в исходное состояние". Триггеры 2 и 3 устанавливаются в единичное состояние. В процессе вычисления через управляющий вход устройства на вход элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ 1 подается сигнал "Значение аргумента, указанное в уравнении", на входы элементов И 6, 7 подается сигнал "Дизъюнкция", на вход элемента И 8 подается сигнал "Закрывающая скобка" ") " и на вход узла 4 счета подаются сигналы Открывающая скобка" "(" и "Закрывающая скобка"

")". Эти сигналы подаются в том .порядке, как они записаны в уравне:нии.

Когда zza всех входах устройства установятся сигналы, подается сигнал синхронизации, по переднему фронту которого переключаются триггеры 2 и 3 и узел 4 счета. При подаче на один вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 сигнала "Значение аргумента, указанное в уравнении", на другой вход элемента ИСКЛЮЧА10ЩЕЕ ИЛИ 1 подается действительное значение аргумента.

Если эти значения совпадают, т..е.

1Е tl на обоих входах будет либо нуль либо "единица", то на выходе элемента будет "нуль", и если есть знак "Дизъюнкция", то триггер 3 переводится в нулевое состояние, так как на входах элемента И 6 будут единичные сигналы. При этом накладывается запрет на вычисление последующих аргументов, так как на входе элемента И 5, соединенном с выходом триггера 3, будет нулевой сигнал. Одновременно узел 4 счета подготавливается к отсчету открывающих и закрывающих скобок. Если по ходу вычисления все открывающие г скобки будут скомпенсированы закрывающими скобками и имеется лишняя закрывающая скобка (частный случай, когда между знаком дизъюнкции и закрывающей скобкбй нет ни одной открывающей скобки), то на обоих входах элемента И 8 будут единицы и триггер 3 через вход установки

10 единицы будет переведен в единичноег состояние.

Если действительное значение аргумента и значение аргумента, указанное в уравнении, не совпадают, то

15 на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 будет единица, и если нет знака

"Дизъюнкция", то по входу установки нуля триггер 2 переведется в нулевое состояние. При этом узел 4 сче2О та будет подготовлен к отсчету открывающих z» закрывающих скобок. Если по ходу вычисления все открывающие скобки будут сколгпенсированы закрыII 11 вающими и имеется знак Дизъюнкция

25 (частный случай, когда после вычисленного аргумента сразу же стоит знак дизъюнкции), то на обоих входах элемента И 7 будут- единицы, триггер 2 будет переведен в единичное состояние, и вычисление продолжается.

После вычисления последнего аргумента уравнения значение функции (О или l) снимается с выхода триг35 гера 2. Это значение является результатом решения уравнения. .Рассмотрим пример вычисления конкретной булевой функции, записанной в виде алгебраического уравнения

4р Х1+Х2/ХЗ /Х4+Х5/+Х6 i Х7/+Х8/Х9+

+Х10/Х11+Х12/Х13+Х14/+Х15 = Y.

Предположим, действительное зна- е чение аргументов ХЗ, Х7, Х8, Х9, Х13 совпадает со значением аргу45 ментов, записанным в уравнении, а действительное значение остальных . аргументов — не совпадает.

Результаты решения уравнения сведем в табл. 2.

1218376

1О

Таблица

Выход элемент

ИСКЛЮЧАЮЩЕЕ

ИЛИ

СостояСостояние счетчика -.

Состояние

НалиСостояние

Наличие

НалиШаг вычисления (проверяемый аргумент) ние на выходе узла

4 счета чие чие триггера 3 тригге" ра 2 закрывающей скобки знака откры"дизъюн вающей кции "+ скобки

Нет 1

Нет 0

Нет 0

Нет 0

Есть 0

Нет 0

Есть 1

Нет 1

Нет

Есть

Х1

ЕЕет

Нет

Х2

Есть

ХЗ

Есть ХХ

Х4

Нет

Х. Х5

Нет

Хб

Есть

Е!ет

Х7

Нет

0.0

Нет

Х8

Нет 1

Есть

Есть

Х9

Нет 1

Нет

Х10

Есть Нет 1

Х11

Нет Нет 1

Есть Нет 1

Х12

Х

Х13

Есть 1

Нет

Х14

Есть 1

Нет

Х15

Знак Х обозначает безразличное состояние.

Результатом решения уравнения является значение функции Y = снимаемое с выхода триггера 2 после

50 вычисления последнего аргумента уравнения.

Формула изобретения

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

1218376

1218376

ВНИИПИ, Заказ 1132/56 Тираж 673 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4