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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическикРеспублик и 960795(22) Заявлено210579 (21) 2769578/18-24с присоединением заявки Й 9(23) Приоритет И) М. Кп. С 06 Р 7/00 Государственный комитет СССР по делам изобретений и открытийОпубликовано 23.09.82. Бюллетень Мо 35 Дата опубликования описания 23.09,82(54) УСТРОЙСТВО ДЛЯ РАСПОЗНАВАНИЯ ФУНКЦИОНАЛЬН ПОЛНОТЫ СИСТЕМ ЛОГИЧЕСКИХ ФУНКЦИЙ ь- ст н о о Изобретение относится к вычислительной технике и может быть испол зовано при синтезе цифровых устрой вИзвестно, что одной из важных, задач синтеза логических устройств является выбор типов элементов, из которых должны собираться логические схемы ( Ц .Основное требование, предъявляемое при этом к набору логических элементов, состоит в том, чтобы с егб,помощью можно было построить любую сколь угодно сложную логическую схему.Поскольку существует взаимно-однозначное соответствие между законами функционирования логических элементов и логическими Функциями, То техническая задача определения набора логических элементов, с помощью которых можно построить любую логическую схему, сводится к математической задаче отыскания функционально-полного набора булевых функций. При этом для синтеза оптимальных цифровых устройств среди огромного, множества систем логических Функций приходится выбирать функциональноп лные системы, удовлетворяющие нек торым критериям оптимальности. В частности существенными достоин/ствами при синтезе об тадают неизбыточные (базисные) системы булевыхфункций, представляющие также большой теоретический интерес как системы образующих алгебры логики,Задача распознавания функциональ"ной полноты систем логических,функций до сих пор решалась, по существу, вручную, на основании теоремы Поста: для того, чтобы система булевых функций была функционально-полной, необходимо и достаточно,чтобы она содержала хотя бы однуфункцию, не сохраняющую константууль, хотя бы одну функцию, несохраняющую константу единица, хотябы одну немонотонную функцию, хотябы одну нелинейную функцию и хотя быодну несамодвойственную функцию 2),Учитывая тот факт, что существу- ,ет бесконечное множество функционально-полных систем булевых Функций (3),а также трудоемкость операций повыявлению свойств полноты, было быжелательно автоматизировать процессрешения указанной задачи.Целью изобретения является созда"ние устройства для распознавания ЗО функциональной полноты, с помошьюЗ 1 16, Ф;1 аоа ННКЦЕНам ЦО 1 0 ВОМЮИнания наборов свойств полйоты СоеДМ-.иен с третьйми входами сорокового и 4 О соединен со вторыми входами четвертого, десятого, двадцать первого,двадцать четвертого и тридцать третьего элементов И дешифратора базисных групп, выход .восьмога.триггера регистра заноминания.наборов свойств5 полноты соединен со вторыми входами пятого, пятнадцатого, девятнадцато". го, двадцать второго, двадцать пя-. того, двадцать шестого,: двадцать девяткой Ь., тридцатого, трщщать:чет:- .О верного, тридцать.пятого, тридцать. . шестого и тридцать седьмого.элемен- тов И дешиФратора базисных групп, . выход девятоготриггера регистра "за.поминания: наборов. свойств.полноты, соединен со вторник входайи.шесто-, го, шестнадцатого, двадцатого, двад-.; цать третьего, двадцать седьмого, двадцать восьмого, .тридцать первого, тридцать второго, тридцать восьмого, .2 О тридцать девятого, сорокового,к сорок первого элеиейтов .И: дешкфрагора базиснЫх групп, выхоД деся"Гого триггера регистра запоминания вабо:" ров .свойств. полноты соейннен со вторьвщ входами седьмого и одиннадца-, того и третьими. входами двадцдть девятого, тридцать первого,: трид цать шестого и. тридцать, восьмого эле- ментов И дешиФратора базисных групп,. выход. одиннадцатого триггерарегисМф ЗО ра Запоминания наборов .свойств.пол- . ноты соединенс третьими Входамй: жмнадцатога, восеийадцатого, Щ- вятнадцатого, двадцатого,. трйдцато го, тридцать второго., тридцать седь мого и тридцать девятого элементов И дешиФратора базисных:групп,: выход . двенадцатого триггера регистра запомисорок первого.элементов:И дешифратора;базисныхгруПп, .выход тринадцатого триггера регистра запойинаниийаборов свойств полноты соедйненсо вторьваивходами восьмого и двенадцатого, с третьими входами двадцатьпятого,. двадцать .седьмогои трйдцать четвергого и с .четвертым входом,сорокового элементов.И МжшиФратора базисных групп, выход четырнадцатоготриггера регистра зайоиинаиия наббров,свойств полноты .соединен с тре-;тьими входами тринадцатого четцрвадцатого, пятнадцатого, шестнадцатого,двадцать шестого, двадцать восьмого,.;и тридцать пятого и четвеРтым. вхфдом сорок первого элементов,И де 3 иифф. ратора базисных групп, выходы ПеР"вого, второго, третьего, чбтвертого, -пятого, шестого., седьмого, восЬмогь,девятого, десятого, одинйарщатото, 6 Одвенадцатого, двадцать перЫго,двадцать второго, двадцать третъегр,двадцать четвертого и тридцать тре.тъего элементов И дешифратора базисных групп соединены со входами пер ного элемента ИЛИ блока сборки., выход которого подключен ко второму выходу устройства, выходы тринадцатого,: четырнадцатого, пятнадцато- го, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого, двад" цатого, двадцать пятого, двадцать шестого, двадцать седьмого, двадцать восьмого, двадцать девятого, трид цатого, .тридцать первого, .тридцать второго, тридцать четвертога тридцатьпятого, тридцать шестого, тридцать: седьмого, тридцать восьмого н тридцать девятого элементов И дешиФратора базисных групп. соединены со входами второго элемента ИЛИ бло ка сборки, выход которого соединен с третьим выходом .устройства, выходы сорокового и сорок первого элемен-. тов И дешиФратора базисных групп соединены со входами третьего .элеменга ИЛИ блока, сборки, выход которого подключен к четвертому:выходу устройства, блок определения свойства несохрайения константы нуль содержит элемент НЕ, входкоторого ссе динен с пряьым выходом этого блока и с выходом первого переключателя: наборного поля, а выход является инверсным выходом блока определения свойства несохранения константы нуль, блокопределения свойства несохранения константы единица содержит эле-: мент НЕ.,:вход которого соединен с инверсным .выходом этого .блока и выходомпоследнего переключателя на- . борного поля, а выход является приам выходом блока определения свойства несохранения константы единица, блок определения свойства не- монотонности содержит п 2 " " элемен. тов ЗАПРЕТ, элемент ИЛИ и элемент НЕ, причем входы каждого элемента ЗАПРЕТ соединены с .выходами тех двух переключателей наборного. поля, двоичные номера которых отличаются только в одном разряде, причем за.,прещающие входы элеменгов ЗАПРЕТ соединены с выходами переключателей наборного поля, имеющих больший номер, выходы элементов ЗАПРЕТ сое- дннеИЫ со входами элеМента ИЛИ, вЫ- ход которого непосредственно соединен с йрямцм,.а.:через элемент НЕ - с инверсными вйходами блока опреде: .: Ления свойства немонотонности, блок 1 .ьлределенйя свойства нелинейности со:держйт и 2 ". ". элементов РАВНОЗНАЧ;НОСТЬ, и элементов И-НЕ, и 2 п." элементов И, элемент ИЛИ и; элемент НЕ, причем входы каждого элемента РАВНО;ЗНАЧНОСТЬ соединены с выходамй тех двух переключателей наборного поля, 1 двоичные номера. которых отличаются только 1 водном разряде, выходы эле.ментов РАВНОЗНАЧНОСТЬ, соединенных входами с выходами переключателей наборного поля, разность номеров ко"2 В27 , 960795торых .одинакова, соединены Со Входа- ментов РАВНОЗНАЧНОСТЬ; соединены соми одного элемента И-НЕ:и с первыми входамн элемента: ИЛИ, выход кото-.входамн соответствующихэлементов И, рого.непосредстванно.,соединен с прявторые входы которас подлюдны.к вы- мым, а через элемент"ЙЕ - сннверсходу. этого элемента: И-НЕ,.выходы : ньэе выходамй "блока определения .злеыентаа:и:йодкщвмеиы:ко входам,. 5 свойстванесамодвойственности.злемейта ИлИ., выход которого йЕпОс- . . Истачиики инФормации,редственно .Соединен с Фрямьз, а че-.: . принятйе во внимайие йри.экспертизерез элемент НЕ. -с .инверсными:вйхо.- -1 Вавйловф.:Н,и: др, Синтездами блока определениясвойства. не- схем:электройных ииФройык мащин. и.,линейности,.блок оиределения свой-. 10 Советское:разно 1,;:1963,:с. 27.ства неаамодвойствеииости:содервит: " : 2. Яблонский С,В и др. Дискрат-2"элементов РАВНОВЙАчнОсть ,эле-, ная,математика и математические вопИент .ИЛИ.и ЭлЕмеит НК:, приЧем вхщаю : -Росм кибернетики. М., "Наукаф,каждого, элемента РАЗИОЗНЗЛНОСфЬ,сое,: т. 1,"с 73,дииены с выходамитех двух аереклю, 3. Поспелов Д,А. Логические методычателей наборного вОлЯ, суввеа номе- анжза и синтеза схем. И., фЭнеррав которых равна 2" ф, аыходв зле- . . гияс ,. 1968, с, 41 (йрототип 1.,которого производится упрощение про. "цесса выявления базисных систем логических функций по сравнению с ручными метэдами.Указанная цель достигается тем,что устройство для раскознаванйяфункциональной полноты сцстем логи.ческих функций содержит наборноеполе из 2 перееключателей (где.пичисло переменных булевых Функций),блок определения свойства не сохранения константы нуль, блок апре".деления свойства не сохранения константы единица, блок определениясвойства немонотоинасти, блок опре 1 деления свойства нелинейности, блокопределения свойства .несамодвойственностндешифратор наборов свойствполноты, регистр запоыкканкя наборов свойств полноты, дешифратор ба,зисных групп и блок сборки, причем дешифратор .наборов. свойств полнотысодержит четырнадцать элементов И, дешифратор базисных групп содержитсорок один,элемент И, бло сборкисодержит три элемента ИЛИ, прямойвыход блока определения свойстване сохранения константы нуль соединен с первыми входами первого, вто"рого, третьего, четвертого, пятогои шестого элементов И двшкфраторанаборов свойств полноты, инверсиый,выход блока определения свойстване сохранения константы нуль соединен с первыми входами остальныхэлементов И дешифратора наборовсвойств полноты, прямой выход блокаопределения свойства ие соранамния константы единица соединен со вторыми входамк первого, второго,третьего, седьмого, восьмого и девятого элементов И дешкфратора наборов свойств полноты, инверсныйвыход блока определения свойства не сохранения константы единкцасоединен со вторющ входами осталь-.ных элементов И ,дешифратора наборов свойств полноты, прямой выходблока определения свойства немонотонности соединен с третьими входа" ми первого, второго, третъего, четвертого, цятого, седьмого, восъмого, десятого, одиннадцатого и двенадцаТого элементов И дешифратора наборов свойств полноты, третьи входы остальных элементов И которого соединены с инверсным выходом блока определения свойства немонотонности, прямой выход блока определения свойства нелинейности соединен с четвертыми входами первого, второго.четвертого, седъмого, десятого, один.надцатого, тринадцатого и четырнадцатого элементов И дешифратора наба" ров .свойств полноты, четвертые входы остальных элементов И которого соединены с инверсным .выходом блока определения свойства нелинейносТи,;. прямой выход блока определениясвойства несамодвойственности соединен с пятыми входами первого, четвертого, пятого, шестого, седьмого, 5восьмого, девятого, десятого и тринадцатого элементов И дешифраторанаборов свойств йалнаты, пятне входы остальных элементов Й которогрсоединены с инверсным Выходамблокаопределения свойства несамодвойствен ности, шестые входи всех элементов Идешифратора наборов свойств полнотысоединены с шиной ввода устройства,а .выходыпадключены к входам установки в единицу соответствующих тркгге ров регистра эапомйнанкя наборовсвойств полноты, аходы установки в.нуль которых соедкненй с шиной сброса устройства, выход первого триггера регистра запоминания наборов 20 свойств полноты соединен с неранм выходом устройства, выход второго триггера регистра запоминайия наборов:свойств полноты соединен с первымивходами первого, второго, третьего, 25 четвертого, пятого, .шестога, седьмого и восьмого элементов И дешкфратора базисных ГруПП, ВЫХад тРетьего триггера регистра запоминаниянабороВ свойств подиоты соЕдИНЕН с ЗО первыми входами девятога, десятого,одиннадцатого, двенадцатого, тринад-.цатого, четырнадцатого, пятнадцатого, шестнадцатого, семнадцатого,восемнадцатого, девятнадцатого к 35 двацатаго элементов И дешифраторабазисных групп, выкод четвертОга .триггера регистра запоминаний наборов свойств полноты соедкнев со вторыми входамк первого к девятого. и а 40 первыми входами двадцать первого,двадцать второго,к двадцать тратъега.,элементов И дешифратарабазисныхгрупп, выход пятога триггера регистразапоминания наборов свойств полноты 45 соединен со вторще входами второготринадцатого и семнадцатага и первыми входами двадцать чвтвертага, двадцать пятого, двадцать шестого, Мвдцать седьмого, двадцать восьмого,двадцать девятого., тридцатога тридцать первого и тридцать вторага элементов И дешифратара базксйык: Щупп,выход шестого триггера регистразапоминания наборов .свойств полйоты .соединен со втарымк входами третьего, 55 четыриадцатага и васемнадцатага и .спервыми входами тридцать третьего,тридцать четвертого, 1 ркдцать пято"го, тридцать шестога, тридцать седьмого, тридцать восьмого, тридцать 60 девятого, сорокового и сорок первого элементов И дешифратора базисныхгрупп, выход седьмого триггера регистра запоминания наборов свойствполноты соединен со вторыми входами 65 четвертого, десятого, двадцать первого, двадцать четвертого и тридцатьтретьего элементов И,дешифратора базисйых групп, вшход восьмого триг,гера регистра запоминания наборов свойств .полноты соедийен со вторыми;, входами:пятого, пятнадцатого, девятнадцатого, двадцать;второго, .двад" цать пятого., двадцать. шестого, двадцать. девятого тридцатого:, тридцать.четвертого,.тридцать пятого, тридцать.шестого и тридцать седьмого элементов. й дешифратора базисныхгрупп.выходдевятого триггера ре-, . гистра запоминания наборов свойствполноты соединен со вторыми входамишестого;шестцадцатого, двадцатотФ,: . 15двадщть третьего, двадцать седьмого,:двадцать восьмого .тридцатьпервого, тридцать второго, тридцатьвосьмого, тридцать девятого, сороко вого й сорбкпервого элементов И дешифратора базисных групп, вйход десятого триггера .регистра запоминайиянаборов свойств полноты соединен со вторыми. входами седьмого и одинйадцатого и третьими. входами. двадцать девятого, тридцатьпервого,;тридцать шестого и тридцать восьмого элементов И дешифратара базисных, групП, выхододиннадцатого триггера регистра запоминания наборов свойств полб 3) иоты. соединен с третьими входамисемнадцатого, восемнадцатого, девятнадцатого, двадцатого, тридцатого, тридцать второго, тридцать .седьмого и тридцать девятого. элементов И,це шйфратора базисных групп,.выход двенадцатого триггера регистра запоми- . нания наборов свойств полноты соединей с третьими входами сорокового и сорок первого элементов.И дешифра- щ тора базисных группвыход тринадцатого триггера регистра запоминания наборов свойств полноты соединен со зторцми входами восьмого и двенадцатого, с третьими входами двадцать пятого, двадцать седьмого и тридцать четвертого и с четвертым входом сокового элементов И дешифратора.азисних групп, выход четырнадцатого.триггера регистра запоминания наборов свойств полноты соединен с 50 третьими входами тринадцатого, четырнадцатого, пятнадцатого, шестнадцатого, двадцать шестого, двадцать восьмого и тридцать пятого и четвертым входом сорок первого элемен тЬв И двшифратора базисных групп, выходы первого, второго, третьего, четвертого, пятого,: шестого, седьмого, восьмого, девятого, десятого, одиннадцатого, двенадцатого, двад- ; 60 цать первого, двадцать второго, двад; ать третьего, двадцать четвертого и ,тридцать третьего элементов И деаифратора базисных групп соединены со входами первого элемента ИЛИ бло- у 5 ка сборки, выход которого подключен ко второмувыходу устройства, выходы тринадцатого, четырнадцатого,пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого, двадцатого, двадцать, пятого, двадцать шестого, двадцать седьмого,.двадцать восьмого, двадцать девятова го,.тридцатого, тридцать первого, тридцать второго, тридцать четвертого, трйдцать пятого, тридцать шестого, тридцать седьмого, тридцать восьмого и тридцать девятого элементов И дешифратора базисных. групп соединены со входами второго элемента.ИЛИ блока сборки, выход которого, соединен с третьим выходом устройства, выходы сороковогб и сорок первого элементов И дешифратора базисных групп соединены со входами третьего элемента ИЛИ блока сборки, выход которого подключен к четвертому выходу устройства, блок определения свойства несохранения константы нуль содержит элемент НЕ, вход которого соединен с прямым выходом этого блока и с выходом первого переключателя наборного поля, а выход является ин.версным выходом блока определения свойств несохранения константы нуль, блок определения свойств несохранения константы единица содержит элементНЕ, вход которого соединен с инверсным выходом этого блока и выходом последнего переключателя наборного поля, а выход является прямым выходом блока определения свойства несохранения константы единица, блок определения свойства нет монотонности содержит и 2 элементов ЗАПРЕТ, элемент ИЛИ и элемент НЕ, причем входы каждого элемента ЗАПРЕТ соединены с выходами тех двух переключателей наборного поля, двоичные номера которых отличаются только в одном разряде, причем запрещающие входы элементов ЗАПРЕТ соединены с выходами переключателей наборного поля, имеющих больший номер; выходы элементов ЗАПРЕТ соединены со входами элемента ИЛИ, выход которого непосредственно соединен с прямым, а через элемент НЕ - с инверсными выходами блока определения свойства немонотонности, блок определения свойства нелинейности содержит.и 2 элементов РАВНОЗНАЧНОСТЬ, п элементов И-НЕ 7 и 2 "-" элементов И, элемент ИЛИ и элемент НЖ, причем входы каждоо элемента РАВНО ЗНАЧНОСТЬ .соединены с выходами тех двух, переключателей наборного поля, двоичные номера которых отличаются только в одном .разряде, выходы элементов РАВНОЗНАЧНОСТЬ, соединенных входами с выходами переключате" лей наборного поля, разность номеров которых одинакова, соединены савходами одного элемента И-НЕ и с первыми входами соответствующих элементов И, Вторые входы которых подключены к выходу .этого элемЕнта И-НЕ,выходы элементов И цадключены ковходам элемента ИЛИ, выход которо"го непосредственно. соединен с пряМйм, а через элемент НЕ - с инверс. ными входами блока определениясвойства нелинейности, блан определения свойства несамодвойственностисодержит ,2" " элементов РАВНОЗНАЧ 510 НОСТЬ, элемент ИЛИ и элемент НЕ, при-.чем входы каждого элемента РАВНО.ЗНАЧНОСТЬ соединены с выходами техдвух переключателей наборного поля,сумма номеров которых раина 2 ф - 1,выходы элементов РАВНОЗНАЧНОСТЬ сое:динены со входами элемента ИЛИ, .вы-. .ход которого. непосредственна соединен с прямым, а .через элемент НЕ - синвероными входами блока определе.ния свойства несамодвайстаенности.При таком построении устройствареализуется критерий неизбыточнойполнатй, прн котором для каждой булевой Функции из заданной системывйделяются и запоминаются не простосвойства полноты, .как это делаетсяв известном устройстве, а так называемые наборы свойств Полноты, идалее проверяется. наличие не простовсех свойств полноты, а так. называемых базисных групп наборов.свойств . полноты, что позволяет непосрадственно выявлять неизбыточные Функциональ но-полные системы булевых, Функций.Назовем каждое из указанных втеореме о полноте Поста пяти свойствбулевых Фнукций, т.е, первое свой-ство - .не сохранять константу.нуль 40 .(Ко), второене сохранять констан-, ту единица (К), третье - быть немо-.нотонной (Й), четвертое - багь не.линейной (Й) н пятое - быть несамо двойственной (С) - свойством полно- :,45 гыОбозначим.циФрай О случай, когдабуде. вая Функция обладает данным свойствамполноты, и циФрой 1, если не обла" дает нм. Тогда, очевидно,можйо составить 32 различных набора свойств полноты. Каждый такой набор будем рассматривать как двоичную записьЙисла, являющегося номвром набора, Расположив. наборы для удобства свер- . ху вниз в естественном:порядке, со-ответствующем расположению чйаел от; О да 31, каК это указана,В табл.- 1.Не существует булевых фунйРФ обладающих наборамн свойств полноты с номерами 2, 4, 5, б, 7, 9, 11, 12, 13, 15; 17 у 19 у 20, 21, 23, 26 и 30.для доказательства этого утверж-, дения разобьем указанные наборы на 65 следующие группы: 1) 9, 11, 13, 15;2) 17, 19, 21 23 У 3) 4, 5, 6, 714) 12 у 5) 20 у б) 2 у 7) 26 и 30.Докажем отдельно для каждой ука-.занной группы, что в алгебре логики несуществует Функций, обладающихсочетанием свойств полноты, соот-.ветствующим этой группе.К первой группе наборов свойствполноты относятся булевы:. Функции,одновременно не .сохраняющие. константу нуль, сохраняющие константу единица и являющнеся самодвойственнымйаЕсли булеза Функция .й (х,.х) не сохраняет константу нуль,то г (00) = 1 . Если булезаФункция Ю (х,х) сохраняет константу единица, то Ю (11) = 1.Если булеза Функция является самодвойствеиной, то на любых двухпротиноположных наборах она принимает противоположные значения. Поскольку наборыфВсе О 1 и .Все:1 фявляются противоположньве, а значения Функции.на этих наборах одина- .ковы (равны 1), то условие самодвойственности при выполнении условийне сохранения константы нуль н сохранения константы единица не можетбыть выполнено, что И доказнааЕтприведенное утверждение дпя случаяпервой грунин наборов свойств пол"иоты, Аналогично. приведенноЕ утверж-дение доказываетея й для всех остальных случаев.Таким образом, булевы Функцйн мо-.гут обладать только 15-ю наборамисвойств полноты, имеющими номера .О 1 ю 3:ф Зр 10 ю 14 ф 1 бф 18 г 22 24 г25, 27, 28, 29 и 31;Группу йабарое свойств полноты,.удовлетворяющую критерию, Функциональной полноты,. назовем полной группой наборов:свойств йалноты.Группа наборов свойств полнотыудовлетворяет критерию полноты,в томслучае, если булевн Функции, обладающие наборами свбйств падноты,составляющими. эту группу, образуютФункционально-полную систему буле-.вых Функций,. Для тогами ЧтОбы ГРуйпа наборовсвойств полноты была полной. группой наборов:, необходимо и достаточна,чтобы нули в двончнйк номерах .наборов группы.соэместна перекры-.вали. все пять позиций., соответствующих свойствам полноты.неиэбыточную полную групйу наборов свойств полноты назовем базнс-.най группой.;Неизбнточная полная группа набо-ров свойств падноты характеризуется тем, чта нули в.двоичных номерахнаборов группы .совместно перекрывают все пять позиций, соответствую 1:нуль, блок 8 определения свойствнесохранения константы единица,блок 9 определения свойства немонотонности, блок 10 определениясвойств нелинейности, блок 11 определения свойства несамодвойственности, шестивходные элементы И 12 - 25,входящие в состав дешнфратора 3,триггеры 26 - 39,.входящие в составрегистра 4, двухвходовые .элементы И;40 в . 56, .четырехвходовые элементы И 57 и 58 и трехвходовые элементы И 59. - 80, образующие дешифратор 81 базисных групп,:блок 82 сборки,.содержащий элементы ИЛИ 83 - 85., На фйг,2 показан также не входящий в состав устройства блок 86 индикации:с элементами 87 - 90 индикации.На перехлЮЧатели 2 наборного Поля: 1 по шинам 91 и 92 подаются .логически.е константы 0, и ф 1 ф. В.зависимости от положения переключателей 2 эти сигналы.по шинам 9396 Подаются на входы,.блоков 7 - 11.Блок 7:содержит элемент НК 97 и насвоих. прямом н, инвереном выходахФормирует сигналы, ноступающие пошинам 98 й 99 на входы.дешифрато-ра 3 Блок 8 содержит элемент НЕ 100:и на свойх прямом и инверснбм.выходах формирует сигналы, поступаюшие по шинам 10.1 и:102 на од дешифратораЗ. Блок 9 содержит элементы ЗАПРЕТ. 103 106, элемент йЛИ07, элементНЕ 108 и. Формирует насвоих пряМом нинверсном вйходах сигНали поступавшие.по шинам .169 й1 О: на входы дешифратора 3". Блок 10содаржит элемеиты РАВНОЗНАЧНОСТЬ 111- .114:, элЕменты И-НЕ 115 и 116, элементЫ И: 117 - 120, элемент ИЛИ 121,:элемент НЕ 122 и Форщрует:на своихПрямом иинверсном выходах сигналы,поступающие по шинам 123 и 124 на,входы дешифратора 3. Блок 11 содержит элеьейты РАВНОЗНАЧНОСТЬ 125 и:126, элемент ИЛИ 127 элемент НЕ 128к Формирует на своих прямом и инверснбм:эыходахсигналы, поступающие по шинам 129 и 130. на входы дешифратора 3. Входы дешифратора 3соединены .со входами регистра 4, выход первого триггера 26 которого является выходом устройства и шиной131 соединен с элементом 89 индикации. Выходы остальных триггеров:27 - 39 регистра 4 шинами 132144 соединены со входами дешифратора 81,; виходЫ элементов И 40-80 которого сОединены со входами элементов ИЛИ 83 в . 85 блока 82, входы ко:торых являются выходами устройства1,и соединены со входами элементов 8790 индикации..Устройство работает следующимобразом. щих свойствам полноты, однако изтакой .группы нельзя исключить ниодного набора свойств полноты без,того, чтобы не было нарушено это .свойство.В алгебре логики имеется конечноечисло, равное 42, .":базисных группнаборов свойств полнотыЭто вытекает иэ того что в алгебре логикисуществует всего пятнадцать.наборов .свойств. полноты, коибийирование: ко+ 10торых в базисные группы:и доказывает.справедливость этого утверждения еПриведем все. возможные : базисныегруппы наборов свойств полнстыг:О, .181 1, 10,. 1, 14 У 1 ю 16 У 1,; 1"8.У1, .22 У 1.,:24 У , 281 3, 8 У 3.,: ".16 У3 2:4 у 1,.3, 28 р 8:.1 бу :, 18; 8, 22.10, 18:, 24 у 10, 22, 241 10,. 22., 25 у14,. 18. 241,14, 18,25.У 14, 2.2, 2411422, 214,; 22,. 27284 14 22,27 .29 "10 18,:25.Айализ йолучейных:бааисйых групппозволяет сделать следукаве, выводы:з алгебре,логики:имеется,.всего.,одна,базисная груйпа йаборов свойств:полноты.,.состФящдя:из одаогонабо-.ра, -семиащать баэисных групй. -; издвух наборов, двадцать две базисныегруппы,- иэ трез. наборов и; две,базисныегруппы - из четырщ нафорое . 35свойств полноты.Известно, что Функционально-,полиая .система .булевых Функциа,никакая составная часть которр:ве:яв.- ляется полной назйваетсябазиои.: ,4 ОаВГебрылОГикиДля того:, чтобы. система булевйх,Фуймций бйла.базйсом:алгебрй.вникй: необходимо к дОстатючно, чтОЬыгруппанаборовсвойств ттолноты:.Со-отвЕтствуваая этойсистеме, йол-:,йостью совпадалас одйой жз.42.воз+можных в алгебре логики .баэисййх.групп,На Фиг;1 и 2 предетавлейа структурнаясхема устройствамина фиг,Звыполнение наборного. йоля.и:блокомопределения: свойства несосраие 9 йяканстанти нуль, определениясзФВ-ства,несохранения константыедкий .ца, свойства немонотойности,. свОж-.;ства нелинейности, свойств иесамодвойственности для случая И:2.Устройство содержит .наборное по-.ле 1, содержащее, например, дляслучая И"2:переключатели 2.р 2, 602, 23 дешифратор 3 наборов .свойств полноты, регистр 4 запоми- .нания овойств полноты, шину 5 вво- .да, шину 6 сброса, блок 7 определе-,ния свойств несохранения константы 6510 б 0 Каждая булева функция иэ заданной системы последовательно одна задругой задается с помощью 2" двухпозиционцых переключателей 2 наборного поля 1 сп - максимально возможное число переменных аналиэнруемых .булевых Функций),.через которыев блоки 7 - 11 подаются сигналы логического 0 ф или 1 ф 1 ф в зависимости от положения переключателей 2..комбинационные логические схемы, вы. рабатывают на своих выходах .лять соответствующих булевых функцийК. - П (ЦЗначение функции несохраненияконстанты нуль равно единице, если .переключатель 2 с номером О, соот,ветствующий набору булевой функцииВсе Оф установлен в полажениефф 1, и равно нулю, если этот пе. реключатель установлен в положение9 10кк,"- пу. (2)Значение функции несохраненияконстантыединица равно единице,.если переключатель 2 с номером 21, соответствующий набору булевойфункцииВсе 1, установлен в положение 0 ф, и разно нулю, еслиэтот переключатель установлен в по-ложение 1йй = Ч П; П, (3):где 1 и Э - номера соседних наборов.,Значение функции немонотоннастиравно единице, если найдется хотябы одна пара йсереключателей 2, соответствующих соседним (склеивающимся) наборам и установленных в 40противоположные положения, причем втакие, когда переключатель с нсмером,в котором склеивающаяся переменнаяравна нулю, установлен в положение 1 1, и равно нулю в противном 45случае. В Формуле (3) операция ч берется по всем п 2" " Мрвся. соседнихнаборовЯ = Чп . П ф (4)где 1 и 3 .- номера наборов, сосед-них по существенной переменной.Значение функции нелинейности раво единице, если найдется хотя бы ода пара переключателей 2, соответствующих соседним по существеннойпеременной наборам и установленныхв одинаковое положение, и равно нулюв противном случае. В Формуле.:(4)операция Ч берется по всем п 2 я "парам соседних наборов,16 щ ЧП; П,(5)где 1 + 3 - 2 ф - 1Значение функций несамодвойствен-.ности разно единице, если найдется 65 хотя бы одна пара переключателей 2, соответствующих противоположным на.- борам и .установленных в одинаковое положение, и равно нулю в противном случае. В формуле (5) операция мберется по всем 2" парам противоположных наборов.В Формулах (1) " . (.5).у - логическая операция ИЛИ 7- логическая операция РАВНОЗНАЧНОСТЬ= - логиЧеская операция ЗАПРЕТс-- логическая операция НЕ.Наборное поЛе 1 садеркит 2 пе реключателей 2, занумерованных так, .чта двоичные их номера совпадают с соответствующими наборами логйческих функций и переменных.: Все первые переключаемые контакты переключателей 2 наборного поля 1 саедйнены с аиной 91 логического нуля, все вторые - с айной 92 логической едини-.: цы, а переключающие контакты соединены со Входамй блоков 7 -. 1.1.ВлоК 7 апредеЛения свойства Неаохранения константынуль представ . ляет собой повторительсиГнала (проводник, соединяющий переключатель 2 с номером О, с.прямым выха" ,дом блока 7, на которси реализуется логическая Функция (1) Юй 0. Для получения инверсного. Выхода блока 7 используется элемент НЕ 97. Злак 8 определения свойства несахранения константы единица представляет собой элемент.НЕ 100, вход которого сое.- динен спереключателем 2, ийеющим номер 2 - 1, на вцйодекоторого реализуется логическая функцэя:(2) йй, и зтат Выход является йрямыи выходом блока 8. Для получения инверсного выхода исвальзуетс",я.значв-ние Функции на входе злемеита НЕ 100,Влбк 9 определения свойства. оеманотанности представляет собой . п 2"-" двухвхадавих элементов ЗА- пРет 103 ." 106, Входы каждого из которых соединены с переключателями 2, двоичные номера котодик отличаются только в одйом разряде, при этом запрещающие входы соединени .с переключателями 2, имеющими.боливий номер а выходы соедннэии с:Входами пф 2" " вхадавога элемента ИЛИ 107, на выходе которого реализуется логическая функция (3) йИ, и этот Выход яВляется прямым Выходам блока 9, Для.получения инверсного выхода используется элеМент НЕ 108.Блок 11 определения свойства не-., линейности представляет собой в 2" ", двухвхадових элеЯеитов РАВНОЗНАЧНОСТЬ 111 - 114, п 2 " " входавых элементов И-ЫЕ 115 - 116, о 2"-":двухвходовых элементов И 117 - 120 н один в 2 " 1 входовой элемент ИЛИ 121, при этом входы каждого иэ элементов РАВНОЗНАЧНОСТЬ 111 - 114 соедитем группируются в четыре сигнала почислу наборов в базисных группах спомощью элементов ИЛИ 83-85 для Фор".мирования выходных сигналов устрой.ства, которые осуществляют включе"ние четырех элементов 87 - 90 индикации блока 86 индикации. 60 иены с переключателями 2, двоичные.номера которых отличаются только:в .одном разряде, выхолы элементов РАВНОЭНАЧНОСТЬ 111 - 114, соединенных своими входаьн с переключателями 2 наборного поля 1, разность номеров 5 между которыми одинакова, соедине- . ны с входами одного к того же элемента И-НЕ 115, 116, а также с.пер-. вымк входами. соответствующих элементов 117 - 120, вторые входы кото рцх.подключены к выходу этого эле.мента И-НЕ 115-П 6, выходн элемен-.тов:И 117 - 120 соединены.с входами элемента ИЛИ 121, на выходе ко-.торого реалйзуется логическая .Функция (4)ХЛ, и этот выход яв-ляется. прямым выходом блока 10. Для получения инверсного выхода кспользуется элемент НЕ:122.Блок 11 определения свойства -несамодвоствениости представляет со- бОй 2. . Двухвходовых элементов РАВНОЗНАЧНОСТЬ 125 к 126, входы каждого из.которых соединены с переклю-.чателями 2, суйма номеров которых.и., - . 25 равна 2 - 1, а выходы соединены с входамк. 2" " входового элементаИЛИ .117, выход которого является ирямам выходом блока.11, реализующего Функцию (5) ЕС., Для получения ин-.версного .выхода используется элемент НВ 128.Навыходах блоков 7 - 11 образу;ется двоичвйй пятиразрядный потен-, цкаЛьный код набора. свойств полноты, которым обладает набранная булеза Функция. Дешифратор,З:наборовсвойств полноты, представляющий со" бой комбинационную логичеСкую схЕМу кэ четырнадцати щестивходовых эле ментов И 12 - 25, осуществляет прэ 40 обраэованиЕ каждого КЗ ПЯтиадцатм возможных кодов наборов. свойств полноты в сигналы установок и единицу триггеров 26 -,39 регистра 4.устайовка .в единицу триггеров 26 .-45 39. регистра 4, для которык.выработав сигнал, установки в:единицу, цро" исходит по команде ввода. (например, путем кратковременного нажатия кнопки:ввода к подачи управляющего сиг+ 5 О кала.по шине 5 ввода).Сигналы с триггеров 26 - 39 с помощью дешифратора,81 баэискых групп, представляющего собой элементы .И 40- 80, соответствующие. всем. возможным 55 в алгебре логики базисным группаз 4 наборов свойств полноты, преобразуют-, ся в сорок два сигнала, которые эаТаким образом, поочередно набирая булевы Функции из заданной системы, автоматически определяя ихсвойства полноты и осуществляя каждый раз ручной ввод полученного очередНого набора свОйств полнотЫ в,регистр.с последующей автоматическойпроверкой хранящейся в памяти группы .наборов .свойств полноты на наличие базисных групп, мы получаем.информацию о том, является ли даннаясистема избыточной,. базисной или неполной. При этом возМожны следующие случаи:а) После анализа всех булевыхФункций из заданной системы не включен ни один нз четырех элементов индикации. Это говорит о том, что анализируемая система логическихФункций не полна.б) После анализа всех булевыхфункций из заданной системы включены илк несколько элементов индикации блока 86 индикации, кли толькоодин. элемент индикации, соответствующий базискьэю группам, число .наборовсвойств полнотй в которых меньшечисла. анализируемых булевых функцийв системе. Это говорит о том, чтоанализируемая система логическихФункций полна и избыточна,в) После анализа всех булевыхФункций иэ заданной. системы включентолько один из четырех элементов индикации, соответствующий базиснымгруппам, число наборов свойств пол"ноты в которых совпадает с.числомФункцкй в заданной для анализа системе,. Это говорит о,том, что анализируемая система логических Функцийполна к неизбыточна, тф.е. являетсябазисной.После окончания работы триггеры26 - 39 регистра 4 могут быть установлены .в исходное состояние (обнулекы) по команде сброса, (йапри;мер, путем кратковременного нажаткякнопки сброса и подачи управляющегосигкЬа по Шине 6 сброса) .РассМотрим работу устройства наследующих четырехконкретных примерах,приведенных в табл. 2.П р к м е р 1. С помощью таблиц:истинности задана система изчетырех логических Фуикцкй от трехпеременных Е, Е,.ЕЗ и Е 4 Опреде.лить, .является лк она избыточной,базисной кли неполной.Набираем Функцию Е установкойпереключателей 2, .2, 2, 24 наборкого поля 1 в положение ф 1,остальные переключатели устанавливаем в положение 0. Так как переключатель 2 р наборного поля 1 установлен в положение Оф, тоЙйэО. Так как переключатель 2960798 16 твтттютютюЮтютавюттююттттютафттттютютта аЮаютСВОЙСТВ ПОЛНОТЫтЮеюавююю ювтавтююе юартвтют еаюаеаттаеюее аатаюютМ Л Свтютетаею ттттетютт ава Юав ее ее ет ютт аватаете Замечание овозможностинабора в .алтгебре логики Десятичныйномер иаботра свойствполноты Двоичный код набора 1 еттаеает ает 0 0 0 0 00 0 0 0 0 0 0 Не возможен О О 0 0 О 0 Не возможенТо же 0 0 0 0 0 П 0 жение ф 0, то йй 1. Так как переключатели 2 и 2 наборного по ля, соответствующие склеивающимся наборам, установлены в противоположные положения, причем переключатель 2, соответствующий набору, 5 в котором склеивающаяся буква равна ф 01 ф, установлен в положение ф 1 1, то ГМ = 1. Так как переключатели 20 .и 2 З наборного поля, соответствуюзие наборам с четным чис лом единиц, установлены в противоположные положения, тб. ЮЯ щ 1, %ак как переключатели 2 О и 2 наборного поля 1, соответствующие про" тивоположнцм наборам, установлены . В одинаковое положението И 1.Таким образом, на инверснмх вы: ходах блоков 7 - 11 образуется двоичный код 10000, соответствующий набору свойств йолноты набранной булевой функции й, которая сохраняет константу .нуль, не. сохраняет константу единица и является немонотоиной, нелинейной и несамодвойственной.25с помощью элемента И 18 дещифратора 3 наборов свойств. полноты двоичный код 10000 преобразуется в сигйал установки в единицу триггера. 32 регистра 4., соответствующего наборусвойств полноты с десятичным номером 1 бф 1. Установка в единицу этого триггера происходит.по команде ввода, ФТак как не существует базисной группы, состоящей из одного набора 35 с номером 16, то на ВЫходах дешифратора 81 базисных групп и блока 82 сборки вырабатывается сигнал 1 фО 1 и остаются не включенными все четы. ре элемента 87 " 90 Индикации блока 40 786 индикации, соответствующие базис ным группам из одного, двух, трех и четырех наборов свойств полноты.Айалогичйо",после набора и ввода информации об остальных Функциях Г, Ез и й 4, оказываютсЯ Установленными в единицу триггеры 29, 38 и 39, соответствующие наборам свойств полноты с. Иамерами 18, 28 и 29. Одю вако на выхоиах десцифратора 81 базисных групп блока 86 сборки по- прежнему вйрабатывается сигнал О и остаются йе включенными. все чеТыре элемента 87 - 90 индикации, так как не существует базисных групп, состоящих из всех или части указанных наборов. Таким обраэом, можно сделать Вывод о том, что система булевых функций для данного примера не полна. Аналогично осуществляется работа устройства и в случае приме- . ров 2 - 4 (см. табл. 2) .Данное устройство почти полностью состоит из кбмбинациоииых схей, пОЭтОМу ОНО ИМЕЕТ ВЫСОКОЕ бЫСтродЕйствие и простую структуру, сложность которой не зависит от числа переменных анализируемых булевых функций (за исключениемконструкции наборного поля 1 И. блоков 7 - 11). Действия. оператора максимально облеагчеиы и сводятся к простейщим операциям по набору заданных булевых функций и пользованию кнопками ввода и сброса.Данное устройство позволяет раз" личить не только функционально-полные, но и базисные системы логическиХ:,. функций, т .е проиЗВОдить довольно тонкий анализ свойств систем булевых функций,.необходимый В ряде случаев при создании оптимаюьньФ структур интегральных субсистем.960795 18 атютюввщт Двоичный код набора свойств полноты етщтт тютю 0 Не возможен О 0 Не возможен 12 0 0 То же 0 13 0 0 14 О Не возможен 16 О Не возможен О 3 0 О..10 Не возможен2 б 0 0 28 О 0 29 30 Не возможен 31 е ивеющи ттеивтеаивщиеюЕетютюЮт Ютттвтюетаевтвттютетев ате а ав еще Десятичныйномер набора свойствполнотыЕеививта Юв Вта О . О 00 0 1 0 . 1 Продолжение табл, 1 13 амечание о воэможности набора в алгебре логики