- •Глава 16. Специальные циклы и метрика графов 345
- •Глава 17. Графовые инварианты 404
- •Введение
- •Цели и задачи преподавания дисциплины «дискретная математика»
- •Модуль 1. Основы Теории множеств (2 кредита)
- •Комплексная цель и задачи изучения модуля
- •Глава 1. Исчисление множеств
- •1.1. Понятие множества
- •1.2. Способы задания множеств
- •1.3. Подмножество
- •2. Пустое множество не имеет собственных и истинных подмножеств.
- •3. Одноэлементное множество имеет два подмножества - сaмo себя и , т.Е. Не имеет собственных подмножеств.
- •Множество – это многое, мыслимое как единое.
- •Глава 2. Операции над множествами
- •2.1. Объединение множеств
- •2.2. Пересечение множеств
- •2.3. Разность множеств
- •2.4. Дополнение множества
- •2.5. Тождества алгебры множеств
- •2.6. Доказательства тождеств с множествами
- •Глава 3. Упорядоченные множества
- •3.1. Кортеж (Упорядоченное множество)
- •3.2. Декартово произведение
- •3.3. Операция проектирования множеств
- •3.4. График
- •Декартово произведение множеств позволяет перейти к графическому представлению упорядоченных множеств.
- •Глава 4. Отношения
- •4.1. Основные понятия отношений
- •4.2. Основные свойства отношений
- •4.3. Операции над отношениями
- •4.4. Основные свойства специальных отношений
- •4.5. Разбиение множеств
- •4.6. Отношение порядка
- •Использование отношений позволяет строить модели взаимосвязей между любыми обьектами в природе.
- •5. Соответствия
- •5.1. Определение соответствия
- •5.2. Операции над соответствиями
- •5.3. Понятия образа и прообраза при соответствии
- •5.4. Доказательства тождеств с соответствиями
- •5.5. Основные свойства соответствий
- •5.6. Функция
- •Глава 6. Упорядоченные бесконечные множества
- •6.1. Основные сведения об упорядоченных бесконечных множествах
- •6.2. Проблема континуума
- •Глава 7. Основные понятия теории мультимножеств
- •7.1. Понятие мультимножества
- •7.2. Операции над мультимножествами
- •Возможность многократного вхождения элементов в мультимножество создает новое качество и позволяет расширить класс описываемых, анализируемых и синтезируемых математических объектов.
- •8. Нечеткие множества
- •8.1. Нечеткие высказывания
- •8.2. Операции над нечеткими множествами
- •8.3. Нечеткие отношения и соответствия
- •Тестовые задания к модулю 1
- •24. Множество называется графиком, если каждый его элемент ...
- •25. Соответствие может быть задано … способом.
- •Критерии оценки
- •Нечеткие и приближенные высказывания, множества, соответствия и отношения позволяют формально задавать расплывчатую информацию в виде, удобном для обработки на эвм.
- •Глоссарий к модулю 1
- •Глава 1.
- •Глава 2.
- •Глава 3.
- •Глава 4.
- •Глава 5.
- •Глава 6.
- •Глава 7.
- •Глава 8.
- •Галилей Модуль 2. Основы теории алгоритмов (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 9. Введение в теорию алгоритмов
- •9.1. Понятие алгоритма
- •9.2. Основные свойства алгоритмов
- •9.3. Классификация алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •10.1. Преобразование слов в произвольных абстрактных алфавитах
- •10.2. Числовые функции
- •10.3. Построение алгоритмов по принципу «разделяй и властвуй»
- •10.4. Представление алгоритма в виде детерминированного устройства
- •10.5. Универсальные схемы алгоритмов
- •10.5. “Жадные” алгоритмы
- •10.6. Нечеткие (расплывчатые) алгоритмы
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •11.1. Анализ алгоритмов
- •11.2. Сложность алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 2
- •Критерии оценки
- •Модуль 3. Алгебра логики (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 12. Элементы алгебры логики
- •12.1. Логические функции
- •12.2. Основные логические тождества и законы
- •12.3. Булевы функции одной и двух переменных
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •13.1. Дизъюнктивная и конъюнктивная нормальные формы
- •13.2. Способы перехода от нормальных к совершенным нормальным формам
- •2. Графический способ.
- •13.4. Функциональная полнота бф
- •13.3. Алгебра Жегалкина
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •14.1. Реализация булевых функций
- •14.2. Минимизация булевых функций
- •14.3. Карты Карно
- •14.4. Метод Квайна - Мак-Класски
- •14.5. Переход от бф к простейшим комбинационным схемам
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Критерии оценки
- •Глоссарий к модулю 3
- •Модуль 4. Основы Теории графОв (2 кредита) Комплексная цель и задачи изучения модуля
- •Глава 15. Введение в теорию графов
- •15.1. Способы задания графов и виды графов
- •15.1.1. Способы задания графов
- •15.1.2. Виды графов
- •15.1.3. Нечеткие неориентированные графы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •15.2. Маршруты, цепи, циклы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •При моделировании систем модели и алгоритмы нахождения маршрутов, цепей, циклов, разрезов, связности графов позволяют строить эффективные алгоритмы преобразования графов.
- •15.3. Нахождение кратчайших маршрутов (цепей)
- •15.3.1. Алгоритм Форда
- •15.3.2. Алгоритм Дейкстры
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Алгоритмы Форда и Дейкстры являются эффективным способом определения кратчайшей по стоимости цепи между двумя вершинами графа.
- •Глава 16. Специальные циклы и метрика графов
- •16.1. Эйлеровы и гамильтоновы цепи и циклы
- •16.1.1. Связь между эйлеровыми и гамильтоновыми графами
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.2. Алгоритмы построения гамильтонова цикла
- •16.2.1. Алгоритм Робертса ─ Флореса
- •16.2.2. Алгебраический метод
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.3. Задача о коммивояжере и алгоритмы ее решения
- •16.3.1. Алгоритм Хелда и Карпа
- •16.3.2. Геометрический метод решения
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.4. Расстояния на графах
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.5. Деревья
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Глава 17. Графовые инварианты
- •17.1. Цикломатическое и хроматическое числа графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.2. Числа внутренней и внешней устойчивости графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Числа внутренней и внешней устойчивости относятся к инвариантам графа. Они позволяют определить специальные группы вершин в графах.
- •17.3. Планарность графов
- •17.3.1. Плоские и планарные графы
- •17.3.2. Эвристики для определения планарности
- •17.3.3. Минимизация пересечений ребер графов
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.4. Ориентированные графы
- •17.4.1. Способы задания
- •17.4.2. Решение стандартных графовых задач с использованием орграфов
- •17.4.3. Выделение сильносвязных компонент
- •17.4.4. Нечеткие ориентированные графы
- •Примеры решения задач
- •Вопросы
- •Задания для самостоятельной работы
- •175 Гиперграфы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 4
- •Критерии оценки
- •Глоссарий к модулю 4 Глоссарий к главе 1
- •Глоссарий к главе 2
- •Глоссарий к главе 3
- •Библиографический комментарий
- •Литература
- •Заключение
- •Приложение 1
- •Учебное издание Гладков Леонид Анатольевич, Курейчик Владимир Викторович, Курейчик Виктор Михайлович
Возможность многократного вхождения элементов в мультимножество создает новое качество и позволяет расширить класс описываемых, анализируемых и синтезируемых математических объектов.
Часто неясность происходит столько же от многословия, сколько и от излишней краткости.
Ж. Даламбер
8. Нечеткие множества
Понятие нечеткого высказывания, степень истинности нечеткого высказывания, функция принадлежности, операции над нечеткими высказываниями, определение и способы задания нечетких множеств, операции над нечеткими множествами, нечеткие отношения и соответствия
ЦЕЛИ
Освоив эту главу студенты должны:
иметь понятия о нечетких множествах;
уметь строить функцию принадлежности;
определять степень истинности составных высказываний;
уметь выполнять операции над нечеткими множествами и высказываниями;
иметь понятие о нечетких отношениях и соответствиях и операциях над ними.
8.1. Нечеткие высказывания
В множествах можно однозначно указать, принадлежит или не принадлежит рассматриваемый элемент данному множеству. Следовательно, рассматриваемые выше множества имеют четкие границы, определяющие принадлежность или не принадлежность элемента множеству. В интеллектуальных системах часто нельзя провести четкую грань между принадлежностью и не принадлежностью элементов множеству. В этой связи возникло предположение описывать множества объектов с расплывчатыми границами принадлежности. Например, как определить понятие красоты, любви, удачи, счастья и других расплывчатых понятий. Л.Заде является основателем теории нечетких множеств. Он предложил ввести числовую меру описания расплывчатых понятий. Это дает возможность использовать существующий математический аппарат для описания, преобразования и исследования расплывчатых понятий.
Пусть задано произвольное непустое множество Х.
Х
= {x1,
x2,
..., xn}.
Множество
называется
нечетким или
расплывчатым множеством в
Х и обозначается
= {<А(x),
x>}, xX.
В нечетком множестве каждый элемент есть кортеж длины два, первая компонента которого обозначается А(х) и называется функцией принадлежности. Она задается на сегменте [0, 1]. Вторая компонента кортежа — элемент множества Х.
При задании множества каждому элементу х присваивается число 0 А(х) 1. Это число и определяет степень принадлежности элемента х множеству .
Например, пусть задано некотрое множество X = { x1, x2, x3, x4 }. Тогда одним из возможных нечетких множеств на множестве Х будет множество = { < 0.1, x1 >, < 1, x2 >, < 0, x3 >, < 0.8, x4 >}.
Носителем нечеткого множества называется подмножество А Х, содержащее те элементы из Х, для которых А(х) > 0. Функция принадлежности для каждого нечеткого множества определяется субъективно. В настоящее время для нахождения функции принадлежности используют экспертные системы.
Рассмотрим нечеткие высказывания. Нечетким высказыванием называется предложение, относительно которого можно судить о степени его истинности или ложности.
Например, нечеткое высказывание: “2 — маленькое число”. Данное высказывание является субъективным. Если четкое множество Х на котором выбрано число 2 является – относительно большим, например, Х=100. Тогда нечеткое высказывание: “2 — маленькое число” является истинным. Если, например, Х=3, тогда рассматриваемое высказывание является ложным.
Нечеткое высказывание, равное 0.5, называется индифферентным, т.к. оно истинно в той же степени, что и ложно. Следовательно истинность нечеткого высказывания является субъективной характеристикой. Нечеткие высказывания бывают простые и составные. Составные образуются из простых с помощью логических операций: отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности.
Отрицанием высказывания называется нечеткое высказывание не , степень истинности которого определяется по формуле:
= 1 — . (8.1)
Символ в данной главе используется для обозначения инверсии.
Конъюнкцией
высказываний
,
называется нечеткое высказывание,
степень которого определяется по
формуле:
= min ( ). (8.2)
Дизъюнкцией высказываний называется нечеткое высказывание, степень которого определяется по формуле:
= max ( ). (8.3)
Импликацией высказываний называется нечеткое высказывание:
= max (1 — , ). (8.4)
Из последнего выражения вытекает, что степень истинности не меньше, чем степень неистинности ее посылки или степень истинности ее следствия.
Эквивалентностью высказываний называется новое составное нечеткое высказывание обозначаемое:
= min(max(1 - , ),max(1 - , )). (8.5)
Если степени истинности нечетких высказываний и одинаковы, то степень истинности эквивалентности лежит в сегменте [0.5, 1].
Пример.
Пусть
= 0.7,
= 0.4,
= 0.9 и требуется найти степень истинности
следующего составного нечеткого
высказывания:
=
(
)
(
).
= max(1 — ( ), ( )) = = max((1—max( , )), 1 — ) = = max((1 — max(min( , 1 — ), min(1 — , ))), 1 — min( , )) = max((1 — max(min(0.7, 0.6), min(0.3, 0.4))), 1 — min(0.7, 0.9)) = max(1 — max(0.6, 0.3), 0.3) = max(0.4, 0.3) = 0.4.
При вычислении степени истинности данного составного высказывания использовались формулы (8.1) – (8.5).
Введем понятие степени включения нечетких множеств. Пусть задано множество Х и на нем нечеткие множества , . Тогда степень включения нечеткого множества в нечеткое множество обозначается ( , ) и определяется по формуле
( , ) = (А(х) В(х)).
хХ
Если ( , ) 0.5, то считается, что нечеткое множество нестрого включается в . . Если ( , ) < 0.5, то не включается в .
Например. Пусть на множестве Х = {x1, x2, x3, x4, x5} заданы два нечетких множества = { < 0.3, x2 >, < 0.7, x3 >, < 0.9, x4 > }, = { < 0.1, x1 >, < 0.8, x2 >, < 0.3, x3 >, < 0.9, x5> }. Тогда степень включения нечеткого множества в определяется следующим образом:
( , ) = (00.1) (0.30.8) (0.70.3) (0.90) (00.9) = 1 0.7 0.7 1 1 = 0.7. Следовательно, .
Отметим, что степень включения одного нечеткого множества в другое может быть определена для любых двух нечетких множеств, при этом она может принимать любое значение от 0 до 1.
