Russia, St.-Petersburg, Institute for Problems of Mechanical Engineering of RAS

The algebraic system named as Euler logic structure (E-structure) is designed to be a potential formal tool for simulation and analysis of natural reasoning. This structure may be used as a tool for many problems solution such as deductive and inductive inferences, and analyze collisions of cycle and paradox, and creation and examination of hypotheses etc. Here the E-structures are used as a tool for creation of cognitive multi-agents systems.

Россия, Санкт-Петербург, Институт проблем машиноведения РАН

Для моделирования естественных рассуждений разработана алгебраическая система, названная логической структурой Эйлера (E-структурой). На ее основе можно решать такие задачи, как дедуктивный и индуктивный вывод, анализ коллизий парадокса и цикла, формирование и проверка гипотез и т.д. В докладе предложено использовать E-структуры для создания когнитивных многоагентных систем.

Многие системы общения на естественном языке и некоторые технические системы можно выразить в виде совокупности отношений типа “объекты-свойства”, “вид-род”, “часть-целое”, “подмножество-множество”. Математически отношения этого типа изоморфны отношению включения множеств, которое по своим свойствам принадлежит классу отношений частичного порядка [1]. Обычно частично упорядоченные множества рассматриваются как объекты без операций. Для частного случая этих структур (решеток) введены операции inf и sup (нижняя и верхняя грани). Эти операции подобны операциям пересечения и объединения алгебры множеств, но не во всем соответствуют им. Понятие дополнение в решетках также не соответствует полностью одноименной операции алгебры множеств и даже не считается операцией, поскольку существуют решетки с неединственными дополнениями.

Рассматриваемая здесь система понималась вначале как обобщение силлогистики на основе алгебры множеств, расширяющее аналитические возможности естественных рассуждений [2,3]. Исследования свойств отношения частичного порядка в этой системе показали, что она не имеет аналогов. Это позволило дать ей новое название: логическая структура Эйлера или сокращенно — E-структура [4,5]. По сути это новый тип частично упорядоченных множеств, у которых введены универсальные правила вывода и операция дополнения, свойства которой соответствуют одноименной операции алгебры множеств. Эти особенности позволяют рассматривать данную систему как некоторую формализацию баз знаний (БЗ).

Структурными элементами БЗ на основе E-структур являются термины и суждения. Каждая отдельная E-структура может быть задана конечным множеством T терминов и некоторой совокупностью суждений, т.е. предложений типа

где литерал L_i (i = 0,1,2,…) является некоторым термином (T_i), либо его отрицанием (). Левая часть предложения (1) называется субъектом суждения, а литералы в правой части — предикатами суждения. Суждение с одним предикатом называется элементарным суждением. Связка “® ” здесь не импликация, а отношение частичного порядка, изоморфное отношению включения множеств.

Все свойства данной системы соответствуют свойствам алгебры множеств. Но имеется существенное отличие. В алгебре множеств предполагается, что в заданной системе множеств определены все возможные результаты операций с первоначально заданными одноэлементными множествами. В силу этого с точки зрения теории структур алгебра множеств рассматривается как полная решетка, содержащая 2^N компонент. Поэтому многие алгоритмы ее логического анализа имеют экспоненциальную сложность. В E-структурах эта изначально заданная или подразумеваемая сложность не имеет места — для заданных N компонент системы определяется дополнительно еще только N дополнений (или отрицаний) этих компонент. Этого вполне достаточно для постановки и решения с полиномиальной сложностью многих практически значимых задач. При этом в частных случаях не сохраняются свойства решеток и полнота, но остаются неизменными законы алгебры множеств и общие свойства отношения частичного порядка. В системе также допускаются термины, которым соответствуют бесконечные множества.

Различают корректные E-структуры, т.е. структуры с отношением частичного порядка со свойствами рефлексивности, транзитивности и антисимметричности и не содержащие терминов, соотносимых с пустым множеством, и некорректные E-структуры, у которых при выводе следствий появляются 1) циклы (коллизия цикла) или 2) отношения типа L_i® (коллизия парадокса). Коллизия цикла означает, что некоторые предположительно различные термины на самом деле эквивалентны, а коллизия парадокса указывает на то, что некоторые значимые по предположению термины при аналитическом продолжении вырождаются в пустое множество (? ).

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

Правила вывода, критерии и методы распознавания коллизий в E-структурах в точности соответствуют свойствам отношения включения множеств. Правилами вывода являются:

1) правило C (контрапозиции): из A® B выводится ® ;

2) правило T (транзитивности) из A® B и B® C выводится A® C.

Совокупность исходных суждений и всех следствий данной E-структуры названо CT-замыканием. С помощью CT-замыкания оценивается ее корректность и совместимость. При объединении двух и более E-структур можно оценить их взаимную совместимость с помощью построения общего CT-замыкания.

С помощью правил вывода можно получить не все следствия, а только общие суждения типа “Всем A присуще B, C, …”. В них содержатся только базовые термины, т.е. термины из множества T или их отрицания. Обобщением частных суждений с квантором “некоторые” является суждение W® (L₁&L₂&…), где литералу W соответствует новый термин, не содержащийся в T. Они названы экзистенциальными суждениями, поскольку в подходящей системе множеств они равносильны отношению S_1C S_2C …?  ? , где S_i — множество, соответствующее литералу L_i. Эти суждения выводятся уже не с помощью правил вывода C и T, а с помощью простого алгоритма восстановления главных фильтров E-структуры.

Любую корректную E-структуру можно неограниченно расширять, добавляя новых суждения и термины. Покрытием корректной E-структуры G является корректная E-структура G _C , в CT-замыкании которой содержится CT-замыкание G . Если в G _C не содержится только термины из G , то G _C является базовым покрытием G . Если для E-структуры G не существует другого базового покрытия кроме G , то такая E-структура называется полной. В полной E-структуре любое базовое суждение, не содержащееся в ее CT-замыкании, вызывает коллизию. В то же время для полных E-структур можно построить произвольное число корректных покрытий с новыми терминами.

Если E-структура H (возможно, состоящая из одного суждения) невыводима из G , но выводима из G _C , то она имеет статус корректной гипотезы для G . Для каждой корректной гипотезы H можно построить несовместную с ней гипотезу ~H , которая будет корректной относительно G . За счет добавления таких альтернативных пар гипотез в тождественные E-структуры можно получать множество корректных, но несовместимых друг с другом E-структур. Таким образом, за счет наращивания гипотез можно получить модель кумулятивного развития и дифференциации знаний, “ядром” которых является одна и та же E-структура G .

Неполнота систем рассуждения встречается нередко. Элементарными примером неполной системы является система из одного суждения типа A® (B, C). Интерпретацией этого суждения могут быть предложения типа “Все A характеризуются свойствами B и C” или “Множество A включено в пересечение множеств B и C”. Анализ неполноты этой простой системы методами E-структур показывает, что для нее формально корректными являются по отдельности базовые гипотезы B® C; C® B и ® C и соответствующие им контрапозиции.

На этом же примере можно показать разницу между импликацией и отношением “® ” в E-структурах. Если это предложение представить в виде логической формулы AE (B& C), где знак E обозначает импликацию, то окажется, что любая из перечисленных выше гипотез соответствующей E-структуры возможна лишь при условии, что одна из выполняющих подстановок формулы AE (B& C) является ложной. Отсюда ясно, что представление суждений в виде импликации отображает только один из нескольких возможных вариантов содержания соответствующих предложений.

Пусть n — число терминов E-структуры или нескольких объединяемых для решения определенных задач E-структур, и O(f(n)) означает функцию, порядок которой не более, чем f(n). Тогда любая корректная E-структура или их объединение могут быть представлены минимальным множеством элементарных суждений, оценкой числа которых является O(n). При этом число суждений в CT-замыкании и число возможных базовых элементарных гипотез оцениваются как O(n²). Алгоритмами с вычислительной сложностью O(n²) решаются следующие задачи:

1) построение CT-замыкания и главных фильтров E-структуры;

2) построение инвариантов E-структуры (диаграммы Хассе и минимального определяющего множеств элементарных суждений);

3) проверка корректности и показ всех возможных коллизий;

4) проверка полноты и показ всех возможных базовых элементарных гипотез;

5) проверка корректности и совместимости различных E-структур и их композиций;

6) проверка корректности произвольных экзистенциальных суждений.

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

1) построение всех возможных совместимых экзистенциальных суждений;

2) построение всех базовых покрытий для неполных E-структур.

В современной логике индуктивный вывод обычно ассоциируется с понятием вероятности [6]. Однако вполне правомерен другой подход к индуктивному выводу, при котором формирование правдоподобных гипотез производится с помощью восстановления недостающих звеньев какой-либо дедуктивной структуры. Такое восстановление не всегда представлено только одним вариантом, но окончательный выбор может быть сделан не на основе подсчета вероятностей, а на основе содержательной оценки правдоподобности получаемых при восстановлении гипотез.

К индуктивному выводу этого типа можно отнести процедуру восстановления пропущенных посылок в категорическом силлогизме [6]. С помощью E-структур можно оказывается не только решать эти задачи, но и намного более сложные. Начнем с простого примера. Заодно мы рассмотрим некоторые “ручные” (т.е. с помощью изображений графов) приемы анализа рассуждений на E-структурах.

Дано рассуждение “Этот человек не знает дорогу к реке. Следовательно, он не местный житель”. Это по сути силлогизм с пропущенной посылкой. Но мы выразим его в E-структурах. Введем обозначения: H – этот человек, K — знающий дорогу к реке, V — местный житель. Исходной посылкой является связь H® , предполагаемым следствием H® . Данное рассуждение можно представить в виде графа (рис. 1). Здесь посылка изображена сплошной линией, предполагаемое следствие — пунктиром. Чтобы суждение H® стало следствием, необходимо чтобы из вершины H был путь в вершину . Достаточно посмотреть на рисунок, чтобы найти недостающее “звено”: ® (рис.2). Контрапозицией этого суждения является V® K (все местные жители знают дорогу к реке).

Рис. 1 Рис. 2

Рассмотрим более сложный пример, который уже нельзя решить методами силлогистики. Для экономии места будем использовать вместо содержательных терминов простые символы. Пусть даны посылки A® B; C® (,); E® D. Второе суждение означает “Всем C не присуще B и D”. Пусть предполагаемым следствием является A® . Требуется восстановить недостающие посылки, не вводя при этом новых терминов.

Для исходных посылок построим соответствующую диаграмму (рис. 3). Затем добавим в нее все контрапозиции исходных суждений (рис. 4).

Рис. 3 Рис. 4

Теперь мы получили структуру, которая обладает одним очень важным свойством: в ней обязательно содержится диаграмма Хассе системы (соответствующая теорема в E-структурах доказана для любого набора исходных посылок). Поэтому на рис. 4 должны быть все возможные максимальные пути нашей структуры. Выделим все максимальные пути, идущие из A, и все пути, ведущие в . Здесь мы находим только такие — из A: A® B® ; в : C® ® . Теперь нам надо найти варианты их соединения.

Ясно, что соединять с C нам нельзя из-за явной коллизии парадокса. Посмотрим другие возможности – их оказывается не так уж и мало:

® ; ® ; B® C; B® ; B® ; A® C; A® .

Рассмотрим подробно первый вариант. Подставив связь ® , мы получим искомый путь из A в , что говорит о том, что суждение A® является следствием нашей новой системы. Но при этом (см. рис. 4, в котором необходимо вставить связь ® ) у нас появляется путь D® ® , из чего следует коллизия парадокса D® . Здесь же возникает еще одна коллизия парадокса E® . Следовательно, “склейка” ® не подходит.

Проверив аналогично все остальные “склейки”, приходим к тому, что из семи вариантов не приводят к коллизиям только три: B® ; B® и A® . Какой из этих вариантов самый подходящий, можно решить только на основе содержательного анализа. Каждая новая связь влечет за собой свой спектр новых следствий, некоторые из которых могут оказаться несовместимыми с какими-то явно невыраженными, но подразумеваемыми правильными суждениями.

Рассмотрим распределенную систему знаний (РСЗ), содержащую множество K различных БЗ, представленных E-структурами, и множество H различных аргументов или гипотез, которые могут быть отдельными суждениями или их совокупностями. Будем считать, что каждая из этих структур K_i (или H_i) имеет соответствующее множество T_i базовых терминов. В машинном исполнении структура K_i состоит из двух подструктур: множества (или простого списка) T_i и матрицы смежности графа, вершинами которого являются элементы T_i или их отрицания.

В РСЗ каждый термин может иметь несколько вариантов обозначений — эти варианты можно в первом приближении считать синонимами. В идеале словарь синонимов V может быть единым для всех носителей знаний в РСЗ, но более реальна ситуация, когда разные группы носителей знаний ориентируются на свои собственные словари V_g, которые со временем могут изменяться и, возможно, объединяться с другими словарями. Приведение множества T_i некоторой базы знаний K_i в соответствии со словарем V_g к некоторой единой терминологии называется унификацией K_i по V_g. Следует учесть, что возможны несовместимые пары (V_g, K_i ), например, когда разные термины K_i содержатся в одной словарной статье V_g. Тогда после “жесткой” унификации изменяется структура K_i и возможна ситуация, когда в корректной K_i появляются коллизии цикла или парадокса.

Ограничения на несовместимость в любой K_i можно задать в виде множеств терминов TP_i I T_i и TC_i I T_i. Для TP_i не допускается коллизия парадокса (каждый термин из этого множества не может быть равен пустому множеству или универсуму), а для TC_i не допустима коллизия цикла (каждый термин из этого множества не может быть эквивалентен с другими базовыми терминами). Для случая TP_i =T_i и TC_i=T_i некорректность K_i совпадает с ее несовместимостью.

Анализатором БЗ назовем вычислительную систему, в которой содержится некоторый набор словарей синонимов и для произвольного набора входных данных (V_g, K_i, T_i, TP_i, TC_i) осуществляется следующий набор операций: Union({K_i}, K) — формальное объединение разных БЗ или гипотез в одну БЗ; Unif(K_i, V_g) — унификация T_i по выбранному словарю V_g; Clos(K_i) — построение CT-замыкания K_i и его инвариантов; Corr(K_i) — проверка корректности K_i; Comp(K_i, TP_i, TC_i) — проверка совместимости K_i; UnC(K_i) — проверка неполноты K_i.

Пусть имеется система объектов, каждый из которых имеют собственную БЗ. Эти объекты могут иметь собственный анализатор с полным или частичным набором операций или при отсутствии анализатора могут осуществлять обмен информацией с некоторым централизованным анализатором, обслуживающим определенную группу объектов. Кроме того, объекты могут обмениваться информацией с другими подобными объектами. Эти объекты мы назовем когнитивными агентами на основе E-структур (сокращенно — E-агенты). E-агенты могут решать следующие задачи, являющиеся содержательной интерпретацией операций анализатора или их композиций: 1) поиск “оппонентов” и “единомышленников” и сохранение в специальной памяти имен и/или “мнений” тех и других; 2) обновление собственной БЗ за счет присоединения БЗ или их фрагментов, поступивших от других E-агентов, при условии их новизны и совместимости; 3) поиск подходящих и/или неподходящих словарей синонимов; 4) формирование альтернативных пар гипотез, совместимых по отдельности с собственной БЗ, и классификация других E-агентов по совместимости с членами этих пар.

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

1. Скорняков Л. А. Элементы теории структур. М.: Наука, 1982.
2. Кулик Б. А. Моделирование рассуждений на основе законов алгебры множеств // Труды V нац. конфер. по искусственному интеллекту, Казань, 7-12 октября 1996 г. Т. 1, с. 58-61.
3. Кулик Б. А. Логические основы здравого смысла (под ред. Д.А. Поспелова). СПб, Политехника, 1997.
4. Кулик Б.А. Алгебраические основы естественных рассуждений: E-структуры / Материалы второй международной конференции “Логико-лингвистическое управление динамическими объектами (DOLLC’99), Санкт-Петербург, 21-25 июня 1999 г., с. 29-40.
5. Кулик Б.А., Романов Л.Н. Алгебраический подход к моделированию и анализу естественных рассуждений на основе E-структур // Интеллектуальное управление: новые интеллектуальные технологии в задачах управления (ICIT’99). — Труды Междунар. Конфер., Переславль-Залесский, 6-9 декабря 1999 г. М.: Наука. Физматлит, 1999. С. 50-54.
6. Светлов В. А. Практическая логика. СПб. Изд-во РХГИ. 1995.