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

ЛИСТИЧЕСНИХ 475 594 С 06 Р 7/ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАН ОБРЕТЕН И 4 НАБюл. У 3 ов, Е .С. Вальшоыок,С. Сигалов8)свидетельство СССР.06 Р 7/00, 1975.идетельство СССРС 06 Р 7/00, 1982.идетельство СС 06 Г 7/00,ССР1982,ВТОРСНОМУ СВИДЕТ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ 3ЧЕНИЙ БУЛЕВЫХ ФУНКЦИЙ(57) Изобретение относится к автоматике и вычислительной технике. Цельизобретения - расширение функциональных возмозностей за счет вычисле.ния булевых функций, заданных в про,извольной скобочной форме. Устройство содержит три ВВ-триггера, три элемента СЛОЖЕНИЕ ПО МОДУЛ 0 ДВА, дваэлемента И, мультиплексор, информационные входы которого являются информационными входами устройства, шинууправления, выход устройства. 1 ил.Изобретение относится к автоматике и вычислительной технике и можетбыть использовано для вычисления булевых функций в системах контроля иуправления техническими и технологическими средствами.Целью изобретения является расширение функциональных возможностейустройства за счет вычисления булевыхфункций в произвольной скобочной форме.На чертеже приведена схема устройства для определения значений булевыхфункций.Устройство для определения значений булевых функций содержит элементСЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И 2, КЯ-триггер 3, мультиплексор 4, элемент 5 СЛОЖЕНИЕ ПО МОДУЛЮДВА, КБ-триггер б, элемент 7 СЛОЖЕНИЕ 0ПО МОДУЛЮ ДВА, элемент И 8, КБ-триггер 9, информационные входы 10, шину 1 номера аргумента, шину 12 управления, выход 13.Устройство работает следующим образом.Перед вычислением булевой функции,представленной в любой форме в базисе И, ИЛИ, НЕ, устройство приводитсяв начальное (нулевое) состояние. Дляэтого на управляющие входы мультиплексора 4 подается код адреса шины"Лог, 1", на вторые входы элементов И 2 и 8 по шине управления подается сигнал Лог. О, на нулевые входы триггеров 3, 6 и 9 и на второйвход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнал "Лог. 1". Приэтом происходит обнуление триггеров 3, б и 9 (считаем, что они ра Оботают в положительной логике).Если булевая функция представлена в дизъюнктивной нормальной форме(ДНб), то ее вычисление производитсяв следующем порядке. 451. На вторые входы элементов И 28и на нулевые входы триггеров 3,6 и 9 подается сигнал "Лог, О", науправляющие входы мультиплексора 4поочередно подаются коды номеров аргументов первой конъюнкции. При этом; если аргумент входит в конъюнкцию с отрицанием, то в момент выбора его на второй вход элемента 5 СЛОЖЕНИЕПО МОДУЛИ ДВА подается "Лог. О", в противном случае - "Лог. ". Если хотя бы один из сомножителей конъюнкции равен "О", триггер 6 переключается в состояние "Лог, 1", так какна его единичный вход поступает сигнал "Лог. 1", в противном случаетриггер 6 остается в нулевом состоянии. Таким образом, после переборавсех аргументов конъюнкции состояниетриггера 6 эквивалентно результатувычисления отрицания этой конъюнкции,2. На управляющие входы мультиплексора 4 подается код адреса шины"Лог. 1", на второй вход элементов 5и 7 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И 8 подается сигнал "Лог. 1", нанулевые входы триггеров 6 и 9 - сигнал "Лог. О", При этом на единичныйвход триггера 9 поступает сигнал,значение которсго равно инверсии состояния триггера б, т,е, равно значению вычисленной конъюнкции. Состояние триггера 9 становится эквивалентным значению конъюнкции.3. На управляющие входы мультиплексора 4 подается код адреса шины"Лог. 1", на второй вход элемента 5СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и нулевой входтриггера 6 подается сигнал "Лог. 1",на нулевой вход триггера 9 и второйвход элемента И 8 - сигнал "Лог. О".При этом происходит обнуление триггера 6, состояние триггера 9 не меняется,Происходит повторение действий поп. 1-3 столько раз, сколько в вычисляемой функции осталось невычисленных конъюнкций. В результате на триггере 9 в прямом виде формируется результат вычисления функции, представленной в ДНО,5. На второй вход элемента И 8,на нулевой вход триггера 9 и на второй вход элемента 1 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается "Лог. О". При этойна выход устройства поступает результат вычисления булевой функции.Вычисление булевой функции в КНФпроизводится в следующем порядке. 1, На второй вход элемента И 8 и на нулевой вход триггера 6 подается сигнал "Лог, О", на управляющие вхо- ды мультиплексора 4 поочередно подаются коды номеров аргументов первой дизъюнкции. При этом, если аргумент входит в дизъюнкцию с отрицанием, то на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнал "Лог.1", в противном случае - "Лог. О".1262475 Если хотя бы одно из слагаемыхдизъюнкции равно "Лог. 1", триггер 6гереключается в состояние "Лог. 1".Таким образом, после перебора всехслагаемых состояние триггера 6 эквивалентно результату вычисления дизьюнкции.2. На управляющие входы мультиплексора 4 подается код адреса шины"Лог, 1", на вторые входы элементов 5 и 7 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА иэлемента И 8 подается сигнал "Лог.1",на нулевые входы триггеров 6 и 9подается сигнал "Лог. О". При этомна единичный вход триггера 9 поступает сигнал, значение которого равноинверсии состояния триггера 6, т.е.инверсии результата вычисления дизьюнкции. Состояние триггера 6 приэтом не меняется, а состояние триггера 9 становится эквивалентным инверсному значению дизъюнкции.3. Производится обнуление триггера 6 по п. 3 вычисления функции вДНФ.254. Производится повторение действий по и. 1-3 столько раз, сколькоосталось невычисленных дизъюнкций.В результате, если хотя бы одна извычисленных дизъюнкций равна "Лог.О",30триггер 9 переключается в состояние"Лог, 1", в противном случае он останется в нулевом состоянии . Таким образом, его состояние эквивалентно инверсии результата вычисления функ 5. На второй вход элемента 1 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА подается сигнал"Лог. 1", на нулевой вход триггера 9и второй вход элемента И 8 - сигнал 40"Лог, О. При этом на выход устройства в прямом виде поступает результат вычисления функции,Вычисление булевой функции в произвольной скобочной форме показан на 45примере . Пусть требуется вычислитьфункцию, представленную в видеХ ЧХ (Х ЧХ)ЧХ (ХЧХ),1. Вычисление дизъюнкцйи (Х Ч Х )на триггере 6. Для этого на второй 50вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮДВА, элемента И 2 и на нулевой входтриггера 6 подается лог. "О", на управляющие входы мультиплексора 4 поочередно подаются коды номеров Х и 55бХ . Если хотя бы одно из слагаемыхХ нли Х равно Лог. 1 , то триггер 6 переключается в состояние "Лог,41", в противном случае он остается в нулевом состоянии, т.е. на нем сформируется результат вычисления дизьюнкции (Х Ч Х ).2, Вычисление конъюнкции Х (Х Ч Х ).5 6 Для этого на второй вход элемента 7 СЛОЖЕНИЕ ПО МОДУЛ 10 ДВА подается "Лог, О", на второй вход элемента И 8 - "Лог. 1". Таким образом, информация из триггера 6 переписывается в триггер 9. Далее обнуляем триггер 6 по п. 3 вычисления функции в ДНФ, Затем на управляющие входы мультиплексора 4 подается код номера Х, на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемента И 8 подается "Лс,г. 1", на второй вход элемента 7 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и на нулевые входы триггеров 6 и 9 в "Лог. О".При этом триггер 6 переключается в состояние, эквивалентное значению Хб, а триггер 9 переключается в состояние Х ч(Х чХ ). После этого наб бвторые входы элемента И 2 и элемента 1 СЛОЖЕНИЯ ПО МОДУЛЮ ДВА подается "Лог. 1", т,е. в триггер 3 записывается результат вычисления Х Ч(Х чХ ) Х (Х чХ).3. Йа нулевые входы триггеров 6 и 9 подается сигнал "Лог. 1", а на нулевой вход триггера 3 в . "Лог. О", на вторые входы элементов И 8 и 2 подается "Лог. О", а на второй вход элемента 5 СЛОЖЕНИЕ ПО МОДУЛЮ ДВА - "Лог. 1", на управляющие входы мультиплексора 4 подается код адреса шины "Лог. 1", Происходит обнуление триггеров 6 и 9 и сохранение информации в триггере 3.4. Вычисление конъюнкции Х (Х ЧХ )3 производится как вычисление функции У = Х (Х ЧХ ) (как видно, функция У представлена в КНФ). Результат вычисления в прямом виде подается на первый вход элемента И 2, на второй вход которого поступает сигнал "Лог. 1", на нулевой вход триггера 3- сигнал "Лог, О". Таким образом, состояние триггера 3 эквивалентно ре" зультату вычисления выраженияУ,- Х,(Х,ЧХ ) Х (Я. ЛГ). 5, Производится обнуление тригге- ров 6 и 9 по и. З,.после чего вычисляется функция Т " ХЧ.Ч, как функция, представлеиная в ДНФ, У подается на вход устройства с выхода триггера 3 через мультиплексор 4.1262475 Вычисление булевых функций, представленных в произвольной скобочной форме, позволяет во многих случаях ,сократить длительность вычисления. Например, функцию вида- Х Х чХ Х чХ Х ччХ Х ч9представленную в ДНФ, значительно быстрее можно вычислить, представив в виде 1 ОУ - Х (ХчХ ч чХ )чХ Х.Вторым преимуществом нычисленйя булевых функций в произвольной скобочной форме является возможность вычисления двух и более функций, ес ли они входят одна в другую как аргументы. Например, рассмотрим функцииУ - Х Х Х чХ ) Х чХ ),1 - (Х чХ) ХВычисляя фуйкцию У в произволь ной скобочной форме, можно в виде промежуточного значения получить результат вычисления функции У . Если5 1 представить в ДНФ, то вычислить У в процессе вычисления Уне пред ставляется возможным. Формула изобретения Устройство для определения значе ний булевых функций, содержащее первый и второй КЯ-триггеры, первый и второй элементы И и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем первый вход первого элемента СЛОЖЕНИЕ З 5 ПО МОДУЛЮ ДВА соединен с шиной управления устройства, а выход соединен с первым входом первого элемента И, второй вход которого соединен с шиной управления устройства, выход вто-щ рого элемента И соединен с единичным входом первого КБ-триггера, нулевойвход которого соединен с шиной управления устройства, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей за счет вычисления булевых функций в произвольной скобочной форме, в него введены мультиплексор, третий КЯ-триг - гер, второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем выход первого КБ-триггера соединен с вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого элемента И соединен с единичным входом второго КБ-триггера, нулевой вход которого соединен с шиной управления устройства, а выход второго КЯ-триггера соединен с первым информационным входом мультиплексора, второй информационный вход которого соединен с шиной логической единицы, остальные ин-, формационные входы мультиплексора являются информационными входами устройства, управляющий вход мультиплексора соединен с шиной, номера аргумента, а выход мультиплексора соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход ,которого .соединен с единичным входом третьего КЯ-триггера, выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом второго элемента И, вторые входы второго и третьего элементов СЛОЖЕ 11 ИЕ ПО МОДУЛЮ ДВА, второго элемента И и нулевой вход третьего КБ-триггера -соединены с шиной управления устройства, выход которого соединен с выходом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.