Ячейка однородной среды

(54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ Изобретение относится к автоматике и вычислительной технике и предназначено для построения линейных однородных структур, содержащих Ьтаких ячеек и реализующих произвольные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) из Ь букв, произвольные скобочные форьи при Ь 411), а также большой класс скобоч ных форм (при Ьъ 11), при равной доступности прямых и инверсных выходов источников информации.Известны ячейки однородной среды, содержащие элементы И, ИЛИ НЕ 1.Однако эти ячейки не эффективны . ф при реализации булевых формул, так как структуры, построенные на их,ос- новеобладают большой элементной сложностью. Наиболее близким по технической сущности к предлагаемому является ячейка однородной среды, содержащая два элемента И, два элемента ИЛИ, причем первый вход первого элемента ИЛИ соединен с выходом первого элемента И, первый вход второго элемента ИЛИ соединен с выходом второго элемента И, выходы первого и вто; рого элементов ИЛИ являются выходами 30 ячейки . Кроме того, входы элементов И являются входами ячейки 21.Недостатком ее является невозможность реализации скобочных форм.Цель изобретения - расширение функ циональных воэможностей за счет реализации скобочных выражений алгебры логики .Цель достигается тем, что ячейка содержит .элементы И, ИЛИ, причем прямой вход первого элемента И соединен с выходом третьего элемента,И и с первым входом второго элемента И, второй вход первого элемента ИЛИ соединен с выходом четвертого элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ, первый вход которого соединен с выходом четвертого элемента ИЛИ и с прямым входом пятого элемента ИЛИ, выход которого подключен к первому входу пятого элемента И, соединенного своим выходом с вторым входом второго элемента ИЛИ, первый вход ячейки соединен с вторым входом четвертого элемента И, второй вход ячейки соединен с инверсными входами первого элемейта И и пятого элемента ИЛИ,вторыми входами второго элемента И и третьего элемента ИЛИ, третий вход ячейки соединенЯчейка путем настройки реализуетследующие системы формул при 2=0 и 2=0,Г =у х Ь =Уг,при г =О и гг=1 б =урхг=у,б хг =У Уг при г =1 и гг=О 25 при 2 1 и гг 1 . 11 х(г= учугДля реализации произвольной ДНФ из Ь букв, Ьтаких ячеек объеди- Зр няются в двухканальную линейную однородную среду. Для вложения заданной ДНФ в среду, для этой ДНФ строится соответствующая древовидная схема из двухвходовых элементов, которая собственно и вкладывается в структуру.Вложение схемы в среду осуществляется таким образом, что в каждой ячейке однородной среды размещается один элемент древовидной схемы, а получающаяся схема однородной среды 40 после соответствующей настройки каждой из ячеек, совпадает с древовидной схемой.Древовидная схема из двухвходовых элементов, реализующая ДНФ из шести 45 букв имеет вид ух хгхчх 4 хчх, а на фиг. 3 б - ее реализация в линейной однородной среде из пяти предлагаемых ячеек.Аналогичным образом линейная одно О родная среда из Ьпредлагаемых ячеек позволяет реализовать произвольную конъюнктивную нормальную форму (КНФ) из Ь букв, что невозможно при использовании ячеек Шорта.Таким образом, среда, построенная на основе предлагаемой ячейки, являет. ся универсальной в классе произвольных ДНФ, но в отличие от среды, построенной на базе ячейки Шорта, является также универсальной в классе про- бО извольных КНФ.Структура, построенная на основе предлагаемой ячейки, является также универсальной в классе произвольных формул (в том числе и любых скобоч- б 5ъ с первыми нходами третьего элемент.И и четвертого элемента ИЛИ, нторыевходы которых соединены и являютсячетвертым входом ячейки, причем пятыйвход ячейки соединен с вторым входомпятого элемента И.5На фиг . 1 показана схема ячейки;на фиг. 2-4 - возможные соединенияячеек н среде .Ячейка содержит входы 1-5, элементы И .6-10, элементы. ИЛИ 11-15, ныхо рды 16 и 17,Структура предлагаемой ячейки.описывается следующей системой формул" =Угч (Учгч гг) х,12=у гг ч (уч гч 2) у . 15 ных в базисе)ф, ч,из одиннадцати и менее букв, что также невозможно при использовании известного устройства.При числе букв большем одиннадцати предлагаемая структура н классе произвольных скобочных форм не является универсальной, но реализует большой класс Формул, для которых соответстнувнцие им древовидные схемы обладают структурой, содержащей не более одного каскада третьего уровня .Одноканальный каскад из двухвходовых элементов является каскадом первого уровня . Подсоединяя к его входам по одному выходу новых одноканальных каскадов из таких же элементов, получим структуру, содержащую каскады второго уровня. Подсоединяя в сною,очередь, к входам каскадов второго уровня по одному выходу новых одноканальных каскадов, получим структуру с каскадами третьего уровня и т.д.Древовидная схема, реализующая Формулу из одиннадцати букв имеет следующий вид, М:Х х )х чх )ч(х чк )Х чу )(Х Х чК ),. содержит один каскад третьего уровня, реализуется однородной линейной струк турой из десяти предлагаемых ячеек (Фиг. 4, б) .Если Формула содержит более одиннадцати букв, а соответствующая ей древовидная схема не имеет структуры с указанным выше свойством, то в формуле необходимо раскрыть часть скобок таким образом, чтобы соответствующая ей структура обладала указанным свойством, что всегда возможно.Таким образом, предлагаемая ячейка обладает по сравнению с известной значительно большими Функциональными воэможностями.Формула изобретенияЯчейка однородной среды, содержащая дна элемента И, два элемента ИЛИ причем первый вход первого элемента ИЛИ соединен с выходом первого элемента И, первый вход второго элемента ИЛИ соединен с выходом второго элемента И, выходы первого и второго элементов ИЛИ являются выходами ячейки, о т л и ч а ю щ а я с я тем, что, с целью расширения Функциональных возможностей за счет реализации скобочных выражений алгебры логики, ячейка дополнительно содержит элементы И, ИЛИ, причем прямой вход первого элемента И соединен с выходом третьего элемента И и с первым входом второго элемента И, второй вход первого элемента ИЛИ соединен с ныфходом четвертого элемента И, первый вход которого, подключен к выходутретьего элемента ИЛИ, первый входкоторого соединен с выходом четвертого элемента ИЛИ и с прямым входомпятого элемента ИЛИ, выход которогоподключен к первому входу пятого элемента И, соединенного своим выходомс вторым входом второго элемента ИЛИ,первый вход ячейки соединен с вторымвходом четвертого элемента И, второйвход ячейки соединен с инверснымивходами первого элемента и пятогоэлемента ИЛИ, вторыми входами второгоэлемента И и третьего элемента ИЛИ,третий вход ячейки соединен с первыми входами третьего элемента И и четвертого элемента ИЛИ, вторые входы которых соединены и являются четвертым входом ячейки, причем пятый вход ячейки соединен с вторым входом пятого элемента И,.Источники инФормации, прийятыд во внимание при экспертизе1. Авторское свидетельство СССР В 596940, кл . 6 Об Р 7/00, 1974.798804 ЦООЙю ИИПИ Заказ 10047/65 Тираж 756 Подписное илиал ППП "Патент", г. Ужгород, ул. Проектная ф 1аф4