§ 6.1. Специальная нечеткая логика

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

Пусть Хі (і = 1, п)— переменные со значениями из [О, 1]. Мы будем использовать следующие обозначения: ~\х = і — х (отрицание), Хі V Ха = max(а:і, х^) (дизъюнкция), x-^f\x^ = = min(a;i, х^) (конъюнкция). Нечеткая формула определяет функцию, задающую отображение из [О, 1]” в [О, 1]. Определим нечеткую формулу с помощью следующих правил:

а)   числа О и 1 — нечеткие формулы,

б)   нечеткая переменная Хі — нечеткая формула,

в)   если /— нечеткая формула,    — нечеткая формула.

г)   если / и g —нечеткие формулы, то f/\g и /Vg —нечеткие формулы,

д)   других формул нет.

Нечеткие формулы являются обобщением структуры булевых функций, так как удовлетворяют всем аксиомам последних, кроме закона о дополнении, т. е. /ѴЛ/^1, и /Л~1/=/=0. Следовательно, нечеткие формулы образуют дистрибутивную структуру с псевдодополнением (алгебра Де Моргана). Пусть Г— истинностная функция, — множество нечетких формул.

Определение 6.1. Нечеткая формула называется

общезначимой (противоречивой), если T{f)> 0,5 (Г(/)^0,5) для всех значений переменных формулы /. Нечеткая формула 1 ^ необщезначима (непротиворечива), если она не является общезначимой (противоречивой).

Приведем примеры общезначимых и противоречивых формул:

а)   рассмотрим формулу/ = а; Ѵ~Іа:, тогда

Таким образом, T{f)>0,5 и / — общезначима (см. рис. 6.1, а).

б)   рассмотрим формулу g=x/\~]x, тогда

Таким образом, T(g)^0,b и g противоречива (см. рис. 6.1,6).

Назовем литералом переменную Хі или ее отрицание П х<. Фразой или конъюнктом назовем конъюнкцию литералов. Дизъюнкцию литералов назовем предложением (дизъюнктом) .

Определение 6.2. Нечеткая формула / является дизъюнктивной нормальной формой (ДНФ), если

где Ф; — конъюнкты. Определение 6.3. Нечеткая формула / называется конъюнктивной нормальной формой (КНФ), если

где Cj — дизъюнкты.

В работе [49] показано, что понятия общезначимости и противоречивости в нечеткой и обычной логике совпадают, точнее, имеет место следующая теорема.

Теорема 6.1. Формула    нечетко общезначима (не

четко противоречива) тогда и только тогда, когда /—общезначима (противоречива).

Нечеткие формулы, рассматриваемые как отображения из [О, 1]” в [О, 1], сохраняют отношение частичного порядка А такое, что V^i, ajS[0, 1] UiAaj тогда и только тогда, когда либо 0,5^ sSa'i^flj, либо 0,5>ai>aj. Например, имеет место 0,54а,- Ѵа^е е [О, 1], а величины а, е ]0,5, 1] и aj е [О, 0,5] — несравнимы. Выражение а-Ащ обозначает, что аі является более неопределенным значением истинности, чем а,.

Отношение А может быть расширено на [О, 1]" следуюш;им образом:

аАЬ тогда и только тогда, когда Ѵі — 1,п UiAbi. Имеет место следующая теорема [46].

Теорема 6.2. Пусть / — нечеткая формула, задающая отображение [О, 1]" [О, 1]; если аАЬ, тогда f{a)Af{b).

Теперь обратимся к понятию нечеткой импликации. Хорошо известно, что в двузначной логике формула / влечет формулу g, если T{f) = i=^ T(g) = 1. При этом / называется импликантом g, а g называется импликатом /.

Определение 6.4. Пусть f я g — две нечеткие формулы. Будем говорить, что / нечетко имплицирует g или f\g, если

В этом случае будем говорить, что / н-имп.тіицирует g, или / является н-импликантом g или, что g — н-импликат /. Поскольку в дальнейшем мы будем иметь дело в основном только с нечеткими формулами, букву «н» будем опускать.

Рассмотрим примеры нечетких импликаций:

Введем определение нечеткого первичного импликанта.

Определение 6.5. Пусть / — формула в ДНФ и Ф — конъюнкт. Назовем Ф нечетким первичным импликантом / (сокращенно НПИ), если из

следует Ф' = Ф или Ф' = /.

Таким образом, НПИ является максимальным элементом во множестве всех истинных нечетких импликант в соответствии с упорядочением, порожденным «->-». Аналогично определяется двойственное понятие нечеткого первичного импликата (НПи).

Определение 6.6. Пусть / — формула в КНФ и С — дизъюнкт. Назовем С нечетким первичным импликатом *) /, (сокращенно НПи), если из f-^C ж f-^ С', С'->~С следует, что С' = / или С' = С.

Заметим, что в двухзначной логике Ф является первичным импликантом /, если Ф ->■ / и из Ф Ф', Ф' -^ / следует Ф = Ф'

или Ф' = | п Ф^О (т. е. Ф — непротиворечив). Аналогично, первичный импликат считается не равным 1 (противоречивым). Например, для четкой формулы f = х Д \x\J у очевидно х Д Д I x~*-f, у -*-]• Следовательно, первичным имплпкатом является только у. В нечеткой логике формула / имеет два НПИ, так как гД и у->/.

Мы можем теперь поставить задачу порождения всех НПИ нечеткой функции. Эта проблема связана с задачей нахождения минимальной формы для нечетких функций. Для нахождения минимальной формы нечетких функций важной является следующая характеристика элементов, неразложимых в объединение.

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

Для нечеткой функции существует и единственно ее представление в виде объединения неразложимых элементов. При поиске этой формы представления может быть использован следующий алгоритм:

а)   записать функцию / в ДНФ, используя соотношения алгебры Моргана для нечетких функций;

б)   элементы в /, неразложимые в объединение, умножить на Хі V”1 xs, соответствующее каждой пропущенной литере;

в)   новое выражение опять записать в ДНФ;

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

д)   полученное выражение является единственным представлением /.

Задача порождения всех нечетких первичных импликант и импликат нечеткой функции может быть решена с помощью следующей теоремы [49].

Теорема 6.4. Следующие утверждения истинны:

а)   нечеткими первичными импликантами (нечеткими первичными импликатами) дизъюнктов (конъюнктов), неразложимых в пересечение (в объединение), являются все их литералы;

б)   нечеткими первичными импликантами (нечеткими первичными импликатами) дизъюнктов (конъюнктов), неразложимых в пересечение (в объединение), являются все их литералы и все конъюнкции Хі Д \хі (все дизъюнкции ЖіѴ-]хі), соответствующие пропущенным литералам.

Обозначим через НПИ(/) и НПи(/) множества всех НПИ и НПи нечеткой формулы /.

Теорема 6.5 [49]. Пусть / и g — нечеткие функции; тогда НПИ (НПи) / Д g (fVg) порождаются всеми конъюнкциями р Д q (дизъюнкциями pV q), где /?<^НПИ(/), ^еНПИ(^) (р^ еНПи(/) и ^еНПп(^)), и последующим вычеркиванием тех

конъюнкций (дизъюнкций), которые имплицируют (имплицируются) другими.

Алгоритм для нахождения всех НПИ и НПи будет следующим:

а)   заменить каждый конъюнкт на его НПИ, используя теорему 6.4;

б)   вычислить для / НПи, используя теорему 6.5 (дизъюнкцию импликат);

в)   заменить каждый НПи на его НПИ, снова используя теорему 6.4;

г)   вычислить для / ее НПИ, снова используя теорему 6.5 (конъюнкцию импликант).

Алгоритм для порождения всех первичных импликант предложен в [29] и в [53]. Эти методы были подвергнуты критике в работах [20, 50]. Затем в [21] предложен метод, основанный на понятии нечеткого следствия, расширенный в [22] на случай неполностью определенных нечетких выражений. Дальнейшие модификации метода содержатся в [19, 23, 24, 28, 46].

Для этой же цели в [15] предложен другой метод, основанный на различии между простыми конъюнктами и противоречивыми конъюнктами канонической дизъюнктивной формы нечеткого выражения. Этот подход подробно исследован в [13, 47, 49]. Позднее в [48] предложен быстрый алгоритм, которыіі находит сразу особые первичные импликанты, т. е. те первичные импликанты, чьи дизъюнкции образуют минимальную дизъюнктивную форму для рассматриваемого нечеткого выражения. В настоящем изложении мы опирались, в основном, на [49]. Представляют также интерес алгоритмы [21, 46], основанные на понятии нечеткого следствия, приведенные ниже.

Пусть Р и Р' — конъюнкты над множествами переменных {хі, х2, ..., х„}. Нечетким следствием Р и Р' называется противоречивый конъюнкт Ф, построенный следующим образом: ищется Хі такой, что Р = Хі/\ Q, Р' =(_1 x*)/\Q', где Q, Q' не содержат неремепной х{; полагается Ф = Q Д Q' тогда и только тогда, когда Q t\Q' является противоречивым конъюнктом; полагается Ф = Q Д Q' Д Х\ Д СП хі) тогда и только тогда, когда Q f\Q'

(♦ |

Xj означает либо xt, либо \xt). Тогда алгоритм порождения первичных импликантов основан на следующей теореме [46].

Теорема 6.6. Дизъюнктивная форма нечеткого выражения / содержит все своп первичные импликанты тогда и только тогда, когда

1)   не существует конъюнкта, который является импликантом другого конъюнкта /;

2)   нечеткие следствия любых двух конъюнктов либо не существуют, либо являются следствиями, по крайней мере, одного конъюнкта /.

Аналогичная теорема предложена в [49].

Теперь можно построить следующий алгоритм порождения первичных импликант. Пусть f(xi, Хп)—нечеткая функция в ДНФ, тогда:

а)   сравнить каждую пару конъюнктов в / и вычеркнуть те, из которых следуют другие;

б)   нечеткое следствие каждых двух конъюнктов добавить к списку, если конъюнкты из следствия не имплицируют другие члены в /;

в)   вычеркнуть все конъюнкты, которые имплицируют другие.

г)   повторять пп. б) и в) до тех пор, пока не выполнится условие теоремы 6.6.

Полученные конъюнкты будут являться всеми НПИ функции /.

В работах [30—32] принцип резолюции [8] обобщен на случай специальной нечеткой логики. Пусть задана формула /. Формула С является логическим следствием / тогда и только тогда, когда формула 1 /\~Лё противоречива. Если f /\~\ё противоречива, то Г (/ Д “П g) < 0,5 для всех интерпретации. Для заданного множества дизъюнктов следствие С (которое считается дизъюнктом) называется первичным логическим следствием S, если не существует других логических следствий С' множеств S (тоже дизъюнктов) таких, что С также является логическим следствием С.

Пусть S — множество дизъюнктов. Резолюция S, обозначаемая R{S),— это множество, состоящее из элементов S вместе с резольвентами всех пар элементов S. Резолюция п-іі степени, обозначаемая R"{S), определяется для всех п'^0 следующим образом; R°(S) = S и /?"“■*■* (5) = Л (/?" (5)). Тогда теорема 6.7 [21] утверждает, что принцип резолюции является полным в специальной нечеткой логике.

Теорема 6.7. В нечеткой логике, если некоторый дизъюнкт С является первичным логическим следствием множества дизъюнктов S, то для некоторого п>0, C^R’‘(S).

Имеет место следующая интересная теорема, которая утверждает, что если каждый дизъюнкт в S немного больше, чем «полу- истина», и наиболее ненадежный дизъюнкт имеет значение истинности а, т. е. гарантируется, что все логичесіше следствия, полученные повторным применением принципа резолюции, имеют значения истинности по крайней мере а, но никогда не превышают значения истпнностп наиболее надежного дизъюнкта.

Теорема 6.8. Пусть 5 — множество дизъюнктов, а Сі, Сг, ... ..., См — дизъюнкты из S. Пусть также

и

а Сп — любой дизъюнкт из множества R71 (S). Тогда для всех п> 0 а<Т(Сп)^Ь.

Полезность этой теоремы мы можем проиллюстрировать следующим простым рассуждением. Пусть имеется два множества дизъюиктов S, и S2, представляющих два информационных массива. Из Si мы можем вывести логическое следствие, которое рекомендует добираться до работы на автобусе. Из S2 мы можем вывести логическое следствие, которое рекомендует добираться до работы на метро. Пусть, например, T(Sl) = 0,6 и T(S2) = 0,9, где Т (Sj) = min Т (Су),     В соответствии с теоремой мы

і

можем заключить, что корректность второго предложения, по крайней мере, 0,9, в то время, как про первое гарантировано только то, что его корректность не менее 0,6. Тогда риск при принятии первого решения может быть 0,4, а второго — не выше 0,1. Чтобы минимизировать максимальный возможный риск, надо принять второе решение и ехать на метро.

Теорема 6.7 была обобщена в [31], где доказано, что принципы семантической лок-резолюции, IDI-резолюции и LI-резолюции [8] являются полными в специальной нечеткой логике.

В гл. 1 описаны L-нечеткие множества, функции принадлежности которых могут принимать значения в произвольной дистрибутивной решетке. Логика, множеством значений истинности которой является некоторая полная дистрибутивная решетка, связанная с теорией L-нечетких множеств, называется общей нечеткой логикой. Мы не будем останавливаться на логиках этого типа. Отметим только, что в [32] на случай общей нечеткой логики были обобщены теоремы 6.1, 6.7, а также результаты [31], т. е. доказано, что обычный принцип резолюции, а также IDI- резолюция и Ll-резолюция являются полными в общей нечеткой логике.