960795 - Устройство для распознавания функциональной полноты систем логических функций

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

Иллюстрации

Показать все

Реферат

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советскик

Социалистическик

Республик

<>960795 (61) Дополнительное к авт. свид-вувЂ” (22) Заявлено 210579 (21) 2769578/18-24 с присоединением заявки ¹ (23) Приоритет

f/)) М Ку 3

С 06 Р 7/00

Государственный комитет

СССР по делам изобретений и открытий

Опубликовано 23.09.82. бюллетень ¹ 35 !

Дата опубликования описания 23.09.82 (33) УДК 681.3 (088 ° 8) (72) Автор изобретения

О.И. Сидоренко (71) заявитель (54) УСТРОЙСТВО ДЛЯ РАСПОЗНАВАНИЯ ФУНКЦИОНАЛЬНОЙ

ПОЛНОТЫ СИСТЕМ ЛОГИЧЕСКИХ ФУНКЦИЙ

Изобретение относится к вычислительной технике и может быть использовано при синтезе цифровых устройствИзвестно, что одной из важных . задач синтеза логических устройств является выбор типов элементов, из которых должны собираться логические схемы (1) .

Основное требование, предъявляе мое при этом к набору логических элементов, состоит в том, чтобы с

:его-.помощью можно было построить лю бую сколь угодно сложную логическую схему.

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

При этом для синтеза оптимальных цифровых устройств среди огромного, множества систем логических функций приходится выбирать функциональнополные системы, удовлетворяющие некоторым критериям оптимальности. В частности существенными достоинJ ствами при синтезе об тадают неизбыточные {базисные) системы булевых функций, представляющие также большой теоретический интерес как системы образующих алгебры логики.

Задача распознавания функциональной полноты систем логических, функций до сих пор решалась, по существу, вручную, на основании теоремы Поста: для того, чтобы система булевых функций была функционально-полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию, не сохраняющую константу нуль, хотя бы одну функцию, не сохраняющую константу единица, хотя бы одну немонотонную функцию, хотя бы одну нелинейную функцию и хотя бы одну несамодвойственную функцию (2).

Учитывая тот факт, что существу-, ет бесконечное множество функционально-полных систем булевых функций (3), а также трудоемкость операций по выявлению свойств полноты, было бы желательно автоматизировать процесс решения указанной задачи.

Целью изобретения является созда" ние устройства для распознавания функциональной полноты, с помошью

960795

4. которого производится упрощение про. "цесса выявления базисных систем логических функций по сравнению с ручными метэдами.

Указанная цель достигается тем, что устройство для раснознаванйя функциональной полноты систем логических функций содержит наборное поле из 2 перееключателей (где.п и число переменных булевых функций), блок определения свойства не сохранения константы нуль, блок опре деления свойства не сохранения константы единица, блок .определения свойства немонотоинести, блок опре1деления свойства нелинейности, блок определения свойства несамодвойственностн, дешифратор наборов свойств полноты, регистр запоыинания набо ров свойств полноты, дешифратор ба,зисных групп и блок сборки, причем дешифратор .наборов свойств полноты содержи четырнадцать элементов И, дешифратор базисных групп содержит сорок один .элемент И, бло» сборки содержит три элемента ИЛИ, прямой выход блока определения свойства не сохранения константы нуль соединен с первыми входами первого, второго, третьего, четвертого, пятого и шестого элементов И двшифратора наборов свойств полноты, инверсиый, выход блока определения свойства не сохранения константы нуль соединен с первыми входами остальных элементов И дешифратора наборов свойств полноты, прямой выход блока определения свойства ие сохране ния константы единица соединен со вторыми входами первого, второго, третьего, седьмого, восьмого и девятого.элементов И дешифратора наборов свойств полноты, инверсный выход блока определения свойства не сохранения константы единица соединен со вторили входами осталь-. ных элементов И дешифратора наборов свойств полноты, прямой выход блока определения свойства немонотонности соединен с третьими входа« ми первого, второго, третъего, четвертого, пятого, седьмого, восъмого, десятого, одиннадцатого и двенадцаТого элементов И дешифратора наборов свойств полноты, третьи .входы остальных элементов И которого соединены с инверсным выходом блока определения свойства немонотонности, прямой выход блока определения свой-. ства нелинейности соединен с четвертыми входами первого, второго„.четвертого, седъмого, десятого, один-надцатого, тринадцатого и четырнадцатого элементов И дешифратора наборов . свойств полноты, четвертые входы остальных элементов И которого соединены с инверсным .выходом блока определения свойства нелинейносТи,;. прямой выход блока определения свойства несамодвойственности соединен с пятыми входами первого, четвертого, пятого, шестого, седьмого, восьмого, девятого, десятого и тринадцатого элементов И дешифратора наборов свойств йолноты, пятне входы остальных элементов Й которогр соединены с инверсным выходом блока определения свойства несамодвойстаен10 ности, шестые входн всех элементов и дешифратора набсров свойств полноты соединены с шиной ввода устройства, а .выходы .подключены к входам установки в единицу соответствующих тригге15 ров регистра эапомийания наборов свойств полноты, аходы установки в .нуль которых соединен с шиной сброса устройства, выход первого тригге..ра регистра запоминания наборов

20 свойств полноты соединен с нераам выходом устройства, выход второго триггера регистра запоминания наборов: свойств полноты соединен с первыми входами первого, второго, третьего, 25 четвертого, пятого, .шестого, седьмого и восьмого элементов И дешифратора баэнсных рупп, вЫхад третьего триггера регистра запоминания набороВ свойств полноты соединен с

ЗО первыми входами девятого, десятого, одиннадцатого, двенадцатого, тринад-. цатого, четырнадцатого, пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого -8

35 двацатого элементов И дешифратора базисных групп, выкод четвертОго . триггера регистра запоминаний наборов .свойств полноты соединев со вторыми входами первого и девятого и с

40 первыми входами.двадцать первОГоg двадцать второго,и двазщать тратъего.. элементов И дешифратора ..:базисных

rpynn, выход пятого триггера регистра запоминания наборов свойств полноты

45 соединен со вторщ и вхоцами второго, тринадцатого и семнадцатого и первыми входами двадцать четвертого, двадцать пятого, двадцать шестого, двадцать седьмого, двадцать восьмого двадцать девятого., тридцатого тридцать первого и тридцать второго элементов И дешыфратара базисйык lynn< выход шестого триггера регистр@ запоминания наборов свойств полйоты соединен со вторыми входами третьего, 55 четырнадцатого и восемнадцатого и.с первыми входами тридцать третьего, тридцать четвертого, тридцать пятого„ тридцать шестого, тридцать седьмого, тридцать восьмого, тридцать

60 девятого, сорокового и сорок nepsoro элементов И. дешифратора базисных групп, выход седьмого триггера регистра запоминания наборов свойств полноты соединен со вторыми входами

65 четвертого, десятого, двадцать пер960795 восьмого, тридцать девятого., сороко» вого и сорок первого элементов И де- 2О шйфратора базнсныХ грУпп, вйход де.сятого триггера .регистра запоминайия цать шестого и тридцать восьмого элементов И дешифратара базисных, групП, выход одиннадцатого триггера регистра запоминания наборов свойств пол4 3g иоты соединен с третьими входами ..семнадцатого, восемнадцатого, девятнадцатого, двадцатого, тридцатого, тридцать второго, тридцать .седьмого и тридцать девятого. элементов И де- 35 шйфратора базисных групп,.выход двенадцатого триггера регистра запоминания наборов свойств полноты соединей с третьими входами сорокового и сорок первого элементов.И дешифра- 4 тора базисных групп,,выход тринадцатого триггера регистра запоминания наборов свойств полноты соединен со зторыми входами восьмого и двенадцато|о, с третьими входами двадцать 4 пятого, двадцать седьмого и тридцать четвертого и с четвертым входом сокового элементов И дешифратора азисних грунп, выход четырнадцато го.триггера регистра запоминания наборов свойств полноты соединен с 50 третьими входами тринадцатого, четырнадцатого, пятнадцатого, шестнадцатого, двадцать. шестого, двадцать восьмого и тридцать пятого и четвертым входом сорок первого элемен- 55 тЬв И двшифратора базисных групп, выходы первого, второго, третьего, четвертого, пятого,: шестого, седь« мОго, восьмого, девятого, десятого, :Одиннадцатого, двенадцатоГо, двад- ;Я} цать первого, двадцать второго, двад; ать третьего, двадцать четвертого

:и,тридцать третьего элементов И дешифратора базисных групп соединены со входами первого элемента ИЛИ 6ло- у5 вого, двадцать четвертого и тридцать третьего элементов И,дешифратора базисйых групп, выход восьмого триг-. ,гера регистра. запоминания наборов свойств .полноты соедийен со вторыми;, входами пятого, пятнадцатого, девятнадцатого, двадцать..:второго, двад" цать пятого., двадцать. шестого, двадцать. девятого,. тридцатого:, тридцать..четвертого,.тридцать пятого, тридцать. шестого и тридцать седьмого элементов. и дешифратора.базисных групп„.выход:девятого триггера ре-, . гистра запоминания наборов свойств полноты соединен со вторыми входами шестогб,.;шестцадцатого, двадцатот,:.. 15 двадцать- третьего., двадцать седьмого,:двадцать восьмого .тридцать первого, тридцать второго, тридцать наборов свойств полноты соединен са вторыми входами седьмого и одинйадцатого и третьими. входами двадцать девятого, тридцать первого,,тридка сборки, выход которого подключен ко второму выходу устройства, выходы тринадцатого, четырнадцатого,пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого,. девятнадцатого, двадцатого, двадцать, пятого, двад-.

:цать шестого,. двадцать седьмого,. двадцать восьмого, двадцать девято го,.тридцатого,- тридцать первого, тридцать. второго, тридцать четвертого, трйдцать-.пятого, тридцать шестого, тридцать седьмого, тридцать восьмого и тридцать девятого элементов И дешифратора базисных. групп соединены со входами второго элемента ИЛИ блока сборки, выход которого . соединен с третьим выходом устройства, выходы сороковогб и сорок первого элементов И дешифратора базисных групп соединены со входами третьего элемента ИЛи блока сборки, выход которого подключен к четвертому выходу устройства, блок определения свойства несохранения константы нуль содержит элемент НЕ, вход которого соединен с прямым выходом этого блока и с выходом первого переключателя наборного поля, а выход является ин.версным выходом блока определения свойств несохранения константы нуль, блок определения свойств несохранения константы единица содержит элемент НЕ, вход которого соединен с инверсным выходом этого блока и выходом последнего переключателя наборного поля, а выход является прямым выходом блока определения свой1 ства несохранения константы единица, блок определения свойства неи-1 монотонности содержит и. 2 элементов ЗАПРЕТ, элемент ИЛИ и элемент НЕ, причем входы каждого элемента ЗАОРЕТ соединены с выходами тех двух переключателей наборного поля, двоичные номера которых отличаются только в одном разряде, причем запрещающие входы элементов ЗАПРЕТ соединены с выходами переключателей наборного поля, имеющих больший номер, выходы элементов ЗАПРЕТ соединены со входами элемента ИЛИ, выход которого непосредственно соединен с прямым, а через элемент НЕ вЂ” с инверсными выходами блока определения свойства немонотонности, блок определения свойства нелинейности содержит п.2 элементов РАВНОЗНАЧНОСТЬ, и элементов И-НЕ; п 2" " элементов И, элемент ИЛИ и элемент НЕ, причем входы каждо о элемента РАВНО

ЗНАЧНОСТЬ . соединены с выходами тех двух, переключателей наборного поля, двоичные номера которых отличаются только в одном .разряде, выходы элементов РАВНОЗНАЧНОСТЬ, соединенных входами с выходами переключателей наборного поля, разность номе960795 ров которых одинакова, соединены со входами одного элемента И-НЕ и с первыми входами соответствующих элементов И, вторые входы которых подключены к выходу .этого элеманта И-НЕ, выходы элементов И цадключены ко входам элемента ИЛИ, выход которо» го непосредственно соединен с пряМйм, а.через элемент:НЕ - c инверс. ными входами блока определения свойства нелинейности, блок определения свойства несамодвойственности содержит .2" " элементов РАВНОЗНАЧ5

Обозначим. цифрой О случай, когда булевая функция обладает данным свойством полноты, и цифрой:1, если не обладает им. Тогда, очевидно, можйо составить 32 различных набора свойств полноты. Каждый такой набор будем рассматривать как двоичную запись

Ниола, .язляющагосЯ нОМвроМ Набора, расположив- наборы для удобства свер- .: ху вниз в естественном:порядке, со- ответствующем расположению чйаел от;

О до 31, каК это указано,В табл.- 1.

Не существует булевых фунюцМ обладающих наборамн свойств полноты с номерами 2, 4, 5, 6, 7, 9, ll, 12, 13, 15; 17, 19, 20, 21, 23, 26 и 30. для доказательства этого утверж-, дения разобьем указанные наборы на 65

НОСТЬ, элемент ИЛИ и элемент НЕ, при-. чем входы каждого элемент"а РАВНО.ЗНАЧНОСТЬ соединены с выходами тех 15 двух переключателей наборного поля, сумма номеров которых раина 2" - 1, выходы элементов РАВНОЗНАЧНОСТЬ сое:динены со входами элемента ИЛИ, .вы-. .ход которого. непосредственна соединен с прямым, а .через элемент ЕЕ - с инверсными входами блока определе.ния свойства несамодвойственности.

При таком построении устройства реализуется критерий неизбыточной. полнотй, при котором для каждой булевой функции из заданной системы вйделяются и запоминаются не просто свойства полноты, .как это делается в известном устройстве, а так назы- 30

saewe наборы свойств полноты, и далее проверяется. наличие не просто всех свойств полноты, а так. наэывае" мых базисных групп набовов.свойств . полноты, что позволяет непосредственно выявлять неизбыточные функциональ-35 но-полные системы булевых, Функций.

Назовем каждое из указанных в теореме о полноте Поста пяти свойств булевых фнукций, т.е..первое свой- ство вЂ” не охранять константу нуль 4О ,(Ko), второе -- не сохранять константу единица (К„), третье - быть немо-. нотонной {Й), четвертое - багь не. линейной (Й) и пятое - быть несамо- двойственной (C) . вЂ” свойством полно- :,45

l гы .. следующие группы: I ) 9, I l . 3, 15 °

2) 17, 19, 21 23) 3) 4, 5, 6, 7;

4) 12; 5) 20у 6) 2ó 7) 26 и 30.

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

К первой группе наборов свойств полноты относятся булевы:. Функции, . одновременно не .сохраняющие. константу нуль, сохраняющие константу единица и являющнеся самодвойственнымй °

Если булеза функция .f (х,. ° °

x„) не сохраняет константу нуль, то f (0,...,0) = 1 . Если булеза

Функция f (х,,,...,х„) сохраняет константу единица, то f (1 1) = 1.

Если булеза функция является самодвойствеиной, то на дюбых .двух протиэоположных наборах она принимает противоположные значения. Поскольку наборы .Все Î и . ace .1 являются противоположнюм, а значения функции.на этих наборах одина-ковы (равны 1), то условие самодвойственности при выполнении условий не сохранения константы нуль и сох-. ранения константы единица не может быть выполнено, что И доказиэаЕт приведенное утверждение дпя случая первой группы наборов свойств пол» ноты. Аналогично. приведенноЕ утверж- дение доказываетея и для всех ocTcUlbных случаев.

Таким образом, булевы функцйн мо-. гут обладать только 15-ю наборами свойств полноты, имеющими номера .

Оф 1у 3:ф 8р 10ю 14р 16р 18р 22, 24

25, 27, 28., 29 н 31;

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

Группа наборов свойств полноты удовлетворяет критерию полноты,в том: случае, если булевы функции, обладающие наборами свОйств подноты, составляющими. эту группу, образуют функционально-полную систему буле-. вых функций. . Для того, чтобы ГРуппа наборов свойств полноты была полной.группой наборов:, необходимо и достаточно, чтобы нули в двончнйк номерах .. наборов группы .созмеетио ПереКРы-. вали, все пять позиций, соответствую щих свойствам полноты. неиэбыточную полную групйу наборов свойств полноты назовем базнс-. ной группой. .Неизбыточная полная группа набо- ров свойств полноты характеризуется тем, что нули .в.двоичных номерах наборов группы .совместно.перекрывают все пять позиций, соответствую

960795

:нуль, блок 8 определения свойств несохранения константы единица, блок 9:определения свойства немонотонности, блок 10 определения свойств нелинейности, блок ll определения .свойства. несамодвойственности, шестивходные элементы И 12 вЂ” 25, входящие в состав дешифратора 3, триггеры 26 вЂ” 39,.входящие в состав регистра 4, двухвходовые .элементы И;40 вЂ . 56, четырехвходовые элементы И 57 и 58 и трехвходовые элементы И 59. вЂ” 80, образующие дешифратор 81 базисных групп, блок 82- сборки,.содержащий элементы ИЛИ 83 вЂ” 85., На фйг.2 показан также не входящий s. состав устройства блок 86 индикации:с элементами 87 - 90 индикации.

На перехлЮЧатели 2 наборного Поля:-1 по шинам .91 и 92 подаются .логические константы 0, и 1 .. В зависимости от положения переключателей 2 эти сигналы.по .шинам. 93

96 йодаются на входы,-блоков 7 - 11.

Блок 7:содержит элемент НЕ 97 и на своих прямом и. инвереном выходах

Форйирует сигналы, оступающие по шинам 98 и 99 на входы.дешифрато- ра 3. Блок 8 содержит элемент НЕ 100: и на свойх прямом и инверсном выходах формирует сигналы, поступаю»

iage no rrraiaM 101 а..:102 aa axon zeшифратора. 3. Блок 9- содержит элементы 3АНРВТ. 10 3 106, элемент йЛИ

107, элемент". НБ 108 и. Формирует нд своих пряМом н инверсном восходах сигНали, поступающие по шинам .199 и

11О: на входы дешифратора 3". Блок 10 содаржит элемеиты РАВНОЗНАЧНОСТЬ lll- .

114:, элЕменты И-НЕ 115 и 116, эле-. ментЫ- И: 117 - 120, элемент ИЛИ 121, :элемент HE 122 и Формирует:на своих пря юм и инверсном выходах сигналы, поступающие .по шинам 123 и 124 на . входы дешифратора 3. Блок 11 содержит элеьеиты РАВНОЗНАЧНОСТЬ 125 и 126, элемент ИЛИ 127„ элемент НЕ 128 к формирует на своих прямом и инверсном:выходах сигналы, поступающие по.шинам 129 и 130: на входы дешифратора 3. Входы дешифратора 3 соединены .со входами регистра 4, выход первого триггера 26 которого является .выходом устройства и шиной

131 соединен с элементом 89 индикации. Выходы остальных триггеров

:27 - 39 регистра 4 шинами 132

144 соединены со входами дешифратора 81,: выходЫ элементов И 40-80 которого соединены со входами элемен тов ИЛИ 83 вЂ . 85 блока 82, входы ко:торых являются выходами устройства

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

B алгебре логики имеется конечное число, равное 42, ..базисных групп наборов свойств полноты..Это вытекает иэ того,, что в алгебре логики существует всего пятнадцать .наборов . свойств. полноты, коибийирование: ко+ 1 0 торых в базисные группы:и доказывает.справедливость этого утверждецияе

Приведем все воэможные: базисные группы наборов свойств полнсты :О, .

1, 81 l е 10..» 1, 14У .1,. 16; 1,. 1 8.У

1, .22; 1.,:2-4 1, .281- 3, ВУ 3.,: ".16У

3 2:4; з,. 3, 28 ; 8,:. 1 6 ) 8:, 18 ; 8, 22»

10»16 14» 16». 3, 10» 29ю 3» .14» .29ю

3» 18» 29t .3» 22 29 .10»-. 18» 28; . 10, 18 29> 14„18, 28; 1.4, 18, 29.

10» 22». 28 : 10, . .22» 29;- 3»., 10, 25;

3.,- 14,- 25» 3, . 18, 25 у 3» 22, 25; .10 .1.8:, 24у 10, 22, 245:1:О,. 22., Я5у

1 14.: 18 25j 14» 22s 24

14, 22, 25 у 14,; 22, . 27, 28; 14, 22, 27,- 2 9 10» 18,:25.

Айализ йолученных: бааисйых . групп позволяет сделать - следуйвве, аыводыг з алгебре, логики имеется,.всего.,одна,баЭисиая грУйпа:наборов Свойств: полноты,:.состоящдя из одйого " набо-. ра, -семнащ ать баэиснЫх групй -; из двух -наборов,. двадцать две базисные группы,- as трех. наборов и; две,базисные.,группы- -. из четырех .нафорое . 35 свойств полноты.

Известно, что Функционально-.пол« иая .система:.булевых функциф,ника - кая составная часть каморр ве яв.-.. ляется полной, назйвается-:базисои.:,4О алгебры-;. логики

Для .того, чтобы. система булевйх .

Фуймций бйла. базйсом: алгебр® moraки,: необходимо к достаточно, чтоЬы группа ::наборов свойств ттолноты,".Со- отватствувщ@я этой системе, йол- -, йостью совпадала,с одйой .жз.42.воз+ можиых в алгебре логики .баэисййх. групп.

На Фиг 1 и 2 предстазле®а .струк- 50 турная схема -устройствами на фиг,:3выполнение наборного. йоля.и :блоков определения:.свойства несо фаие йя константы нуль, определения свой- ства,несохранения константы .едкий». ца, свойства немонотойности»: свой-.; ства нелинейности, свойства иесамодвойственности для случая 0=2.

Устройство содержит .наборное поле 1, содержащее, например,:,для случая И.-2:переключатели 2.р, 2, 1» 23 . дешифратор 3 наборов - свойств полноты, регистр 4 запоминания овойств полноты, шину 5 вво- . да, шину 6 сброса, блок 7 определе- . ния свойств несохранения константы- 65

960795

IÎ

Каждая булеза функция иэ заданной системы последовательно одна за другой задается с помощью 2" двухпазиционцых переключателей 2 наборного поля 1 {n вЂ” максимально возможное число переменных аналиэнруе- 5 мых .булевых Функций),.через которые в блоки 7 - 11 подаются сигналы аогического 0" или l в зависимости от положения переключателей 2. . Используя информацйю о состояниях переключателей 2 наборного .тюля 1, бараки 7 - 11, представляющие собой .комбинационные логические схемы, вы. рабатывают на своих выходах .пять со-ответствующих Оулевых функций

fK0 IIO . (1)

Значение функции несохранения константы нуль равно единице, если переключатель 2 с номером О, соот,ветствующий набору булевой функции .Все 0 установлен в полажение 1, и равно нулю, если этот переключатель установлен s положение

В I0 Ф!

fR, -- ПУ.„ (2)

Значение функции несохранения константы единица равно единице,. :если переключатель 2 с номером 2

1, соответствующий набору булевой функции Все 1, установлен в положение 0, и разно нулю, если этот переключатель установлен в ао- ложение 1

fM = VlI, lI;, . (3): где 1 и j вЂ” номера соседних наборов.

Значение функции немонотоннасти равно единице, если найдется хотя бы одна пара йереключателей 2, соответствующих соседним (склеивающимся) наборам и установленных в 40 противоположные положения, причем в такие, когда переключатель с нсмером, в котором склеивающаяся переменная равна нулю, установлен в положение 1, и равно нулю в противном 45 случае. В формуле (3) операция ч берется по всем и 2" " парма. соседних наборов й) . = Ч П- П, (4) где 1 и j .- номера наборов, соседних по существенной переменной.

Значение функции нелинейности раво единице, если найдется хотя бы ода пара переключателей 2, соответствующих соседним по существенной переменной наборам и установленных в одинаковое положение, и равно нулю в противном случае. B Формуле.:(4).. операция V берется по всем и-2" парам соседних наборов, f6= ЧП; П (5) где i.+ ) = 2"-1:.

Значение функций несамодвойствен-. ности разно единице, если найдется 65 хотя бы одна пара переключателей 2, соответствующих противоположным на.борам и -установленных в одинаковое положение, и равно нулю в противном случае. В формуле {5) операция берется по всем 2" парам противоположных наборов.

В формулах {1) " . (-5.). ч - .логическая операция ИЛИ7 вЂ” логическая операция РАВНОЗНАЧНОСТЬЮ.

- логиЧеская операция-.ЗАПРЕТ вЂ” - логическая операция НЕ.

Наборное поЛе l содеркит 2 пе» реключателей 2,:занумерованных так,,чта двоичные их номера совпадают с соответствующими наборами логйческих функций и переменных.: 9ce первые нереключаемые контакты переключателей 2 наборного поля l соедйнены c щиной 91 Логического нуля,:все вторые - с айной 92 логической едини-.: цы, а переключающие контакты соединены со входамй блоков 7 -. 11. .ВлоК 7 опредеЛения сзойотза .Неаохранения константы нуль представ ляет собой повторитель сиГнала (проводник), соединяющий переключатель 2 с номером О, с.прямым выхо" ,дом блока 7,.на котором реализует cs логичеекая функция (l),fR0. Для

ПОЛУЧЕНИЯ ИИВЕРсного. Выхода блока 7 используется элемент НЯ 97. Блок 8

Определения свойства несахранения (КонстаитЫ Единица ПрЕдстазляет сабай элемент.НЕ 100, вход которого сое.динен с„переключателем 2, имеющим номер 2 - 1, на выйоде которого реализуется логическая функцэя (2) йй„, и этот выход является йрямыи выходом блока 8. Для получения инверсного выхода используется.значе- ние- функции на входе злемеита НЕ 100.

БлЬк 9 Определения свойства ыемонотонности представляет собой . и 2"-" двухвходазык ЗЛЕМентоЗ. ЗАпРет 103 .- 106, входы каждого из которых соединены с переключателями 2, двОичные номера которых Отличаются только в одйом разряде, при этом запрещающие входы соединены с переключателями 2< имеющими.боливий номерz R выхОды сОединеиы с:Входами и 2" " входавого элемента ИЛИ 187 на выходе которого реализуется логическая функция (3) fИ, и этот выхОд является прямым выходом бла» ка 9, Для.получения инверсного выхода используется элеМент НЕ 108.

Блок 11 Определения свойства не-.. линейности ..представляет собой я 2" ", двухвходовых элеЯеитав РАВНОЗНАЧ НОСТЬ 111 - 114, и 2 "." входовых эле» ментов И-88 115 - 116 о.2" ":двух входовых элементов И 117 - 120 и один и 2 " входовой элемент ИЛИ 121, при этом входы каждого иэ элементов РАВНОЗНАЧНОСТЬ 111 - 1 14 соеди960795

14 тем группируются в четыре сигнала по числу наборов в базисных группах с помощью элементов ИЛИ 83-85 для Фор". мирования выходных сигналов устрой.ства, которые осуществляют включе" ние четырех элементов 87 - 90 индикации блока 86 индикации.

60 иены с переключателями 2, двоичные. номера которых отличаются только:в .одном разряде, выходе элементов РАВ33ОЭНАЧНОСТЬ 111 - 114, соединенных своими входаьн с переключателями 2 набориого поля 1, разность .номЕроз между которыми одинакова, соедине-.. ны с входами одного и того же элемента И-HE 115, 116, а также с.первыми входами соответствующих элементов. 117 - 120, вторые входы кото- 10 рйх.подключены к выходу этого эле.мента И-НБ 115-116, выходы элемен-. тов:И 117 - 120 соединены.с входами элемента ИЛИ 121, на выходе ко-. торого реалйзуется логическая .Функция (4)-..ХЛ, и этот выход является. прямым выходом блока 10. Для получения инверсного выхода используется элемент,НЕ:122.

5лОк 11 определения свойства "не» 20 . самодвофствениости представляет со ббй 2" . двухвходовых элементов РАВНОЗНАЧНОСТЬ 125 и.l2бр входЫ каждого из.которых соединены с переключателями 2, сумма номеров которых и равна 2 - 3,, а выходы соединены с входами 2" " входового. элемента ИЛИ .3.17, выход которого является пряьщм выходом блока.11, реализующего функцию (5) fC., Для получения ин-. версного .выхода используется элемент НВ 128.

Н@ выходах блоков 7 - 13, образу;ется двоичнйй пятиразрядный потен-, циаЛьный код набора. свойств полноты, которым обладает набранная булеза функция. Дешифратор,З:наборов

-свойств полноты, представляющий собой комбинационную логическую схему иэ четырнадцати щестивходовых элементов И 12 вЂ” 25, осуществляет аре40 образованиЕ каждого ИЗ ПЯтиадцатм возможных кодов наборов. свойств пол» ноты в сигналы установок в,единицу. триггеров 26 -,39 регистра 4. устайовка в единицу триггеров 26 .-45

39..регистра 4, для которыХ.выработан сигнал, усгаиовки в едийицу, происходит по команде ввода. (напр мер, путем кратковременного нажатия кнопки:ввода и подачи управляющего сиг+ 5О нала по шине 5 ввода).

Сигналы с триггеров 26 - 39 с помощью дешифратора 81 базисах групп, представляющего собой элементы .И 4080, соответствующие. всем- возможным 55 в алгебре логики базисиым группаМ наборов свойств hoëíîòí, преобразуют-, ся в сорок два сигнала, которые эаТаким образом, поочередно набирая -булевы Функции из заданной системы, автоматически определяя их свойства полноты и осуществляя каждый раз ручной ввод полученного очередиого набора свойств полнотЫ в ,регистр с последующей автоматической проверкой .хранящейся в памяти группы .наборов свойств полноты на наличие базисных групп, мы получаем.информацию о том, является ли данная система избыточной,. базисной или неполной. При этом возможны следующие случаи: а) После анализа всех булевых функций из заданной системы не включен ни один нз четырех элементов индикации. Это говорит о том, что анализируемая система логических

Функций не полна. б) После анализа всех булевых функций из заданной системы включены или несколько элементов индикации блока 86 индикации, или только один элемент индикации, соответствующий базисным группам, число -наборов свойств полнотй в которых меньше числа анализируемых булевых функций в системе.. Это говорит о том, что анализируемая система логических

Функций полна и избыточна. в) После анализа всех булевых

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

После окончания работы триггеры

26 - 39 регистра 4 могут быть установлены .в исходное состояние (обнулены) по команде сброса, (йапри;мер, путем кратковременного нажаткя кнопки сброса и подачи управляющего сиги@ма по шине 6 сброса) .

РассМотрим работу устройства на следующих четЫрех конкретных примерах, приведенных в табл. 2. ..Пример 1. С помощью таблиц:истинности задана система из четырех логических Функций от трех переменных Е„, Е, Еэ и Е4..Опреде.лить, является ли она избыточной, базисной или неполной.

Набираем Функцию f< установкой переключателей 2„, .2, 2g 24 наборного поля 1 в положение 1, остальные переключатели устанавливаем в положение 0 . Так как переключатель 2 наборного поля 1 установлен в положение 0, то

Ny O. Так как переключатель 2>, наборноГо поля 1 установлен в поло15

960795

Замечание о возможности набора в .ал.-. гебре логики

Двоичный код набора свойств полноты

Десятичный номер набора свойств полноты

КО б

0 -

Не возможен

То же

0 жение 0, то fR 1. Так как переключатели 2„ и 2 наборного по- Ч ля, соответствующие склеивающимся наборам, установлены в противоположные положения, причем переключатель 2„, соответствующий набору, Б в котором склеивающаяся буква равна 0, установлен в положение 1!, то fM = 1. Так как переключатели 3О .и 2> наборного поля, соответствуюзие наборам с четным чис- 10 лом единиц, установлены в противоположные положения, тб. ЮЯ ** 1.: йак как переключатели 2О и 2 наборного поля 1, соответствующие противоположным наборам, установлены . в.одинаковое положение,,то И» l.

Таким образом, на инверсных вы: ходах блоков 7 - 11 образуется двоичный код 10000, соответствующий набору свойств йолноты набранной булевой функции f которая сохраняет константу .нуль, не- сохраняет константу единица и является немонотоиной, нелинейной и несамодвойственной.

C помощью элемента И 18 деаифратора 3 наборов свойств.полноты двоичный код 10000 преобразуется в сигйал установки в единицу триггера. 32 регистра 4., соответствующего набору свойств полноты с десятичным номером 16 .. Установка в единицу этого триггера происходит.по команде ввода. Ф

Так как не существует базисной группы, состоящей из одного набора 35 с номером 16, то на ВЫходах дешифратора 81 базисных групп и блока 82 сборки Вырабатывается сигнал 0 и остаются не включенными sce четы. Ре элемента 87 - 90 индикации блока 40

86 индикации, соответствующие базис ным группам из одного, двух, трех и четырех наборОВ свойств полноты.

Айалогичйо ; после набора и ввода информации об остальных функциях„

fop fg И 24p ОКаэынаются УстанОВ» ленными в единицу трнггеры 29, 38 и 39, соответствующие наборам свойств полноты с. намерами 18, 28 и 29. Однако на выхопах деаифратора 81 базисных групп блока 86 сборки по" прежнему вйрабатывается сигнал- 0 и остаются ge включенными. все четыре элемеита 87 - 90 индикации, так как не сущес1вует базисных групп, состоящих из всех или части указанных наборов. Таким обраэом, можно сделать Вывод о том, что система булевых функций для данного примера не полна. Аналогично осуществляется работа устройства и s случае примеров 2 вЂ” 4 (см. табл. 2).

Данное устройство почти полностью состоит из комбинационных схеМ, поэтому оно.имеет высокое быстродействие и простую структуру, сложность которой не зависит от числа переменных анализируемых булевых функций (за исключением конструкции наборного поля l и. блоков.7 - 11). Действия. оператора максимально облегчены и сводятся к простейщим операциям по набору заданных булевых функций и пользованию кнопками ввода и сброса.

Данное устройство позволяет различить не только функционально-полные, но и базисные системы лОГНЧЕСКИХ:,. фуНКЦИйz т+ei ПРОИЗВОДИТЬ ДОВОЛЬНО тонкий анализ сВОйств систем булевых функций,.необходимый в ряде случаев при сОздании оптимальных стРуктуР интегральных субсистем. ,Т а б :л и ц а 1

960795

)Замечание о воэможности набора в алгебре логики!

Десятичный номер набора свойств полноты

Kî..К1

Не возможен

9 .: lQ

Не возможен

То же

Не возможен

lб

Не возможен

О О

17.0

О.

Невозможен

То же

Не возможен

23 О

О О

О . О

2б Не возможен .) О

Не возможен

Двоичный код набора свойств полноты

О . О

О 0

0 1

0 . 1

l 0

1 . 0

1 1

О О

О . l 1 . О . 1 .. О

1. 1

Продолжение табл. 1

960795 го

-3

l.&

1 I

I . 1

I 3

Ф t

1 Ч3 3

1 !

I ! .

l . I

1 l

3 е3

t. W I ! 3 1

I . с щ 1

1 !

М4 1

I I о о

1 I

l с ! М 3

1 I 1 I

I 1

В» 4

I т

Ч4!!

I, I

1 еъ

1 ! !

О о 3

l .

l о

I . I

t Ф l

3 ° W

Ь 4

t .

tл

1 л

t I

W о t н н о o. o

W I

t о. н н

1 !

I л

I !

l о о

Ii !

3 !

l..

I W I

g 3

Р Ц

r4 I

l6 1

1,ф" 1!.Ìt

Ц 1

O l

4 t

&I 1

1,! C4

3 Ф

1 Д

I l!

1 .I

ВРюФ 33 Ф

"4 I gI

ЕОРМа оам3к

1 .333аХЦ

Q . о о н о и н о . ю н о ч о о

О.. О О О О О О о о!очи о о о л о ч

О ю е ю о л ч

Ь 3 Ь 3 О л w н !

3 и ю .! О и и н о о н о л.н н н (о л о н о о н н о

Ч. O. О О О!.О О Ь О О

I . t н о н

3 о н о о. н о н н н о о н 4 л о н о о н

3 о .

I (I

1 $3 wp

w.a. o o ! Ж ЭММА

О О О. О Н

960795

I чI.) ! ) «1

° ): ! р!

1II 1 н .Э ббб ..

Ч» В

I . .Вч

Ч !

1 !

Ц 1

R ),! б

1 м

В !

I l.

I, 1 I

I ! 1

1 I 1

) I: I ъ

)ВВ I ао

I !

Ви

-.!. ц

I.В В I .)- I

Ф вЂ” " Ч

I ! . f . I, 4 1 1

:Ч- 1

l I « . ! Ч» В ,l ))б 1.

:I В I 4 Я ф . Ч- I

1 О t

) I I

I 1\Ч 1

1 t.. .I Вч

) ч1 .!

l 1 ,1 I

),!

) .

) . В

t 1 ч-

I 3

1 1 ж

Ч ! тб

I Г

1 . Э О ф I.-Н f )б»-б ааэемо.

eОа э iI

Я Р Э Я ))б Ц

oaf:f." oo» х..ж --.!) f: e В!; ° . I вн )) аВ i О )Э) Я нйж .а:8 0 )

Э М Ф ! 3оеФ ре

ВВВ М

Д »366; ! e 5)В) хе я.". h o )! Н:)) б)) ..В )XI 0$ М

))

)cokeô

Ю Э. )) å -e2R

Я и)» южюефЗ

М аж%); 2 ! ! ! стн е

ОВ.Э, М;g а3 !

" н нам ж oo.o: ,„, еомр, е""". .ц ом: б))

Ю ф g ,1,1 -L 153

t yX f-"N й: йцо

+ ): )) йао аио) р.

ЭЭ > ys

ВВ ж а 0О i O)1)O))e)) у о 0 о) о Оа у а ))". ж у

f I

I Ц

) е !

I М t

t,Ê !! . I!I . 1. I !If 1

;! e., !

If) I н !

0.l .М о

1 I! !

I; f

I»I I

1 Ж

I I

1 Ift ) . З

Ц I о

Я Ц . t

) 1 ВВ) If) I

1 $g 5 но.ue

I -I. l !

) m 1

g !

1! g ) l, Iff I.! 3 !! бб) II) 1 35. !

:но .!.

0Н !

1 Я I

I ОЮ. 1

1 I

I Ю I! Ж

Ц I о

I f I

) I

I Э I

1. L I

1 !

I Ф I и

1 ff I и,I

I Ц о

1 )б) 1. Я

I М

27, 960795 торых .одинакова, соединены Со. Йхода- ментов РАВНОЗНАЧНОСТЬ; соединены со ми одного элемента И-НЕ:и:с:первыми ., входами элемента- ИЛИ-, выход кото-. входамн соответствувщих..элементов И, рого.непосредственно..соединен с прявъорые входы котодас под@лю4эны.к вы- мым, а через элемент"83 вЂ” с ннверсходу. этого элемента: и-не,.выходы :. нъз@и выходамй "блока определения . злеыентав:и:йодкщвч4еНЫ кО Входаы, .. сВОйстВа НесаыоДвОйственнссти. злемейта или., щаход которого непос- . . истачиик

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

Патент 960795