Устройство для определения значений булевых функций
Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет вычисления булевых функций, задант 1х в , извольной скобочной форме. Устройство содерлсит три RS-триггера, три элемента СЛОЖЕНИЕ Ш МОДУЛЮ ДВА, два элемента И, мультиплексор, информационные входы которого являются информационными входами устройства, шину управления, выход устройства, t ил.
СОЮЗ СОВЕТСНИХ сОЦИАлистичесних
РЕСПУБЛИК (sg 4 G 06 F 7/00
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3825461/24-24 (22) 10.12.84 (46) 07.10.86. Бюл. У 37 (72) В.И. Вавилов, Е .С. Вальшоыок, В.Д. Митин и А.С. Сигалов (53) 681.3(088.8) (56) Авторское свидетельство СССР
Ф 610104, кл. G 06 F 7/00, 1975.
Авторское свидетельство СССР
У 1049898, кл. С 06 F 7/00, 1982.
Авторское свидетельство СССР
Ф 1037240, кл. С 06 F 7/00, 1982.
„„SU„„1262475 А 1 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЗНАЧЕНИЙ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возмохностей за счет вычисле.ния булевых функций, заданных в про--, извольной скобочной форме. Устройство содержит три RS-триггера, три элемента СЛОЖЕНИЕ ПО ИОДУЛ10 ДВА, два элемента И, мультиплексор, информационные входы которого являются информационными входами устройства, шину управления, выход устройства. 1 ил.
1.262475
Изобретение относится к автоматике и вычислительной технике и может быть использовано для вычисления булевых функций в системах контроля и управления техническими и технологическими средствами.
Целью изобретения является расширение функциональных возможностей устройства за счет вычисления булевых функций в произвольной скобочной форме.
На чертеже приведена схема устрой— ства для определения значений булевых функций.
Устройство для определения значений булевых функций содержит элемент 1 СЛОЖЕНИЕ ПО МОДУЛИ ДВА, элемент И 2, RS-триггер 3, мультиплексор 4, элемент 5 СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, RS-триггер б, элемент 7 СЛОЖЕНИЕ о
ПО МОДУЛИ ДВА, элемент И 8, RS-триггер 9, информационные входы 10, шину ll номера аргумента, шину 12 управления, выход 13.
Устройство работает следующим образом.
Перед вычислением булевой функции, представленной в любой форме в базисе И, ИЛИ, НЕ, устройство приводится в начальное (нулевое) состояние. Для этого на управляющие входы мультиплексора 4 подается код адреса шины
"Лог. 1", на вторые входы элементов И 2 и 8 по шине управления подается сигнал "Jlor. О, на нулевые вхо- 35 ды триггеров 3, 6 и 9 и на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА подается сигнал " Лог. 1". При этом происходит обнуление триггеров 3, б и 9 (считаем, что они ра- щ ботают в положительной логике).
Если булевая функция представлена в дизъюнктивной нормальной форме (ДНф), то ее вычисление производится в следующем порядке. 45
1. На вторые входы элементов И 28 и на нулевые входы триггеров 3, 6 и 9 подается сигнал "Лог. О", на управляющие входы мультиплексора 4 поочередно подаются коды номеров аргументов первой конъюнкции. При этом; если аргумент входит в конъюнкцию с lf отрицанием, то в момент выбора его на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛИ ДВА подается "Лог. 0", в противном случае — "Лог. 1". Если хотя бы один из сомножителей конъюнкции равен "0", триггер 6 переключается в состояние "Лог. 1", так как на его единичный вход поступает сигнал "Лог. 1", в противном случае триггер 6 остается в нулевом состоянии. Таким образом, после перебора всех аргументов конъюнкции состояние триггера 6 эквивалентно результату вычисления отрицания этой конъюнкции.
2. На управляющие входы мультиплексора 4 подается код адреса шины
"Лог. 1", на второй вход элементов 5 и 7 СЛОЖЕНИЕ ПО МОДУЛИ ДВА и элемента И 8 подается сигнал "Лог. 1", на нулевые входы триггеров 6 и 9 — сигнал "Лог. 0". При этом на единичный вход триггера 9 поступает сигнал, значение которсго равно инверсии состояния триггера б, т.е. равно значению вычисленной конъюнкции. Состояние триггера 9 становится эквивалентным значению конъюнкции.
3. На управляющие входы мультиплексора 4 подается код адреса шины
"Лог. 1", на второй вход элемента 5
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и нулевой вход триггера 6 подается сигнал "Лог. 1", на нулевой вход триггера 9 и второй вход элемента И 8 — сигнал "Лог. О".
При этом происходит обнуление триггера 6, состояние триггера 9 не меняется.
Происходит повторение действий по п. 1-3 столько раз, сколько в вычисляемой функции осталось невычисленных конъюнкций. В результате на триггере 9 в прямом виде формируется результат вычисления функции, представленной в ДНЮ.
5. На второй вход элемента И 8, на нулевой вход триггера 9 и на второй вход элемента 1 СЛОЖЕНИЕ ПО МОДУЛИ ДВА подается "Лог. 0". При этом(4 на выход устройства поступает результат вычисления булевой функции.
Вычисление -булевой функции в КНФ производится в следующем порядке.
1. На второй вход элемента И 8 и на нулевой вход триггера 6 подается сигнал "Лог. О", на управляющие вхо- ды мультиплексора 4 поочередно подаются коды номеров аргументов первой дизъюнкции. При этом, если аргумент входит в дизъюнкцию с отрицанием, то на второй вход элемента 5 СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА подается сигнал "Лог.l", в противном случае - "Лог. 0".
1262475
Если хотя бы одно из слагаемых дизъюнкции равно "Лог. 1", триггер 6 гереключается в состояние "Лог. 1".
Таким образом, после перебора всех слагаемых состояние триггера 6 экви- 5 валентно результату вычисления дизьюнк ции .
2. На управляющие входы мультиплексора 4 подается код адреса шины
"Лог. 1", на вторые входы элементов 5 и 7 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И 8 подается сигнал "Лог.1", на нулевые входы триггеров 6 и 9 подается сигнал "Лог. 0". При этом на единичный вход триггера 9 посту-. пает сигнал, значение которого равно инверсии состояния триггера 6, т.е. инверсии результата вычисления дизьюнкции. Состояние триггера 6 при этом не меняется, а .состояние триггера 9 становится эквивалентным инверсному значению дизъюнкции.
3. Производится обнуление триггера 6 по п. 3 вычисления функции в
ДНФ.
4. Производится повторение действий по r . 1-3 столько раз, сколько осталось невычисленных дизъюнкций.
В результате, если хотя бы одна из вычисленных дизъюнкций равна "Лог.0",30 триггер 9 переключается в состояние
"Лог. 1", в противном случае он останется в нулевом состоянии . Таким образом, его состояние эквивалентно инверсии результата вычисления функции.
5. На второй вход элемента 1 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнал
"Лог. 1", на нулевой вход триггера 9 и второй вход элемента И 8 — сигнал
"Лог. О . При этом на выход устройства в прямом виде поступает результат вычисления функции.
Вычисление булевой функции в произвольной скобочной форме показан на 45 примере . Пусть требуется вычислить функцию, представленную в виде
Y — Х ЧХ (Х чX)VX (ХЧХ).
1. Вычисление дизъюнкцйи (Х Ч Х ) на триггере 6. Для этого на второй gp вход элемента 5 GJIOEEHHE ПО МОДУЛЮ
ДВА, элемента И 2 и на нулевой вход триггера 6 подается лог. "0", на управляющие входы мультиплексора 4 поочередно нодаются коды номеров Х и у б
Х . Если хотя бы одно из слагаемых
Х нли Х равно Лог. 1 то триг гер 6 переключается в состояние ™Лог.
1", в противном случае он остается в нулевом состоянии, т.е. на нем сформируется результат вычисления дизьюнкции (Х Ч Х ) °
2. Вычисление конъюнкции Х (X v X ).
5 6
Для этого на второй вход элемента 7
СЛОЖЕНИЕ ПО МОДУЛ10 ДВА подается "Лог.
О", на второй вход элемента И 8 "Лог. 1". Таким образом, информация из триггера 6 переписывается в триггер 9. Далее обнуляем триггер 6 по п. 3 вычисления функции в ДНФ. Затем на управляющие входы мультиплексора 4 подается код номера Xg, на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И 8 подается
"Лс.г. 1", на второй вход элемента 7
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и на нулевые входы триггеров 6 и 9 — "Лог. О" .
При этом триггер 6 переключается в состояние, эквивалентное значению
Х5, а триггер 9 переключается в состояние Х v(X чХ ). После этого на б б вторые входы элемента И 2 и элемента 1 СЛОЖЕНИЯ ПО МОДУЛЮ ДВА подается "Лог. 1", т.е. в триггер 3 записывается результат вычисления
Х (Х v X,) = Х (X Х, ).
3. Йа нулевые входы триггеров 6 и 9 подается сигнал "Лог. 1", а на нулевой вход триггера 3 †. "Лог. О", на вторые входы элементов И 8 и 2 подается "Лог. О", а на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА—
"Лог. 1", на управляющие входы мультиплексора 4 подается код адреса шины "Лог. 1". Происходит обнуление триггеров 6 и 9 и сохранение информации в триггере 3.
4. Вычисление конъюнкции Х . (Х ЧХ )
3 .е производится как вычисление функции
Y = X (Х ЧХ ) (как видно, функция
7 представлена в КНФ). Результат вычисления в прямом виде подается на первый вход элемента И 2, на второй вход которого поступает сигнал
"Лог. 1", на нулевой вход триггера 3сигнал "Лог. 0". Таким образом, состояние триггера 3 эквивалентно результату вычисления выражения
0. Х 2(Х ЗЧ ХЯ ) Х$ (б 7) 5. Производится обнуление триггеров 6 и 9 по и. З,.после чего вычисляется функция Y Х„ Ч.Y как функция, представлеиная в ДНФ, Yz подается на вход устройства с выхода триггера 3 через мультиплексор 4.
1262475
Вычисление булевых функций, представленных в произвольной скобочной форме, позволяет во многих случаях ,сократить длительность вычисления.
Например, функцию вида
Y — Х Х vX Х vX Х v... VX Х v
9 представленную в ДНФ, значительно быстрее можно вычислить, представив в виде 10
Y — Х (ХчХ v... vX )VX Х.
Вторым преимуществом нычисленйя булевых функций в произвольной скобочной форме является возможность вычисления двух и более функций, ес- 15 ли они входят одна в другую как аргументы. Например, рассмотрим функции
Y = Х, Х,((Х,vX ) X vX );
Y — (Х vX) Х
Вычисляя фуйкцию Y в произволь- 20 ной скобочной форме, можно в виде промежуточного значения получить результат вычисления функции Y . Если
Y представить в ДНФ, то вычислить .
Y в процессе вычисления У не пред- 25 ставляется возможным.
Формула изобретения
Устройство для определения значе- 30 ний булевых функций, содержащее первый и второй КЯ-триггеры, первый и второй элементы И и первый элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем первый вход первого элемента СЛОЖЕНИЕ З5
ПО МОДУЛЮ ДВА соединен с шиной управления устройства, а выход соединен с первым входом первого элемента И, второй вход которого соединен с шиной управления устройства, выход вто-,10 рого элемента И соединен с единичным входом первого RS-триггера, нулевой вход которого соединен с шиной управления устройства, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей за счет вычисления булевых функций в произвольной скобочной форме, в него введены мультиплексор, третий КЯ-триггер, второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем выход первого RS-триггера соединен с вторым входом первого элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, выход первого элемента И соединен с единичным входом второго
RS-триггера, нулевой вход которого соединен с шиной управления устройства, а выход второго RS-триггера соединен с первым информационным вхо дом мультиплексора, второй информационный вход которого соединен с шиной логической единицы, остальные ин-, формационные входы мультиплексора являются информационными входами устройства, управляющий вход мультиплексора соединен с шиной, номера аргумента, а выход мультиплексора соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход ,которого .соединен с единичным входом третьего RS-триггера, выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом второго элемента И, вторые входы второго и.третьего элементов СЛОЖЕIIИЕ ПО МОДУЛЮ ДВА, второго элемента И и нулевой вход третьего RS-триггера
-соединены с шиной управления устройства, выход которого соединен с выходом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
12624?5
Составитель О. Березикова
Редактор Г. Волкова Техред Л.Сердюкова Корректор E. Cupoxuap
Заказ 5428/46 Тираж 671 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Иосква, Ж-Э5, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4