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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет вычисления булевых функций, задант 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