Нечеткая Аристотелева логика

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

Нечеткая Аристотелева логика

Г.С. Плесневич

В работе рассматривается нечеткая Аристотелева логика и определяется понятие нечеткого силлогизма как некоторого состоятельного правила вывода для баз фактов в этой логике. Построены нечеткие силлогизмы для пропозициональной Аристотелевой логики с треугольной нормой Заде, то есть с нормой Т(х, у) = min{x,y}.

Основные определения

В последние годы были предложены и в настоящее время разрабатываются новые подходы к Аристотелевой логике, позволяющие расширить ее выразительные и дедуктивные возможности. Помимо традиционных приложений к философии и лингвистике, эта логика применяется в системах искусственного интеллекта и, вообще, в информационных системах. Отметим, например, применение Аристотелевой логики в амбициозном проекте Semantic Web (Семантический Веб), выдвинутом Т. Бернерс-Ли, изобретателем WWW, [Berners-Lee et al., 2001]. Язык Аристотелевой логики используется как формализм для спецификации онтологий, с помощью которых записываются семантические аннотации к ресурсам Веба.

Как известно, основанные на двузначной логике методы недостаточны для обработки плохо структурированной, неопределенной или нечеткой информации. Но именно такого рода информацию часто нужно представлять в онтологиях для Семантического Веба. В связи с этим перспективным является применение методов нечеткой логики к решению задач Семантического Веба, [Sanchez, 2006].

Существуют различные подходы к построению нечетких онтологий [Bobillo et al., 2009], [Tho, 2006]. Мы будем использовать нечеткую Аристотелеву логику с нечеткими силлогизмами в качестве правил вывода.

Классическая логика Аристотеля состоит из предложений вида

P а Q, P i Q, P е Q, P о Q,

где P и Q - переменные, значениями которых служат множества (классы объектов), а а, i, е и о - Аристотелевы связки, обозначающие отношения между множествами. Этими отношениями служат включение, непустое пересечение, пустое пересечение и отрицание включения множеств P I и Q I, которые являются значениями переменных P и Q в интерпретации I. Таким образом, если U I - универсум интерпретации I, то

P IU I, Q IU I и

(P а Q) I = 1 (истина) P IQ I, (P i Q) I = 1 P IQ I ,

(P e Q) I = 1 P IQ I = , (P o Q) I = 1 P I - Q I .

Силлогизмы Аристотеля - это правила вывода для логики Аристотеля. Эти правила традиционно классифицируют по четырем формам (так называемым фигурам): силлогизм аристотелевый множество

(I) Y б Z, X в Y |- X г Z,

(II) Z б Y, X в Y |- X г Z,

(III) Y б Z, Y в X |- X г Z,

(IV) Z б Y, Y в X |- X г Z,

где б, в, г {a, i, e, o}.

Известно, что существует 15 силлогизмов как состоятельных правил вывода. Например, силлогизм Barbara относится к фигуре (I) и имеет паттерн ааа, а силлогизм Baroco относится к фигуре (II) и имеет паттерн аоо. Паттерн - это слово бвг с конкретными значениями б, в, г для данного правила. В традиционном названии силлогизма гласные определяют его паттерн. Вот список всех 15 силлогизмов (с указанием фигур):

(I) Barbara, Darii, Celarent, Ferio

(II) Camestres, Baroco, Cesare, Festino

(III) Datisi, Ferison, Disamis, Bocardo

(IV) Camenes, Fresison, Dimaris.

Обозначим через б* обратное к б отношение (т.е. будем интерпретировать предложение P б*Q так же, как и предложение Q б P). Тогда все 15 силлогизмов можно свести к одной форме, например к форме X б Y, Y в Z |- X г Z. При этом получается только 8 правил вывода. Эти правила даны в табл.1, где указаны их паттерны.

Табл. 1

aaa Barbara iai Darii, Datisi, Disamis aee Celarent, Cesare, Camesres, Camenes ieo Ferio, Festimo, Ferison, Fresison oa*o Baroco a*oo Bocardo

Рассмотрим, например, силлогизм Festino: Z e Y, X i Y |- X o Z . Переставляя посылки и учитывая, что Z e Y и Y e Z эквивалентны (т.е. (Z e Y)I = (Y e Z)I для всех интерпретаций I), получаем правило X i Y, Y e Z |- X o Z с паттерном ieo.

Нечеткая Аристотелева логика имеет тот же синтаксис, т.е. ее предложения имеют вид P б Q, где б{a, i, e, o, a*, o*}. Интерпретация I назначает каждому имени Р нечеткое подмножество PI универсума UI, т.е. функцию P I : U I > [0,1] = {x | 0x1}. Значениями предложений в интерпретации I служат по определению:

(P a Q) I = sup{P I(u)Q I(u) | uU I}

= sup{(PI(u)QI(u)) | uU I},

(P i Q)I = inf{P I(u)Q I(u) | uU I}, (1.1)

(P е Q)I = sup{(P I(u)Q I(u)) | uU I},

(P о Q)I = inf{P I(u)Q I(u) | uU I}.

Здесь и - нечеткие логические связки, которые обычно определяется следующим образом: x = 1-y и xy = T(x,y), где Т - треугольная норма. В этом случае соотношения (1.1) переходят в соотношения:

(P a Q)I = sup{1-Т(P I(u), 1- Q I(u)) | uU I},

(P i Q)I = inf{Т(Р I(u), Q I(u)) | uU I},

(P е Q)I = sup{1-Т(P I(u), Q I(u)) | uU I},

(P о Q)I = inf{Т(P I(u), 1- Q I(u) | uU I}.

Выражения вида sP б Qt будем называть (нечеткими) фактами. Здесь б{a, i, е, о, а*, о*}, а s и t - числа из интервала [0,1], причем st. Значением факта sP б Qt в интерпретация I служит 1 (истина) или 0 (ложь) и (sP б Qt) I = 1df s(P б Q) It.

Конечное множество нечетких фактов назовем базой фактов. Пусть Fb - произвольная база фактов и ц - какой-либо факт. Логическое следствие Fb |= ц определяется стандартным образом, т.е. как отсутствие интерпретации, при которой все факты из Fb истинны, но факт ц ложен. База фактов называется невыполнимой, если не существует ни одной интерпретации, при которой все факты из Fb.

Рассмотрим правила вывода для фактов, имеющие вид

R(g,h): aP б Qс, bP в Qd |- gP г Qh.

Здесь a, b, c, d рассматриваются как параметры (переменные), принимающие значения в интервале [0,1], а g и h - некоторые функции от этих параметров. Правило R(g,h) состоятельно, если имеет место логическое следствие aP б Qс, bP в Qd |= gP г Qh.

Ясно, что это логическое следствие тривиально имеет место, если посылки правила R(g,h) составляют невыполнимое множество. Естественно исключить из рассмотрения такие правила вывода. Существует условие, накладываемое на числа a, b, c и d, когда пара посылок правила R(g,h) невыполнима. Это условие назовем условием невыполнимости

Ясно, что для любых связок б, в, г{a, i, е, о, а*, о*} и любых чисел a, b, c, d[0,1] таких, что aс и bd, найдутся числа g и h такие, что правило R(g,h) состоятельно (например, можно взять g = 0 и h =1). Ясно также, если правило R(g,h) состоятельно, то состоятельно также и правило R(g',h'), где g'g и h'h. Следовательно, существуют оптимальные границы для g и h, при которых состоятельно правило вывода R(g,h). Положим

gбвг(a,b,c,d)=sup{g| правило R(g,1) состоятельно},

hбвг(a,b,c,d) = inf{h | правило R(0,h) состоятельно}.

Правило вывода

aP б Qс, bQ в Rd |- gбвг(a,b,c,d)P г Rhбвг(a,b,c,d)

мы называем нечетким силлогизмом с паттерном бвг. Построить нечеткий силлогизм - значит, найти выражения для функций gбвг(a,b,c,d) и hбвг(a,b,c,d), а также указать условие невыполнимости для его правой части.

Ясно, что имеется ровно 216 = 666 различных нечетких силлогизмов. Однако, можно взять 6 силлогизмов, которые являются базовыми в том смысле, что любой другой силлогизм, можно свести к некоторому базовому силлогизму (см. далее раздел 2).

В настоящей работе мы рассматриваем в основном случай нечеткой пропозициональной Аристотелевой логики, когда допускаются только интерпретации с одноэлементными универсумами. Точнее, пусть U I ={щ} для всех допустимых интерпретаций. Тогда соотношения (1.1) превращаются в соотношения:

(P a Q) I = 1 - Т(P I(щ), 1- Q I(щ)), (P i Q) I = Т(Р I(щ), Q I(щ)),

(P е Q) I = 1-Т(P I(щ), Q I(щ)), (P о Q) I = Т(P I(щ), 1- Q I(щ)).

Мы можем трактовать значение P I(щ) как значение нечеткой пропозициональной переменной, которую обозначим р. Таким образом, мы приходим к нечеткой пропозициональной Аристотелевской логике (НПАЛ) с предложениями вида p a q, p i q, p е q, p о q, для которых имеем:

(p a q) I = 1 - Т(p I, 1- q I), (p i q) I = Т(p I, q I),

(p е q)I = 1-Т(pI, qI), (p о q)I = Т(pI, 1- qI).

В нечеткой пропозициональной Аристотелевой логике силлогизмы принимают вид

ap б qс, bq в rd |- gбвг(a,b,c,d)p г rhбвг(a,b,c,d).

Одним из мотивов для введения НПАЛ является то, что проблема невыполнимости в логике Аристотеля сводится к проблеме выполнимости в пропозициональной логике Аристотеля (см. раздел 3).

В разделе 4 мы рассмотрим метод аналитических таблиц для вывода фактов НПАЛ с нормой Заде, т.е. с нормой Т(х, у) = min{x,y}. Используя этот метод, мы строим нечеткие силлогизмы для этой логики (см. раздел 5).

Базовые нечеткие силлогизмы

В качестве базовых силлогизмов возьмем нечеткие силлогизмы со следующими паттернами: aai, ааа*, iaа, iii, iai, а*аi.

Рассмотрим, например, как нечеткий силлогизм с паттерном o*ie можно свести к базовому силлогизму iii. При интерпретации I предложений этого силлогизма имеем импликацию

аsup{1-Т(Q I(u),1-P I(u)) | uU I}c, binf{Т(Q I(u),R I(u)) | uU I}d

=> go*ie(a,b,c,d)sup{1-Т(P I(u),R I(u)) | uUI} go*ie(a,b,c,d).

Отсюда

1-c inf{Т(Q I(u),1-P I(u)) | uU I}1-a,

binf{Т(Q I(u),RI(u))|uU I}d =>

1-ho*ie(a,b,c,d)inf{Т(P I(u),R I(u)) | uU I}1 -go*ie(a,b,c,d).

Переименовав P на R, Q на P и R на Q и сделав перестановку посылок импликации, получим

binf{Т(P I(u),Q I(u)) | uU I}d

1-c inf{Т(Q I(u),1- R I(u)) | uU I}1-a =>

1-ho*ie(a,b,c,d)inf{Т(P I(u),R I(u)) | uU I}1-go*ie(a,b,c,d).

В силу произвольности интерпретации I имеем состоятельный силлогизм

bP i Qd, 1-cQ i R1-a |- 1-ho*ie(a,b,c,d)P i R1-go*ie(a,b,c,d).

Отсюда giii(b,1-c,d,1-a) = 1-ho*ie(a,b,c,d), hiii(b,1-c,d,1-a) = 1-go*ie(a,b,c,d) и, значит, go*ie(a,b,c,d) = 1-hiii(b,1-c,d,1-a), ho*ie(a,b,c,d) = 1-giii(b,1-c,d,1-a).

Итак, нечеткий силлогизм с паттерном o*ie сводится к нечеткому силлогизму с паттерном iii в том, что границы первого силлогизма вычисляются из границ второго.

Теорема 1. Каждый нечеткий силлогизм

a ? p б q ? c, b ? q в r ? d |- gбвг(a,b,c,d) ? p г r ? hбвг(a,b,c,d)

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

a'?p л q? c', b'? q м r ? d ' |- gлмн(a',b',c',d ') ? p r ? hлмн(a',b',c',d '),

где лмн {aai, ааа*, iaа, iai, iii, а*аi} и a', b', c', d '{a, b, c, d,1-a, 1-b,1-c,1-d}.

Проблема невыполнимости в логике Аристотеля

Теорема 2. Пусть S - конечное множество предложений логики Аристотеля. Тогда по S можно построить такое множество предложений S1 пропозициональной логики Аристотеля, что выполняется эквивалентность

S выполнимо S1 (пропозиционально) выполнимо.

Если множество S содержит m предложений со связками i или о, то |S1| = m(|S| - m). Другими словами, проблема невыполнимости в логике Аристотеля полиномиально сводится к проблеме невыполнимости в пропозициональной логике Аристотеля.

Как построить базу знаний S1 можно понять из следующего примера. Пусть S = {A i B, A o C, A a D, B e C, B e D}. Предложения из S запишем в языке логики предикатов:

x(A(x)B(x)), x(A(x)C(x)), (3.1)

x((A(x)D(x)), x((B(x)C(x))),x((B(x)D(x))). (3.2)

Заменим формулы (3.1) на формулы

А(s1)B(s1), A(s2)C(с 2), (3.3)

где s1 и s2 - сколемовские константы. Эта замена сохраняет свойство выполнимости и поэтому множество S выполнимо тогда и только тогда, когда множество E формул (3.2) и (3.3) выполнимо. По теореме Эрбрана множество E будет выполнимым тогда и только тогда, когда оно выполнимо в универсуме Эрбрана, который в данном случае состоит из двух элементов - констант s1 и s2. Следовательно, множество E будет выполнимым тогда и только тогда, когда выполнимо множество, состоящее из формул (3.3) и формул, получаемых из формул (3.2) подстановкой констант s1 и s2 вместо переменной х:

А(s1)B(s1), A(s2)C(s2), (A(s1)D(s1)), (B(s1)C(s1)),

(B(s1)D(s1)), (A(s2)~D(s2)), (B(s2)C(s2)), (B(s2)D(s2).

Формулы

А(s1), A(с 2), B(с 1), B(с 2), С(с 1), С(с 2), D(с 1), D(с 2)

можно рассматривать в качестве пропозициональных переменных и обозначить соответственно р 1, р 2, р 3, р 4, р 5, р 6, р 7, р 8. Возвращаясь к обозначениям с аристотелевскими связками, мы получим множество

Е 1= {р 1 i р 3, р 1 o р 6, р 1 a р 7, р 3 e р 5, р 3 e р 7, р 2 a р 8, р 4 e р 6, р 4 e р 8}.

Таким образом, множество Е выполнимо тогда и только тогда, когда выполнимо множество Е 1.

Метод аналитических таблиц для пропозициональной Аристотелевой логики с нормой Заде

Очевидно, что справедливы следующие соотношения:

min{x,y} ? c x ? c или у ? c, min{x,y} ? c x ? c и у ? c,

max{x,y} ? c x ? c и у ? c, max{x,y} ? c x ? c или у ? c.

Такие же соотношения имеют место, если нестрогие неравенства заменить на строгие. Эти соотношения доказывают состоятельность приведенных в табл.1 правил вывода, действующих на фактах с односторонними неравенствами. (Такие факты для краткости будем называть 1-фактами.) Аналогичные правила имеются для 1-фактов со строгими неравенствами. Обозначим R множество этих правил вывода, т.е. R состоит из всех указанных в табл.3 правил, а также правил, получаемых из них заменой знаков и на знаки < и >.

Табл. 1.

р а q ? c р а q ? с ---------------- ----------- р ? 1- c | qc p ? 1- c q ? с	p i q ? c p i q ? c ----------- ------------- р ? c p ? c | q ? c q ? c
p e qc p e qc ---------------------- ----------- р ? 1- c | q ? 1- c p ? 1- c q ? 1- c	p o q ? c p o qc ----------- ------------------- р ? c p ? c | q ? 1- c q ? 1- с

Легко видеть, что распознавание логического следствия Fb |= ц может быть сведено к распознаванию невыполнимости множеств 1-фактов. В самом деле, пусть Fb'- множество 1-фактов, получаемое из Fb заменой каждого входящего в Fb факта t ? p б qs на два факта p б qt и p б qs. Для произвольного факта ц: t ? p б qs обозначим через ц- факт p б qt, а через ц+ - факт p б qs. Тогда

Fb |= ц множества Fb'{ ц- } и Fb'{ ц+ } невыполнимы.

Правила из R составляют полную систему вывода для 1- фактов.

Теорема 1. Для произвольного множества 1-фактов S имеют место следующие утверждения:

Если множество S невыполнимо, то при применении (в любом порядке) правил вывода из R, начиная с "ветви", составленной из 1-фактов множества S, мы, в конце концов, получим замкнутое дерево;

Если при применении правил вывода (в каком-либо порядке) мы получили замкнутое дерево, то множество S невыполнимо.

Силлогизмы для нечеткой пропозициональной Аристотелевой логики с нормой Заде

Правила вывода системы R могут быть использованы для построения нечетких силлогизмов для НПАЛ с нормой Заде. Например, покажем, как построить базовый нечеткий силлогизм с паттерном аai.

Пусть

Fb = {ap a qc, bq a rd} -

факты, составляющие посылки силлогизма с паттерном aai. На рис.1 показано дерево вывода для множества 1-фактов

Fb'= {p a qc, p a qa, q a rd, q a rd}.

Это дерево изображено в части между точечными линиями А и Б. Дерево будет замкнутым тогда и только тогда, когда будут невыполнимым пара 1-фактов {qc, q1-d}. Ясно, что эта пара предложений невыполнима тогда и только тогда, когда c<1-d, то есть, когда c+d<1. Таким образом, неравенство c+d<1 служит условием невыполнимости для посылок нечеткого силлогизма.

Для получения нижней границы gaai(a,b,c,d) для нечеткого силлогизма с паттерном aai строим дерево вывода для множества Fb'{p i r < g}. Это дерево изображено в части ниже линии А. В дереве нужно найти пары 1-фактов, которые могут противоречить друг другу. В табл.4 выписаны эти пары вместе с условиями их несовместности, а также с номерами ветвей дерева, которые блокируют (замыкают) эти ветви. Пару 1-фактов, для которой имеется условие, выполнение которого блокирует хотя бы одну ветвь таблицы, назовем блокирующей.

Заметим, что условием невыполнимости пары {p1-c, p1-a}, лежащей на ветвях (1), (2), (3), (4), служит неравенство a>c. Но это неравенство не может быть выполнено, так как всегда ac. Поэтому эта пара не является блокирующей.

Табл. 2

p1- c, p < g	g1- c	(1), (3), (5), (7)
rb, r < g	gb	(4), (8)
rd, r < g	gd	(2), (4), (6), (8)

Из табл.1 видно, что условие g1-cgd блокирует все ветви таблицы. Очевидно, что g1-cgdgmin{1-c, d}. Значит, наибольшим g, при котором дерево будет замкнутым, является min{1-c, d}. Следовательно, gaai(a,b,c,d) = min{1- c, d}.

Для нахождения верхней оценки рассмотрим часть дерева (рис.1) выше линии Б. Мы обнаруживаем, что здесь нет блокирующих пар для ветвей (5), (6), (7) и (6), если только h < 1; если же h = 1, то все ветви будут блокированы. Следовательно, haai(a,b,c,d) = 1.

Найдем еще нижнюю границу для нечеткого силлогизма с паттерном iаа. Для этого построим соответствующее дерево Т (рис.2).



Дерево в части между линиями А и Б не имеет блокирующих пар, так как его ветвь (2) всегда открыта. Следовательно, силлогизм с паттерном iaa не имеет условия невыполнимости. Чтобы найти нижнюю границу для этого силлогизма, найдем блокирующие пары для дерева Т.

В табл.3 представлены все блокирующие пары для ветвей дерева Т.

Табл. 3

qa, q1- b	а+b > 1	(1), (3)
r < g, r b	gb	(2), (4)
p > 1- g, pс	g1- c	(1), (2)
q1- d, qc	C+ d < 1	(3), (4)

Очевидно, что дерево Т замкнуто тогда и только тогда, когда либо a+b>1 & gb, либо c+d<1 & g1-c, то есть когда выполняется условие (a+b>1 & gb) (c+d <1 & g1- c). Отсюда получаем:

(i) если a+b >1 и c+d <1, то gb g1- c;

(ii) если a+b >1 и c+d1, то gb;

(iii) если a+b1 и c+d <1, то g1- c;

(iv) если a+b1 и c+d1, то 0.

Поскольку ac и bd, то c+d > 1, когда a+b > 1. Поэтому (i) можно исключить, а (ii) свести к a+b > 1. Следовательно, мы получаем:

* если a+b > 1, то giaa(a,b,c,d) = b;

* если a+b1 и c+d < 1, то giaa(a,b,c,d)= 1- c;

* если a+b1 и c+d1, то giaa(a,b,c,d) = 0.

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

Табл. 4

Паттерн	Условие невып.	Нижняя граница	Верхняя граница
аai	с+d< 1	min{1-c,d}	1
aaa*	с+d< 1	1- d	1
Aa		b, если a+b > 1 1-c, если a+b1, c+d < 1 0, если a+b1, c+d1	1-a, если a+b > 1 max{d,1-a}, если a+b1
Iai		min{a,b},если a+b >1 0, если a+b1	max{c,d}, if c+d < 1 d, if c+d1
iii		min{a,b}	max{c,d}, если b >c, a > d c, если bc, a > d d, если b > c, ad 0, если bc, ad
а*ai		0	c, если cd d, если dc

Благодарности. Автор благодарит РФФИ за финансовую поддержку настоящей работы (проекты 08-01-00465 и 09-01-00587).

Список литературы

1. [Ионин и др., 2009] Ионин В.К., Плесневич Г.С. Нечеткая пропозициональная силлогистика // V-ая Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна 2009). Сб. научных трудов. - М.: Физматлит, 2009.

2. [Новак и др., 2006] Новак В., Перфильева И., Мачкорж И. Математические принципы нечеткой логики. - М.: Физматлит, 2006.

3. [Berners-Lee et al, 2001] Berners-Lee T., Hendler J. and Lassila O. The Semantic Web // Scientific American. Vol. 284, № 5, 2001.

4. [Sanchez, 2006] Sanchez E. Fuzzy Logic and the Semantic Web. - Elsevier, 2006.

5. [Stanford, 2007] Stanford Encyclopedia of Philosophy. Aristotle's Logic. - http//plato.stanford.edu/Aristotle-logic.

Размещено на Allbest.ru