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

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

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

На фиг. 1 приведена функциональная схема ячейки однородной структуры; на фиг. 2 приведен фрагмент однородной структуры. На фиг. 3 приведен вариант реализации блока управления коммутацией; на фиг. 4-6 - возможные варианты схемных решений блока настройки, блока результата и коммутатора.

Ячейка содержит первый управляющий вход 1, первый 2 и второй 3 входы-выходы вертикальной настройки, первые входы- выходы 4 результата, регистр 5, первый мультиплексор 6, блок 7 результата, коммутатор 8, элемент И 9, второй мультиплексор 10, первый 11 и второй 12 триггеры, блок 13 управления коммутацией, блок 14 настройки, первый 15, второй 16 и третий 17 инвертирующие усилители-передатчики, вторые входы-выходы 18 результата, второй управляющий вход 19, вход-выход 20 горизонтальной настройки, вход 21 признака терминальной вершины.

Однородная структура содержит ячейки 22.

Блок управления коммутацией содержит элемент И 23, элемент ЗАПРЕТ 24, элементы И 25 и 26, элементы ИЛИ 27, 28 и 29, элемент ЗАПРЕТ 30, шифратор 31, элемент НЕ 32.

Блок настройки содержит элементы ЗАПРЕТ 33-36, элемент И 37, элемент ИЛИ 38. элемент И 39.

Блок результата содержит элемент РАВНОЗНАЧНОСТЬ 40, элемент И 41, элемент РАВНОЗНАЧНОСТЬ 42, элемент И 43.

Коммутатор содержит элементы И-НЕ с третьим состоянием 44-49.

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

Как правило, логические формулы задаются в дизъюнктивной нормальной форме (ДНФ).

Например: а Ьлс; b dve(1).

Пусть необходимо синтезировать схему, реализующую это выражение. Каждое равенство из (1) можно рассматривать как логическую операцию эквивалентность (равнозначность) и формулы (1) представить в видв.ХЬлс- а)1 «(d A v e).

Рассмотрим выражение ( )л A(dv ), которое тождественно преобразуется к виду

(Ьл )(2)

Каждое выражение внутри скобок из (2) называют предложением Хорна, где - означает знак логической операции импликации, Члены предложения слева от - - условие предложения, а член справа - заключение предложения (3). Предположение с процедурной точки зрения интерп- ретируется так: если b и с истинны, то а присвоить значение Истина.

Таким образом, предложение определяет зависимость только значений а от значений b и с (заметим, что равенство а Ьлс позволяет, кроме этого, определить значение Ьлс по известному а).

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

В нашем случае получим выражение ()л()л()лсАйле.(3)

Для синтеза схемы воспользуемся правилами:

Каждое предположение аппаратурно реализуется конъюнктором, на входы кото- рого подаются сигналы, соответствующие условиям предложения, а с выхода снимаются сигналы, соответствующие заключению.

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

Если несколько предложений имеют одинаковые заключения, то выходы реализующих их элементов подключаются на входы элемента ИЛИ (дизъюнктора), с выхода которого снимается сигнал, соответствующий значению общего заключения. Однолитерные дизъюнкты соответствуют входам схемы.

Согласно этим правилам строится логическая схема.

Эта схема реализует формулы (1). При- менение приводимых правил возможно автоматизировать, С этой целью в выражении типа (4) каждую импликацию заменим тождественно эквивалентным дизъюнктом:

()()ACAdAe (bvcva)A(dv Ь)л()лслйле. (4)

В такой записи связь между элементами, реализующими дизъюнкты, описывается условием: связь существует, если одни из дизъюнктов содержат какую-либо литеру в прямом, а другие - содержат эту литеру в инверсном виде.

Кроме того, можно показать, что процесс поиска решений в экспертных системах продукционного типа, а также решение

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

Автоматическое выполнение правил синтеза необходимой комбинационной схемы возможно на следующей математической модели. Рассмотрим матрицу М || mijk II ; I 1,п, где п - количество дизъюнктов в формуле вида (4).

J 1.S, где S - количество атомов в правой части формулы вида (4), К Е{0, 1}.

Пусть mijo 1IXj G Xi, т.е., если j-я литера входит в 1-й дизъюнкт в инверсном виде:

mijo 0l XiЈXt;

miji 11 Xj Ј Xi;(5)

miji OI X) ЈXi

miji описывают вхождение j-й литеры в прямом виде в множество литер -го дизъюнкта.

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

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

Строки, содержащие точно одну единицу, описывает входы схемы (терминальные вершины схемы), так как соответствуют од- нолитерным дизъюнктам.

Таким образом, если каждую строку М считать конъюнктором, а каждый столбец дизъюнктором, то М - схема, реализующая заданную формулу, Связи между элементами схемы описываются следующим образом. С этой целью введем ряд булевых переменных:

. ел - признак выбранной строки;

Vj0 - признак выбранного 0-го подстол- бца в j-м столбце;

V|i - признак выбранного 1-го подстол- бца в j-м столбце;

Ti - признак терминальной вершины

(однолитерного дизъюнкта).

Определим значения этих переменных следующим образом:

5

Ш| V (Vj0 mijo Vji miji) mtjo miji; (6)

П

Vj0 V WiArriiji/iVji; J 1 n

Vji mijoAVjo;

J 1

Ti 01 I Xi | 1.

(7) (8)

(9)

В результате процесс синтеза схемы

можно представить в следующем виде:

1)в подстолбце, соответствующем целевой литере, обозначим Vijk 1;

2)согласно (6) во всех строках М сфор- мируем значения У| ;

3)согласно (7) и (8) сформируем значения Vj0 и Vji по всем столбцам;

4)повторить с п. 2.

Очевидно, что процесс формирова- ния значений Vj0, Vji заканчивается в строках матрицы, соответствующих одно- литерным дизъюнктам.

При этом элементы матрицы, для которых выполняется условие 1 Vj0 mijovVjiAmiji 1,(10)

соответствует выходам конъюнкторов или входа дизъюнкторов, а те элементы, для которых

ipi ол л mijiAVjwaii д 1. (11) соответствуют входам конъюнкторов или выходам дизъюнкторов.

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

Нечеткие операции И и ИЛИ классиче- ски определены следующим образом:

3 & uj- мин (а, Ь) - операция нечеткого И, где а. Ь - нечеткие высказывания;

a, b - степени истинности а, Ь, причем: О а, b S 1;

avb макс (a, b) - операция нечеткого ИЛИ;

7 а а - инверсия а (5).

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

В таблице показан пример кодирования такого количества градаций степени истинности.

Логический элемент, реализующий операцию нечеткого И (ИЛИ), должны находить минимальное (максимальное) значение среди кодов степени истинности, поступающих на его входы, и передавать найденное значение на выход,

Поскольку в предложенной выше модели количество входов нечеткого элемента И может меняться от 0 до п-1, а количество входов нечетного элемента ИЛИ от 0 до S-1, представляется целесообразным операции нахождения мин и макс выполнять на общей шине (в общем канале).

Так для m + 1 разрядных кодов степени истинности операция нахождения макс может быть представлена совокупностью булевых функций:

Вт V Г;

е-1 гт т i.m i.ro

Вс

V 1 1

,т Л

т v В /.

г

... v (В1д li v BVliV li°.

где Вт - значение т-го разряда общей шины (выхода элемента);

lim - значение m-ro разряда на i-м входе элемента;

0 - 1 - количество входов нечеткого дизъюнктора.

Операция нахождения мин эквивалента операции нахождения макс для инверсных кодов степени истинности.

Согласно предложенной модели однородной структуры операция нахождения мин должна выполняться построчно (строка М описывает нечеткий элемент И), а операция нахождения макс - по столбцам (столбец описывает нечеткий элемент ИЛИ).

Пусть RjmRj° - вертикальные шины, а

Pim,...,Pi° - горизонтальные шины результата.

Поскольку каждый элемент матрицы М может описывать как вход, так и выход нечеткого элемента, поскольку должны изменяться его функции, элементы матрицы, для которых выполняется условие 1 (описывает выходы нечетких коньюнкторов - входы нечетких дизъюнкторов), должны реализовать операции нахождения макс среди кодов, поступающих по шинам PimPI°;

i 1,п и формировать результат на шинах

R)mRj°;J i7S, т.е. для т 2

т

«Г

V piAPi2;

I 1

10

Rj1 V 1A( P|2V R)2AP,2 )дР, J 1

5

0

5

0

5

5

0

5

R)° V piA(Rj2 P|VRj2 iPiV J 1

/(Rj1A PiV RjV PiV Pi°. (11)

Элементы матрицы, для которых выполняется условие pi 1 (описывают выходы дизъюнкторов - входы нечетких конъюн- кторов). должны реализовать операции нахождения макс среди инверсий кодов степеней истинностен, поступающих

по шинам RjmRJ°; j - 1,5 и формировать

результат на шинах PimPi°; I 1,п, т.в. (для

m 2)

- s

Pf

,2.

P|

P.°

V p2ARj

i

v р2Л (Rj2A Pi2V Rj2H Pi2)AR) 1 1

5

v (Rj2/ PA-RM Pi2) л AtRJ PiV RJ / Р. МЛ- (12)

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

Ячейка работает следующим образом.

Во время подготовки однородной структуры к работе на входы 2 vmn 3 подаются сигналы VJOH или VJIH, несущие информацию о вхождении j-ой литеры в инверсном или прямом виде в 1-й дизъюнкт реализуемой нечеткой логической формулы. На входы- выходы 4 подаются сигналы RJH RJH°, несущие информацию о кодах степеней истинности в том случае, если ячейка соответствует одному из входов, реализуемой логической схемы, При совпадении сигналов YJB и Х|В, поступающих через входы 1 и 19, на входах элемента И 9, на его выходе вырабатывается сигнал записи и подается

на управляющие входы регистра 5 и триггеров 11, 12. В регистр 5 записывается код степени истинности нечеткого высказывания (в случае, если ячейка -- вход схемы), а в триггеры 11, 12 -информация, соответствующая значениям признаков ггщо и miji. С приходом сигнала VJOH (VjiH) и при единичном состоянии триггера 11 (12) вырабатывается сигнал У|Н блоком настройки 14, Усилитель-формирователь 17 удерживает активный (нулевой) уровень сигнала на входе-выходе 20 независимо от других ячеек данной строки, обеспечивая тем самым монтажное ИЛИ. В случае, если оба триггера 11, 12 находятся в единичном состоянии, выработка сигнала сиы блокируется тем самым исключается дизьюнкттавтология. находящаяся в этой строке однородной структуры. В отсутствии сигналов VJOH и VJIH с приходом они активного уровня блоком настройки вырабатываются сигналы VJOH, если в единичном состоянии триггер 12 или сигнал VJIH, если триггер 11 в единичном состоянии. В случае наличия одного HJ сигналов VJOH или VjiH и наличия услови для выработки другого, формирование последнего запрещается (см. (7). (8)). тем самым устраняется неоднозначность определе ния входов и выхода нечеткого логического элемента, описываемого выбранной строкой однородной структуры. Использов а- ние усилителей-формирователей 15, 16 обеспечивает удержание активных нуль- ных уровней сигналов VJOH и VjiH на шинах вертикальной настройки в соответствующем столбце однородной структуры независимо от других ячеек.

При условии тут лТ|В лУ)1в 1 данная ячейка соответствует прямому входу синтезируемой схемы. В этом случае блок управления коммутацией 13 вырабатывает управляющие сигналы, обеспечивающие передачу кода степени истинности с прямых входов регистра 5 через мультиплексор 6 на первые входы блока результата 7. На вторые входы блока результата 7 через мультиплексор 10 подаются сигналы R2jHR°JH,

соответствующие инверсии кода степени истинности на вертикальных шинах результата. Коммутатор 8 обеспечивает передачу сигналов с выхода блока результата 7 на вертикальные шины результата через входы-выходы 4. Пусть значения сигналов R2jHR°JH единичные (111), что соответствует коду степени истинности 000. Пусть в регистре 5 хранится код 011. Единичное значение первого разряда регистра 5 через первые входы блока результата 7 и первые выходы коммутатора 8 установит значение

сигнала R Н 0 на входах-выходах 4 (изменит код вертикальных шин результата на 101) и далее на вторых входах блока результата 7. В блоке результата 7 произойдет сравнение значения первого разряда на первых входах и инверсии значения первого разряда на вторых входах. Совпадение значений разрешает прохождение единичного значения следующего (нулевого) разряда с первых входов на выход блока результата 7, что приведет к установлению в нулевое значение нулевого разряда на первых выходах коммутатора 8 и входах-выходах 4. На вертикальных

шинах результата установится код 100. соответствующий коду степени истинности 011. В блоке результата 7 совпадут значения второго разряда на первых входах и его инверсии на вторых входах. Однако нулевое значение второго разряда не изменит значения кода на вертикальных шинах результата. Таким образом, обеспечивается выполнение операции нахождения макс в столбцах однородной

структуры. В случае выполнения условия mijo л VJOBA Т|В 1, данная ячейка соответствует инверсному входу синтезируемой схемы и ее работа в этом случае отличается только подключением инверсных выходов

регистра 5 на входы блока результата 7 через мультиплексор 6.

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

Р IBP°IB на горизонтальных шинах результата. Следует отметить, что время поиска макс или мин кодов степени истинности не зависит от их числа (т.е. от количества ячеек, участвующих в этих операциях) и определяется разрядностью кода и глубиной схемы: мультиплексор 6 (10) - блок результата 7 - коммутатор 8.

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

отрицательный результат решения задачи логического вывода.

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

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

первого и второго триггеров соединены с выходом элемента Й,выход первого триггера соединен с первым входом блока настройки, выход второго триггера соединен с вто рым входом блока управления

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в однородных вычислительных структурах для обработки нечетких (расплывчатых) логических формул (составных нечетких высказываний), а также для логического вывода в многозначном исчислении высказываний. Цель изобретения - упрощение настройки однородной структуры за счет обеспечения хранения признаков принадлежности литеры дизъюнкту реализуемой нечеткой логической формулы, а также за счет снятия ограничений на количество входов нечетких логических элементов. Ячейка содержит управляющий вход 1, входы - выходы 2 и 3 вертикальной настройки, входы - выходы результата 4, регистр 5, мультиплексор 6, блок результата 7, коммутатор 8, элемент И 9, мультиплексор 10, триггеры 11 и 12, блок управления 13 коммутацией, блок настройки 14, инвертирующие усилители 15, 16, 17 передатчика, входы - выходы результата 18, управляющий вход 19, вход - выход 20 горизонтальной настройки, вход 21 признака терминальной вершины. Однородная структура содержит ячейки 22. Блок управления коммутацией содержит элементы ЗАПРЕТ, элементы И, элементы ИЛИ, шифратор, элемент НЕ. Блок настройки содержит элементы ЗАПРЕТ, элементы И, элемент ИЛИ. Блок результата содержит элементы РАВНОЗНАЧНОСТЬ и элементы И. Коммутатор содержит элементы И - НЕ с третьим состоянием. Ячейка предназначена для выполнения операции записи и хранения кода степени истинности нечеткого высказывания, хранения признаков вхождения литеры в дизъюнкт реализуемой логической формулы, формирования сигналов настройки однородной структуры и нахождения результатов нечетких логических операций. 6 ил., 1 табл.

#Ј «g:

8ioЈ1

e

tt

Ы

1

I.

и

rtRfl

WlfriQl

WHW.91.

-ь.К 5л.8

Фиг.5