- •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
- •Контрольные вопросы и задания
- •Список литературы
h(R) = max max μR (x, y) = max max μR (x, y) |
|
x y |
y x |
или h(R)=R(1)(2) =R(2)(1) .
Если h(R)=1 – отношение нормально, если h(R)<1 – субнормально.
Важное значение в теории нечетких множеств имеет композиция (или произведение) нечетких отношений. В отличие от обычных (четких) отношений композицию (произведение) нечетких отношений можно определить разными способами.
Нечеткое отношение R = R1R2 называется максиминной компо-
зицией (произведением) нечетких отношений R1 и R2, если его функция принадлежности определяется выражением
μR (x, z) = max min{μR (x, y), μR |
( y, z)}. |
|
y U |
1 |
2 |
|
|
Нечеткое отношение R = R1 R2 называется минимаксной ком-
позицией (произведением) нечетких отношений R1 и R2, если его функция принадлежности определяется выражением
μR (x, z) = min max{μR |
(x, y), μR |
( y, z)}. |
|
y U |
1 |
|
2 |
Нечеткое отношение R = R1 R2 |
|
называется максимультипли- |
кативной композицией (произведением) нечетких отношений R1 и R2, если его функция принадлежности определяется выражением
μR (x, z) =sup{μR1 (x, y) μR2 (y, z)} .
y U
7.7. Нечеткие числа
Нечеткое число – это нечеткое подмножество универсального множества действительных чисел, имеющее нормальную и выпуклую функцию принадлежности, то есть такую, что:
•существует значение носителя, в котором функция принадлежности равна единице (условие нормальности);
•при отступлении от своего максимума влево или вправо функция принадлежности не возрастает (условие выпуклости).
Нечеткое число А унимодально, если условие μА (х) =1 справедливо только для одной точки действительной оси.
265
Выпуклое нечеткое число А называется нечетким нулем, если
μА (0) = sup(μA (x)) .
U
Подмножество S A называется носителем нечеткого числа А,
если S A ={x | μA > 0}.
Нечеткое число А положительно, если x S A x > 0 , и от-
рицательно, если x S A x < 0 .
Нечеткие числа (L-R)-типа – это разновидность нечетких чисел специального вида, задаваемых по определенным правилам с целью снижения объема вычислений при операциях над ними.
Функции принадлежности нечетких чисел (L-R)-типа задаются с помощью невозрастающих на множестве неотрицательных действительных чисел функций действительного переменного L(x) и
R(x).
Возможные графики функций принадлежности нечетких чисел (L-R)-типа приведены на рис. 7.7.
Рис. 7.7
Пусть L(у) и R(у) – функции (L-R)-типа. Унимодальное нечеткое число А с модой а (т.е. μА (а) =1 ) задается с помощью L(у) и R(у)
следующим образом:
μА
L( (х) =
R(
a α− x ), x −β a ),
если х ≤ а;
если х ≥ а,
266
где а – мода; α > 0, β>0 – левый и правый коэффициенты нечеткости.
Таким образом, при заданных L(у) и R(у) нечеткое число (унимодальное) задается тройкой А=(а;α,β).
Толерантное нечеткое число задается, соответственно, четверкой параметров А=(а1,а2;α,β), где а1 и а2 – границы толерантности, т.е. в промежутке [а1;а2] значение функции принадлежности равно 1. Толерантные нечеткие числа (L-R)-типа называются тра-
пезоидными числами.
Унимодальные нечеткие числа (L-R)-типа называются тре-
угольными числами.
Треугольные числа формализуют высказывания типа «приблизительно равно a». Ясно, что а ± δ≈ а, причем по мере убывания δ до нуля степень уверенности в оценке растет до единицы.
На практике часто используется альтернативное определение нечеткого треугольного числа.
Треугольным нечетким числом А называется тройка <a,b,c> (a≤b≤c) действительных чисел, через которые его функция принадлежности μА (х) определяется следующим образом:
x − a |
, |
если х [a;b]; |
||
|
|
|
||
|
|
|||
b |
− a |
|
|
|
x − c |
|
|
||
μА(x) = |
|
|
, |
если х [b; c]; |
|
− c |
|||
b |
|
|
||
0, |
в противном случае. |
|||
|
|
|
|
|
|
|
|
|
Второе число b тройки <a,b,c> обычно называют модой или
четким значением нечеткого треугольного числа. Числа a и c характеризуют степень размытости четкого числа.
В общем случае при определении нечеткого треугольного числа не обязательно использовать линейные функции. Часто в различных приложениях используются две функции, из которых одна монотонно возрастает на интервале [a;b], а другая монотонно убывает на интервале [b;c].
267