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

, гЯ ПИС ИЗОБРЕТЕ ематическая логика и ател ьство теорем,"М.: фиг.1 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано.для анализа баз знаний и решения задач логического вывода. Целью изобретения является расширение функциональных возможностей устройства за счет решения 5 О 1675907 задач автоматического доказательства теорем, Устройство содержит блок 1 задания матрицы прямого вхождения литер в диэьюнкты, блок 2 проверки достижимости И- вершин графа, блок 3 элементов ИЛИ, блок 4 определения терминальных вершин, блок 5 задания матрицы инверсного вхождения литер в дизьюнкты, выходы 6 признаков доказанности высказываний устройства. Перед началом работы в блоки 1, 5 заносят информацию из базы знаний и целевой дизьюнкт, который является ключом поиСка в базе знаний. При этом на соответствующем ему выходе 6 формируется сигнал, определяющий противоречивость целевого дизьюнкта дизьюнктам базы знаний, Устройство может быть выполнено в виде однородной структуры, 1 табл 5 ил.5 10 15 20 30 35 40 45 Изобретение относится к вычислительной технике и может быть использовано для анализа баз знаний и решения задач логического вывода.Целью изобретения является расширение функциональных возможностей устройства за счет решения эада 1 автоматического доказательства теорем,На фиг, 1 представлена функциональная схема устройства; на фиг, 2 - пример реализации устройства в виде однороцной структуры; на фиг, 3- функциональная схема ячеек однородной структуры; на фиг. 4 - графичес".ое представление И-ИЛИ графа; на фиг,5 - матричное представление И-ИЛИ графа,Устройство содержит блок 1 задания матрицы прямого вхождения литер в дизьюнкты, блок 2 проверки достижимости И- вершин графа, блок 3 элементов ИЛИ, блок 4 определения терминальных вершин, блок 5 задания матрицы инверсного вхождения литер в дизъюнкты, выходы 6 признаков доказанности вьсказь 1 ваний устройства, ячейки 7, инвертирукщий шинный преобразователь 8, блок 9 формирования результата, блок 10 настройки, блок 11 определения однолитерного дизъюнкта, вход 12 маскирования, вход/выход 13 признака открытого ребра, входы 14 координатной выборки, входы 15 вертикальной настройки, информационные входы/выходы ",6, настроечный вход 17, вход/выход 18 горизонтальной настройки, вход/выход признака открытой вершины 19, входы 20 признака однолитерного дизьюнкта, выходы 20 признака одно- литерного дизъюнкта, элемент И 22,элемент НЕ 23, элемент И 24, элемент ИЛИ 25, триггер 26, триггер 27 и инвертирующий шинный преобразователь 28,Устройство работает следующим образом.Пусть необхоцимо решить задачу логического вывода, напримео для фс рмулыА 1 АлА лА лА лА л А=( а ч Ь ч с) ( -е ч С ч д) (" 1 ч а) л (,д, а).л л, лгде знак означает отрицание высказывания. При этом база знаний до решения задачи содержит дизъюнкты А 1-Аб, являющиеся описанием некоторой проблемной области (знаниями о ней;. Отрицание целевого дизъюнктаАо доба вл яется в базу знаний на этапе решения задачи. Следует отметить, что знания о предметной области в базу знаний вносятся экспертами (людьми - специалистами в этой области), а целевой дизъюнкт вводится пользователем интеллектуальной системы и является вопросом к этой системе. Таким образбм, для указанного примера А 1 - Аб - долговременная информация в базе знаний, а А, - временная с той точки зрения, что после решения задачи - Ао должен быть удален.Каждый дизъюнкт может быть преобразован в множество предложений (импликаций) типа предложений Хорна, однако в общем виде таковыми не являющимися.В какое предложение будет преобразован дизъюнкт зависит от того, какая литера из дизъюнкта выбрана в качестве заключения предложения, Выбирая поочередно все литеры диэъюнкта заключением предложения, получаем множество всех предложений, соответствующих этому дизъюнкту.Таким образом.А 1 .-(а Ь-с, а с- -Ь, Ьс- а); А 2.-(е о-д, е до, б - д- е); Аз =(1- а,-а - фАа =:(д-а,-а- -д);А 5 =( е, -е);Аб( б.,-б),где Ф означает соответствие.Целевой дизъюнкт Ао является ключом поиска в базе знаний, он же определяет какими предложениями будут представлены дизъюнкты при решении задачи, Из всех множеств предложений сначала выбираются только те предложения, заключения которых совпадают с Ао, Затем из оставшихся предложений выбираются такие, заключения которых входят в условия ранее выбранных предложений. Процесс выбора предложений продолжается до тех пор, пока не будут выбраны предложения, не имеющие условий (соответствующие А 5 и Аб в нашем примере), а также, если не найдется предложений с заключениями, входящими в условия ранее выбранных предложений (в примере нет предложений с заключениями Ь и 1). Множество выбранных предложений (выбранные предложения подчеркнуты) образуют структуру, описываемую И-ИЛИ графом,Предложения с уникальными заключениями образуют И вершины графа, причем заключение соответствует исходящему ребру вершины, а условия входящим ребрам, Несколько предложений с одинаковыми заключениями образуют ИЛИ вершину,Таким образом, формуле А 1 " А 2Аз " А 4 Аб Аб " Ао соответствует множество предложений(а Ь-с, е б-д, 1-а, д-а, -е, -б), выбранных с помощью ключа с -, Эти предложения образуют И-ИЛИ граф, представленный на фиг. 4.Ъ 5 10 15 Для записи единицы в триггеры 26 заданных ячеек достаточно сформировать единичные значения сигналов хв. ув на соответствующих адресных шинах 14. Для за писи нуля в триггер 26, до подачи сигналов на адресные шины, необходимо сформировать сигнал Ч 1 н низкого уровня на соответствующей шине 15. Аналогично производится запись в триггеры 27 заданВершины с и 9 И-вершины (помеченыдугой), а ИЛИ-вершина(без дуги), ВершиныЬ и 1 закрытые, а е и б открытые терминальные вершины; С - корневая (целевая) вершина. Открытые терминальные вершинысоответствуют фактам из базы знаний(предложениям без условий - е и -ф б), азакрытые терминальные вершины соответствуют отсутствию фактов в базе знаний(нет предложений с заключениями 5 и Ь).В однородной структуре для хранениязнаний и синтеза И-ИЛИ графа используются дизъюнкты - прообразы предложенийввиду того, что дизъюнкты хранить проще иэкономнее, Все сказанное выше, при описании процессов порождения И-ИЛИ графа,справедливо и для матричной модели с учетом следующих условий: /каждая строка матрицы - дизъюнкт (Ивершина графа);несколько дизъюнктов, имеющие одинаковые литеры (обязательно с одним знаком), могут образовать ИЛИ-вершину графа(столбец матрицы, содержащий более одной единицы в одном подстолбце);ребру в графе соответствует наличиеконтрарных (с разными знаками) пар литерв диэъюнктах.М=п 1 ц . где =О, и;) =1, и; К=01,где и - число дизъюнктов в задаче (в нашемслучае и = 7); Ь = (а,Ь,с,б,е9)= 7 - количество атомов в формуле (1).Таким образом для представленногопримерап 1010 = 1, Гп 020 = 1, гп 030 = 1, гп 140 = 1,гп 150 = 1, п 1171 = 1, п 1211 = 1, Гп 260 = 1,гпз 11 = 1, пъ 370 = 1, гп 451 = 1, п 1541 = 1,гп 630 = 1.В результате матрица М имеет вид, представленный на фиг, 5. Таким образом, длярешения данной задачи необходима однородная структура, состоящая иэ и7 строки Ь7 столбцов заявляемых ячеек. Приэтом, в единичном состоянии должны находиться триггеры 26 в ячейках с индексом 03,17, 21, 31, 45 и 54, а также триггеры 27 вячейках с индексами 01, 02, 14, 15, 26, 37 и63. Все названные триггеры должны быть внулевом состоянии,20 25 30 35 40 45 50 5 ных ячеек, при этом записываемая информация подается сигналом Ч 1 о н на шину 15, Состояние триггеров 26 и 27 всех ячеек однородной структуры не изменяется в течение всего времени решения задачи, После записи информации в триггеры ячеек, через время, обусловленное переходными процессами, на шинах 21 появляются сигналы ВЫСОКОГО урОВНя, 0407 вых в, 0507 вых в 0607 вых , ВЫСОКОГО урОВНя. СИГНаЛЫ 0417 вых в, 0517 вых в, 0617 вых в На ШИНаХ 21 ОСтаНутСя НИЗКОГО уровня. С этого момента однородная структура готова к решению задачи. Пуск однородной структуры осуществляется в три этапа:в строке 6 однородной структуры на шину 12 подать сигнал Мб высокого уровня, что запретит выработку сигнала для строки 6, содержащий признак гпбз 0 = 1, соответствующий корневой вершине И-ИЛИ графа,В столбце 3 однородной структуры по- датЬ СИГНаЛ ЧЗ 1 н = 0 (аКтИВНОГО урОВНя) ИЛИ В СтрОКЕ 6 ПОдатЬ СИГНаЛ Вбн = О, Чта ВСЕ раВНО ПрИВОдИт К ВЫрабОтКЕ ЧЗ 1 н=О. ПОяВЛЕНИЕ СИГНаЛа ЧЭ 1 н = 0 ПрИВЕдЕт К ПОяВЛЕ- нию сигналов собн = О, с 01 н = О, й 2 н = О, М 3 н =О, СО 4 н О, Обн 0 И Ч 11 н = О, Ч 21 н = О, Ч 61 н=О, Ч 71 н=О,Ч 51 н=О, Ч 41 н=О.В выбранных строках (вн = О) однородной структуры, содержащих однолитерные диэъюнкты, соответствующие открытым терминальным вершинам И-ИЛИ графа. подать сигналы й= 1. Для рассматриваемого примера следует подать сигналы й 4 е = 1 и й 5 е=1.Высокие уровни сигналов й 4 в приведут к появлению сигналов Т 4 = 0 и Т 5 = О, что в свою очередь, приведет к выработке сигналов й 1 Б = 1, Т 7 н = О йэ В= 1 и Т 1 Н = О, и описывающим значения переменных й 1 и Т, кодируемых сигналами йв и Т 1 н, Сигнал й 2 в равен нулю в виду того, что 661 н (вершина 1 - закрытая терминальная вершина), однако значение й 2 р = 0 не окажет влияния на формирование Т 1 н, поскольку Т 1 н = О удерживается на шине активным значением сигнала йзв = 1, По причине 02 н = 1(вершина Ь также закрытая терминальная вершина) сигнал Т 2 н = 1 и йов -- О. В результате, значение сигнала Тзн = 1 остается равным единице. Сигнал Тзп=1 соответствует условию недоступности корневойвершины С И-ИЛИ графа,Таким образом, формула (1)А 1 А 2 АЗ А 4 А 5 Аб Ао =(- 9 ча)"е б " сне противоречива. Этоозначает, что Ао = с не является логическимследствием дизъюнктов А 1 - А 6,Следует отметить, что третий этап пускаоднородной структуры не является обязательным для рассмотренного примера, таккак значения сигналов Влв и В 5 в и без ихустановки единичного уровня. Однако длярешения задач в предметных областях с быстро изменяющимися данными, вместо коррекции базы знаний в соответствии собстановкой, возможно существующие факты отмечать сигналами В;в, а отсутствующие - сигналами Вв, = О, в соответствии сдинамикой их изменения,Элемент И 22 предназначен для вцработки сигнала записи информации в триггеры 26 и 27 при одновременном появлениисигналов координатной выборки на входах14, Инвертор 23, элемент 24, элемент ИЛИ25 образуют схему управления ячейкой 7при чтении хранимой в ней информации,При появлении сигнала горизонтальной выборки на входах 14 и сигнала "чтения" навходе 17 схема разрешает задачу информации с триггеров 26 и 27 через инвертирующие преобразователи 28 и 8 на шины 16ячейками строки однородной структуры, выбранной сигналом горизснтальной выборки, Триггеры 26 и 27 представляют собойсинхронизируемые Р-триггеры и предназначены для приема информации с шин 15при появлении сигнала "Запись" с элемента22 и хранения ее, Хранимая информацияпредставляет собой признаки в,1 к, = О, и;) = 1 и, К = О, 1 вхождения )-й литеры впрямом или инверсном виде в 1-й дизьюнкт.Инвертирующие преобразователи 28 и8 предназначены для выдачи информации стриггеров 26 и 27 на шины 16 и организациимонтажного ИЛИ совместно с другими ячейками ДлЯ пРиэнакав С 1 и Оо.Блок 9 формирования предназначендля формирования признака В - доступности И-вершины и признака Т -доступностиИЛИ вершины. Ячейки 7 одной строки включены по признакам В на общие шины 19, аячейки одного столбца обьединены общейшиной 13 по признакам Т, Общие шиныпозволяют реализовать монтажное ИЛИдля обоих признаков,Блок 10 настройки предназначен дляформирования сигналов Чо 1 н, Ч 11 н и вн.Ячейки 7 одного столбца объединены общими шинами 15 признаков Чи и Чо по монтажному ИЛИ, а ячейки одной строки такимже образом обьединены шиной 18 признакаЧЧь что позволяет каждой ячейке неэависи 5 10 15 20 25 ЗО 35 40 45 50 55 мо отдРУгих фоРмиРовать сигналы Чжон, ЧРн ив н при возникновении необходимых условий.Блок 11 определения однолитерного дизъюнкта вырабатывает сигналы Ро 1 выхв и Ри 18 ыхв на шинах 21 в зависимости от входных сигналов Рьехв и Чцхь на шинах 20. Работа блока описывается таблицей,Комбинация РцвхвРонхв (1,0) невозможна,Признаком наличия однолитарного диэъюнкта в 1-й строке служит комбинация сигналов Ръыхв = 1 и Рщнцхв = 0 на выходе крайней правой ячейки 7 строки, что соответствует наличию открытой терминальной вершины в этой строке матрицы ячеек 7,Шина 12 маскирования предназначена для передачи сигнала Мв, запрещающего выработку признака однолитерного дизьюнкта в строке, описывающей корневую вершину И-ИЛИ графа,Шина 13 признака открытого ребра предназначена для передачи сигналов, соответствующих наличию открытого ребра или открытой ИЛИ-вершины И-ИЛИ графа, Тн по всем ячейкам одного столбца матрицы ячеек,За логическую единицу на шине 13 принят низкий уровень электрического сигнала, что связано с применением элементов, обеспечивающих включение по монтажному ИЛИ. Шины 14 координатной выборки содержат горизонтальную шину Х и вертикальную шину У, обеспечивающие адресацию ячейки при выполнении операций записи и чтения информации,Шины 15 вертикальной настройки предназначены для передачи на входы триггеров 26 и 27 записываемой информации при работе ячейки в режиме записи и передачи сигналов псиска вхождения )-й литеры в прямой (Ч;1 н = 0) или в инверсном (Чьн= О) виде в дизьюнкты решаемой задачи. Сигналы Чин и Чан определяют наличие ребер в И-ИЛИ графе или наличие связей в эквивалентной комбинационной схеме. Все ячейки одного столбца подключаются к шинам 15 по монтажному ИЛИ.Информационные шины 16, обьединяющие по монтажному ИЛИ все ячейки одного столбца, предназначены для передачи сигналов 01 он и 01 н, несущих информацию о пустых подстолбцах матрицы, что необходимо для определения закрытых терминальнцх вершин И-ИЛИ рафа, а также для выдачи хранимойячейкой 7 информации о режиме чтения,Настроечный 17 вход ячейки 7 представляет собой шину, объединяющую всеячейки однородной структуры, Наличие наней сигнала высокого уровня соответствуетпереводу ячеек 7 в режиме чтения, а отсутствие сигнала переводит ячейки в режимрешения задач, 5Настроечная шина 18 объединяет помонтажному ИЛИ ячейки одной строки ипредназначена для передачи сигналов выбора строки (Юн, соответствующих вхождению И-вершины в И-ИЛИ граф, 10Шина 16 признака открытой вершиныобъединяет по монтажному ИЛИ ячейки 7одной строки матрицы и предназначена дляпередачи сигналов Вв о доступности И-вершины И-ИЛИ графа. Для нее характерно, в 15отличие от других шин, прям е кодированиесигналов.Входные 20 и выходные 21 шины признака однолитерного дизьюнкта предназначены для последовательной передачи 20сигналов от левых к правым ячейкам 7 однойстроки о хранимой в них информации с. целью определения открытых терминальных вершин И-ИЛИ графа.Входные шины левой ячейки 7 являются 25входными соседней с ней правой ячейки.Входные шины крайней левой ячейки каждой строки заземлены. Выходные шиныкрайней правой ячейки каждой строки служат для формирования признака наличия ЗОоднолитерного дизьюнкта в этой строкематрицы.Ячейка работает следующим образом.В режиме записи по шинам вертикальной настройки 15 подается записываемая 35информация о вхождении )-й литеры в 1-йдизьюнкт прямом (Ч 1 н = 1) или в инверсном(Ч 10 н = 1) виде на О-входы триггеров 26 и 27.При одновременном появлении сигналовкоординатной выборки на шинах 14 формируется сигнал разрешения записи элементов И 22, поступающий на С-входытриггеров 26 и 27 и производится записьинформации,В режиме чтения на настроечном входе 4517 появляется сигнал высокого уровня, поступающий на входы инвертора 23 и элемента 24. При отсутствии сигналагоризонтальной координатной выборки наобоих входах элемента ИЛИ 25 логические 50нули и сигнал нулевого уровня с его выхода,поступающий на управляющие входы формирователей 28 и 8, запрещает выдачу информации с триггеров 26 и 27 на шины 16.Появление сигнала горизонтальной координатной выборки на шинах 14 влечет появление сигнала разрешения выдачиинформации нэ управляющих входах формирователей 28 и 8 и одновременную выдачу хранимой информации всеми ячейками выбранной строки,Отсутствие сигнала чтения на настроечном входе 17 переводит ячейку 7 в режим хранения информации и решения задачи,После записи информации в триггеры 26 и 27 крайние левые ячейки 7 каждой строки формируют сигналы нэ шинах 21, которые вызывают последовательное срабатывание блоков определения однолитерных дизьюнктов 11 во всех ячейках 7 среды.Через время окончания переходных пооцессов во всех ячейках одной строки на выходах 21 крайних правых ячеек 7 среды устанавливаются сигналы, соответствующие наличию или отсутствию в строках однолитерных дизьюнктов и среда готова к решению задач.Появлениесигнала активного(нулевого) уровня Ч 10 н = 0 Я 1 н = 0) на шинах 15 при единичном состоянии триггера 27 (26) ец = 1 (ац = 1) вызывает формирование блоком 10 настройки активного сигнала ЧЧн = О при условии, что только один из триггеров 26 и 27 находится в единичном состоянии. Одновременное единичное состояние триггеров 26 и 27 означает одновременное вхождение )-й литеры в прямом и в инверсном виде в 1-й дизьюнкт, который в этом случае является тавтологией, ( а ч а ч.= Тле) и не должен приниматься во внимание при решении задачи. Включение по монтажному ИЛИ обеспечивает удержание сигнала активного уровня на шине 18 независимо от условий его формирования в остальных ячейках 7. Появление сигнала активного (нулевого) уровня М/н = 0 на шине 18 вызывает формирование сигналов Чон = О Я 1 н = 0) блоком 10 настройки при единичном состоянии триггера 27 (26), Включение по монтажному ИЛИ обеспечивает удержание активного уровня сигнала на шинах 15 независимо от других ячеек 7 среды, При появлении сигнала Яв = 1 на шине 19 и единичном состоянии любого из триггеров 26 или 27 формируется активный сигнал Т 1 н = 0 на шине 13, что означает наличие открытого ребра И-ИЛИ графа, Монтажное ИЛИ для шины 13 обеспечивает сохранение сигнала Тн = О независимо от других ячеек, что позволяет реализовать правило. ИЛИ- вершина открыта, если открыто хотя бы одно входящее в нее ребро.Появление сигнала Т 1 н = 1 на шине 13 или наличие любого сигнала ОоН = 1 или 01 н = 1 на шинах 16 при единичном состоянии любого из триггеров вызывает формирование пассивного сигнала (Яв = 0) на шине 19. Прямое кодирование сигнала Яв и1575907 а;иТ а в;1 Ьл Б 0 0 1 1 С С 1 С 1 О 0 а 0 1 15 7 Б гг го вкл 5 очениа по монтажному ИЛИ ячеек 7 кшине 19 позволяет одной ячейке 7 удержатьсигнал Вв = 0 на шина независимо от агозначения в других ячайках 7. Тем самымобеспечивается выпслнение правила: Ивершина недоступна, если закрыто хотя быодно входящеа в наа ребро,Это правило зквивалантнО приведенному ранее: И-вершина доступна, если открыты все входящие в нее ребра, 10Формула изобрзтенияУстройство для решения задач на графах, содержащее блок задания матрицыпрямого вхождения литер в диэъюнкты,блок проверкидостижимости И-вершин графа и блок задания матрицы инверсноговхождения литер в дизъюнкты, о т л и ч а ющ е е с я тем, что, с целью расширенияфункциональных возь ожностей устройстваза счет обеспечения решения задач автома. 20тического доказательства теорем, в наговведены блок элементов ИЛИ и блок определения терминальных вершин, причем выход значения К,У)-го элемента блоказадания матрицы прямого Вхождения литер 25в дизъюнкты (К = 1, Л, гда Л - количестволитер в базе знаний; У = 1,О, где г.г ". количество дизъюнктов в базе знаний) подключен к входам признаков принадлежности К-й вершины У-й группе вершин, входящих в И-вершину блока проверки достижимости И-вершин графа и блока определения терминальных вершин, выход признака принадлежности К-й вершины множеству терминальных вершин которого подключен к К-му разряду первого информационного входа блока элементов ИЛИ, К-й разряд информационного выхода которого является выходом признака доказанности К-го высказывания устройства и подключен к входу опроса К-й входящей вершины блока проверки достижимости И- вершин графа, выход признака достижимости К-й И-вершины которого подключен к К-му разряду второго информационного входа блока элементов ИЛИ, выход значения К,М)-го элемента блока задания матрицы инверсного вхождения литер в дизъюнкты подключен к входам признаков принадлежности К-й И-вершины М-й группе входящих вершин блока определения терминальных вершин и блока проверки достижимости И-верШин графа.1675907 Составитель А, МишинРедактор ГГербер Техред М,Моргентал ктор Э, Лончако зводственио-издательскиЧ комбинат "Патент", г, Ужгород, ул,Гагарина, 101 аказ 3004 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5