Алгебраический подход к моделированию и анализу естественных рассуждений на основе E-структур
Использование новой математической структуры, которая является обобщением алгебры множеств и совмещает в себе некоторые свойства частично упорядоченных систем и логических исчислений. Особенность моделирования концепции естественных рассуждений.
Рубрика | Математика |
Вид | статья |
Язык | русский |
Дата добавления | 16.01.2018 |
Размер файла | 41,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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. Ясно, что решение этой задачи необязательно единственно, но алгоритмически разрешимо.
Литература
1. [Кулик, 1997] Кулик Б. А. Логические основы здравого смысла. СПб, Политехника, 1997.
2. [Кулик, 1999] Кулик Б.А. Алгебраические основы естественных рассуждений: E-структуры / Материалы второй международной конференции «Логико-лингвистическое управление динамическими объектами (DOLLC'99), Санкт-Петербург, 21-25 июня 1999 г., с. 29-40.
Размещено на Allbest.ru
...Подобные документы
Основные понятия размерности упорядоченных множеств. Определение размерности упорядоченного множества. Свойства размерности конечных упорядоченных множеств. Порядковая структура и элементы алгебраической теории решёток.
дипломная работа [191,8 K], добавлен 08.08.2007Анализ логических ошибок с помощью E-структур. Коллизиями E-структуры: коллизии парадокса и цикла. Основные методы анализа рассуждений. Построение графа рассуждения и применение к посылкам правила контрапозиции. Корректные и некорректные E-структуры.
контрольная работа [188,6 K], добавлен 04.09.2010Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
учебное пособие [1,5 M], добавлен 27.10.2013История развития и становления математического понятия функции. Абстрактные характеристики упорядоченных алгебр многоместных функций: P-алгебры и D-алгебры. Исследование теории суперпозиций алгебраических структур n-местных функций Менгера и Глускера.
курсовая работа [263,7 K], добавлен 22.12.2015Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
реферат [40,5 K], добавлен 17.11.2008Применение граф-схем - кратчайший путь доказательства теорем. Нахождение искомых величин путем рассуждений. Алгоритм решения логических задач методами таблицы и блок-схемы. История появления теории траекторий (математического бильярда), ее преимущества.
реферат [448,4 K], добавлен 21.01.2011Теория частичных действий как естественное продолжение теории полных действий. История создания и перспективы развития теории упорядоченных множеств. Частично упорядоченные множества. Вполне упорядоченные множества. Частичные группоиды и их свойства.
реферат [185,5 K], добавлен 24.12.2007Предпосылки развития алгебры множеств. Основы силлогистики и соотношение между множествами. Применение и типы жергонновых отношений. Понятие пустого множества и универсума. Построение диаграмм Эйлера и обоснование законов транзитивности и контрапозиции.
контрольная работа [369,0 K], добавлен 03.09.2010Элементы линейной алгебры. Виды матриц и операции над ними. Свойства определителей матрицы и их вычисление. Решение систем линейных уравнений в матричной форме, по формулам Крамера и методу Гаусса. Элементы дифференциального и интегрального исчислений.
учебное пособие [1,5 M], добавлен 06.11.2011Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
реферат [63,3 K], добавлен 06.12.2010Понятие нечеткого множества и свойства его элементов. Определение логических операций: отрицания, конъюнкции, дизъюнкции. Основные этапы нечеткого вывода, метод центра тяжести. Оценка состояния повреждения объекта на основе теории нечетких множеств.
курсовая работа [316,8 K], добавлен 22.07.2011Основы формальной логики Аристотеля. Понятия инверсии, конъюнкции и дизъюнкции. Основные законы алгебры логики. Основные законы, позволяющие производить тождественные преобразования логических выражений. Равносильные преобразования логических формул.
презентация [67,8 K], добавлен 23.12.2012Элементы алгебры, логические операции над высказываниями. Получение логических следствий из данных формул и посылок для данных логических следствий. Необходимые и достаточные условия. Анализ и синтез релейно-контактных схем. Логические следствия и формы.
дипломная работа [295,2 K], добавлен 11.12.2010Природа математики как строгой науки, отношения математических объектов и целостных структур реального мира. Различия в трактовке Платоном и Аристотелем онтологического статуса математических сущностей. Анализ математической концепции семинара Н. Бурбаки.
реферат [26,4 K], добавлен 29.01.2014Краткое историческое описание становления теории множеств. Теоремы теории множеств и их применение к выявлению структуры различных числовых множеств. Определение основных понятий, таких как мощность, счетные, замкнутые множества, континуальное множество.
дипломная работа [440,3 K], добавлен 30.03.2011Понятия множеств и их элементов, подмножеств и принадлежности. Способы задания множеств, парадокс Рассела. Количество элементов или мощность. Сравнение множеств, их объединение, пересечение, разность и дополнение. Аксиоматическая теория множеств.
курсовая работа [1,5 M], добавлен 07.02.2011Мономорфные стрелки. Эпиморфные стрелки. Изострелки. КатегориЯ множеств. Мономорфизм в категории множеств. Эпиморфизм в категории множеств. Начальные и конечные объекты в категории множеств. Произведение в категории множеств.
дипломная работа [144,3 K], добавлен 08.08.2007Применение системы MathCAD при решении прикладных задач технического характера. Основные средства математического моделирования. Решение дифференциальных уравнений. Использование системы MathCad для реализации математических моделей электрических схем.
курсовая работа [489,1 K], добавлен 17.11.2016Понятие множества, его обозначения. Операции объединения, пересечения и дополнения множеств. Свойства счетных множеств. История развития представлений о числе, появление множества натуральных, рациональных и действительных чисел, операции с ними.
курсовая работа [358,3 K], добавлен 07.12.2012Способы решения логических задач типа "Кто есть кто?" методами графов, табличным способом, сопоставлением трех множеств; тактических, истинностных задач, на нахождение пересечения множеств или их объединения. Буквенные ребусы и примеры со звездочками.
курсовая работа [622,2 K], добавлен 15.06.2010