ГЛАВА 6. НЕЧЕТКАЯ ЛОГИКА И ПРИБЛИЖЕННЫЕ РАССУЖДЕНИЯ

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

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

Пусть переменные со значениями из [0, 1]. Мы будем использовать следующие обозначения: (отрицание), (дизъюнкция), (конъюнкция). Нечеткая формула определяет функцию, задающую отображение из в [0, 1]. Определим нечеткую формулу с помощью следующих правил:

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

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

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

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

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

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

Определение 6.1. Нечеткая формула называется общезначимой (противоречивой), если для всех значений переменных формулы Нечеткая формула необщезначима (непротиворечива), если она не является общезначимой (противоречивой).

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

а) рассмотрим формулу тогда

Таким образом, — общезначима (см. рис. 6.1, а).

б) рассмотрим формулу тогда

Таким образом, и противоречива (см. рис. 6.1, б) .

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

Рис. 6.1. Графическое изображение нечетких формул

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

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

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

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

Теорема 6.1. Формула нечетко общезначима (нечетко противоречива) тогда и только тогда, когда -общезначима (противоречива).

Нечеткие формулы, рассматриваемые как отображения из в [0, 1], сохраняют отношение частичного порядка А такое, что и только тогда, когда либо либо Например, имеет место , а величины — несравнимы. Выражение обозначает, что является более неопределенным значением истинности, чем

Отношение А может быть расширено на следующим образом:

тогда и только тогда, когда Имеет место следующая теорема [46].

Теорема 6.2. Пусть — нечеткая формула, задающая отображение ; если тогда

Теперь обратимся к понятию нечеткой импликации. Хорошо известно, что в двузначной логике формула влечет формулу если При этом называется импликантом называется импликатом

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

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

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

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

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

следует или

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

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

Заметим, что в двухзначной логике Ф является первичным импликантом если и из следует

или (т. е. Ф — непротиворечив). Аналогично, первичный импликат считается не равным 1 (противоречивым). Например, для четкой формулы очевидно Следовательно, первичным импликатом является только у. В нечеткой логике формула имеет два НПИ, так как

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 6.5 [49]. Пусть и — нечеткие функции; тогда порождаются всеми конъюнкциями (дизъюнкциями ), где и последующим вычеркиванием тех

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

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

а) заменить каждый конъюнкт на его НПИ, используя теорему 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], основанные на понятии нечеткого следствия, приведенные ниже.

Пусть — конъюнкты над множествами переменных Нечетким следствием называется противоречивый конъюнкт Ф, построенный следующим образом: ищется такой, что где не содержат переменной полагается тогда и только тогда, когда является противоречивым конъюнктом; полагается тогда и только тогда, когда является простым конъюнктом означает либо либо Тогда алгоритм порождения первичных импликантов основан на следующей теореме [46].

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

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

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

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

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

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

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

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

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

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

В работах [30—32] принцип резолюции [8] обобщен на случай специальной нечеткой логики. Пусть задана формула Формула С является логическим следствием тогда и только тогда, когда формула противоречива. Если противоречива, то для всех интерпретаций. Для заданного множества дизъюнктов следствие С (которое считается дизъюнктом) называется первичным логическим следствием если не существует других логических следствий С множеств (тоже дизъюнктов) таких, что С также является логическим следствием С.

Пусть — множество дизъюнктов. Резолюция обозначаемая это множество, состоящее из элементов вместе с резольвентами всех пар элементов Резолюция степени, обозначаемая определяется для всех следующим образом: Тогда теорема 6.7 [21] утверждает, что принцип резолюции является полным в специальной нечеткой логике.

Теорема 6.7. В нечеткой логике, если некоторый дизъюнкт С является первичным логическим следствием множества дизъюнктов то для некоторого

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

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

и

а любой дизъюнкт из множества Тогда для всех

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

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

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