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

(54) УСТРОЙСТВО ДЛЯ РАСПОЗНАВАНИЯ ФУНКЦИОНАЛЬНОЙ ПОЛНОЧИ СИСТЕМ ЛОГИЧЕСКИХ ФУНКЦИЙ

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

Основное требование, предъявляемое при этом к набору логических элементов, состоит в том, чтобы с ег«&..помощью можно было построить любую сколь угодно сложную логическую схему.

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

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

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

15 функцию, не сохраняющую константу нуль, хотя бы одну функцию, не сохраняющую константу единица, хоти бы одну немонотонн-ую функцию, хотя бы одну нелинейную функцию и хотя бы

20 одну неса14одвойственную функцию 2J , .

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

Целью изобретения является создание устройства для распознавания

30 функциональной полноты, с

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

Указанная цель достигается тем, что устройство для распознавания функциональной полнЬзм логических функций содерасит наборное поле из 2 переключате:пей (где п число переменных булевых функций), блок определения свойства не сохранения константы нуль, блок деления свойства не сохранения константы единица, блок опр еделения свойства немонотоиности, блок определения свойства нелинейвости, блок определения свойства .несамодвойственности, дешифратор наборов свойств полноты регистр запоминания наборов свойств полноты, дешифратор базисных групп и блок сборки, причем дешифратор .наборов свойств полноты содержит четырнадцать элементов И, дешифратор базисных групп содержит сорок один элемент И, блок сборки содержит три эл«4ента ИЛИ, прямой выход блока определения свойства не сохранения константы нуль соединен с первыми входами первого, второго, третьего, четвертого, пятого и шестого элементов И дешифратора наборов свойств полноты, инверсный выход блока определения свойства не сохранения констаиты нуль соединен с первыми входами остальных элементов И дешифратора наборов свойств полноты, прямой выход блока определения свойства не сохранен ния константы единица соединен со вторыми входами первого, второго, третьего, седьмого, восьмого и девятого элементов И декшфратора наборов свойств полноты, инверсный выход блока определения свойства не сохранения константы единица соединен со вторшш входами остальных элементов И .дешифратора наборов свойств полноты, прямой выход блока определения свойства немонотонности соединен с третьими входами первого, второго, третьего, четвертого, rpiToro, седьмого, восьмого, десятого, одиннадцатого и двенадцатого элементов И дешифратора наборЬв свойств полноты, третьи входы остальных элементов И которого соеф1нены с инверсным выходом блока определения свойства немонотонности, прямой выход блока определения свойства нелинейности соединен счетвертыми входами первого, второго,- четвертого, седьмого, десятого, одиннадцатого, тринадцатого и четырнадцатого элементов И дешифратора наборов .ювойств полноты, четвертые входы остальных элементов И которого соединены с инверсным выходом блока опреде;11ения свойства нелинейности

прямой выход блока определения сврйства несамодвойственности соединен с пятыми входами первого, четвертого, пятого, шестого, седьмого,

вось1 юго, девятого, десятого и тринадцатого элементов И дешифратора 1)аборов рвойств полноты, пятые входы остальных элементов И которого соединены с инверсным быходом блока сшределения свойства несамодвойственности, шестые входа всех элементов И дешифратора наборов свойств полноты соединены с шиной ввода устройства, а выходы подключены к входам установки в единицу соответствующих тряггерр8 регистра запо « нания наборов СВОЙСТВ полноты, входы установки в нуль которых соединены с 11шной сброса устройства, выход первого триггера регистра запсашнаняя наборов

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

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

первыми входами девя ого, десятого, одиннадцатого, даенадцатого, тринадцатого, четырнадцатого, пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого к

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

первыми входами двадцать , двадцать второго и двадцать третьего элементов И дешифратора . 1$аГз11сных групп, выход пятого триггера регистра запоминания наборов свойств полноты

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

двадцать девятого, «ридцатого тридцать первого и тридцать второго элементов И деЕШ{фратора базисншс , выход шестого триггера регистра запоминания наборов свойств полйоты соединен со вторьо и входами ,

четырнадцатого и восемнадщатого н с первьош входами тридцать третьего, тридцать четвертого, фихщать пятого, тридцать шестого, тридцать седьмого, тридасахь восьмого, тридцать

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

четвертого, десятого, двадцать первого, двадцать четвертого и тридцат третьего элементов И дешифратора ба зисных групп, выход восьмого триггера регистра запоминания наборов свойств полноты соединен со вторыми входами пятого, пятнадцатого , девят надцатого, двадцать второго, двадцать пятого, двадцать шестого, двад цать девятого, тридцатого, тридцать четвертого, тридодать пятого, тридцать шестого и тридцать седьмого элементов И дешифратора базисных групп,, клход девятого триггера регистра запоминания наборов свойств полноты соединен со вторыми входами шестого, шестнадцатого, двадиатого, двадаз ть третьего, двадцать седьмого, двадцать восьмого тридцать перв ого, тридцать второго, тридцать восьмого, тридцать девятого, сороко вого и сорок элементов И де Ш1ф.ратора базиснЁ групп, выход десятого триггера регистра запоминания наборов свойств полноты соединен со вторьвхи входами седьмого и одиннадцатого и третьими входами дв адцать девятого, тридцать первогчэ, тридцать шестого и тридцать восьмого эле ментов И дешифратора базисных групп дмход одиннадцатого триггера регистра эапок нания наборов свойств пол1$ ноты соединен с третьими входами семнадцатого, восемнадцатого девятнадцатого, двадцатого, тридцатого, тридцать В.ТОРОГО, тридцать седьмого и тридцать девятого элементов И дешифратора базисных групп, выход двенадцатого триггера регистра запоминания наборов свойств полноты соединен с третьими входсми сс окового и сорок первого элементов И дешифратора базисных групп, шлход тринадцатого триггера регистра запоминания наборов свойств полноты соединен со вторьми входами восьмого и дв енадцатого, с третьими входами двадцать пятого,.двадцать седьмого и трйдадать четвертого и с четвертым Входом соW KOBoro элементов и дешифратора оазисных Групп, выход четырнаДцатога триггера регистра запоминания наборов свойств поппоты соединен с третьими входам тринадцатого, чет афнадцатого, пятнадцатого, шестйадцатого двадцать шестого, двадцать восьмого и тридцать пятого и четвертым входом соЕюк первого элементЬв И дешифратора базисных групп, выхода Первого, второго, третьего, чётвертого. Пятого, шестого, седьмого ,- восьмого, девятого, десятого, :одиннадцатрго, двенадцатого, двад%ать первого. Двадцать второго, двад .ать третьего, двадцать четвертого И Т1 иДцать третьего элементов И де|Шифратора базисных групп соединены со входами первого элемента ИЛИ блока сборки, выход которого подключен ко вторсяяу выходу устройства, выходы тринадцатого, четырнадцатого,пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого, двадцатого, двадцать, пятого, двадгцать шестого, двадцать седьмого, двадцать восьмого, двадцать девято го, тридцатого, тридцать первого, тридцать второго, тридцать четвбртого, тридцать пятого, тридцать шестого, тридцать седьмого, тридцать восьмого и тридцать девятого элементов И дешифратора базисных групп соединены со входами второго элемента ИЛИ блока сборки выход которого . соединен с третьим выходом устройства, выходы сорокового и сорок первого элементов И дешифратора базисных групп соединены со входами третьего элемента ИЛИ блока сборки, выход которого подключен к четвертому выхо- ду устройства, блок определения свойства несохранения константы нуль содержит элемент НЕ, вход которого соединен с прямшл выходом этого блока и с выходом первого переключателя наборного Поля, а выход является инверсным выходом блока определения свойств нёсохранения константы нуль, блок определения свойств несохранения константы единица содержит эле- . мент НЕ, вход которого соединён с инверсным выходом этого блока и выходом последнего переключателя наборного поля, а выход является пряМым выходом блока определения свойства несохранения константы единица, блок определения свойства немонотонИости содержит п-2 элементов ЗАПРЕТ, элемент ИЛЬ и элемент НЕ, причем входы каждохчэ элемента ЗАПРЕТ соединены с выходами тех двух переключателей наборного поля, двоичные номера которых отличаются только в одном разряде, причем запрещающие входы элементов ЗАПРЕТ сое- , динены с выходами переключателей наборного поля, имеющих больший номер;, выходы элементов ЗАПРЕТ соединены сО входами элемента ИЛИ, выход которого непосредственно соединен с прямым, а через элемент НЕ - с инверсными выходёми блока определения свойства немонотонности, блок определения свойства нелинейности содержит п-З элементов РАВ НОЗНАЧНОСТЬ, п элементов П2 элвлен тов И, элемент ИЛИ и элемент НЕ, входы каждого элемента РАВНО- . ЗНАЧНрСТЬ соединены с выходами тех двух .переключателей наборного поля, двоичные номера которых отличаются только в одном разряде, выходы элементов РАВНОЗНАЧНОСТЬ, соединенных входами с выходами переклюЧателей наборного поля, разность номеров которых одинакова, соединены сю входами одного эламента И-НЕ и с пе выми входами Соо.твехствующих элемен тов И вторые входы которых подключен : к ВЫХОДУ этого элемента И-НЕ , выхода элементов И подключены ко входам элемента ИЛИ, выход котррого непосредственно ос Динён с лрякйлм, а через элемент НЕ - с инверсными 8хрда 4и блока определения свойства нелинейности, блох оп:ределения свойства нёсамодвойственности содержит . элементов РАВНОЗНАЧНОСТЬ, элемент ИШ и НЕ, пр чем входы каждохх элемента РАВНОЗНАЧНОСТЬ соединены с выходами тех двух переключателей наборного.поля, сумма нбмеров Которых равна 2 - 1, выходы элементов РАВНОЗНАЧНОСТЬ сое данейы со входами элеменэ а ИЛИ/ выг ход которого непосредственно соединен с прямым, а через элемент НЕ инверсн 04и входами блока определения свойства несгимодвойственности. При таком построений устройства реализуется критерий неиэбыточной полноты, при котором для каждой булеври функции из заданной системы вйделяготся и запоминаются Не просто свойства полноты,у.как это делается в известном устройстве, а так наэы ваекыё наборы свойств полноты, и далее проверяется наличие не прОсто всех СВОЙСТВ полноты, а так/называе мах. базисных групп наборов свойств . полноты, что позволяет непосредстве но выявлять неизбыточные ;функциональ но-пОлные системы булевых.функций Назовем каждое из указанных В теореме о. полноте Поста пяти свойств булевых фнукций Tile, первое свойств(э - не сохранять константу нуль ,(Ко) , второе -- не сохранять константу единица(К), третье - быть немонотонной (М) четвертое - «йдагь н линейной (И) и пятое - быть несамодвойственной (С) - свойством Полно- ты., . , . / . .- -.. ;, Обозначим-цифрой О случай, когда Нул вая функция обладает данным свойством полноты, ц цифрой 1/ если не риладает им. Тогда, очевидно, можно составить 32 различных иабо1за свойств полноты. Каждый такой яабОр будем рассматривать как двоичную эайись , являюхоегося номером набора, расположив: на боры Дпя Удо 5ства свер ху вниз в естественном- пОрядрсе, соОтветотвуюц(ем расположению чИеел от О до 31, -кщ- это указано В tat&n 1« не существует булекахфун1««1Й облэьдающих -наборами свойстзв полноты с номерами: 2, 4 5, -б, 7, 9t 11 12, la, 15, 17, 19, 20, 21, 23, 26 и-30. . , , . . .. .- : Для доказательства этого утвбрждения разобьем указанные наборына следующие группы: 1) э, 11, 13, 15; 2) 17, 19, 21, 23г 3) 4, 5, 6, 7; 4) 12; 5) 20; 6) 2; 7) 26 и 30. Докажем отдельно для каждой .указанной трупгил, что в алгебре логи ки не сугсвеОтвует функций, обладающих сочетанием свойств полноты, соответствующим этой группе, К первой группе наборов свойств полноты Относятся булевы-, .функции, : одновр енно не сохраняющие константу нуль, сохрайя101цие константу единица и являющиеся самодвойственны мй.. :.-. : ,,/, /, . ,; ,; V ; ; Если булева функции f(x,,.,., х„) не соэфаняет кОнстанту нуль, то f (О,...,0) 1 .Если булева функция f (х,...,х„) сохраняет константу единица, то f {1...,1) 1. Если булева функция является самодвойствеинОй, то на любых двух противоположных наборах она принимает противоположные значения. Поскольку наборы Все и Все являются пр6тивополож:ныьш, а З11ачения функции на этих наборах одинаковы (равны I), то условие самадвойственности При выполнении условНй не сохранения константы нуль и сохранения константы единица не може выполнено, что и доказыва.ет приведенное утверждение Для случая первой группы наборов свойств полноты. Аналогично приведенное утверждение доказывается и для всех остальных случаев, : .-:.,. , : Таким образом, булёиа Функции ioгут обладать только 15-ю наборами . свойств полноты, имеюкрми О, 1, 3, 8,10, 14/16, 18, 22, 24, 25, 27, 28, 29 и 31V Группу наборов свойств полноты; удовлетворяк 11 ю к ;щтёрию, функйиональной полноты, ндзовем полной Г1 уппой наборов свойств ПОЛНОЙ i / группа наборов свойств полноты удовлетворяет полноты .в том случае, сли булввы фуйкх йи, обладающие наборволи (СВОЙСТВ noJiHOTibiг составляющи. эту грйшуу образок фувкционалынр-полну систе 1у булевытл. функций.;;/,/. .: ...;.,:.,;-::,.,;: .-:, Для тогч, чтЬбы rpsrtifaa наборов свойств полноты была полной группой наборов йеОбхоАимо и J cTato HO,4Toefei нули в двоичных номерах наборов группы соймертнО дервкры- ; Вали все пять позйци ;,; cObifBeTCTByib-ВДЙС СВОЙСТВаМ;ДОЛНОТЫ.л. f ,.. V : , . ., Неизбыточну полную rpyniiy наборов СВОЙСТВ полноты назовём базнсНОЙ-. , ;.;..:;:,:;.. . : ШеизбытОчндЯ полная fpyftna наборов свойств полноты характерйзуетоя тем, что нули в двоичных номерах наборов группы совместно перекрывают все пять позиций, соответствующих свойствам полноты/ однако из такой /группы нельзя исключить ни ,одного набора свойств полноты без того, чтобы не было нарушено это I свойство.

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

Приведем все возможные базисные группы наборов свойств полноты: О, 1, 8; 1, 10; 1, 14 1, 16; 1, Д8; 1, .22; 1, 24; 1, 28|, 3, 8,- 3, 3f 24; «,3, 28; 8, 16; 8, 18; 8, 22 10,16; 14, 16; 3, 10, 29; 3,, 14, 29 3, 18, 29; 3, 22, 29; 10, 18, 28; 10, 18, 29; 14, 18, 28; 14, 18, 29; 10, 22, 28; 10, 22, 29; 3, 10, 25; а, 14, 25; 3, 18, 25; 3, 22, 25; 10, 18, 24; 10, 22, 24; 10, 22, 5; 14, 18, 24; 14, 18, 25; 14, 22, 24; 14, 22, 25;14, 22, 27, 28; 14, 22, 27, 29; Ю, 18, 25.

Анализ полученных базисных групп поз гол4ет сделать следушсие, выводы: а алгебре логики имеете;; всего одиа базисная группа наборов свойств полноты, состоящая из одйого набора, семнадцать базисных rpyijn - на двух наборов, двадцать две б«13|1 :ные группы - из трех наборови две.базисные группы из четырех н«бороа свойств полноты.

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

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

На фиг.1 и 2 представлена c.Tpyteтурная cx&ta устройства; на фиг.3 Нзшолнение наборного поля и блоков определения свойства несбхранен константы нуль, опр&деле1шя свОйства несохранения константы едияИг да, свойства немонотонности/ свдй- ст&а нелинейности, свайст1за иесамодвойственности для случая Ks2.

Устройство содержит наборное поле 1, содержащее, например, для случая И-2 пере лючатели 2{j, 2., 22, 2j, дешифратор 3 наборов свойств полноты, регистр 4 загнмшнания свойств полноты, шину 5 вво- . да, шину б сброса, блок 7 определения СВОЙСТВ несохранения константы

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

5 , На фиг.2 показан также не входящий в состав устройства блок 86 индикации с элементами 87 - 90 индикации.

На переключатели 2 наборного поля 1 по шинам 91 и 92 подаются логические константы О и . В зависимости от положения переключателей 2 эти сигналы по пшнам 93 96 подаются на входы блоков 7-11.

5 Блок 7 содержит элемент НЕ 97 и на своих прямом и инверсном выходах формирует сигналы, поступающие по леи нам 98 и 99 на входы, дешифратора 3 Блок 8 содержит элемент НЕ 100

0 и на своих прямом и инверсно и выходах формирует сигналы, поступающие по шинам 101 и 102 на входа дешифратора 3. Блок 9 содержит элементы ЗАПРЕТ 103 Юб, элемент ИЛИ

с 107, элемент НЕ 108 и Формирует на своих прямом и инверсном выходах сиг{1а ш, поступающие по шинам 109 и 110 на входы дааифратора 3. Блок 10 содержит элементы РАВНОЗНАЧНОСТЬ 1111J4, элементы И-НЕ 115 и 116, элементы И 117 - 120, элемент ИЛИ 121, элемент НЕ 122 и формирует на своих пряь« м и инверсном выходах сигналы поступающие по шинам 123 и 124 на . входы дешифратора 3. Блок 11 содар5 жит эл««яты РАВНОЗНАЧНОСТЬ 125 и 126, элемент ИЛИ 127, элемент НЕ 128 и формирует аа своих прямом и инверснс выходахсигналы, поступающие яо шинам 129 и 130 на входы дешифратора 3. Входа дешифратора 3 соединены со уходами регистра 4, выход ijepBoro триггера 26 которого является выходом устройства и шиной .131 соединен с элементом 89 индикации. Выходы остальных триггеров 27 - 39 регистра 4 шинами 132 - , 144 соединены со входами дешифратора 81,. шоходы элементов И 40-80 которого соединены со входами элеменg тов ИЛИ 83 - 85 блока 82, входы которых являются выходами устройства И соединены со входагли элементов 87190 индикации.

)- :Уст йство работает следующим 65об разом. Каждая 0улева функцця из задан йой систе последовательно одна за другой зг1дается с поыюсцью 2 двухйОзиционШх переключателей 2 наборКого поля 1 Сп - максимально возможное число переменных анализируемых булевых функций), через которые в блоки 7 - 11 подаются сигналы лов зависягическогомости от полсжения переключателей 2. Используя информацию о состояния переключателей 2 наборного поли 1, блоки 7 - 11, представляювдие собой комбинационные Логические схемы, вы ра1батывают на своих .выходах пять ср ответств щнх оулешйх функций Значение функции несохранения константы нуль равно единице, если переключатель 2 с нсялером О, CCJOTдетствуЮщий набору булевой функции Все О установлен в положение 1, и равно нулю, если этот пе. реключатель установлен в -положение «О П.(2) Значение функции несохранения /константы единица равно единице, если переключатель 2 с номером 2 -1, соответствующий набору булевой функции Все 1, установлен в положение и равно нулю, если этот переключатель установлен в положенне i М УП|: где 1 и j - номера соседних наборов Значение функции немонотонности равно едяняа е, если найдется хотя 6iJi одна парапереключателей 2, соотВеТетвуюпшх соседним (склеиваюшмся) наборам и установленных в тфотивополоя ные положения, причем в такие, когда переключатель с номеро в котором склеиваю1((аяся переменная равна нулю, установлен в положение , и равно нулю в противном случае. В формуле (3) операция У б рется по всем соседних наборов jf Vn -v-nj, (4) где i и номера наборов, соседних по существенной пер менной . Значение функции нелинейности ра йо единице, если найдется хотя бы о 4ia пара переключателей 2, соответствующих соседним по существенной пёрекюнной наборам и установленных в одинаковое положение, и равно нул в противном случае. В формуле- (4). . операция V берется по всем парам соседних наборов, fC V , (5) где 1-+ j 2 - U Значение функ1хии ; несамодвойствен иости равно единице, если найдется хотя бы одна пара переключателей 2, соответствующих противоположным наборам и установленных в одинаковое положение, и равно нулю в противном случае. В формуле С5) операцияv берется по всем 2 парам противоположных наборов. В ормулс1Х (1) - (5) V - логическая операция ИЛИ; л. - логическая операция РАВНОЗНАЧНОСТЬ;- логическая операция ЗАПРЕТ логическая операция НЕ. Наборное поле 1 содержит 2 переключателей 2, занумерованшлх так, что двоичные их номера совпадают с соответствуюгцими наборами логических функций п переменных. Все первые переключаемые контакты переключателей 2 наборного поля I соединены с оганой 91 логического нудя, все вторые - с шиной 92 лощческой единиt@3i, переключакмяне контакты соединею со входами блоков - 11. Влок 7 определения свойства несохранения константы нуль представляет сюбой повторитель сигнала (проводник) , соединяюищЛ переключатель 2 с номером О, с прямш4 выходом блока 7f на котором реализуется логическая функция 1) fICQ. Для получения инверсного в)яхода блока 7 используется элем&ну RB 97. Влок 8 определения свойства иесохранения {Константы единица представляет собой элемент.НЕ 100, вход которого соединен с переключателем 2, имеинфм ifl номер 2 - 1, на шисоде которого реализуется логическая фуикш1в (2) ; fR, .и этот выход является прямым выходом блока 8. я получения инверсного выхода И я1оль9ует1;я значение- функции на входе элемен.та ,НВ 100. Бл(Ж 9 определения свойства немонотонности представляет собой п-2 .двухвходовшс элементов ЗАПРЕТ 103 1б6, входы каждого из коToi ix соединены с переключателями 2, двоичшяе номера которшс отличаются только в одном разряде, при этом запрещаю 19 е входда соедаанены с переключателями 2/ имеющими болъаялй номер, а жгходы соедииейы с входами ПЗ входо ого элетлента ИЛИ. 107, на кяходе которого рееитизуется логическая функЕШЯ (3) и, и этот выход является выходом блока 9. Лля получения инверсного выхода используется НЕ 108. Блок 11 определения свойства нет. линейности представляет собой . двухвходовых элементов РАВНОЗНАЧОСТЬ 111 - 114, П. входовых эле ентов И-НЕ 115 - 116, двухвходошдх элементов И 117 . 1гОи входовой элемент ИЛИ 121,1 один п« 2 при этом входа каждого из элементов РАВНОЗНАЧНОСТЬ 111 - 114 соедийены с переключателями 2, двоичные номера которых отличгиотся только в разряде, выхода элементов РАВНОЗНАЧНОСТЬ 111 - 114, соединенных своими входаьв с пepeключaтeля вI 2 наборного поля 1, разность номеров между которыми одинакова, соединены с входами одного и того же элемента И-НЕ 115, 116, а также с :iiepвыми входами соответствующих элементов 117 - 120, вход KOTolMox подключены к выходу этого Элемента И-КЕ 115-116, выходы элементов И 117 - 120 соединены с входами элемента ИЛИ 121, на выходе которого реализуется логическая/ : функция (4) fЛ и этот вы:ход является п)ямым выходом блока: 10 . Для получения инверсного выхода используется элемент:-йЕ:1, ;/.: V:.;. блок 11 Определения свойств,а несамодаойственности представляет соn-t

2

двухвходоаых элементов РАвНОЗВАЧНОСТЬ 125 И 126, кйждого из которых соедане ны с перекл, 2, cyMvia номеров к6тр|ар

равйа 2 1 а выходы соёданена с вхЬдамй вхоаового элемента ИЛИ 117, выход которого являемся прямам выхрдЬм блока 11 реадиэ щего функцию (5) f. Для получения sepcHoro выхода испрльзуё тся эле- мен-э .ИЙ-; 1.2:8i;-, , :;, .-.,-. ., , :На выходах блоков 7 - 11 образу чается двоичный пятиразряднкй пот«нг циайьный .код набора, сйойств полноты, ко го1«лм облагает набранная б лёяа функций. .Оешифратор 3 н аборрв чзройств полноты, представляюиЫй собой комбинадиойнзгтр логическу схему из четырнадцати (дестивходов ах элементов И 12 - 2.5, рсУйествляе преобразование каждого ИЗ пятнадцати

возможных кодов наборов СВОЙСТВ ПОЛноты в ОигНалы установок в;ёлщнту триггеров 26 - 39 регистр а 4i

Установка в единицу трирре| эй 26 39 регистра. 4, для которых выработай сигйсШ установки в /единицу |яроисходит по команде ввода (например; пут кратковременного нажатия кнопки ввода и полачи управляаб«1Е ГО сиг нала по шине;5 ввода). , : CHrHajQii с триггеров 26 - ,39 с пОМощью дёи1Ифрато1 а .81 базисных Групп, представляющего собой элементы JR 40 86, соответствующие всём ВозможНЕф) в алгебре логики базисньвй( группа . наборов свойств полноты, прёОбраз1а тся в сорок два сигнала, которые яатем группируются в четыре сигнала по числу наборов в базисных rpynnittc с помощью элементов ИЛИ 83-85 ФО рмирования выходных сигналов устройства, которые осуществляют включение четырех элементов 87 - 90 индикации блока 86 индикации.

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

а) После аналиэа всех булевых

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

б) После анализа всех булевых функций из заданной системы включены или несколько элетлентов индикации блока 86 индикации, или только один элемент индикации, сОответствуюififiu базисным группам, число наборов свойств полноты в KOTOF«3ix меньше числа анализируе ушрс булевых функций в системе. Это говорит о том, что анализируетлая система логических

Функций полна и избыточна.

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

базисной..

После окончания работы триггеры 26 - 39 регистра 4 могут быть устаНовл1ены в исходное состояние (обнулены) по команде сброса, Шапри

мер Я1утемкратковр1еменНогО нажатии кнопки сброса и подачи управляющего . сигнала пО йинё 6 сброса) .

Рассмотрим работу устройства на следующих четырехконкретных примераз

приведенных S табл. 2.

П р им ер 1. С помощью таблиц истинности зада1на система из четырех логических ФУНКЦИЙ от трёх переменных f, f, f и 4 Определить, является ли она избыточной, 6a3 HCKc HjrBt неполной.

Иабираем функцию fvj установкой переключателей 2, 2, 2,,, 24 наборного поля 1 в положение ,

остальные переключатели устанавлиТак как певаем в положение

рёкдсэчатель 2(, наборного поля 1 устаиОвлен в положение , то К0 б. Так как переключатель 2, te наборного поля 1 установлен в положение то fK в i, хак как переключатели 2 и 25 наборного поля, соответстаующие склеивакнцимся наборам установлены в противоположные положения, причем переключатель , соответствующий набору, в котором склеивающаяся буква равна О , установлен в положение 1 то fii i. Так как пе еключатели р и 2з наборного поля, соответс вуюзие наборам с четным числом единиц, установлены в Противоположные положения, тс. Л ° 1 ак как переключатели 2 о и 2 наборного поля 1, соответствуювре проти воположньви наборам, установлены в одинаковое положение,.то f5« 1.

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

с помоЬ(ью 9л&лен1Л И 18 дзшфратора 3 наборов свойств, полноты двоичнь1|й код 10000 преобразуется в сигнал установки в единицу триггера- 32 регистра 4, соответствуяздего набору свойств полноты с десятичным номером . Установка в единицу этого триггера происходит/по команде ввода. .. I.- ... .,/ ,:

Так как не существует базисной группы, состоя1цей из одного набора с номером 16, то на выходах дешифратора 81 базисных групп и блока 82 сборки вырабатывается сигнал О и остаются не включенныкш все четыре элемента 87 - 90 индикации блока

- : : . :

О

ОО

О

О

О

О

О

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

Аналогично; после набора и ввода информации об остальных функциях,, f2 f3 и 4, оказываются установ- . ;ленн1А|И в единицу триггеры 29, 38: и 39, соответствующие наборам свойств полноты с ншер1ами 18, 28 и 29. Однако на Щ1хооах 2(е111ифратора 81 базисных групп блока 86 сборки попрежнему В1Ы{ 4батывается сигнал О и остаются не включенными все элемейта 87 - 90 индикации, так как не сущед вует базисных групп, состоящих из всех или части указанных наборов. таким образом, можно сделать вывод О , что система булевых функи ийдяя данного npHiv pa не полна. АйалоЙ1чНо осуществляется работа устройства и в случае приме1ЮВ 2 - 4 ((й1м табл. 2) .

Данное устройство почти полностью состоит из комбинационных схем/ лоэтому ойо имеет высокое бысгррдей, ствие и прост5«о структуру, сложность которой не зависит от чИ)ЕУ1а переменных анализируёмьЬс булевых функций (за исключением конструкции на рното поля 1 и блоков 7 - 11). Действия оператора максимально облегчены н сводятся к п остейшим операциям По набору заданных булеш:1х функций и пользованию кнопка1иидвода и сброса. Данное устройство позволяет различить не только функционально полные,

5 но и базисные системы логических, функций, т.е. производить довольно тонкий анализ свойств систем булеШ11Х функций, необходимый в ряде схпучаев при создании оптимальных С.ТРУКТУР

0 интегральных-субсистем.

Таблица 1

Не возможен

Не возможен То же

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

о о о

о но о

о - ...

О О О о о о о о

1-4 гЧ

О гН о Н о

Н - о -Ч о Н о о

О «-1 . о ,

о о о ,н о

о iH

о - о

X. . .Н -И

О о. О

о о «-1

;в мЧ А

о

,%

о -« Hi

Н М П «) 1Л 0 го н н н

о |-« г-1

он н

е н н о н

о н н н о

о о

о. о о о

гч о

.о о о- о о

-I гЧ

о н

о а; н

о гЦ

1-Г о - о

о но о

1-4 Н 1-1

о н -« но

н -«Э . (

о . г- -

н н

о о

о н о о

о о

о 00

о о о о

А Ш

о о

g

1в «: ж

III

Я Формула изобретения Устройство для распознавания фун чиональной полноты систем логически функций, о т л и ч а ю ад е ее я тем TQf 6 целью упрощения процесса выявления базисзиых систем логических функций, устройство содержит наборное поле из переключателей (где п - число перемейнмх булевых функций) , блок определениям свойств не сохранения койстанты нул блок определения свойств а йе coxpiaH нйя константы единица, блок определ ния свойства немонотоинос-Ги, блок определения свойства нелинейнос и/ блок определения свойства Hecavipдвойственности, девшфратрр набрроё свойств .полноты, регистр эапомииания набЬров свойстве полноты, дешйф ратор базисных групп н блок ёборки, причем дешифратор наборов сйойств ПОЛНОТЫ: содержит четыриадцазсь элементов И, деЕаиФ1)атор1 баэиснах групп содержит сорок один элемент И, блок сборки содержит три элемента ЙЯИ прямой выход блока определежия.свой ства не сохранения констан1;ы нуль соединен с перззьош первого, второ1 о, третьего, четвертого/ йятого и шестого элементов И дешифратора наборов свойств полноты инверснЁнй выход блока определения свойства не сохранения константы нуль сйедииен с первыми входами остальных элементов И дешифратора наборов свойств полноты, прямой выход блока определения свойства не сохра нения константы единица соединен со вторыми входами первого второго третьего, седьмого, восьмого и девя того элементов И дешифратора наборов евдйст в полноты, инверсный выход блока определения свойства не сохранения константы соединен со вторыми входами ос альник элементов И дешифратора наборов свойств полнотгы, прямой выход блока определения свойства немонотонности соединен с третьими входами перв го/второго, третьего, четвертого, пятого, седьмого, восьмого, десятого, оданнадцатоГо и двенадцатого алементов И дешифратора наборов свойств полноты, третьи взсоды осi-альных элементов И которого соедипены с инверсным выходом блока опре деления свойства Иемонотонности, пр мой выход блока определения свойства нелинейности соединен с четверты ми входами первого, второго, 4етвер того, седьмого, десятого, одиннадцатого, тринадцатогоiи четырнадцатого элементов И дешифратора наборо свойств полноты,, четвертые входы ос тальных элементов И которого соединены Ь инверсным выходом блока.определения свойства нелинейностиi прямой выход блока определё Ьия свойства несамодвойственности соединен с пятыми входами первого, четвертого, пятого, шестого, седьмого, восьмого, .девятого, десятого и тринадцатого элементов И дешифратора наборов свойств полноты, пятые входы остальных элементов И которого соединены с инверснш выходом блока определения свойства несамодвойственности, шестые 9сех элементов И дешифратора наборов свойств полноты соединены с шиной ввода устройства, а выходы подклочены к входам установки ц единицу соответ твукидах триггеров регистра запоминания наборов свойсФв пол -готы, входы установки в нуль которых соединены с шиной сброса устройства, выход первого ТЕ«Г.гера регистра запоминания наборов {свойств полноты соединен с первым выходом устройства, шлход второго триггера регистра запоминания наборов свойств полноты соединен с первыми входалш первого, второго, третьего, четвертогог пятого, шестого, седьмого и восьмого элементов И дешифратора базисных групп, выкод третьего т$ч|ггера регистра запоминания наборов свойств полноты соединен с первыми входси«и девятого/ десятого, одиннадцатого, двенадцатого, тринадцатого, четырнадцатого, пятнадцатого, пюстнадцатого, семнадцатого, восемнадцатого, девятнадцатого и двадцатого .элементов И дешифратора базкснызс групп, выход четвертого триггера регистра запоминания наборов свойств полноты соединен со вторыкш входами первого и девятого и с первыкш входами двадцать пер вохх), два;Ещать второго и двадцать третьего эле(ейтов И хвзшифратора базисных групп, выход Питого триггера регистра запоминания наборов свойств полноты соединен, со вторыш входами йтррого, тринадцатого и сш 4надцатого и nepKiMil входакш двадцать четвертого двадцать пятого, двадцать шее- того, двсцщать седьмого, двадцать восьмого, двадцать девятого, тридцатого, тридцать первого и тридцать второго элементов И дашовфратора базисных групп, выход шестого триггера регистра запоминания наборов свойств полноты соединен со вторыми входами третьего четырнадцатого« и восемнадцатого и с перкдаед входами тридцать третьегд, тридцать четвертого, тридцать пятого, тгждцйть шестого, тридцать седьмого, тридцать восьмого, тридцать девятого, сорокового и сорокпервого элементов И дешифраТоргГ б«1ЭИсных групп, выход седьмого триггера регистра запсшинания наборов свойств полноты соединен со вторыми входами четвертого, десятого, двадцать первого, двадцать четвертого и, тридцать третьего элементов И дешифратора базис ных групп, выход восьмого триггера регистра запоминания наборов свойств полноты соединен со вторыми входами пятого, пятнадцатого, девятнадцатого г двадцать второго, двадцать пятого, двадцать шестого, двадцать девятого, тридцатого, триоиать четBeptoro, тридцать пятого, тридцать шестого и тридцать седьмого элементов И дешифратора базисных групп, выход девятого триггера регистра запоминания наборов. свойств полногги соединен со вторыми входами шестого, шестйадцатого, двадцатого, двадцать третьего, двадцать седьмого, двадцать восьмого, трида ать первого, тридцать второго, тридцать восьмого тридцать девятдго сорокового к сорок первого элементов И детиифратора баэисн групп, выход десят ого триггера регистра запоминания наборов свойств полноты соелннен со вто fosom входами седьмого и однннадцатого и третьими входаьет двадцать девятого, тридцать первого, тридцать шестого и тридцать восьмого эле ментов И дешифратора базисных групп выход одиннадцатого триггера perHC-i pa запсмимнания наборов рвойств полноты соединен с третьими входами семнадцатого, восемнадцатого , девятнадцатого, двадцатого, тридалато го, тридцать второго, тридцать седьмого и тридцать девятого эдхементов И дешифраторам базисных групп, выход двенадцатого триггера регистра запом нания свойств полноты соединен с третьими входами сорокового и сорок первого элементов И детяифратора.базисных групп, выход тринадцатого Tfmrrepa регистра запоминания наборов СВОЙСТВ полноты соединен со вторьоли входами восьмого и двенгщцатого, с третьими входа ш двадхшть пятого, двёщцать седьмого и тридцать четвертого и с четвертым входом сорокового элементов .И дешифратора базисных групп, выход четырнадцатого триггера регистра запоминания наборов свойств полнот ы соединен с третьими входами тринадцатого четырнад цатого, пятнадцатого, шестнадцатого двадцать шестога, двадцать воеьмо чЭ и тридцать пятого и четвертым входом сорок первого элементов и даииф. ратора базисных групп, выходи первого, второго, третьего, четвертого пятого, шестого, седьмого, восьмого девятого, десятого, одиннадаатого, двенадцатого, двадцать перббго, двадцать.второго, двадцать третьего двадцать четвертого и тридцать тре тьего элементов И дешифратора базйсных групп соеди нены со входами пёрг вого элемента ИЛИ блока сборки, выход которого подключен ко второму выходу устройства, выходы тринадцатого, четырнадцатого, пятнадцатого г шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого, двад цатого, двадцать пятого, двадцать шестого, двадцать седьмого, двадцать восьмого, двадцать девятого, тридцатого, .тридцать первого, тридцать бторрго, тридцать четвертого,, тридцать пятого, тридщать шестого, тридцать седьмого, тридцать восьмого и тридцать девятого элементов И дешифратора базисных групп соединены со входами второго элемента И1М блока сборки, шлход которого соединен с третьим выходом устройства, выходы сорокового и сорок первого элементов И дешифратора базисных групп соединены со входами третьего элемента ИЛИ блока сборки, выход которого подключен к четвертому вйходу устройства, блок определения свойства гесохранения константы нуль содержит элемент НЕ, вход которого соединен с прямым выходом этого блока и с выходом первого переключателя наборного поля, а выход является инверсным выходсм блока определения свойства несохранения константы нуль, лок определения свойства несохранения константы единица содержит элемент НЕ, вход которого соединен с инверсным выходом этого блока и выходо л последнего переключателя наборного поля, а выход является пряъФдм выходом блока определения свойства несохранения константы единица, блок определения свойства немонотонности содержит элементов ЗАПРБТ, элемент ИЛИ и элемент НБ, причем входы каждого ЗАПРЕТ соединены с вы одс1ми тех двух переключателей наборного поля, двоичные номера которых отличаются только в одном разряде, запрещающие входы элементов ЗАПРЕТ соединены с выходами переключателей наборного поля, имеющих больший номер, выхоф эл дентов ЗАПРЕТ соединены совходами элемента ИЛИ, которого непосредственно соединен с прямым, а.через элемент НЕ - с инверсными кйсодами блока опредё. t ления свойства немонотонности, блок.-. определени } свойства нелинейности содержит п-З элементов РАВНОЭНАЧ.НОСТЬ, и элементов И-НЕ, элементов И, элемент ИЛИ и элемент НЕ, причш« входы каждого элемента РАВНО:311А 1НОСГЬ соединены с выходами тех 31№ух переключателей наборного поля, 1двои1 8ае номера, которых отличаются |только IB одном разрял е, выходы элеiMeHTOB РАВНОЗНАЧНОСТЬ, соединенных входаМ11 с вь1ходами переключателей наборного поля, разность номеров которых одинакова, соединены со входами одного элемента И-ИВ и с левыми входами соответствующ11Х 9П&4(я1тоз И, вторые входы котор пс поркто тя к выходу этого элемента И-Я,выходы .. але «ентов И подклвпсенм ко входам элемента или, выход которого редственно соединен с тфякаи, а через элемент НЕ - с инверсными шкодами блока определениясвойства нелинейности, блок определения свойства несамодвойствеяности содержит элементов РАВЯОЗН&ШЮСТЬ, элеKteHT ИЛИ и длемент НЕ, причем вх&ды каждого элемента РАВНОЗНАЧНОСТЬ;соединены с выходами тех двух переклю.чателей наборного поля, сумма номе2ti i

выходы элеров которых равна

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

Источники информации, принятые во внимание при.экспертизе

S3

S7