- •1.3.6. Экстремальные характеристики отношения
- •3.2.3. Связь между исчислением высказываний и алгеброй
- •3.2.4. Основные результаты исследования исчисления
- •Предисловие
- •1.1. Понятие компьютинга и дискретной математики
- •1.2. Теория множеств
- •1.2.1. Основные понятия теории множеств
- •1.2.2. Способы задания множеств
- •1.2.3. Операции над множествами
- •1.2.4. Свойства операций над множествами
- •1.2.5. Аксиоматика теории множеств
- •1.3. Бинарные отношения и их свойства
- •1.3.1. Декартово произведение и бинарное отношение
- •1.3.2. Функции и операции
- •1.3.3. Способы задания бинарных отношений
- •1.3.4. Свойства бинарных отношений
- •1.3.5. Типы бинарных отношений
- •1.3.7. Отношение толерантности
- •1.3.8. Операции над отношениями
- •Контрольные вопросы и задания
- •2.1. Фундаментальные алгебры
- •2.2. Алгебра высказываний
- •2.3. Формализация логических высказываний
- •2.4. Таблицы истинности сложных высказываний
- •2.5. Равносильности алгебры высказываний
- •2.6. Булевы функции
- •2.7. Формы представления логических функций
- •2.7.1. Дизъюнктивные нормальные формы
- •2.7.2. Конъюнктивные нормальные формы
- •2.8.1. Законы алгебры Буля
- •2.8.2. Упрощение логических функций
- •2.8.3. Метод Квайна – МакКласки
- •2.9.1. Теорема о полноте системы булевых функций
- •2.10. Построение логических схем
- •Контрольные вопросы и задания
- •Глава 3. Формальные теории
- •3.1. Основные свойства формальных теорий
- •3.1.1. Выводимость
- •3.1.2. Интерпретация
- •3.1.3. Разрешимость
- •3.1.4. Общезначимость
- •3.1.5. Непротиворечивость
- •3.1.6. Полнота
- •3.1.7. Независимость
- •3.2. Исчисление высказываний
- •3.2.1. Интерпретация
- •3.2.2. Правило подстановки
- •3.2.3. Связь между исчислением высказываний
- •3.2.5. Другие формализации исчисления высказываний
- •3.3. Исчисление предикатов
- •3.3.2. Кванторные операции над предикатами
- •3.3.3. Формальное определение исчисления предикатов
- •Контрольные вопросы и задания
- •4.1. Прямые доказательства
- •4.1.1. Правило подстановки
- •4.1.2. Правило вывода
- •4.1.3. Дедукция
- •4.1.4. Математическая индукция
- •4.2. Косвенные доказательства
- •4.2.1. Доказательство «от противного»
- •4.2.2. Доказательство через контрпример
- •Контрольные вопросы и задания
- •Глава 5. Основы комбинаторики
- •5.1. Правила суммы и произведения
- •5.2. Перестановки
- •5.3. Размещения и сочетания
- •5.4. Разбиения
- •5.5. Формула включений и исключений
- •5.6. Рекуррентные соотношения
- •5.7. Производящие функции
- •5.8. Числа Стирлинга второго и первого рода
- •Контрольные вопросы и задания
- •Глава 6. Основы теории графов
- •6.1. Основные понятия
- •6.1.1. Классификация графов
- •6.1.2. Способы задания графов
- •6.2. Операции над графами
- •6.2.1. Удаление вершин и ребер
- •6.2.2. Дополнение
- •6.2.3. Объединение графов
- •6.2.4. Сложение графов
- •6.2.5. Произведение графов
- •6.3. Связность в графах
- •6.3.1. Компоненты связности
- •6.3.2. Вершинная и реберная связность
- •6.3.3. Сильная связность в графах
- •6.4. Цикломатика графов
- •6.4.1. Ациклические графы
- •6.4.2. Базисные циклы и цикломатическое число
- •6.4.3. Базисные разрезы и ранг
- •6.4.4. Эйлеровы графы
- •6.4.5. Гамильтоновы графы
- •6.5. Диаметр графа
- •6.5.1. Основные определения
- •6.5.2. Алгоритм нахождения диаметра
- •6.5.3. Поиск диаметра при операциях над графами
- •6.6. Устойчивость графов
- •6.6.1. Внутренняя устойчивость
- •6.6.1. Внешняя устойчивость
- •6.7. Хроматика графов
- •6.7.1. Хроматическое число
- •6.7.3. Двудольное представление графов
- •6.7.4. Хроматический класс
- •6.8. Преобразование графов
- •6.8.1. Реберные графы
- •6.8.2. Изоморфизм графов
- •6.8.3. Гомеоморфизм графов
- •6.8.4. Автоморфизм графов
- •6.9. Планарность
- •6.9.1. Основные определения
- •6.9.2. Критерии непланарности
- •6.10. Построение графов
- •6.10.1. Преобразование прилагательных в числительные
- •6.10.3. Оценка количества ребер сверху и снизу
- •Контрольные вопросы и задания
- •7.1. Введение в теорию нечетких моделей
- •7.1.1. Принятие решений в условиях неопределенности
- •7.1.2. Основы нечетких моделей
- •7.2. Нечеткие множества. Базовые определения
- •7.2.1. Базовые и нечеткие значения переменных
- •7.2.2. Основные определения
- •7.2.3. Типовые функции принадлежности
- •7.3. Операции над нечеткими множествами
- •7.3.1. Операция «дополнение»
- •7.3.2. Операция «пересечение»
- •7.3.3. Операция «объединение»
- •7.3.4. Операция «включение»
- •7.3.5. Операции «равенство» и «разность»
- •7.3.6. Операция «дизъюнктивная сумма»
- •7.3.7. Операции «концентрирование» и «растяжение»
- •7.3.8. Операция «отрицание»
- •7.3.9. Операция «контрастная интенсивность»
- •7.3.10. Операция «увеличение нечеткости»
- •7.4. Обобщенные нечеткие операторы
- •7.4.1. Треугольные нормы
- •7.4.2. Треугольные конормы
- •7.4.3. Декомпозиция нечетких множеств
- •7.5. Индекс нечеткости
- •7.5.1. Оценка нечеткости через энтропию
- •7.5.2. Метрический подход к оценке нечеткости
- •7.5.3. Аксиоматический подход
- •7.6. Нечеткие бинарные отношения
- •7.6.1. Нечеткие бинарные отношения
- •7.6.2. Свойства нечетких бинарных отношений
- •7.6.3. Операции над нечеткими отношениями
- •7.7. Нечеткие числа
- •7.8. Приближенные рассуждения
- •7.8.1. Нечеткая лингвистическая логика
- •7.8.2. Композиционное правило вывода
- •7.8.3. Правило modus ponens
- •Контрольные вопросы и задания
- •Список литературы
7.8.Приближенные рассуждения
Под приближенными рассуждениями понимается процесс,
при котором из нечетких посылок получают некоторые следствия, возможно, тоже нечеткие. Приближенные рассуждения лежат в основе способности человека понимать естественный язык, разбирать почерк, играть в игры, требующие умственных усилий, в общем, принимать решения в сложной и не полностью определенной среде. Эта способность рассуждений в качественных, неточных терминах отличает интеллект человека от интеллекта вычислительной машины.
7.8.1. Нечеткая лингвистическая логика
Лингвистическая переменная – переменная, значением кото-
рой являются слова или предложения естественного или искусственного языка.
Например, «возраст» – лингвистическая переменная, если она принимает значения «молодой», «немолодой», «старый», «не очень старый» и т.д.
Лингвистическая переменная описывается набором
(x,T (x),U , G, M ) ,
где х – название переменной; Т(х) – совокупность ее лингвистических значений (терм-множеств), т.е. множество названий лингвистических значений переменной х, причем каждое из таких значений является нечеткой переменной ~х со значениями из универсального множества U; U – универсальное множество; G – синтаксическое правило, порождающее термины множества Т(х), т.е. названия ~х значений переменной X; M – семантическое правило, которое ставит в соответствие каждой нечеткой переменной ~х ее смысл M( ~х ), т.е. нечеткое подмножество M( ~х ) универсального множества U.
Назначение семантического правила – связать совместимость первичных термов в составе лингвистического значения с совместимостью составного значения. Неопределенности, такие, как «очень», «вполне», «чрезвычайно», а также союзы «и», «или» по-
268
нимаются как нелинейные операторы, преобразующие смысл соответствующих терминов.
Конкретное название ~х , порожденное синтаксическим правилом G, называется термом. Терм, который состоит из одного слова или из нескольких слов, всегда фигурирующих вместе друг с другом, называется атомарным термом. Терм, который состоит из более чем одного атомарного терма, называется составным тер-
мом.
Лингвистическая переменная отличается от числовой переменной тем, что ее значениями являются не числа, а слова или предложения в естественном или формальном языке. Поскольку слова, в общем, менее точны, чем числа, понятие лингвистической переменной дает возможность приближенно описывать явления, которые настолько сложны, что не поддаются описанию в общепринятых количественных терминах. В частности, нечеткое множество, которое представляет собой ограничение, связанное со значениями лингвистической переменной, можно рассматривать как совокупную характеристику различных подклассов элементов универсального множества. В этом смысле роль нечетких множеств аналогична той роли, которую играют слова и предложения в естественном языке. Например, прилагательное «красивый» отражает комплекс характеристик внешности индивидуума. Это прилагательное можно также рассматривать как название нечеткого множества, которое является ограничением, обусловленным нечеткой переменной «красивый». С этой точки зрения термины «очень красивый», «некрасивый», «чрезвычайно красивый», «вполне красивый» и т.п. – названия нечетких множеств, образованных путем действия модификаторов «очень, не, чрезвычайно, вполне» и т.п. на нечеткое множество «красивый». В сущности, эти нечеткие множества вместе с нечетким множеством «красивый» играют роль значений лингвистической переменной «внешность».
Важный аспект понятия лингвистической переменной состоит в том, что эта переменная более высокого порядка, чем нечеткая переменная, в том смысле, что значениями лингвистической переменной являются нечеткие переменные. Например, значениями лингвистической переменной «возраст» могут быть: «молодой, немолодой, старый, очень старый, не молодой и не старый» и т.п. Каждое из этих значений является названием нечеткой переменной.
269
Если ~х – название нечеткой переменной, то ограничение, обусловленное этим названием, можно интерпретировать как смысл нечеткой переменной ~х .
Любая нечеткая переменная характеризуется тройкой
< x,U, X > ,
где x – название переменной, U – универсальное множество, X – нечеткое подмножество множества U, представляющее собой нечеткое ограничение на значение переменной u U , обусловленное x.
Используя аналогию с саквояжем, нечеткую переменную можно уподобить саквояжу с ярлыком, имеющим «мягкие» стенки. Тогда х – надпись на ярлыке (название саквояжа), U – список предметов, которые в принципе можно поместить в саквояж, а X – часть этого списка, где для каждого предмета u указано число μХ (и) , характе-
ризующее степень легкости, с которой предмет можно поместить в саквояж x.
Другой важный аспект понятия лингвистической переменной состоит в том, что лингвистической переменной присущи два правила:
1)синтаксическое, которое может быть задано в форме грамматики, порождающей название значений переменной;
2)семантическое, которое определяет алгоритмическую процедуру для вычисления смысла каждого значения.
Задача 7.9. Рассмотрим лингвистическую переменную с именем
х= «температура в комнате». Определить оставшуюся четверку
<Т(x),U ,G, M >.
Решение.
1)универсальное множество U=[5,35];
2)терм-множество T = {«холодно», «комфортно», «жарко»} с такими функциями принадлежностями:
μхолодно (и) = |
|
|
|
1 |
|
|
|
, |
|
|
|
и |
|
|
|
||||
1 + ( |
−10 |
)12 |
|
|
|||||
|
|
||||||||
|
|
|
|
7 |
|
|
|
|
|
μкомфортно (и) = |
|
|
1 |
|
|
|
|
, |
|
|
|
и − |
|
||||||
1 + ( |
20 |
)6 |
|
||||||
3 |
|
||||||||
|
|
|
|
|
|
|
|
|
270
μжарко (и) = |
|
|
1 |
|
|
; |
|
|
и − |
|
|||
1 |
+ ( |
30 |
)10 |
|
||
6 |
|
|||||
|
|
|
|
|
|
3)синтаксическое правило G, порождающее новые термы с использованием квантификаторов «и», «или», «не», «очень», «болееменее» и других;
4)семантическое правило М будет являться процедурой, ставящей каждому новому терму в соответствие нечеткое множество из X по правилам, заданным в табл. 7.6.
Таблица 7.6
Правила определения квантификаторов
Квантификатор |
Функция принадлежности ( u U ) |
Не t |
1 −μt (u) |
Очень t |
(μt (u))2 |
Более-менее t |
μt (u) |
|
|
А и В |
max(μA (x), μB (x)) |
А или В |
min(μA (x), μB (x)) |
Рис. 7.8
271