Ячейка однородной среды Советский патент 1981 года по МПК G06F7/00 

(54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ

Изобретение относится к автоматик и вычислительной технике и предназначено япя построения линейных однородных структур, содержащих h-1 таких ячеек и реализуюгцих произвольные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) из h букв, произвольные скобочные форьы при ), а также большой класс скобочных форм (при h7ll) , при равной доступности прямых и инверсных выходов источников информации. Известны ячейки однородной среды содержащие элементы И, ИЛИ НЕ 1. Однако эти ячейки не эффективны при реализации булевых формул, так как структуры, построенные на их.основе,- обладают большой элементной сложностью. Наиболее близким по технической сущности к предлагаемому является ячейка однородной среды, содержащая два элемента И, два элемента ИЛИ., причем первый вход первого элемента ИЛИ соединен с выходом первого элемента И, первый вход второго элемента ИЛИ соединен с выходом второго элемента И, выхо.цы первого и вто рого элементов ИЛИ являются выходами ячейки. Кроме того, входы элементов И являются входами ячейки 2. Недостатком ее является невозможность реализации скобочных форм. Цель изобретения - расширение функциональных возможностей.за счет реализации скобочных выражений алгебры логики. Цель достигается тем, что ячейка содержит элементы И, ИЛИ, причем прямой вход первого элемента И соединен с выходом третьего элемента.И и с первым входом второго элемента И, второй вход первого элемента ИЛИ соединен с выходом четвертого элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ, первый вход которого соединен с выходом четвертого элемента ИЛИ и с прямым входом пятого элемента ИЛИ, выход которого подключен к первому входу пятого элемента И,-соединенного своим выходом с вторым входом второго элемента ИЛИ, первый вход ячейки соединен с вторым входом четвертого элемента И, второй вход ячейки соединер с инверсными входами первого элемента И и пятого элемента ИЛИ,вторыми входами второго элемента И и третьего элемента ИЛИ, третий вход ячейки соединен С первыми входами третьего элемент И и четвертого элемента ИЛИ, вторые входы которых соединены и являются четвертым входом ячейки, причем пяты вход ячейки соединен с вторым входом пятого элемента И. На фиг. 1 показана схема.ячейкиj на фиг. 2-4 - возможные соединения ячеек в среде. Ячейка содержит входы 1-5, элемен ты И ,6-10, элементы ИЛИ 11-15, выходы 16 и 17. Структура предлагаемой ячейки опи сывается следующей системой формул ()x, z (y-fVZi /z2)y2 . Ячейка путем настройки реализует следукидие системы формул fi у X при и z , при и Jf-l . при z 1 и 5 f-i x 2 У1У2 при и Sff X Для реализации произвольной ДНФ из h букв, h-1 таких ячеек объединяются в двухканальную линейную одно родную среду. Для вложения заданной ДНФ в среду, для этой ДНФ строится соответствующая древовидная схема из двухвходовых элементов, которая собственно и вкладывается в структуру. Вложение схемы в среду осуществля ется таким образом, что в каждой ячейке однородной среды размещается один элемент древовидной схемы, а получакндаяся схема однородной среды после соответствукяцей настройки каждой из ячеек, совпадает с древовидной схемой. Древовидная схема из двухвходовых элементов, реализукндая ДНФ из шести букв имеет вид , , а на фиг. 3 б - ее реализация в линейной однородной среде из пяти предла гаемых ячеек. Аналогичным образом линейная одно родная среда из h-1 предлагаемых яче ек позволяет реализовать произвольную конъюнктивную нормальную форму (КНФ) из h букв, что невозможно при использовании ячеек Шорта. .Таким образом, среда, построенная на основе предлагаемой ячейки, являе ся универсальной в классе произволь ных ДНФ, но в отличие от среды, пост роенной на базе ячейки Шорта, являет ся также универсальной в классе про извольных КНФ. Структура, построенная на основе предлагаемой ячейки, является также универсальной в классе произвольных формул (в том числе и любых скобочных в базисе) & ,V, I из одиннадцати и менее букв, что также невозможно при использовании известного устройства . При числе букв большем одиннадцати предлагаемая структура в классе произвольных скобочных форм не является универсальной, но реализует большой класс формул, для которых соответствукнцие им древовидные схемы обладают структурой, содержащей не более одного каскада третьего уровня . Одноканальный каскад из двухвходовых элементов является каскадом первого уровня. Подсоединяя к его входам по одному выходу новых одноканальных каскадов из таких же элементов,получим структуру, содержащую каскады второго уровня. Подсоединяя в свою .очередь, к входам каскадов второго уровня по одному выходу новых одноканальных каскадов, получим структуру с каскадами третьего уровня и т.д. Древовидная схема, реализующая формулу из одиннадцати букв имеет следующий вид ()))()() содержит один каскад третьего уровня, реализуется однородной линейной структурой из десяти предлагаемых ячеек (фиг. 4,6). Если формула содержит более одиннадцати букв, а соответствующая ей древовидная схема не имеет структуры с указанным выше свойством, то в формуле необходимо раскрыть часть скобок таким образом, чтобы соответствующая ейСтруктура обладала указанным свойством, что всегда возможно. Таким образом, предлагаемая ячейка обладает по сравнению с известной значительно большими функциональными возможностями. Формула изобретения Ячейка однородной среды, содержащая два элемента И, два элемента ИЛИ,, причем первый вход первого элемента . ИЛИ соединен с выходом первого элемента И, первый вход второго элемента ИЛИ соединен с выходом второго элемента И, выходы первого и второго элементов ИЛИ являются выходами ячейки, отличающаяся тем, что, с целью расширения функциональных возможностей за счет реализации скобочных выражений алгебры логики, ячейка дополнительно содержит элементы И, ИЛИ, причем прямой вход первого элемента И соединен с выходом третьего элемента И и с первым входом второго элемента и, второй вход первого элемента ИЛИ соединен с вычходом четвертого элемента И, первый вход которого .подключен к выходу

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

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

, 2. Шорт Р. Однородные структу| ы. Анализ, Синтез. Поведение М., Энергия, 1973, с. 30-31.

А«/

y/ 1 nh 1 У Щ,

/ Й

ii-.k

tZU iJI-tlH

I/ &V7l л

yl

a:«

л:/

л«

ZypoffeHb

5

Й7

/

t

S