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

 

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

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

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

РЕСПУБЛИН

А1 ()9) О)) (5)) 4 G 06 F 7/00

3CFI -":)<.." ";

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ИФ Dd жург сю йтраазо

ЖщмИ4М нсхоОное положение

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4)20714/24-24 (22) 20.06.86 (46) 07.02.88. Бюл. )) 5 (71) Московский автомобильный завод им. И.А.Лихачева (72) О.В.Катков, A.È.Aíäåðñîí и В.И.Хохлов (53) 681.3 (088.8) (56) Авторское свидетельство СССР

М 1049898, кл. G 06 F 7/00, )982.

Авторское свидетельство СССР

))- 1242928, кл. Г 06 Г 7/00, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к вычислительной технике, а более конкретно к программному управлению технологическим оборудованием. Цель изобретения — расширение функциональных воэможностей эа счет реализации сложных

EIHBepcHblx форм булевых функций. Устройство для вычисления булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ

), реверсивный счетчик 2, триггер 3>

1372319!

О элемент IIE 4, элемент ЗАПРЕТ 5, коммутаторы 6-8. Вычисление производится в порядке естественной записи аргументов. В процессе вычисления существуют два условных перехода: а) когда результат операции ИСКЛЮЧАЮЩЕЕ

И.1Д! над сигналами на информационном входе и входе признака Инверсия

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

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

На фиг. показана функциональная схема устройства; на фиг.2 — алгоритм работы устройства; на фиг.3— временная диаграмма работы устройства.

Устройство (фиг.1) содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ I, реверсивный счетчик 2, триггер 3, элемент НЕ 4, элемент ЗАПРЕТ 5, коммутаторы 6-8.

Логические блоки устройства выполняют следующие действия.

Блок I устанавливает состояние счетчика 2, равное "0", и состояние триггера 3, равное "1". Блок 2 проверяет состояние счетчика 2 на равен"0",.RJIOK 3 триггера 3 на равенство "1 Блок 4 проверяет, имеется ли знак дизъюнкции "+". Блок 5 проверяет, имеется ли открывающая скобка "(". Блок 6 проверяет, имеется ли закрывающая скобка

")". Блок 7 проверяет, имеется ли знак инверсии "/". Блок 8 устанавливает состояние триггера 3, равное

"1". Блок 9 устанавливает состояние триггера 3, равное "0". Блок 10 производит инкремент счетчика 2. Блок 11 З5 производит декремент счетчика 2.

Блок 12 проверяет значение аргумента на равенство "0".

На временной диаграмме работы устройства показано взаимное расположе40 ние сигналов на входах признаков устравен единице и еСть сигнал признака

Дизъюнкция", б) когда результат операции ИСКЛЮЧАЮЩЕЕ ИЛИ равен нулю и нет сигнала признака Дизъюнкция .

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

НЕ 4, на информационном входе и входе синхронизации устройства.

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

Сигнал установки устройства в исходное состояние, переводящий счетчик 2 в состояние "0", а триггер 3 в состояние 1", подается асинхронно на вход установки устройства в исходное состояние перед каждым циклом вычисления очередной булевой функции.

Устройство используют для вычисления булевых функций алгебраических уравнений (знак дизъюнкции "+", открывающие "(и закрывающие ")" скобки, знак инверсии / ).

Рассмотрим уравнение.

Х, (Х,/+Х +Х /) (Х Х (Х +Х ))» (I) Для любого булевого уравнения вычисления ведут в порядке естественной записи аргументов, слева направо.

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

В начале вычисления устанавливают значение функции, равное "1 . Решают уравнение, вычисляя по порядку аргументы.

В процессе вычисления уравнения существуют два условных перехода:

1372319 когда результат операции ИСКЛ10ЧЛОЩЕЕ 1!ЛИ над сигналами, поступающими на информационный вход устройства и на вход признака инверсии устройст- 5

t l 11 на, равен 1 и есть эпак дизъюнкции

11 11, когда результат операции ИСКЛЮЧАЮЦЕЕ ИЛИ равен " О" и нет з на к а дизъюнк ции + (т . е . стоит знак ко нъюн кции ) .

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

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

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

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

Для отыскания последнего аргумента диэъюнкции при первом условном переходе рассмотрим дизъюнкцию вида (Х, +Х, /+Х,+ ° .. +Х „/) Х „„= Y (3) или Х„+1 (Х1+Хг/+Х, ° ° ° +Х1, /)+Х 11+ г " 50

= у (4) где Х„„ и Х „+ — любые, сколь угодно сложные аргументы.

Из уравнений (3) и (4) видно, что

55 окончание дизъюнкции определяется наличием закрывающей-скобки. Однако любой член дизъюнкции может быть в

Х, + Х,/+Х, +...+X„/ = Y. (2)

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

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

Х Х / Х ...Х„Y (6) Если эта конъюнкция входит в состав более сложного аргумента, то после нее должен стоять знак дизьюнкции, с помощью которого к ней присоединяется в общем случае любой, сколь угодно сложный аргумент

X„ X Х . ° .Х„ .+ Х „, — Y. (7) Из уравнения (7) видно, что окончание конъюнкции определяется наличием знака диэъюнкции +". Однако, как и при первои условном переходе, каждый иэ аргументов может быть сколь угодно сложным, содержащем в сною очередь знаки дизъюнкции и скобки. Например, Х, Х / (B +В ) Х ...Х +Х „,, Y (8) Тогда перед знаком дизъюнкции, входящим в сомножитель вычисляемой конъюнкции, должна быть открывающая скобка, и лишь в том случае, когда свою очередь сложным аргументом и содержать скобки.

Например, Х +В,(В,+В ), когда уравнение (3) примет вид (Х,+В, (В,+В )+Х +...+X„/)X„„=Y (5)

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

I 372319 нсе открывающие ск<16ки скомпенсирпна«II! ЗЛКРЬ«Н««««Ц«ИМИ, ЗНЛК ДИЭЪЮНКЦИИ "+" я««г«я ется указанием нл окончание

КО ««Ъ«1««К««ИИ .

Тогда прлнило для отыскания по-следнегп члена конъюнкции можно практовать тлк: по ходу вычисления подсчитывается количество открывающих и закрынающих скобок, причем закрынаю«цие скобки считая тся лишь т»гда, когда Itt tee тся хп тя бь«одна пткрывл«1«щая скобка. Егли разность между числом пткрынлн щих и закрывающих скобок ранил нулю, то нлttáoлее близкий по ходу )5 вычисления знак дизъюнкции + уклэынлет пл окончл««ие конъюнкции.

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

В начале вычислений счетчик 2 ус — 20 тлнлнлинлетгя н с»стояние О, а

11 11 триггер 3 — н состояние "! ". В процессе вычислений последовательно по шагам для каждого аргумента булевого уравне ния схема ИСКЛ)ОЧА)«)ЩЕЕ ИЛИ 1 при на- 25 л««чии знака инверсии инвертирует сиг««;«л, поступлкцций с информационного входа устройства, при отсутствии знака и««нер<.ии сигналы нл информационном нхпде устройства и на выходе элемента ИСКЛ)«)ЧАИЩЕЕ ИЛИ совпадают.

Если нл выходе элемента ИСКЛ)!)ЧАЮЩЕЕ ИЛИ 1 поянится сигнал логической !" и к тому же имеется знак диэъюнк-! ° 11 ции +, To выполняются условия для

35 первого условного перехода, на входе прямого приращения реверсивного счетчика 2 устлновится сигнал логической I и с приходом импульса синхронизации значение содержимого счетчика 2 40 увеличится íà "I ".

Когда содержимое счетчика 2 отличается от исходного, то значение сигнала на вь«ходе элемента НЕ 4 примет значение 0, при этом накладывается запрет на вычисление последующих ар гументов и изменение состонния триггера 3.

Начинается подсчет. счетчиком 2 открывающих и закрывающих скобок. При этом на нход обратного приращения

50 счетчика 2 через элемент ЗАПРЕТ 5 подается сигнал 13акрынаюн«ая скобка, а на вход прямого приращения счетчика 2 через коммутатор 8 — сигнал "Открывающая скобка . Когда количество

11 закрывающих скобок будет хотя бы нл одну больше числл открывающих скобок счетчик 2 установится н исходное с»гтпян««е "О", л сигнлл иа выходе элементл )II . 4 примет значение "!" и нычисления продолжаются.

Если «п выходе элемента ИСКЛК)ЧА)ОIIII;F. И 1)I появится сигнал логического О и к тому же отсутствует знак дизъюнкции +, то выполняются условия для второго условного перехода.

Триггер 3 сбрасывается в состояние О, л нл его выходе устанавливается значение выходного сигнала (функция), равное "О". При этом счетчик 2 будет подготовлен к отсчету о ткрынающих и закрывающих скобок. Причем закрынающие скобки подсчитываются лишь тогда, когда имеется хотя бы одна открывающаяся скобка. Если по ходу вьгчисления нсе открывающие скобки будут скомпенсирова««ы закрывающими (состояние счетчика 4 равно "О") и имеется

I l l l знак дизъюнкции +, то триггер 3 устанлнливлется в исходное состояние равное !" и нычисления продолжлются .

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

I- и К-входы триггера и тем самым изменяют его состояние на противо««о „эжное .

После проверки всех аргументов реализуемой булевой функции, представленной и виде алгебраического уравнения, значение функции 1 О или

1 1 снимается с выхода триггера 3.

Это значение является результатом решения уравнения.

Рассмотрим и качестве примера работу устройства при вычислении ураннения (фиг.3) (Х, /+ (Х z Х,/ Х «+Х q Х, /+Х, ) /+Хн " (Х1«+Х „)/) Х„ /)/Х „= Ъ. (9) Для определенности предположим, что все аргументы находятся в состоянии логическои ) . Таблица, характеризующая состояние устройстна в процессе нычисления, имеет следующи«1 вид.

Вычисленное значение функции н данном случае равно .

Ф

Предлагаемое устройство для вычисления булевых функций позволяет реализовать сложные инверсные скпбочнь«е формь«булевых фу««к««ий, tipPIicx«III!Ie«tных н ниде алгебраических ypa«1«t««I«It

7 !3723)9

Шаг чис

Х /+

Х2/

2х

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

Устройство для вычисления булевых функций, содержащее элемент ИСКЛЮЧЛН1- 5

ШЕЕ !ПИ, реверсивный счетчик, триггер, элемент ЗАПРЕТ и первый коммутатор, причем входы обратного и прямого приращения реверсивного счетчика соединеггы с выходлми элемента ЗЛПРЕТ (0 и элементл ИГП! первого коммутатора, синхровход и вход сброса реверсивного счетчика соединен с одноименными входлми устройства и одггоименгыми входами триггера, выход которого сое- 5 динен с выходом устройства, вход признака Закрывающая скобка< которого соединен с прямым входом элемента

ЗЛПРЕТ, входы признлков "Открывающая скобка и Дизъюггкггия устройства 20 соединены с прямым входом первого элемента И и первым входом второго элемента И первого коммутатора, вход признака Инверсия" устройства соединен с первым входом элемента ИСКЛЮ- 25

ЧЛЮЦЕЕ И П1, второй вход которого соединен с информационным входом устройства,отли чающее сятем, что, с целью расширения функциональных возможностей за счет реализации З0 сложных инверсггых форм булевых функций, оно содержит второй и третий коммутлторы и элемент НЕ, причем вы— ход реверсивного счетчика соединен с входом элемента НЕ, выход которого соединен с инверсным входом элемента

ЗАПРЕТ, инверсным входом первого элемента И и вторым входом второго элемента И первого коммутатора, первыми входами первого и второго элементов

И второго коммутатора, прямым входом церн<<го элементл l! и <,< рным пря."-я<м входом второго элемента И третье г< !

1 ° комм <т<з то!«< вход прггз н г кл 3 л к pl < <<<1 <« щля скобк;г устройстг<л соединег< с вторым входом первого ггемеггтгг И нторого коммутатора, первым инверсным входом первого элемента И и вторым входом второго элемента И третьегг

II коммутлторл, вход признлка Открынлк щая скобка устройства соединен с прямым входом третьего элемента И первого коммутаторл и вторым инверсным входом первого элемента И третьего коммутатора, вход признлкл

Дизъюнкция устройства соединен с вторым входом второго элемента И второго коммутатора, третьим инверсным входом первого элементл И и инверсным входом второго элемента И третьего коммутатора, третий вход второго элемента И первого коммутатора соединен с выходом элемента ИСКЛЮЧЛЮШЕЕ

ИЛИ и четверт..м инверсным входом первого элемента И третьего коммутатора, третий прямой вход второго элемента И которого соединен с входом признака Инверсия устройства и третьим входом первого элемента И второго коммутатора, выходы первого, второго и третьего элементов И первого коммутатора соединены,с входами элемента ИЛИ первого коммутатора, выходы первого и второго элементов И второго и третьего коммутаторов соединены с входами элементов ИЛИ второго и третьего коммутаторов, выходы которых соединены соответственно с Iи К-входами триггера, выход которого соединен с инверсным входом третьего элемента И первого коммутатора.

Продол ке ни . тл блицы

12

14

17

19

ХЗ/

Х4+

Х5

Хб+

Х7

ХЗ

Х9+

Х10

X ll /

XI2

1372319

+1

+1

+1

2х

2х

2х

2х

2х

2х

)х

)х! 372319 фиг, 2

I 3723 I 9

8,гоа синхронизации

Инжормационныи

&оо

Вкоо признака дизьюнкции

Выно3 элемента 1

ИСКЛЮчАЮЩП иАИ

Выкоо триггера 2

Выхо3 элемента 4

И/И

Фиг.,У

Редактор В.Данко

Заказ 484/41 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

II3035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгорсд, ул. Проектная, ЮЫ признака открыли еи скооки

Вюоо признака занрыбающеи скоони

&оо признана иноерсии

Составитель О.Березикова

Техред М.Ходанич Корректор Н.Король