Глава 1. Алгебраические системы

Оглавление

Введение. 7

Глава 1. Алгебраические системы.. 9

1.1 Множества. 9

1.1.1. Четкие множества. 9

1.1.2. Нечеткие множества. 14

1.2. Соответствия, отображения и функции. 16

1.2.1. Четкие отображения и функции. 17

1.2.2. Нечеткие отображения. 20

1.3. Отношение. 21

1.3.1. Четкие отношения. 22

1.3.2. Нечеткое отношение. 25

1.4. Элементы общей алгебры.. 26

1.5. Булева алгебра. 27

1.5.1. Булевы операции. 28

1.5.2. Законы булевой алгебры.. 28

1.5.3. Формула булевой функции. 29

1.5.4. Описание булевой функции. 29

1.5.5. Суперпозиция булевых функций. 33

1.5.6. Свойства булевых функций. 35

1.5.6.1. Самодвойственные булевы функции. 35

1.5.6.2. Монотонные булевы функции. 36

1.5.6.3. Линейные булевы функции. 36

1.5.6.4. Функции, сохраняющие “0” 38

1.5.6.6. Функционально полные системы. 39

1.5.7. Разложение булевых функции. 40

1.5.7.1. ДНФ булевой функции. 41

1.5.7.2. КНФ булевой функции. 42

1.5.8. Минимизация булевых функций. 44

1.5.8.1.Минимизация ДНФ булевой функции. 46

1.5.8.2. Минимизация КНФ булевой функции. 47

1.6. Алгебра четких множеств. 49

1.6.1. Операции над множествами. 50

1.6.2. Законы алгебры множеств. 56

1.6.3. Эквивалентные преобразования формул. 57

1.6.4. Композиция отображений и отношений. 58

1.6.5. Поиск неизвестного множества. 59

1.7. Алгебра нечетких множеств. 61

1.7.1. Операции над нечеткими множествами. 62

1.7.2. Композиция нечетких отображений. 68

1.7.3. Композиция нечетких отношений. 70

1.7.4. Свойства нечетких отношений. 70

Вопросы и задачи. 73

Глава 2. Элементы комбинаторики. 77

2.1. Размещение из n элементов по k. 78

2.2. Перестановка элементов. 79

2.3 Сочетание из n элементов по k. 79

2.4. Разбиение множества. 81

2. 5 Правила комбинаторики.. 82

Вопросы и задачи.. 87

Глава 3. Основы теории графов. 88

3.1. Граф и его характеристики. 88

3.2. Описание графа. 96

3. 3. Числа графа. 103

3.4. Операции над графами. 106

3.4.1. Унарные операции. 107

3.4.1.1 Поиск дополнительного графа. 107

3.4.1.2. Введение и удаление вершин графа. 107

3.4.1.3. Стягивание вершин графа. 108

3.4.1.4. Введение и удаление ребер графа. 108

3.4.1.5. Поиск плотности и неплотности графа. 109

3.4.1.6. Поиск числа компонент связности графа. 110

3.4.1.7. Поиск устойчивости графа. 113

3.4.1.8. Поиск цикломатического числа графа. 117

3.4.1.9. Поиск хроматического числа графа. 118

3.4.2. Бинарные операции. 118

3.4.2.1. Объединение графов. 119

3.4.2.2. Пересечение графов. 120

3.4.2.3. Композиция графов. 121

3.4.2.4. Соединение графов. 122

3.4.2.5. Прямое произведение графов. 123

3.4.2.6. Изоморфизм графов. 124

3.5. Некоторые алгоритмы на графах. 125

3.5.1. Построение покрывающего остова. 125

3.5.2. Построение остова минимального веса. 128

3.5.3. Поиск кратчайших путей в сети. 131

3.5.4. Поиск максимального потока в сети. 135

3.5.5. Метод критического пути в управлении. 140

3.6. Нечеткие графы.. 146

Вопросы и задачи.. 148

 

Глава 4. Основы математической логики. 152

4.1. Логика высказываний. 152

4.1.1. Алгебра высказываний. 154

4.1.1.1. Логические операции. 154

4.1.1.2. Правила записи сложных формул. 157

4.1.1.3. Законы алгебры высказываний. 161

4.1.1.4. Эквивалентные преобразования формул. 162

4.1.1.5. Нормальные формы формул. 165

4.1.2. Исчисление высказываний. 166

4.1.2.1. Интерпретация формул. 167

4.1.2.2. Аксиомы и правила введения и удаления логических связок 168

4.1.2.3. Метод дедуктивного вывода. 171

4.1.2.4. Принцип резолюции. 176

4. 2. Логика предикатов. 181

4.2.1. Алгебра предикатов. 184

4.2.1.1. Законы алгебры предикатов. 188

4.2.1.2. Предваренная нормальная форма формулы. 189

4.2.1.3 Сколемовская стандартная форма формулы. 191

4. 2. 2. Исчисление предикатов. 192

4.2.2.1. Правила подстановки. 194

4.2.2.2. Правила введения и удаления кванторов. 197

4.2.2.3. Правила заключения. 198

4.2.2.4. Метод дедуктивного вывода. 198

4.2.2.5. Принцип резолюции. 201

4.2.2.6. Логическое программирование. 204

4.3. Логика реляционная. 207

4.3.1 Реляционная алгебра. 210

4.3.1.1. Унарные операции. 212

4.3.1.2. Бинарные операции. 215

4.3.1.3. Правила реляционной алгебры. 218

4.3.2. Реляционное исчисление. 219

4.3.3. Языки реляционной логики. 221

4.4. Нечеткая логика. 224

4.4.1. Нечеткое исчисление. 224

4.4.2. Экспертные системы.. 227

Вопросы и задачи. 230

Глава 5. Основы теории алгоритмов. 235

5.1. Рекурсивные функции. 236

5.1.1. Базовые функции. 237

5.1.2. Элементарные операции. 237

5.2. Машина Тьюринга. 243

5.2.1. Описание машины Тьюринга. 245

5.2.2. Примеры машин Тьюринга. 247

5.2.3. Композиция машин Тьюринга. 258

5.3. Нормальные алгоритмы Маркова. 263

5.4 Сложность вычислений.. 270

Вопросы и задачи.. 271

Глава 6. Конечные автоматы.. 272

6.1. Абстрактный автомат. 272

6.1.1. Типы конечных автоматов. 276

6.1.2. Описание автоматов. 279

6.1.3. Автоматное моделирование алгоритмов. 287

6.1.3.1. Автомат Мили - модель управляющего автомата. 290

6.1.3.2. Автомат Мура - модель управляющего автомата. 293

6.1.3.3. Микропрограммный автомат. 296

6.1.4. Эквивалентность автоматов. 299

6.1.5. Эквивалентность внутренних состояний автомата. 303

6.1.5.1. Детерминированный автомат. 303

6.1.5.2. Недетерминированный автомат. 314

6.2. Структурный автомат. 323

6.2.1. Произведение автоматов. 324

6.2.1.1. Последовательное соединение автоматов. 324

6.2.1.2. Параллельное соединение автоматов. 325

6.2.2. Обратная связь автоматов. 328

6.2.3. Сумма автоматов. 329

6.2.4. Структурный автомат и кодирование. 330

6.3. Логическое проектирование автоматов. 332

6.3.1. Кодирование алфавитов автомата. 332

6.3.2. Автоматы без “памяти”. 333

6.3.2.1. Формирование оператора j. 333

6.3.2.2. Формирование системы операторов j. 337

6.3.2.3. Логическая схема комбинационного автомата. 339

6.3.3. Автоматы с “памятью” 340

6.3..3.1. Формирование оператора j. Ошибка! Закладка не определена.

6.3.3.2. Формирование оператора y. 343

6.3.3.3. Логическая схема автомата с “памятью” 347

Вопросы и задачи. 348

Литература. 350

Предметный указатель. 351

 

“Теперь в математике остаются только целые числа и конечные...системы целых чисел...”

Анри Пуанкаре.

Введение

Основное отличие дискретной математики от классической заключается в отсутствии понятий предела и непрерывности, а основными носителями являются, например, целые числа и многочлены, векторы и матрицы, чертежи и рисунки, слова и команды и т. п. Элементы носителя формируют состав какой-либо системы, а отношения между ними – ее структуру. Отношения и элементы системы могут изменять свое значение в дискретные моменты времени.

Следовательно, состав и структура таких систем представляют дискретную модель, для описания которой привлекается аппарат дискретной математики.

В главе I – Алгебраические системы - изложены основные понятия теории множеств, отображений и отношений. Особенность данной главы заключается в том, что в ней приведены основные характеристики “четких” и “нечетких” объектов. Это – четкие и нечеткие множества, четкие и нечеткие отображения, четкие и нечеткие отношения. Такое построение главы позволяет глубже понять единство и различия “четких” и “нечетких” объектов, условия исполнения алгебраических операций над этими объектами. В главе приведены многочисленные примеры.

В главе 2 - Элементы комбинаторики - сформулированы основные требования к комбинаторным объектам, рассмотрены основные процедуры формирования упорядоченных и неупорядоченных выборок: размещения и перестановки, сочетания и разбиения. Все разделы главы подкреплены примерами на различных множествах.

В главе 3 - Основы теории графов – приведены основные характеристики графов, правила исполнения алгебраических операций над графами и алгоритмы решения некоторых практических задач на графах.

В главе 4 – Основы математической логики – изложены основные понятия логик высказываний и предикатов, реляционной и нечеткой логик, показаны основные процедуры вывода заключений для дедуктивного метода и принципа резолюции. Кратко описаны возможности языков Prolog для программирования логических задач, SQL для формирования запросов. Описана также одна из экспертных систем –MYCIN, использующая правила нечеткой логики при выводе заключения.

В главе 5 – Основы теории алгоритмов - приведены три модели алгоритмов: рекурсивные функции, машины Тьюринга и нормальные алгоритмы Маркова. По каждой модели приведены вычислительные примеры. Показано, что любая частично рекурсивная функция может быть реализована на машине Тьюринга или нормальном алгоритме Маркова.

В главе 6 – Конечные автоматы – изложены основы формализации и классификации конечных автоматов, дано описание их характеристик. Изложены основные приемы минимизации детерминированного и частично определенного (или недетерминированного) абстрактного автомата, формирования структурного автомата при синхронном и асинхронном режимах работы и различных схемных соединениях элементарных автоматов. Для структурного автомата дано описание способов и приемов логического проектирования комбинаторного автомата и автомата с памятью. Приведены примеры минимизации преобразователя кода, рассмотрены проблемы автоматного моделирования алгоритмов и минимизации состава и структуры автомата с памятью.

Глава 1. Алгебраические системы

Алгебраической системой называют множество каких-либо объектов с определенными на нем операциями и отношениями. Множество называют носителем алгебраической системы, а совокупность операций и отношений – ее сигнатурой.

Множества

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

Множество считается заданным, если указано характеристическое свойство, которым обладают все элементы множества. Если понятию “цифра” или “буква”, “таблица” или “рисунок” соответствуют определенные наборы элементов, то понятию “маленькое число” или “большое входное сопротивление”, “красивая женщина” или “высокий мужчина” соответствуют субъективные оценки. То есть каждый наблюдатель сформирует различные группы чисел или входных сопротивлений, женщин или мужчин и т. п.

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

Четкие множества

В языках программирования задают типы данных: INTEGER -, целые числа, CHAR – литеры (символы, знаки), STRING – строки, BOOLEAN - логические переменные и др. Так описывают в компьютере характерные свойства отдельных множеств.

Объекты, включаемые в множество, называют его элементами. Например, ’3’ - элемент INTEGER, ‘c’ - элемент CHAR, ‘monday’ – элемент STRING, ‘true’ – элемент BOOLEAN и т. п..

Общим обозначением множества служит пара фигурных скобок ”{”, “}”, между которыми перечисляют элементы множества.

Например, {1, 3, 5, 7}, или {a, b, c, d} или {Иванов, Петров, Сидоров,...}.

На языке pascal для обозначения множества используют прямые скобки “[“ и “]“, между которыми перечисляют элементы множества.

Например, [1, 3, 5, 7], или [‘a’, ‘b’, ‘c’, ‘d’] или [иванов, петров, сидоров,..].

Для обозначения множеств в тексте используют прописные буквы латинского алфавита A, B, C,...X, Y, Z, а для обозначения его элементов - строчные буквы a, b, c,...x, y, z. Иногда эти буквы используют с индексами из множества натуральных чисел. Например, А₁, А₂, А₃ или а₁, а₂, а₃.

На языках программирования имя или <идентификатор_множества> представляют в виде последовательности букв и/или цифр, но начинающихся с прописной буквы, а имя или <идентификатор_элемента> - в виде последовательности букв и/или цифр, но начинающихся со строчной буквы.

Принадлежность элемента x множеству A обозначают символом “Î“ – знак принадлежности. Например, xÎA..

На языке pascal это записывают так: “x in А”, где x - <идентификатор_элемента >, А - <идентификатор_множества>”.

Если элемент х не принадлежит множеству A, то используют символ “Ï“ – знак непринадлежности. Например, хÏA..

На языке pascal это записывают так: “not(xin А)”.

Порядок перечисления элементов между фигурными скобками произвольный, т.е. {a, b, c, d}={b, c, d, a}, но не допускается неоднократная запись одного элемента среди остальных элементов множества, т. е. {a, a, a, b, b, c, c, d}={a, b, c, d}.

Множество, каждый элемент которого можно индексировать натуральным числом 1,2,... n, называют счетным.

На языке pascal такому элементу присваивают <идентификатор_порядкового_типа>.

Если n конечно, то множество называют конечным.

Например, множество цифр счетно и конечно, а множество целых чисел (INTEGER) – счетно, но не конечно.

На языке pascal, как правило, число элементов множества указывают в диапазоне [1..n].

Число элементов счетного конечного множества A называют его мощностью и обозначают так: |A|=n.

Например, мощность множества цифр равна 10, а мощность множества строчных букв латинского алфавита – 26.

Если все элементы множества A являются также элементами множества B, но не наоборот, то множество A называют подмножеством множества B. Для обозначения этого в тексте используют символ “Í“ - знак включения: AÍB.

Например, если А={1, 2, 3} и B={1, 2, 3, 4, 5}, то A есть подмножество B. На языке pascal факт включения множества A в множество B записывают так: A£B.

Если AÍB и BÍA, то A=B.

Например, если А={1, 2, 3} и B={3, 2, 1}, то A=B.

Если AÍB и A¹B, то A называют собственным подмножеством B.

Для обозначения этого в тексте используют символ “Ì“ - знак строгого включения: AÌB.

Например, если А={1, 2, 3} и B={1, 2, 3, 4, 5}, то AÌB.

Если хотя бы один элемент множество A не принадлежит множеству B, то множество A не включено в множество B. Для обозначения этого в тексте используют символ “Ë“ - знак невключения: AËB.

Например, если А={1, 2, 3, 6} и B={1, 2, 3, 4, 5}, то AËB.

На языке pascal факт невключения множества A в множество B записывают так: not(A£B).

Множество, не содержащее ни одного элемента, называют пустое множество и обозначают символом - Æ. Пустое множество является подмножеством любого множества. Множество, содержащее все элементы всех подмножеств, принимающих участие в решении каких-либо задач, называют универсальным множеством и обозначают символом U.

Например, если в решении задач принимают участие два множества А={a, b} и B={b, c, d}, то универсальное множество будет U ={a, b, c, d}.

Множество, элементами которого являются подмножества, называют семейством подмножеств.

Например, С={А, В}={{a, b}, {b, c, d}}.

Пример. Даны множества А={1; 2} и В={{1; 2; 3}, {1; 3}, 1; 2}. Верно ли, что {1; 2}Î{{1; 2; 3}, {1; 3}, 1; 2}?

Нет, неверно, так как среди элементов множества В нет элемента А={1; 2}, а верно выражение {1; 2}Í{{1, 2, 3}; {1; 3}; 1; 2}, т.к. элементы множества В формируют подмножество А={1; 2}.

Множество, включающее в себя максимально возможное число подмножеств универсального множества, называют булеаном. Он включает в себя пустое подмножество и множества, сформированные из одного, двух, трех и т.д. до общего числа элементов универсального множества. Булеан обозначают символом B (U).

Например, если U={a, b, c}, то B (U)={Æ, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}}.

На языке pascal булеан описывают как объект множественного типа на основе элементов базового типа.

Например, B (U) = set of (‘a’, ‘b’, ‘c’) = [[], [a], [b], [c], [a,b], [b,c], [a,c], [a,b,c]], где B (U):= < идентификатор_булеана >.

Число элементов булеана B (U) зависит от числа элементов универсального множества U по формуле:

| B (U)|=2^|U|,

где |U| - мощность или число элементов универсального множества, а | B (U)| - мощность или число подмножеств булеана.

Например, если |U|=3, то | B (U)|=2³=8, если |U|=5, то | B (U)|=2⁵=32.

В компьютере для кодирования букв, цифр и символов используют 8 разрядов двоичного кода. Это позволяет сформировать 256 кодовых комбинаций для кодирования букв, цифр и символов.

Описание множества может быть выполнено а) перечислением элементов, b) указанием характерных свойств элементов или c) заданием порождающей процедуры.

При перечислении элементов между фигурными скобками указывают все элементы множества.

Например, ЧИСЛА={1, 2, 3, 4, 5}, БУКВЫ={a, b, c, d, е}, ПРОДУКТЫ_ПИТАНИЯ={‘хлебобулочные_ изделия’, ‘кондитерские_ изделия’, ‘молочные_продукты’, ‘напитки’, ‘фрукты’,...} и т. п.

При указании характерных свойств элементов между фигурными скобками после указания текущего элемента ‘x’ ставят знак “½“, вслед за которым наличие этих свойств описывают логической функцей -Р(х):=”..”. Если при х=’а’ функция Р(‘а’) принимает значение “истина”, то элемент ‘a’ включают в перечень элементов множества, если - “ложь”, то - не включают.

При задании порождающей процедуры между фигурными скобками после указания текущего элемента ‘x’ и знака “½“ с помощью оператора присваивания (“x:=<алгебраическое выражение>”) определяют значение элемента, включаемого в множество.

Например, множество нечетных чисел можно задать порождающей процедурой на множестве целых чисел: А={x| x:=(2n-1), где n=1, 2, 3,..}.

Если даны два множества A и B, то упорядоченную пару (x, y), где хÎA и yÎB, называют кортеж.

Множество всех кортежей (x, y) множеств A и B называют прямым произведением. Исполнение этой операции обозначают так:

{(x, y) | хÎA, yÎB}=(AÄB),

где “Ä” – символ прямого произведения.

Если A={a; b; c; d; e; f; g; h} и B={1; 2; 3; 4; 5; 6; 7; 8}, то прямое произведение формирует 8^. 8=64 кортежа {(a, 1), (a, 2),..(h, 7), (h, 8)}. Это – описание шахматной доски, а при описании шахматной партии могут участвовать не все позиции шахматной доски. Поэтому любое множество упорядоченных пар (x, y) при описании шахматной партии есть подмножество прямого произведения, т.е.

{(x, y)|xÎA, yÎB}Í (AÄB).

Прямым произведением нескольких множеств X₁, X₂,...,X_n называют множество всех кортежей

{(x₁, x₂,...x_n)| x₁ÎX₁, x₂ÎX₂,..., x_nÎX_n}=(X₁ÄX₂Ä...ÄX_n).

Любое множество (x₁, x₂,...x_n) есть подмножество прямого произведения, т.е.

{(x₁,x₂,...x_n)| x₁ÎX₁, x₂ÎX₂,..., x_nÎX_n}Í (X₁ÄX₂Ä...ÄX_n).

Если X₁=X₂=...=X, то {(x₁, x₂,...x_n)| x_iÎX}Í Xⁿ..

Для обозначения кортежа используют круглые скобки, а для замещения его в тексте – символ t, т.е. t=(x₁; x₂;...x_n).

Если множество X_i=Æ, то (X₁ÄX₂Ä...ÄX_iÄ...ÄX_n)=Æ.

Следует обратить внимание, что ƹ{Æ}, т. к. |Æ|=0, а |{Æ}|=1.

Каждый элемент кортежа есть его компонента.

Кортеж может содержать повторяющиеся компоненты, но нельзя нарушать заданный порядок компонент.

Например, (x₁, x₁,..x₁)¹(x₁) и (x₁, x₂,..x_n)¹(x_n, x₂,..x₁).

Число компонент кортежа определяет его длину или ранг:

|(x₁; x₂;...x_n)|=n.

Если известны мощности множеств |X₁|=m₁, |X₂|=m₂,..|X_n|=m_n, то мощность прямого произведения есть

|(X₁ÄX₂Ä...ÄX_n)|=m_1*m_2*..._*m_n.

Кортежи, имеющие одинаковые имена компонент, одинаковое их число и одинаковый порядок следования в кортеже, называют совместимыми кортежами. Такие кортежи удобно описывать таблицами.

Например, если дату в документах описывают кортежем (<число>”.”<месяц> ”.”<год>), то при описании множества документов удобно выделить в таблице такую структуру совместимых кортежей.

Строка в языках программирования рассматривается как машинное представление кортежа. Для описания на языке pascal используют линейные списки:

type t=record

element: data

next:Ùt

end.

Специфической операцией, формирующий новый конструктивный объект на множествах, является прямая сумма. Она связывает имя - <идентификатор_множества> - i и его элементы - x, т. е.

{(i, x)| 1£ i £ n, xÎX_i}=X₁ÅX₂Å..ÅX_n.

Прямая сумма породила в языках программирования оператор case для поиска информации в базах данных.

Нечеткие множества

Часто используют неполное или нечеткое описание объекта. Например, "большое (какое?) входное сопротивление осциллографа", "малое (какое?) напряжение на базе транзистора", "постоян­ное (какое?) число оборотов двигателя" не дают числовой характеристики указанного атрибута объекта.

Для подобных задач разработана теория нечетких множеств (fuzzi set).

Пусть дано универсальное множество U. Если на этом множестве задать подмножество X’, имя которого недостаточно четко определено, то принадлежность э лементов uÎU множеству X’может быть описана функцией принадлежности - m_x’(u), как субъективная мера.

Значение функции m_x’(u) называют степен ью принадлежности и определяют на интервале [0, 1], т.е.

m_x’ (u_i): U ®[0, 1].

Итак, нечеткое множество есть

X’={m_x’(u₁)/u₁, m_x’(u₂)/u₂,... m_x’(u_n)/u_n},

где m_x’(u_i)Î[0;1] – степень принадлежности элемента u_iÎU нечеткому множеству X’.

Носителем нечеткого множест ва X’ являются элементы “четкого” подмножества XÍU, т. е.

X={u₁, u₂,...u_n}ÍU, если m_x’(u_i)>0 для i=1, 2,..n.

Если для некоторого u_iÎU имеем m_x’(u_i)=1, то элемент “четко” принадлежит множеству X’. Если все элементы носителя X имеют значение m_x’(u_i)=1, то задано “четкое” подмножество X' множества U.

Если для некоторого u_iÎU имеем m_x’(u_i)=0, то элемент “четко” не принадлежит множеству X’. Если все элементы носителя X имеют значение m_x’(u_i)=0, то задано “четкое” пустое множество, т. е. X’=Æ.

Пример: дано 10 дискет и эксперт должен сформировать множество подмножеств, удовлетворяющих условию “выбрать несколько дискет”. Множество всех подмножеств этих дискет содержит пустое множество, одно-, двух- трех- и т.д. до десятиэлементного подмножества. Так задано универсальное множество U={Æ, 1, 2, 3,.. 10}.

Для подмножеств, содержащих нуль, один, два, половину или все шары, эксперт определил значение функции принадлежности равным нулю, так как можно было бы сказать просто: “взять половину дискет” или “взять две дискеты ” и т.д. Для подмножеств, содержащих три, восемь или девять дискет, эксперт определил значение функции принадлежности равным 0,6, а для подмножеств, содержащих четыре, шесть или семь дискет, - равным 0,8. То есть эксперт сформировал нечеткое множество по условию “несколько дискет”:

X’={0,6/3; 0,8/4; 0/5; 0,8/6; 0,8/7; 0,6/8; 0,6/9}.

Такова была субъективная оценка принадлежности каждого подмножества булеана нечеткому понятию “несколько дискет”.

Носителем этого подмножества является X={3, 4, 6, 7, 8, 9}.

Пример; дан электрический двигатель и эксперт должен отнести значения скорости вращения работающего двигателя в четыре класса: X’₁ ="нулевая скорость вращения", X’₂ - "малая", X’₃ - “средняя" и X’₄ - “большая".

Пусть скорость вращения двигателя изменяется в пределах от 0 до 3150об/мин..

Так как понятия “нулевая”, “малая”, “средняя” и “большая” не имеют числового значения, то их называют лингвистическими переменными, а их множество, заданное также лингвистической переменной, - терм-множеством.

Например, терм-множество “скорость вращения двигателя”, а лингвистические переменные: “нулевая”, “малая”, “средняя” и “большая”.

таблица 1.1.

скорость (об/мин)	степень принадлежности
	“Нулевая”	”Малая”	“Средняя”	“Большая”
	0,33	0,33
		0,33	0,33
			0,33	0,33
		О

Эксперт разбил диапазон изменения скорости на восемь поддиапазонов, установил два уровня принадлежности: 0,33 и 1,00 и составил таблицу принадлежности каждому классу (см. табл. 1.1). В этом случае нечеткие множества описаны так:

X’₁ ("нулевая") = {I/0, 0,33/450};

X’₂ ("малая") = {0,33/450, 1/900, 0,33/1350};

X’₃ ("средняя")={0,33/1350, 1/1800, 0,33/2250};

X’₄ ("большая") = {0,33/2250, 1/2700, 1/3150}.

Можно дать определение прямого произведения нечетких множеств также как и для четких множеств. Например, если даны универсальное множество U={u₁, u₂, u₃, u₄, u₅, u₆, u₇, u₈, u₉} и два нечетких подмножества: A’={0,6/ u₁, 0,4/ u₂, 0,8/ u₃,0,2/ u₄, 1,0/ u₅, 0,3/ u₆} и B’={0,9/ u₁, 0,4/ u₂, 1,0/ u₃, 0,7/ u₇,0,3/ u₈, 0,5/ u₉}, то прямое произведение нечетких подмножеств А’ и В’ есть нечеткое множество C’, состоящее из упо­рядоченных пар (u_i, u_j), первая компонента которых принадлежит множеству А’, а вторая - множеству В’, т. е.

C’={m_С’ (u_i,u_j)/ (u_i, u_j)| u_iÎA’ и u_jÎB’}=(А’ÄВ’).

Степень при­надлежности m_С’(u_i; u_j) равна минимальному значению степени принадлежности m_A’ (u_i) и m_B’ (u_j), т.е

m_С’ (u_i,u_j) =(m_A’ (u_i)&m_B’ (u_j) = min{m_A’ (u_i); m_B’ (u_j)}.

Для приведенных множеств A’ и B’ составлена таблица.

таблица 1. 2

C’= А’ÄВ’	uj =u1	uj =u2	uj =u3	uj =u7	uj =u8	uj =u9
ui=u1	0,6	0,4	0,6	0,6	0,3	0,5
ui=u1	0,4	0,4	0,4	0,4	0,3	0,4
ui=u3	0,8	0,4	0,8	0,7	0,3	0,5
ui=u4	0,2	0,2	0,2	0,2	0,2	0,2
ui=u5	0,9	0,4	1,0	0,7	0,3	0,5
ui=u6	0,3	0,3	0,3	0,3	0,3	0,3

 

На множестве нечетких подмножеств операции включения одного нечеткого подмножества в другое и их сравнения будут рассмотрены в 1.7.

12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: