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

со -д

ю

DO

13723

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

19

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

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

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

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

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

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

Блок I устанавливает состояние счетчика 2, равное О, и состояние триггера 3, равное I. Блок 2 проверяет состояние счетчика 2 на равенство О,.Блок 3 проверяет состояние триггера 3 на равенство . Блок 4 проверяет, имеется ли знак дизъюнкции +. Блок 5 проверяет, имеется л открывающая скобка (. Блок 6 проверяет, имеется ли закрывающая скобка ). Блок 7 проверяет, имеется ли знак инверсии /. Блок 8 устанавливает состояние триггера 3, равное 1. Блок 9 устанавливает состояние триггера 3, равное О. Блок 10 производит ипкремент счетчика 2. Блок 1 производит декремент счетчика 2. Блок 12 проверяет значение аргумента на равенство О.

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

ройства, на выходах элемента ИСКЛЮЧАЮЩЕЕ ИШ1 1, триггера 3, элемента НЕ 4, на информационном входе и входе синхронизации устройства.

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

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

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

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

X,. (Х /ч-Хз+Х /) . (,(X,-t-Xg))«

«Х,+Х,, Y

(I)

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

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

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

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

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

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

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

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

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

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

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

X,

Х,/+Х. -Н...+Х / Y.

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

(X.,,/+X3-t-...-t-X,/) Хп4. Y (3) или (Х,,. ..-ьХ./)+Х„ + 2 - Y,W

где Х, и Х„, - любые, сколь угодно сложные аргументы.

Из уравнений (3) и (4) видно, что окончание дизъюнкции определяется наличием закрывающейскобки. Однако любой член дизъюнкции может быть в

свою очередь сложным аргументом и содержать скобки.

Например, ,(Во+В,), когда уравнение (3) примет нид (Х,-1-В, (B,,),+ ...)X,, У. (5) По ходу вычисления, если, например, значение X, равно , нет знака инверсии и стоит знак дизъюнкции, то это означает, что вся дизъюнкция инстинна. Для продолжения вычислений необходимо найти последний член этой дизъюнкции. Однако закрывающая скобка после аргумента В не характеризует окончания данной дизъюнкции. Такие скобки, принадлежащие сложным аргументам, характеризуются тем, что каждой закрывающей скобке соответствует открывающая скобка, и лишь последняя закрывающая скобка, указывающая на конец дизъюнкции, оказывается нескомпенсированной открывающей скобкой. Поэтому правило для отыскания последнего члена дизъюнкции можно трактовать так: по ходу вычисления подсчитывается количество открывающих и закрывающих скобок, и тот наиболее близкий шаг вычислений, в котором число закрывающих скобок хотя бы на одну больше числа открывающих скобок, указывает на конец дизъюнкции.

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

дд

45

50

X, ...Х„ У.(6)

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

X,. Х,-Х,...Х„.+ X,,, Y. (7)

Из уравнения (7) видно, что окончание конъюнкции определяется наличием знака дизъюнкции Ч. Однако, как и при первом условном переходе, каждый из аргументов может быть сколь угодно сложным, содержащем в свою очередь знаки дизъюнкции и скобки. Например,

Хг XI/-(B,+BJ-X,. ..,, -Y (8)

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

все открывающие скобки скомпенсирова ны закрыван)и1ими, знак диг1ъюикции + является указанием на окончание

К01ГЬИНКПИИ.

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

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

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

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

первого услонного перехода, на входе прямого приращения реверсивног(т счет чика 2 установится сигнггл логической 1 и с приходом импульса синхронизации значение содержимого счетчика 2 увеличится на 1.

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

Начинается подсчет.счетчиком 2 открывающих и закрывающих скобок. При этом на вход обратного приращения счетчика 2 через элемент ЗАПРЕТ 5 подается сигнал Закрывающая скобка а на вход прямого прирашения счетчика 2 через коммутатор 8 - сигнал Открывающая скобка. Когда количество закрываюищх скобок будет хотя бы на одну больше числа открывающих счетчик 2 установится в исходное сос

5 о

5

Q

0

тояние О, а сигнал на выходе элемента НЕ 4 примет значение 1 и вычисления продолжаются.

Если на выходе элемента ИСКЛЮЧАЮЩЕЕ И:Ш I появится сигнал логического О и к тому же отсутствует знак дизт к1нкции то выполняются условия для второго условного перехода. Триггер 3 сбрасывается в состояние О, а на его выходе устанавливается значение выходного сигнала (функция), равное О. При этом счетчик 2 будет подготовлен к отсчету открывающих и закрывающих скобок. Причем закрывающие скобки подсчитываются лишь тогда, когда имеется хотя бы одна открывающаяся скобка. Если по ходу вычисления все открывающие скобки будут скомпенсированы закрывающими (состояние счетчика 4 равно О) и имеется знак дизъюнкции +, то триггер 3 устанавливается в исходное состояние равное I и вычисления продолжаются.

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

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

Рассмотрим в качестве примера работу устройства при вычислении уравнения (фиг.3)

(Х,/ч-(Х,г X,/ .Xj+X,)/-t-Xg « (X,-fX ,„)/) X,. /)/-Х,2 Y. (9)

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

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

Предлагаемое устройство для вычисления булевых функций позволяет реализовать сложные инверсные скобочн} е формы булевых фу}гкций, пpгдcтaвлef - ных в виде алт сбраических уравнений.

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

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

функций, содержащее элемент ИСКТЮЧЛКЬ г тля скобка устройства соедине) с ЩЕЕ 1ШИ, реверсивный счетчик, триг- вторым входом первого элемента И нто- гер, элемент ЗАПРЕТ и первый коммутатор, причем входы обратного и прямого приращения реверсивного счетчика

рого коммутатора, первым инверсным входом первого элемента И и вторым входом второго элемента И третьего

соединены с выходами элемента ЗАЛРЕТ юкоммутатора, пход признака Открынак

и элемента ИЛ первого коммутатора, скобка устройства соединен с

синхровход и вход сброса реверсивно-прямым входом третьего элемента И

го счетчика соединен с одноименными

входами ycTpoiicTBa и одноименными

входами триггера, выход которого сое- коммутатора, вход признака

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

динен с выходом устройства, вход . признака Закрывающая скобка которого соединен с прямым входом элемента ЗАПРЕТ, входы признаков Открывающая скобка и Дизъюнкция устройства соединены с прямым входом первог-о элемента И и первым входом второго элемента И первого коммутатора, вход

20

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

признака Инверсия устройства соединен с первым входом элемента ИСКЛЮ- 25 первого элемента И третьего комьгута- ЧАЮЩЕЕ RTDl, второй вход которого сое- третий прямой вход второго эле- динен с информационным входом устройства, отличающе еся тем, что, с целью расп ирения функциональных возможностей за счет реализации сложных пнверс1{ых форм булевых функций, оно содержит второй и третий коммутаторы и элемент НЕ, причем вы30

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

ход реверсивного счетчика соединен с входом элемента НЕ, выход которого

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

соединен с инверсным входом элемента ны с входами элементов ЯГШ второго и ЗАПРЕТ, инверсным входом первого эле- третьего коммутаторов, выходы кото- мента И и вторым входом второго элемента И первого коммутатора, первыми входами первого и второго элементов .,. И второго коммутатора, прямым входом

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

(

Х1/ +

(

Х2/

О

о о о

первого элемента II и прямым входом нторого элемента И третьег о к :1мм татора, вход признака Закрыиаи

тля скобка устройства соедине) с вторым входом первого элемента И нт

рого коммутатора, первым инверсным входом первого элемента И и вторым входом второго элемента И третьего

первого коммутатора и вторым инверсным входом первого элемента И третье ° коммутатора, вход признака

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

первого элемента И третьего комьгута- третий прямой вход второго эле-

первого элемента И третьего комьгута- третий прямой вход второго эле-

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

ны с входами элементов ЯГШ второго и третьего коммутаторов, выходы кото-

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

о о о о

о

Продолженмо таОлицы

(Havff/ta

/ Hem

Ла / Hem

Hem P j

Л

фиг. 2

Bxoff синхронизм- АЛАЛАЛЛЛЛЛЛЛ71ЛААЛАЛЛЛ.

Инооорцационныи г-i г-л г

npu3Haf(a Г Г Г

отнрыбающей

CffOOffU

Вход признака за рыбаюи4еи скобки

Вход призмаffcr дизъюнкции

Вход /ipujHOffar f Г Г Л Г инберсии

э еиента 1 HC/ /lfffVAH ff

триггера 2

Выход И/f/

г

rLTLTL-Jl

Фиг, 3