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

К9

О

и

сл

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

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

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

Устройство для определения значений булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И 2, RS-триггер 3, мультиплексор 4, элемент 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, RS-триггер 6, элемент 7 СЛОЖЕНИ ПО МОДУЛЮ ДВА, элемент И 8, RS-триггер 9, информационные входы 10, шину 11 номера аргумента, шину 12 управления, выход 13,

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

Перед вычислением булевой функции представленной в любой форме в базисе И, ИЛИ, НЕ, устройство приводится в начальное (нулевое) состояние. Для этого на управляющие входы мультиплекеодэа 4 подается код адреса шины Лог, I, на вторые входы элементов И 2 ц 8 по шине управления подается сигнал Лог, О, на нулевые входы триггеров 3, 6 и 9 и на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнгзл Лог, 1. При этом происходит обнуление триггеров 3, 6 и 9 (считаем, что они работают в положительной логике),

Если булеваяфункция представлена в дизъюнктивной нормальной форме (ДНФ), то ее вычисление производится в следующем порядке.

1, На вторые входы элементов И 28 и на нулевые входы триггеров 3, 6 и 9 подается сигнал Лог. О, на управляющие входы мультиплексора 4 поочередно подаются коды номеров аргументов первой конъюнкции. При этом если аргумент входит в конъюнкцию с отр1щанием, то в момент выбора его на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается Лог. О, в противном случае- Лог. 1. Если хотя бы один из сомножителей конъюнктриггер 6 переключации равен О,

ется в состояние Лог, 1, так как на его единичньм вход поступает сигнал Лог, 1, в противном случае триггер 6 остается в нулевом состоянии. Таким образом, после перебора всех аргументов конъюнкции состояние триггера 6 эквивалентно результату вычисления отрицания этой конъюнкции,

2,На управляющие входы мультиплексора 4 подается код адреса шины Лог, 1, на второй вход элементов 5 и 7 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И 8 подается сигнал Лог, 1, на нулевые входы триггеров 6 и 9 - сигнал Лог, О, При этом на единичньш вход триггера 9 поступает сигнал, значение которого равно инверсии состояния триггера 6, т,е, равно значению вычисленной конъюнкции. Состояние триггера 9 становится эквивалентным значению конъюнкции.

3.На управляющие входы мультиплексора 4 подается код адреса шины Лог, 1, на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и нулевой вхо триггера 6 подается сигнал Лог, 1, на нулевой вход триггера 9 и второй вход элемента И 8 - сигнал Лог. О. При этом происходит обнуление триггера 6, состояние триггера 9 не меняется.

Происходит повторение действий по п, 1-3 столько раз, сколько в вычисляемой функции осталось невьписленных конъюнкций, В результате на триггере 9 в прямом виде формируется резуль тат вычисления функции, представленной в ДНФ,

5. На второй вход элемента ИЗ, на нулевой вход триггера 9 и на второй вход элемента 1 СЛОЖЕНИЕ ПО МО:ДУЛЮ ДВА подается Лог, О. При этом на выход устройства поступает результат вычисления булевой функции.

Вычисление булевой функции в КНФ производится в следукяцем порядке.

i. -ч .

1. На второй вход элемента И 8 и

на нулевой вход триггера 6 подается сигнал Лог, О, на управляющие входы мультиплексора 4 поочередно подаются коды номеров аргументов первой дизъюнкции. При этом, если аргумент входит в дизъюнкцию с отрицанием, то на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнал Лог, в противном случае - Лог. О. Если хотя бы одно из слагаемых дизъюнкции равно Лог. 1, триггер переключается в состояние Лог. 1. Таким образом, после перебора всех слагаемых состояние триггера 6 экви валентно результату вычисления дизъ юнкции. 2.На управляющие входы мультиплексора 4 подается код адреса шины Лог. 1, на вторые входы элементов 5 и 7 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И 8 подается сигнал Лог.1 на нулевые входы триггеров 6 и 9 подается сигнал Лог. О. При этом на единичньй вход триггера 9 поступает сигнал, значение которого равн инверсии состояния триггера 6, т.е. инверсии результата вычисления дизъ юнкции. Состояние триггера 6 при этом не меняется, а состояние триггера 9 становится эквивалентным ;инверсному значению дизъюнкции. 3.Производится обнуление тригге ра 6 по п. 3 вычисления функций в ДНФ. 4.Производится повторение дейст вий по п. 1-3 столько раз, сколько осталось невычисленных дизъюнкций. В результате, если хотя бы одна из вычисленных дизъюнкций равна Лог.О триггер 9 переключается в состояние Лог. 1, в противном случае он ост нется в нулевом состоянии. Таким об разом, его состояние эквивалентно и версии результата вычисления функции. 5.На второй вход элемента 1 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнал Лог. 1, на нулевой вход триггера 9 и второй вход элемента И 8 - сигнал Лог.. О. При этом на выход устройства в прямом виде поступает результат вычисления функции. Вычисление булевой функции в произвольной скобочной форме показан на примере. Пусть требуется вычислить функцию, представленную в виде Y X,VX (XjV XJV X(). 1. Вычисление дизъюнкции ( X ) на триггере 6. Для этого на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемента И 2 и на нулевой вход триггера 6 подается лог. О, на управляющие входы мультиплексора 4 по очередно подаются коды номеров Х и Xj. Если хотя бы одно из слагаемых Xg или Xg равно Лог. Г, то триггер 6 переключается в состояние Лог в противном случае он остается в нулевом состоянии, т.е. на нем сформируется результат вычисления дизъюнкции (Х V Xj). 2. Вычисление конъюнкции X (XvX,). 56-8 Для этого на второй вход элемента / СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается Лог. О, на второй вход элемента И 8 . 1. Таким образом, информация из триггера 6 переписывается в триггер 9. Далее обнуляем триггер 6 по п. 3 вычисления функции в ДНФ. Затем на управляющие входы мультиплексора 4 подается код номера Xt, на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И В подается Льг. 1, на второй вход элемента 7 СЛОЖЕНР1Е ПО МОДУЛЮ ДВА и на нулевые входы триггеров 6 и 9 . О. При этом триггер 6 переключается в состояние, эквивалентное значению а триггер 9 переключается в состояние (XgVXg). После этого на вторые входы элемента И 2 и элемента 1 СЛОЖЕНИЯ ПО МОДУЛЮ ДВА подается Лог. 1, т.е. в триггер 3 записывается результат вычисления () Х (X,vx). 3.На нулевые входы триггеров 6 и 9 подается сигнал Лог. 1, а на нулевой вход триггера 3 - Лог. О, на вторые входы элементов И 8 и 2 подается Лог. О, а на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА . 1, на управляющие входы мультиплексора 4 подается код адреса шины Лог. 1. Происходит обнуление триггеров 6 и 9 и сохранение информации в триггере 3. 4.Вычисление конъюнкции X (XjVX ) производится как вычисление функции Y Х .( ) (как видно, функция YI представлена в КНФ), Результат вычисления в прямом виде подается на первый вход элемента И 2, на второй вход которого поступает сигнал Лог. J, на нулевой вход триггера 3сигнал Лог. О. Таким образом, состояние трнггера 3 эквивалентно результату вычисления выражения Xi(X3VX,)V Xg (,). 5. Производится обнуление триггеов 6 и 9 по п. 3,,после чего вычисяется функцня Y X V Y функия, представленная в ДНФ, Y/j, подаетя на вход устройства с выхода триггера 3 через мультиплексор 4. Вычисление булевых функций, пред ставленных в произвольной скобочной форме, позволяет во многих случаях сократить длительность вычисления. Например, функцию вида представленную в ДНФ, значительно быстрее можно вычислить, представив в виде Y 3 Х (. .. VX )Х Xg. Вторым преим ществом вычисления булевых функций в произвольной скобочной форме является возможность вычисления двух и более функций, ес ли они входят одна в другую как аргументы. Например, рассмотрим функц Y X, X(( ) X,.VX ); Y, (X,vX)-X, Вычисляя функцию Y в произвольной скобочной форме, можно в виде промежуточного значения получить ре зультат вычисления функции Y , Если Y представить в ДНФ, то вычислить Y Б процессе вычисления Y не пре ставляется возможным. Формула изобретени Устройство для определения значе ний булевых функций, содержащее пер вый и второй RS-триггеры, первый и второй элементы И и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем первый вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с шиной упра ления устройства, а выход соединен первым входом первого элемента И, второй вход которого соединен с шиной управления устройства, выход вт рого элемента И соединен с единичны 56 входом первого RS-триггера, нулевой вход которого соединен с шиной управления устройства, отличающееся .тем, что, с целью рас1Ш1рения функциональных возможностей за счет вычисления булевых функций в произвольной скобочной форме, в него введены мультиплексор, третий RS-трнггер, второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем выход первого RS-триггера соединен с вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого элемента И соединен с единичным входом второго RS-триггера, нулевой вход которого соединен с шиной управления устройства, а выход второго RS-триггера соединен с первым информационным входом мультиплексора, второй информационньш вход которого соединен с шиной логической единицы, остальные инт формационные входы мультиплексора являются информационными входами устройства, управляющий вход «1ультиплексора соединен с шиной .номера аргумента, а выход мультиплексора соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого .соединен с единичным входом третьего RS-триггера, выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом второго элемента И, вторые входы второго и третьего элементов-СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второго элемента И и нулевой вход третьего RS-триггера -соединены с шиной управления устройства, выход которого соединен с выходом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет вычисления булевых функций, задант 1х в , извольной скобочной форме. Устройство содерлсит три RS-триггера, три элемента СЛОЖЕНИЕ Ш МОДУЛЮ ДВА, два элемента И, мультиплексор, информационные входы которого являются информационными входами устройства, шину управления, выход устройства, t ил.