Устройство для решения задач на графах

Устройство для решения задач на графах

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК. (si)s G 06 F 15/419

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

,дт; ц)-;;

ОПИСАНИЕ ИЗОБРЕТЕНИ

) а

К АВТОРСКОМУ СВИДЕТЕЛ6СТВУ (21) 4483934/24 (22) 16.09.88 (46) 07,09.91. Бюл. hk 33 (72) В.П.Кириллов и А.А.Умбиталиев (53) 681,333(088.8) (56) Чень Ч„Ли Р. Математическая логика и автоматическое доказательство теорем".М.:

Наука, 1983, Авторское свидетельство СССР

М 1357972, кл. G 06 F 15/20. 1985. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано.для анализа баз знаний и решения задач логического вывода. Целью изобретения является расширение функциональных возможностей устройства за счет решения

„„. >ОÄÄ 1675907 А1 задач автоматического доказательства теорем. Устройство содержит блок 1 задания матрицы прямого вхождения литер в диэьюнкты, блок 2 проверки достижимости Ивершин графа, блок 3 элементов ИЛИ, блок

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

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

1675907

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

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

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

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

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

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

НЕ 23, элемент И 24, элемент ИЛИ 25, триггер 26, триггер 27 и инвертирующий шинный преобразователь 28.

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

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

А1 А2 Аз A4AsAsAp=

= (а v Ь v с) (-е v d v g) (- f ч а) (gva) e" d:, (1) где знак означает отрицание высказывания. При этом база знаний до решения задачи содержит дизъюнкты Ai-As, являющиеся описанием некоторой проблемной области (знаниями а ней ;. Отрицание целевого дизъюнкта Ао доба вл яется в базу знаний на этапе решения задачи. Следует отметить, что знания о предметной области в баэ j знаний вно.ятся экспертами (людьми — специалистами в этой области), а целевой дизьюнкт вводится пользователем интеллектуальной системы и является вопросом к этой системе. Таким образом, для указанного примера А1 — Ac — долговременная информация в базе знаний, а А,— временная с той точки зрения, что после решения задачи - Ap должен быть удален.

Каждый дизъюнкт может быть преобразован в множество предложений (импликаций) типа предложений Хорна, однако в общем виде таковыми не являющимися.

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

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

А1= {a Ь са с- -Ьb с а};

А2 .-(е d, е 9- -d, d g e};

Аз >(f a а — fj

A4 = (g а, a- g}, А5 =>{ е-, е};

As (d, ñ1j, где Ф означает соответствие.

Целевой дизъюнкт Ар является ключом поиска в базе знаний, он же определяет какими предложениями будут представлены дизъюнкты при решении задачи, Из всех множеств предложений сначала выбираются толь;<о те предложения, заключения которых совпадают с Ао, Затем из оставшихся предложений выбираются такие, заключения которых входят в условия ранее выбранных предложений. Процесс выбора предложений продолжается до тех пор, пока не будут выбраны предложения, не имеющие условий (соответствующие А5 и As в нашем примере), а также, если не найдется предложений с заключениями, входящими в условия ранее выбранных предложений (в примере нет предложений с заключениями

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

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

Таким образом, формуле Ar Az Аз

А4 As As Ао соответствует множество предло>кений{а" b c,е б- 9, 1- а,ц- а, - е, - dj, выбранных с помощью ключа с -, Эти предложения образуют И-ИЛИ граф, представленный на фиг. 4.

1675907

Ъ

Для записи единицы в триггеры 26 заданных ячеек достаточно сформировать единичные значения сигналов xi . уев на соответствующих адресных шинах 14. Для за- 5 писи нуля в триггер 26, до подачи сигналов на адресные шины, необходимо сформировать сигнал VI н низкого уровня на соответствующей шине 15. Аналогично производится запись в триггеры 27 заданВершины с и g И-вершины (помечены дугой), а ИЛИ-вершина(без дуги). Вершины

b u f закрытые, а е и d открытые терминальные вершины; С вЂ” корневая (целевая) вершина. Открытые терминальные вершины соответствуют фактам из базы знаний (предложениям без условий - е и - б), а закрытые терминальные вершины соответствуют отсутствию фактов в базе знаний (нет предложений с заключениями f и b}.

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

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

М = 1Im jÄl I. где i =О, и; j =1, h; К=01, где n — число дизъюнктов в задаче (в нашем случае и = 7); h = l(a,Ь,с,d,е,f,g) I = 7 — количество атомов в формуле (1).

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

mp)p = 1, Гп020 = 1, гп030 = 1, п1140 = 1, Ю150 = 1, m17) = 1, m21) = 1, ГП260 = 1, m31) = 1, пъ370 = 1, гп451 = 1, m54) = 1, m63p = 1.

В результате матрица М имеет вид, представленный на фиг, 5. Таким образом, для решения данной задачи необходима однородная структура, состоящая иэ n 7 строк и h > 7 столбцов заявляемых ячеек. При атом, в единичном состоянии должны находиться триггеры 26 в ячейках с индексом ОЗ.

17, 21, 31, 45 и 54, а также триггеры 27 в ячейках с индексами 01, 02, 14, 15, 26, 37 и

63. Все названные триггеры должны быть в нулевом состоянии.

5 ных ячеек, при этом записываемая информация подается сигналом VI, на шину 15, Состояние триггеров 26 и 27 всех ячеек однородной структуры не изменяется в течение всего времени решения задачи. После записи информации в триггеры ячеек, через время, обусловленное переходными процессами, на шинах 21 появляются сигналы

ВЫСОКОГО УРОВНЯ, 0407вых в, 0507вых в 0607вых в ВЫСОКОГО урОВНя. СИГНаЛЫ D4)7evx в, 05|7вых

0617вых в На ШИНаХ 21 ОСтаНутСя НИЗКОГО уровня. С этого момента однородная структура готова к решению задачи.

Пуск однородной структуры осуществляется в три этапа: в строке 6 однородной структуры на шину 12 подать сигнал М6 высокого уровня, что запретит выработку сигнала для строки 6, содеРжащий пРизнак m630 =- 1, соответствУющий корневой вершине И-ИЛИ графа, В столбце 3 однородной структуры податЬ СИГНаЛ Ч3 н = О (аКтИВНОГО урОВНя) ИЛИ в строке 6 подать сигнал шбн = О, что все раВНО ПрИВОдИт К ВЫрабОтКЕ Чз н-=О. ПОяВЛЕНИЕ СИГНаЛа Ч31 н = О ПрИВЕдЕт К ПОяВЛЕнию сигналов шбн = О, вь = О, и н = О, вэн =

Мн = О. Обн = 0 и Ч11н = 0 Ч21 н = О, V6) н = Î, V7) н = 0 V5) н = 0, V4) н = О.

В выбранных строках (й н = О) однородной структуры, содержащих однолитерные диэъюнкты, соответствующие открытым терминальным вершинам И-ИЛИ графа. подать сигналы Ri B = 1. Для рассматриваемого примера следует подать сигналы R4 B = 1 и

R5f3 1 .

Высокие уровни сигналов R4 B приведут к появлению сигналов Т4 „= О и Т5 „= О, что в свою очередь, приведет к выработке сигналов R< g = 1, Т7„= О Кз В= 1 и Т1Н = О, и описывающим значения переменных Ri и TI, кодируемых сигналами Rip и Тщ. Сигнал

К2в равен нулю в виду того, что Q6 н (вершина f — закрытая терминальная вершина), однако значение R2g = О не окажет влияния на формирование Т1н, поскольку

Т1н = О удерживается на шине активным значением сигнала R3 = 1, По причине02н = 1(вершина Ь также закрытая терминальная вершина) сигнал Т2н = 1 и Rpg =О.

В результате, значение сигнала Тзн = 1 остается равным единице. Сигнал Тзп=1 соответствует условию недоступности корневой вершины С И-ИЛИ графа, Таким образом, формула (1) А1 А2 Аэ А4 А5 А6 Ao =

1,675907

= (- d v Ü vñ) (- э ™ d v g)(f v a)

{ g ч а)"е d " с не противоречива. Это означает, что А = с не является логическим следствием дизъюнктов А1 — Ае.

Следует отметить, что третий этап пуска однородной структуры не является обязательным для рассмотренного примера, так как значения сигналов Rqg u Rgg и без их установки единичного уровня. Однако для решения задач в предметных областях с быстро изменяющимися данными, вместо коррекции базы знаний в соответствии с обстановкой, возможно существующие факты отмечать сигналами й;е, а отсутствующие — сигналами Вьц, = О, в соответствии с динамикой их изменения.

Элемент И 22 предназначен для выработки сигнала записи информации в триггеры 26 и 27 при одновременном появлении сигналов координатной выборки на входах

14. Инвертор 23, элемент 24, элемент ИЛИ

25 образуют схему управления ячейкой 7 при чтении хранимой в ней информации, При появлении сигнала горизонтальной выборки на входах 14 и сигнала "чтения" на входе 17 схема разрешает задачу информации с триггеров 26 и 27 через инвертирующие преобразователи 28 и 8 на шины 16 ячейками строки однородной структуры, вы. бранной сигналом горизснтальной выборки, Триггеры 26 и 27 представляют собой синхронизируемые D-триггеры и предназначены для приема информации с шин 15 при появлении сигнала "Запись" с элемента

22 и хранения ее, Хранимая информация представляет собой признаки пн,1к, i = О, и;

j = 1,п, К = О, 1 вхождения j-й литеры в прямом или инверсном виде в i-й дизъюнкт.

Инвертирующие преобразователи 28 и

8 предназначены для выдачи информации с триггеров 26 и 27 на шины 16 и организации монтажного ИЛИ совместно с другими ячейками для признаков Ctji и Qi,.

Блок 9 формирования предназначен для формирования признака Ri — доступности И-вершины и признака Т -доступности

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

Блок 10 настройки предназначен для формирования сигналов Ч о1н, Ч)1н и мн.

Ячейки 7 одного столбца объединены общими шинами 15 признаков Чи и Vip по монтажному ИЛИ, а ячейки одной строки таким же образом объединены шиной 18 признака

ЧЧ, что позволяет каждой ячейке неэависи5

55 мо отдругих формировать сигналы Ч1 н, Чин ив н при возникновении необходимых условий.

Блок 11 определения однолитерного дизъюнкта вырабатывает сигналы Оь вц в и

Di>isuxe на шинах 21 в зависимости от входных сигналов Dt i xa и Ч)11 хь на шинах 20.

Работа блока описывается таблицей,.

Комбинация О цвхв О!о)вхц (1,0) невозможна.

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

Шина 12 маскирования предназначена для передачи сигнала М в, запрещающего выработку признака однолитерного дизьюнкта в строке, описывающей корневую вершину И-ИЛИ графа, Шина 13 признака открытого ребра предназначена для передачи сигналов, соответствующих наличию открытого ребра или открытой ИЛИ-вершины И-ИЛИ графа, Т н по всем ячейкам одного столбца матрицы ячеек, За логическую единицу на шине 13 принят низкий уровень электрического сигнала, что связано с применением элементов, обеспечивающих включение по монтажному ИЛИ. Шины 14 координатной выборки содержат горизонтальную шину Х и вертикальную шину У, обеспечивающие адресацию ячейки при выполнении операций записи и чтения информации.

Шины 15 вертикальной настройки предназначены для передачи на входы триггеров

26 и 27 записываемой информации при работе ячейки в режиме записи и передачи сигналов псиска вхождения j-й литеры в прямой (Vi>p = О) или в инверсном (Чин = О) виде в дизъюнкты решаемой задачи. Сигналы Чин и V(pp определяют наличие ребер в

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

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

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

1675907

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

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

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

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

Входные шины левой ячейки 7 являются 25 входными соседней с ней правой ячейки.

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

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

В режиме записи по шинам вертикальной настройки 15 подается записываемая 35 информация о вхождении )-й литеры в l-й дизьюнкт прямом {Ч 1н = 1) или в инверсном (V1< н = I) виде на 0-входы триггеров 26 и 27.

При одновременном появлении сигналов координатной выборки на шинах 14 форми- 40 руется сигнал разрешения записи элементов И 22, поступающий на С-входы триггеров 26 и 27 и производится запись информации, В режиме чтения на настроечном входе 45

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

Появление сигнала горизонтальной коор- 55 динатной выборки на шинах 14 влечет появление сигнала разрешения выдачи информации на управляющих входах фор мирователей 28 и 8 и одновременную выдачу хранимой информации всеми ячейками выбранной строки, Отсутствие сигнала чтения на настроечном входе 17 переводит ячейку 7 в режим хранения информации и решения задачи, После записи информации в триггеры

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

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

Появление сигнала активного (нулевого) уровня Viol = О Я1н = О) на шинах 15 при единичном состоянии триггера 27 (26) ец = 1 (mph = 1) вызывает формирование блоком 10 настройки активного сигнала

Wiv = О при условии, что только один из триггеров 26 и 27 находится в единичном состоянии. Одновременное единичное состояние триггеров 26 и 27 означает одновременное вхождение j-й литеры в прямом и в инверсном виде в 1-й дизьюнкт, который в этом случае является тавтологией, (...-a ч а ч...= True) и не должен приниматься во внимание при решении задачи. Включение по монтажному

ИЛИ обеспечивает удержание сигнала активного уровня на шине 18 независимо от условий его формирования в остальных ячейках 7. Появление сигнала активного (нулевого) уровня Wlp = О на шине 18 вызывает формирование сигналов Ч)он = О (1/)1н = 0) блоком 10 настройки при единичном состоянии триггера 27 (26), Включение по монтажному ИЛИ обеспечивает удержание активного уровня сигнала на шинах 15 независимо от других ячеек 7 среды, При появлении сигнала R g = 1 на шине 19 и единичном состоянии любого из триггеров

26 или 27 формируется активный сигнал

Т н = О на шине 13, что означает наличие открытого ребра И-ИЛИ графа. Монтажное

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

Появление сигнала Т1н = 1 на шине 13 или наличие любого сигнала QioH = 1 или

О н = 1 на шинах 16 при единичном состоянии любого из триггеров вызывает формирование пассивного сигнала (Rie = О) на шине 19. Прямое кодирование сигнала Rie u

1575907 »;j7i@7» 6

1

1

0

1

С

С

С

0 а

75 76 72

tZ

"8

»9

»»у

121

zî»

12

78

19

7»»

А7»В 2 вкл1очение по монтажному ИЛИ ячеек 7 х шине 19 позволяет одной ячейке 7 удержать сигнал Й»в = О на шине независимо от его значения в других я ейках 7. Тем самым обеспечивается выпслнение правила: _#_- 5 вершина недоступна, если закрыто хотЯ б61 одно входящее в нее ребро, Это правило эквивалентно приведенному ранее: И-вершина доступна, если открыты все входящие в нее ребра. 10

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

Устройство для решения задач на графах, содержащее блок задания матрицы прямого вхождения литер в диэъюнкты, блок проверкидостижимости И-вершин гра- 15 фа и блок задBHvif7 матрицы инверсного вхождения литер в диэъюнкты, О т л и ч а ющ е е с я тем, чго, с целью расширения функциональнь»х воз» Ожностей устройства за счет обеспечения решения задач автома- 20 тическОгО дОказательства теорем, в него введены блок элементов ИЛИ и блок определения терминальных вершин, причем выход значения (K,Ó)-го элемента блока задания матрицы прямого вхождения ЛИтер 25 в диэъюнкты (K = 1, ..., Л, где Л вЂ” количество литер в базе знаний; V =:=, ..., 17, где D-количество диэъюнктов в базе знаний) подключен к входам признаков принадлежности К-й вершины M-й группе вершин, входящих в И-вершину блока проверки достижимости И-вершин графа и блока определения терминальных вершин, выход признака принадлежности К-й вершины множеству терминальных вершин которого подключен к К-му разряду первого информационного входа блока элементов ИЛИ, К-й разряд информационного выхода которого является выходом признака доказанности К-го высказывания устройства и подключен к входу опроса К-й входящей вершины блока проверки достижимости Ивершин графа, выход признака достижимости К-й И-вершины которого подключен к

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

И-верШин графа.

1675907

1675907 О ь>

%1(!

%ь о т Е

11 !!

Составитель А, Мишин

Техред M,Ìoðãåíòàë Корректор Э, Лончакова

Редактор ГГербер

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

Заказ 3004 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5