Алгебраический подход к моделированию и анализу естественных рассуждений на основе E-структур

Размещено на http://www.allbest.ru/

Алгебраический подход к моделированию и анализу естественных рассуждений на основе E-структур

Борис А.

Лев Н.

Введение

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

Значительная часть фрагментов текста в естественных рассуждениях представляет собой предложения, которые с точки зрения логики являются суждениями. К суждениям (точнее, к их обобщенной форме) относятся многие типы повествовательных и условных предложений естественного языка, содержанием которых являются многие факты, их обобщения, определения и толкования терминов, законы природы и математические теоремы. Структура обобщенного суждения может быть представлена как принимаемая в качестве истинной или выводимая импликация L0(L1&L2&…), где литерал Li (i = 0,1,2,…) является некоторым «термином» (Ti) или его отрицанием (). Все типы суждений Аристотелевской силлогистики являются частными случаями обобщенного суждения, которое далее именуется просто «суждение».

Ранее было установлено, что представление рассуждений в виде совокупности суждений позволяет существенно расширить возможности полисиллогистики и, в частности, решать следующие не предусмотренные в ней и весьма важные для анализа рассуждений задачи [Кулик, 1997]:

с помощью простых вычислительных алгоритмов выводить все возможные следствия;

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

проверять совместимость исходной системы с произвольными гипотезами;

осуществлять анализ неполноты моделируемых систем.

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

1. Определение E-структур

Алгебру множеств (SA) можно рассматривать как алгебраическую систему с множеством операций {--, , } и множеством отношений {, , =}. Свойством SA является то, что все операции в ней являются полными. Обобщением SA может служить алгебраическая система, в которой некоторые операции являются частичными. Примером такой системы является полукольцо, в котором полной является только операция пересечения. Другим известным примером обобщения SA являются частично упорядоченные множества (далее -- у-множества), у которых операции отсутствуют полностью. Частным случаем у-множеств являются решетки, у которых вводятся две полные операции inf и sup. E-структура является обобщением SA, у которой полной является только операция дополнения. Рассмотрим конечную систему S множеств

S = <, S1, S2,…, Sn, , ,…,U>,

в которой Si и могут быть как конечными, так и бесконечными множествами, универсум U определяется соотношением U. При этом элементный состав множеств, содержащихся в S или в , может быть неизвестен. Пусть в системе S задано произвольная совокупность соотношений вида

Xk ,

где I = 1, 2, …, n -- множество индексов, в каждом из предложений типа (2) все индексы k,tI попарно различны, Xi -- один из элементов множества {Si, } для любого iI. Примеры предложений типа (2): S4(S2,S5); ( S1).

Определение 1. E-структурой называется система множеств типа (1), заданная конечной совокупностью соотношений типа (2), которые называются суждениями. Исходные суждения, с помощью которых определяется конкретная структура, называются посылками.

Рассмотрим соответствие между компонентами E-структуры и некоторыми логическими понятиями. Множество символов B = {S1, S2, … , Sn, , ,…,} являются базовыми терминами (при этом соответствует отрицанию Si); множество символов {, U} являются константами -- они соответствуют логическим константам False и True. Соотношения типа (2) в E-структуре являются обобщением известных в традиционной логике типов суждений. В частности, суждению "Все Si есть Sk" соответствует соотношение SiSk, а суждению "Все Si не есть Sk" -- соотношение Si. В качестве суждений E-структуры допускаются соотношения, которые не соответствуют ни одному из известных в Аристотелевской силлогистике типов суждений, например, соотношение ( S1). Предполагается, что все термины из B не равны константам. Это исходное предположение при анализе конкретных структур может подтверждаться или опровергаться.

Частные суждения типа "Некоторые Si есть Sk" и "Некоторые Si не есть Sk" в E-структуре формально выражаются как соотношения Sik (Si Sk) и Sik (Si ). Выражение "некоторые Si" вводится в E-структуру не как отдельный термин, но обязательно как соотношение SikSi.

Законы E-структур полностью соответствуют законам SA. В то же время способ задания E-структур позволяет отнести их к у-множествам. От традиционных у-множеств общего вида E-структуры отличаются тем, что в них предусмотрены операции, при этом дополнение является полной операцией, а все остальные -- в общем случае частичные. В то же время бинарное отношение, заданное в E-структурах с помощью соотношений (2), так же, как и в у-множествах, является рефлексивным, транзитивным и антисимметричным.

В отличие от решеток в E-структурах определены дополнения всех элементов. К тому же в решетках операции inf и sup (в принятых обозначениях -- и ) определены для всех пар элементов, а сами эти операции не соответствуют операциям пересечения и объединения SA (или соответствующим операциям и булевой алгебры). Кроме того, любое у_множество можно вложить в подходящую E-структуру -- для решеток это свойство в общем случае не соблюдается, т. е. существуют у-множества, диаграммы Хассе которых нельзя вложить в диаграммы Хассе решеток.

Одно из свойств E-структуры заключается в том, что каждое суждение типа (2) может быть сведено к совокупности элементарных суждений типа XiXk, где Xi{Si,}, Xk{Sk,}, в которых содержится по два термина. В силу этого систему суждений, заданных в посылках, мы можем представить в виде графа, в котором каждая ориентированная дуга XiXk соответствует соотношению включения между парами множеств или соотношению между субъектами и предикатами в традиционных суждениях.

Графы E-структур содержат четное число (2n) вершин или n пар (Si, ) вершин. В каждую E-структуру могут быть добавлены новые дуги с помощью правил вывода, которые определяются в соответствии с основными свойствами соотношения включения множеств.

Определение 2. Правилами вывода E-структуры E являются следующие:

Правило C (контрапозиции): если в E существует дуга XY, то в ней между терминами и необходимо ввести дугу .

Правило T (транзитивности): если в E существуют две дуги XY и YZ, то в нее необходимо ввести дугу XZ.

Естественным дополнением этих правил является соотношение =X.

Определение 3. CT-амыканием произвольно заданной E-структуры E называется построенный из E с помощью правил вывода граф ECT, в котором применение любого из этих правил не приводит к появлению новых дуг.

Определение 4. Множеством всех возможных следствий E-структуры E, называется множество дуг графа ECT\E, где разность графов определяется как разность множеств ориентированных дуг соответствующих графов. математический алгебра множество исчисление

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

2. Коллизии в Е-структурах

Определение 5. Коллизиями E-структуры называются следующие ситуации, появляющиеся при построении CT-замыкания:

коллизия парадокса: появление в ECT суждений типа Xi(или Xi);

коллизия цикла: появление в ECT по крайней мере одного цикла.

Термин "коллизия парадокса" не случаен. При моделировании рассуждений с помощью E-структур соотношения Xi(или Xi) с точки зрения законов SA (в частности, закона исключенного третьего) означают, что заданная структура возможна лишь при условии, что соответствующие множества Xi (или ) тождественно равны пустому множеству, а альтернативные множества -- универсуму. Эта ситуация часто встречается в парадоксах.

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

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

3. Инварианты E-структур

Рассмотрим две E-структуры:

E1: X(Y, ); Y(); Z();

E2: X(Y); Z(,); V(,).

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

E3: X(Y, ); Y(Z); Z()

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

Другим более простым инвариантом E-структур является диаграмма Хассе, которая часто используется в у-множествах и в теории алгебраических решеток.

Определение 6. Диаграммой Хассе EH E-структуры E называется подграф ECT, содержащий только все его максимальные цепи.

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

Теорема 1. В любой E-структуре алгоритмы распознавания коллизий и построения всех инвариантов являются алгоритмами полиномиальной вычислительной сложности.

4. Неполнота E-структур

Пусть E -- корректная E-структура с множеством B базовых терминов, которые являются вершинами соответствующего графа. На множестве вершин структуры E построим полный неориентированный граф KE без петель. Назовем множество KE\ECT дуг невыводимыми базовыми суждениями структуры E.

Определение 7. E-структура E является полной, если добавление в нее любого невыводимого базового суждения приводит к коллизии. Если данное условие не выполняется, то E-структура E является неполной.

С точки зрения логического вывода неполнота конкретной структуры Эйлера означает, что для нее существует по крайней мере одно содержащее только базовые термины суждение, которое не выводится из исходных посылок, но в то же время совместимо с ней. Простым примером неполной E-структуры является E-структура E: X(Y); Y(); V(Y), диаграмма Хассе EH которой показана на рис. 1.

На рис. 2-4 показаны диаграммы Хассе полных E-структур, которые образуются при добавлении в состав посылок структуры E одного из следующих базовых невыводимых суждений: XV (рис.2), X (рис. 3), VX (рис.4).

Теорема 2. Алгоритм проверки неполноты произвольной E-структуры E и алгоритм вывода всех не вызывающих коллизий базовых невыводимых суждений E являются алгоритмами полиномиальной вычислительной сложности.

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

Определение 8. Множеством базовых покрытий системы множеств, заданной E-структурой E, называется множество {Wi} инвариантов корректных E_структур с тем же множеством терминов, для которых справедливо соотношение ECTWiCT.

Базовые покрытия можно использовать для формирования индуктивных заключений. Предположим, что неполная E-структура E является исходной теорией, и для этой теории известное некоторое множество невыводимых суждений R, которые интерпретируются как предполагаемые следствия или факты. В этом случае индуктивным выводом можно считать некоторое минимальное множество дополнительных посылок J, которое в совокупности с теорией E образует некоторое корректное базовое покрытие Wr для E-структуры E, покрывающее также и все суждения из R. Ясно, что решение этой задачи необязательно единственно, но алгоритмически разрешимо.

Литература