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

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

Иллюстрации

Показать все

Реферат

 

(72) Авторы изобретения

В. Л. Артюхов и A. A. Шалыто (71) Заявитель (54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ

Изобретение относится к автоматике и вычислительной технике и предназначено для построения линейных однородных структур, содержащих h-1 таких ячеек и реализующих произвольные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) из h букв, произвольные скобочные форьы при

Ь411), а также большой класс скобоч- 1© ных форм (при Ьъ11), при равной доступности прямых и инверсных выходов источников информации.

Известны ячейки однородной среды, содержащие элементы И, ИЛИ НЕ (1).

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

Наиболее близким по технической сущности к предлагаемому является ячейка однородной среды, содержащая два элемента И, два элемента ИЛИ., причем первый вход первого элемента

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

И являются входами ячейки (2).

Недостатком ее является невозможность реализации скобочных форм.

Цель изобретения — расширение функ. циональных воэможностей за счет реализации скобочных выражений алгебры логики .

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

798804

Ячейка путем настройки реализует следующие системы формул при 2» =0 и 22=0, f» =у» х 2 =У2 при 2 =0 и 22=1

= у»ч х 2 Уя. >

fq x

f2 У» YZ при z„=1 и zz =0

25 при z» =1 и z2=1 . 1 f =х (»г= у„чуг

Для реализации произ воль ной ДНФ из h букв, h-1 таких ячеек объеди- gp няются в двухканальную линейную однородную среду. Для вложения заданной

ДНФ в среду, для этой ДНФ строится соответствующая древовидная схема из двухвходовых элементов, которая собственно и вкладывается в структуру .

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

Древовидная схема из двухвходовых элементов, реализующая ДНФ из шести 45 букв имеет вид у х» хгх чхА x ÷х, а

6 > на фиг. 3 б — ее реализация в линейной однородной среде из пяти предлагаемых ячеек.

Аналогичным образом линейная одно- 5п родная среда из h-1 предлагаемых ячеек позволяет реализовать произвольную конъюнктивную нормальную форму (КНФ) из h букв, что невозможно при использовании ячеек Шорта.

Таким образом, среда, построенная на основе предлагаемой ячейки, является универсальной в классе произвольных ДНФ, но в отличие от среды, построенной на базе ячейки"Борта, является также универсальной в классе про- бО извольных КНФ. Структура, построенная на основе предлагаемой ячейки, является также универсальной в классе произвольных формул (в том числе и любых скобоч- б5 ъ с первыми нходами третьего элемент .

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

На фиг. 1 показана схема. ячейки; на фиг. 2-4 - возможные соединения ячеек н среде .

Ячейка содержит входы 1-5, элементы И .6-10, элементы. ИЛИ 11-15, ныхо- (g ды 16 и 17.

Структура предлагаемой ячейки.описывается следующей системой формул

"» =У» » 1 (у»" 2»ч 22) х, 12=У 2„22ч (У»ч 2»ч zZ) У2 . t5 ных в базисе) ф, ч, ) из одиннадцати и менее букв, что также невозможно при использовании известного устройства.

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

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

Древовидная схема, реализующая формулу из одиннадцати букв имеет следующий вид

3=((X„ X<)(X чХ )ч(Х чу> )(X xX+))(X X we(), содержит один каскад третьего уровня, реализуется однородной линейной струк. турой из десяти предлагаемых ячеек (фиг. 4, б) .

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

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

Формула изобретения

Ячейка однородной среды, содержащая дна элемента И, два элемента ИЛИ„ причем первый вход первого элемента

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

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

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

1. Авторское свидетельство СССР

9 596940, кл. G Об F 7/00, 1974., 2. шорт p . "Однородные структуры.

Анализ . Синтез . -Поведение", И., "Энергия", 1973, с. 30-31 .

798804

Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Я z g» ñå8

ЯЦИК//6

BHHHHH Заказ 10047/65 Тираж 756

Л