- •Н.А. Ююкин
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •1.3.1. Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •1.4. Рекуррентные уравнения
- •1.4.1. Определение рекуррентного уравнения
- •1.4.2. Решение линейного однородного рекуррентного уравнения
- •1 (2).4.3. Решение линейного неоднородного рекуррентного уравнения
- •1.5. Производящие функции
- •1.5.1. Общие сведения о производящих функциях
- •1.5.2. Производящая функция для биноминальных коэффициентов
- •1.5.3. Производящая функция для чисел Фибоначчи
- •1.6.1. Определение z– преобразования
- •1.6.2. Обратное преобразование
- •В правой части этого равенства стоит контурный интеграл в z-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •1.6.3. СвойстваZ-преобразования
- •1.6.4. Использование z-преобразований для решения рекуррентных уравнений
- •1.6.5. Таблица односторонних z-преобразований
- •1.7.Трансверсали и перманенты
- •1.7.1. Множества и мультимножества
- •1.7.2. Трансверсали
- •1.7.3. Пермамент матрицы
- •1.7.4. Число трансверсалей
- •1.8. Матрицы Адамара
- •1.8.1. Определение матрицы Адамара и ее свойства
- •1.8.2. Эквивалентные преобразования матриц Адамара
- •1.8.3. Построение матриц Адамара
- •2. Теория автоматов
- •2.1. Понятие конечного автомата
- •2.1.1. Общие сведения о конечных автоматах
- •2.1.2. Абстрактное определение конечного автомата
- •2.2. Эквивалентности в автоматах
- •2.2.1. Основные определения
- •2.2.2. Покрытия и морфизмы
- •2.2.3. Эквивалентные состояния автоматов
- •2.3. Процедура минимизации конечных автоматов
- •2.4. Автоматные функции и эксперименты с автоматами
- •2.4.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Эксперименты с автоматами
- •2.5. Автоматные языки
- •2.5.1. Представление о формальных языках
- •2.5.2. Алфавит, слово, язык
- •2.5.3. Классификация грамматик и языков
- •2.5.4. Понятие формальной грамматики
- •2.5.5. Автоматные грамматики.
- •2.6. Модификации конечных автоматов
- •2.6.1. Не полностью описанные (частичные) автоматы
- •2.6.2. Понятия недетерминированного и вероятностного автомата
- •2.7. Процедура минимизации не полностью описанного автомата
- •2.7.1. Совместимые состояния
- •2.7.2. Техника определения совместимых состояний.
- •2.7.3. Построение минимального автомата
- •3. Введение в нечеткую математику
- •3.1. Нечёткие множества
- •3.2. Нечеткие отношения
- •3.3. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •1. Элементы комбинаторики 7
- •2. Теория автоматов 58
- •3. Введение в нечеткую математику 106
3.2. Нечеткие отношения
Нечётким отношением на множественазываетсянечеткое подмножество декартова произведенияхарактеризующиеся функциями принадлежностиЗначениепонимаются как степень выполнения отношения
Если Xконечно, то функция принадлежностипредставляет собой квадратную матрицэлемент который означает степень выполнения отношения
Для нечеткого отношения определяется множество уровня:
Матрица множества уровня получается заменой матрицы нечеткого отношенияRединицами всех элементов, значения которых не меньшеа нулями все остальные элементы.
Для уровневых множеств нечетких отношений справедлива теорема от декомпозиции:
Любое нечеткое отношение Rможет быть представлено в форме:
Где
Запись обозначает, что все элементы обычного отношенияумножаются на
Пример
Носителем нечеткого отношения Rназывается обычное отношениетакое, что
Обычное отношение, ближайшее к данному нечеткому отношению определяется следующим образом:
На нечетких отношениях вводятся отношения включения и равенства, а также операции дополнения, пересечения и объединения с помощью тех же формул, что и для нечетких множеств.
Кроме того для нечетких отношений А и В, определенных на утиверсумеХ, вводится операция (максимальной) композиции.
.
Например
А В АВ
Свойства нечетких отношений
Нечеткое отношение Rназывается:
Рефлексивным, если
Симметричным, если
Антисимметричным, еслиили
Несимметрично, если
Совершенно антисимметричным, если
(максимально) транзитивным, если
Транзитивным замыканием нечетного бинарного отношения RназываетсяотношениеЕслито
Виды нечетких отношений
Нечеткие отношения предпорядка– это то, которое обладает свойствами транзитивности и рефлективности.
Нечеткое отношение нестрогого порядка– это то, которое обладает свойствами транзитивности, антисимметричности и рефлективности.
Нечеткое отношение строгого порядка– транзитивное, антисимметричное и антирефлексивное отношение.
Рефлексивное и симметричное отношение называются отношениями сходства.
Нечеткое отношение обладающее свойствами рефлективности, симметричности и транзитивности называются отношениями подобия (нечетким отношением эквивалентности)
3.3. Нечеткая логика
Нечетким высказываниемназывается повествовательное предложение А, степень четности которого принимает значение на отрезке.
Если то, о чем говорится в предложении не определено, то это предложение называется высказывательной функцией или предикатом. Аргументом предиката являются предметные переменные.Нечеткой предметной переменнойназывается переменная, степень истинности которой принадлежит отрезку [0.1].
Как правило, нечеткой предметной переменной является лингвистическая переменная, значениями которой являются слова и словосочетания естественного языка. Лингвистическая переменная служит для качественного писания явления, факты или события. Множество лингвистических переменных называютсятерм-множествоми обозначаютсяT(x).
Нечеткие высказывания бывают простыми и сложными. Для формирования сложных высказываний используются логические связки отрицания, конъюнкции, дизъюнкции, импликации и эквивалентным. В результате этого формируются нечеткие логические формулы.
Степень истинности сложного высказывания определяется по следующий правилам:
В логике нечетких высказываний операция импликации, отличается от классической. Чаще всего она используется в виде: «Если А, то В, иначе С». Такое высказывание определяется через нечеткое отншение на декартовом произведении множеств, т.е.Истинность такого высказывания определяется по формуле.
В частном случае, когда