Устройство для решения задач на графах Советский патент 1991 года по МПК G06F15/173 

±

k

фиг.1

О

сл ю о

4

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

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

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

Устройство содержит блок 1 задания матрицы прямого вхождения литер в дизъюнкты, блок 2 проверки достижимости И- вершин графа, блок 3 элементов ИЛИ, блок

4определения терминальных вершин, блок

5задания матрицы инверсного вхождения литер в дизъюнкты, выходы б признаков доказанности высказываний устройства, ячейки 7, инвертирующий шинный преобразователь 8, блок 9 формирования результата, блок 10 настройки, блок 11 определения однолитерного дизъюнкта, вход 12 маскирования, вход/выход 13 признака открытого ребра, входы 14 координатной выборки, входы 15 вертикальной настройки, информационные входы/выходы 16, настроечный вход 17, вход/выход 18 горизонтальной настройки, вход/выход признака открытой вершины 19, входы 20 признака однолитерного дизъюнкта, выходы 20 признака одно- питерного дизъюнкта, элемент И 22,элемент НЕ 23, элемент И 24, элемент ИЛИ 25, триггер 26, триггер 27 и инвертирующий шинный преобразователь 28.

Устройство работает следующим образом.

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

AI л А2 л Аз л А4 л Ав л Аб л А0

(а v b v с)л(е v d v д)л{ f v а)

(д v а)ле л d л с,

(D

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

указанного примера Ai-Ae - долговременная информация в базе знаний, а А0 - временная с той точки зрения, что после решения задачи А0 должен быть удален. 5Каждый дизъюнкт может быть преобразован в множество предложений (импликаций) типа предложений Хорна, однако в общем виде таковыми не являющимися.

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

Таким образом,

AI {а л , а л с- b, b л с а};

А2 {е л , е л g- d, d л g- e};

Аз { ,a 20 A/j ,

As { e-,

d-,,

где ф означает соответствие.

25Целевой дизъюнкт А0 является ключом

поиска в базе знаний, он же определяет какими предложениями будут представлены дизъюнкты при решении задачи. Из всех множеств предложений сначала выбирают30 ся только те предложения, заключения которых совпадают с А0. Затем из оставшихся предложений выбираются такие, заключения которых входят в условия ранее выбранных предложений. Процесс выбора

35 предложений продолжается до тех пор, пока не будут выбраны предложения, не имеющие условий (соответствующие As и Ае в нашем примере), а также, если не найдется предложений с заключениями, входящими в

40 условия ранее выбранных предложений (в примере нет предложений с заключениями b и f). Множество выбранных предложений (выбранные предложения подчеркнуты) образуют структуру, описываемую И-ИЛИ гра45 фом.

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

Таким образом, формуле AI л А2 л Аз л

55 А/}л As л Ае л АО соответствует множество предложений {а Л Ь- с, е л d- g, f- a, g- a, - е, - d}, выбранных с помощью ключа с -. Эти предложения образуют И-ИЛИ граф, представленный на фиг. 4.

Вершины с и g И-вершины (помечены дугой), а ИЛИ-вершина (без дуги). Вершины b и f закрытые, а е и d открытые терминальные вершины; С - корневая (целевая) вершина. Открытые терминальные вершины соответствуют фактам из базы знаний (предложениям без условий - е и - d), a закрытые терминальные вершины соответствуют отсутствию фактов в базе знаний (нет предложений с заключениями f и Ь),

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

каждая строка матрицы - дизъюнкт (И- вершина графа);

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

ребру в графе соответствует наличие контрарных (с разными знаками) пар литер в дизъюнктах.

М I |mijKl I. где 0, n; j 1,h; K 0,1, где г - число дизъюнктов в задаче (в нашем случае n 7); h |{a,b,c,d,e,f,g}l 7 - количество атомов в формуле (1).

Таким образом для представленного примера

тою 1. 41020 1 тозо 1 mi4o 1mi5Q 1, mni 1, ГТ1211 1, ГП2бО 1.

man 1, тз7о 1. m45i 1, ms4i 1,

ГТ1630 1.

В результате матрица М имеет вид, представленный на фиг. 5. Таким образом, для решения данной задачи необходима однородная структура, состоящая из n 7 строк и h 7 столбцов заявляемых ячеек. При этом, в единичном состоянии должны находиться триггеры 26 в ячейках с индексом 03, 17, 21, 31, 45 и 54, а также триггеры 27 в ячейках с индексами 01, 02, 14, 15, 26, 37 и 63. Все названные триггеры должны быть в нулевом состоянии.

Для записи единицы в триггеры 26 заданных ячеек достаточно сформировать единичные значения сигналов XIB, yjB на соответствующих адресных шинах 14. Для записи нуля в триггер 26, до подачи сигналов на адресные шины, необходимо сформировать сигнал Vji H низкого уровня на соответствующей шине 15. Аналогично производится запись в триггеры 27 заданных ячеек, при этом записываемая информация подается сигналом Vj0 H на шину 15. Состояние триггеров 26 и 27 всех ячеек однородной структуры не изменяется в тече- ние всего времени решения задачи. После записи информации в триггеры ячеек, через время, обусловленное переходными процессами, на шинах 21 появляются сигналы

ВЫСОКОГО уровня, 04о7вых в, ОбоТвых в. Обо7вых

в высокого уровня. Сигналы О-птвых в, ОзтТвых в, в на шинах 21 останутся низкого уровня, С этого момента однородная структура готова к решению задачи.

Пуск однородной структуры осуществляется в три этапа:

в строке 6 однородной структуры на шину 12 подать сигнал Мб высокого уровня, что Q запретит выработку сигнала для строки 6, содержащий признак тезо 1, соответствующий корневой вершине И-ИЛИ графа.

В столбце 3 однородной структуры подать сигнал V31 н 0 (активного уровня) или 5 в строке 6 подать сигнал 0, что все равно приводит к выработке Vai н 0. Появление сигнала /з н 0 приведет к появлению сигналов 0, 0, о&н 0, одзн

0, ОМн 0, (У5н О И УЦ н О, V21 н О,

Vei н 0, н 0, Vs-i н 0, н 0.

В выбранных строках (одн 0) однородной структуры, содержащих однолитерные дизъюнкты, соответствующие открытым с терминальным вершинам И-ИЛИ графа, подать сигналы RI в 1. Для рассматриваемого примера следует подать сигналы R в 1 и

Rs в 1

Высокие уровни сигналов R/з в приведут

0 к появлению сигналов Тз н 0 и Ts н 0, что в свою очередь, приведет к выработке сигналов R1 в 1, 0 ,Rs в 1 и TIH 0, и описывающим значения переменных RI и Tj,

с. кодируемых сигналами RIB и TJH. Сигнал R2B равен нулю в виду того, что Обт н (вершина f - закрытая терминальная вершина), однако значение R2B 0 не окажет влияния на формирование TIH, поскольку

0 TIH 0 удерживается на шине активным значением сигнала RSB 1. По причи- не02н 1 (вершина b также закрытая терминальная вершина) сигнал - 1 и ROB 0.

5 В результате, значение сигнала Тзн 1 остается равным единице. Сигнал соответствует условию недоступности корневой вершины С И-ИЛИ графа.

Таким образом, формула (1) AI л А2 л Аз л Аз л As л Ае л АО

0

( d v b УС)Л( e v d v д)л( f v а)л ( g v а)ле л d л с не противоречива. Это означает, что А0 с не является логическим следствием дизъюнктов Ач-Ае.

Следует отметить, что третий этап пуска однородной структуры не является обязательным для рассмотренного примера, так как значения сигналов RQQ и RSB и без их установки единичного уровня. Однако для решения задач в предметных областях с быстро изменяющимися данными, вместо коррекции базы знаний в соответствии с обстановкой, возможно существующие факты отмечать сигналами RЈB. а отсутствующие - сигналами . 0, в соответствии с динамикой их изменения.

Элемент И 22 предназначен для выработки сигнала записи информации в триггеры 26 и 27 при одновременном появлении сигналов координатной выборки на входах 14. Инвертор 23, элемент 24, элемент ИЛИ 25 образуют схему управления ячейкой 7 при чтении хранимой в ней информации. При появлении сигнала горизонтальной выборки на входах 14 и сигнала чтения на входе 17 схема разрешает задачу информации с триггеров 26 и 27 через инвертирующие преобразователи 28 и 8 на шины 16 ячейками строки однородной структуры, выбранной сигналом горизонтальной выборки. Триггеры 26 и 27 представляют собой синхронизируемые D-триггеры и предназначены для приема информации с шин 15 при появлении сигнала Запись с элемента 22 и хранения ее. Хранимая информация представляет собой признаки ITH.JK. I 0, п; j 1,h, К 0, 1 вхождения J-й литеры в прямом или инверсном виде в 1-й дизъюнкт.

Инвертирующие преобразователи 28 и 8 предназначены для выдачи информации с триггеров 26и27нашины16и организации монтажного ИЛИ совместно с другими ячейками для признаков QJI и QJO.

Блок 9 формирования предназначен для формирования признака RI - доступности И-вершины и признака Tj - доступности ИЛИ вершины. Ячейки 7 одной строки включены по признакам RI на общие шины 19, а ячейки одного столбца объединены общей шиной 13 по признакам Tj. Общие шины позволяют реализовать монтажное ИЛИ для обоих признаков.

Блок 10 настройки предназначен для формирования сигналов VJOIH, VJIH и СУЫ. Ячейки 7 одного столбца объединены общими шинами 15 признаков Vji и Vj0 по монтажному ИЛИ, а ячейки одной строки таким же образом объединены шиной 18 признака Wi, что позволяет каждой ячейке независимо от других формировать сигналы VJOH, VJIH ий)1н при возникновении необходимых условий.

Блок 11 определения однолитерного

дизъюнкта вырабатывает сигналы и DujBbixB на шинах 21 в зависимости от входных сигналов DjojexB и VujBxb на шинах 20. Работа блока описывается таблицей.

Комбинация DiijBxB DfojBxB {1,0} невозможна.

Признаком наличия однояитарного дизъюнкта в 1-й строке служит комбинация сигналов DiojBbixB 1 и DUJBBIXB 0 на выходе крайней правой ячейки 7 строки, что соответствует наличию открытой терминальной вершины в этой строке матрицы ячеек 7.

Шина 12 маскирования предназначена для передачи сигнала MIB, запрещающего выработку признака однолитерного дизъюнкта в строке, описывающей корневую вершину И-ИЛИ графа.

Шина 13 признака открытого ребра предназначена для передачи сигналов, соответствующих наличию открытого ребра

или открытой ИЛИ-вершины И-ИЛИ графа, TJH по всем ячейкам одного столбца матрицы ячеек.

За логическую единицу на шине 13 принят низкий уровень электрического сигнала,

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

Шины 15 вертикальной настройки предназначены для передачи на входы триггеров 26 и 27 записываемой информации при работе ячейки в режиме записи и передачи сигналов поиска вхождения j-й литеры в прямой (VJIH 0) или в инверсном (Vi0H/ 0) виде в дизъюнкты решаемой задачи. Сигналы VHH и VtoH определяют наличие ребер в

И-ИЛИ графе или наличие связей в эквивалентной комбинационной схеме. Все ячейки одного столбца подключаются к шинам 15 по монтажному ИЛИ.

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

Настроечный 17 вход ячейки 7 представляет собой шину, объединяющую все

ячейки однородной структуры. Наличие на ней сигнала высокого уровня соответствует переводу ячеек 7 в режиме чтения, а отсутствие сигнала переводит ячейки в режим решения задач.

Настроечная шина 18 объединяет по монтажному ИЛИ ячейки одной строки и предназначена для передачи сигналов выбора строки (Win, соответствующих вхождению И-вершины в И-ИЛИ граф.

Шина 16 признака открытой вершины объединяет по монтажному ИЛИ ячейки 7 одной строки матрицы и предназначена для передачи сигналов RIB о доступности И-вершины И-ИЛИ графа. Для нее характерно, в отличие от других шин, прямее кодирование сигналов.

Входные 20 и выходные 21 шины признака однолитерного дизъюнкта предназначены для последовательной передачи сигналов от левых к правым ячейкам 7 одной строки о хранимой в них информации с целью определения открытых терминальных вершин И-ИЛИ графа.

Входные шины левой ячейки 7 являются входными соседней с ней правой ячейки. Входные шины крайней левой ячейки каждой строки заземлены. Выходные шины крайней правой ячейки каждой строки служат для формирования признака наличия однолитерного дизъюнкта в этой строке матрицы.

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

В режиме записи по шинам вертикальной настройки 15 подается записываемая информация о вхождении j-й литеры в i-й дизъюнкт прямом (VJIH 1) или в инверсном (VjoH 1) виде на D-входы триггеров 26 и 27. При одновременном появлении сигналов координатной выборки на шинах 14 формируется сигнал разрешения записи элементов И 22, поступающий на С-входы триггеров 26 и 27 и производится запись информации.

В режиме чтения на настроечном входе 17 появляется сигнал высокого уровня, поступающий на входы инвертора 23 и элемента 24. При отсутствии сигнала горизонтальной координатной выборки на обоих входах элемента ИЛИ 25 логические нули и сигнал нулевого уровня с его выхода, поступающий на управляющие входы формирователей 28 и 8, запрещает выдачу информации с триггеров 26 и 27 на шины 16. Появление сигнала горизонтальной координатной выборки на шинах 14 влечет появление сигнала разрешения выдачи информации на управляющих входах формирователей 28 и 8 и одновременную выдачу хранимой информации всеми ячейками выбранной строки.

Отсутствие сигнала чтения на настроечном входе 17 переводит ячейку 7 в режим

хранения информации и решения задачи.

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

Через время окончания переходных

процессов во всех ячейках одной строки на

выходах 21 крайних правых ячеек 7 среды

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

Появление сигнала активного (нулевого)

0 уровня VjoH О (VjiH 0) на шинах 15 при единичном состоянии триггера 27 (26) пи.Л 1 (плцо 1} вызывает формирование блоком 10 настройки активного сигнала WIH 0 при условии, что только один из

5 триггеров 26 и 27 находится в единичном состоянии. Одновременное единичное состояние триггеров 26 и 27 означает одновременное вхождение j-й литеры в прямом и в инверсном виде в i-й дизъ0 юнкт, который в этом случае является тавтологией, (...а v a v... True) и не должен приниматься во внимание при решении задачи. Включение по монтажному ИЛИ обеспечивает удержание сигнала ак5 тивного уровня на шине 18 независимо от условий его формирования в остальных ячейках 7. Появление сигнала активного (нулевого) уровня WIH 0 на шине 18 вызывает формирование сигналов VJOH 0 (VjiH 0)

0 блоком 10 настройки при единичном состоянии триггера 27 (26). Включение по монтажному ИЛИ обеспечивает удержание активного уровня сигнала на шинах 15 независимо от других ячеек 7 среды. При появ5 лении сигнала RIB 1 на шине 19 и единичном состоянии любого из триггеров 26 или 27 формируется активный сигнал TJH 0 на шине 13, что означает наличие открытого ребра И-ИЛИ графа. Монтажное

0 ИЛИ для шины 13 обеспечивает сохранение сигнала TJH 0 независимо от других ячеек, что позволяет реализовать правило: ИЛИ- вершина открыта, если открыто хотя бы одно входящее в нее ребро.

5 Появление сигнала TJH 1 на шине 13 или наличие любого сигнала QioH 1 или Q.J1H 1 на шинах 16 при единичном состоянии любого из триггеров вызывает формирование пассивного сигнала (RIB 0) на шине 19. Прямое кодирование сигнала RIB и

включение по монтажному ИЛИ ячеек 7 к шине 19 позволяет одной ячейке 7 удержать сигнал Яш 0 на шине независимо от его значения а других ячейках 7, Тем самым обеспечивается выполнение правила: И- вершина недоступна, если закрыто хотя бы одно входящее в нее ребро.

Это правило эквивалентно приведенному ранее: И-вершина доступна, если открыты все входящие в нее ребра.

Формула изобретения Устройство для решения задач на графах, содержащее блок задания матрицы прямого вхождения литер в дизъюнкты, блок проверки достижимости И-вершин графа и блок задания матрицы инверсного вхождения литер в дизъюнкты, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения решения задач автоматического доказательства теорем, в него введены блок элементов ИЛИ и блок определения терминальных вершин, причем выход значения (К,М)-го элемента блока задания матрицы прямого вхождения литер

в дизъюнкты (К 1Л, где Л - количество

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

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

блока определения терминальных вершин и блока проверки достижимости И-вершин графа.

«

.§

Изобретение относится к вычислительной технике и может быть использовано для анализа баз знаний и решения задач логического вывода. Целью изобретения является расширение функциональных возможностей устройства за счет решения задач автоматического доказательства теорем. Устройство содержит блок 1 задания матрицы прямого вхождения литер в дизъюнкты, блок 2 проверки достижимости И- вершин графа, блок 3 элементов ИЛИ, блок 4определения терминальных вершин, блок 5задания матрицы инверсного вхождения литер в дизъюнкты, выходы 6 признаков доказанности высказываний устройства. Перед началом работы в блоки 1, 5 заносят информацию из базы знаний и целевой дизъюнкт, который является ключом поиска в базе знаний. При этом на соответствующем ему выходе 6 формируется сигнал, определяющий противоречивость целевого дизъюнкта дизъюнктам базы знаний. Устройство может быть выполнено в виде однородной структуры. 1 табл., 5 ил.