нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет

• Название: Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
• Дата: 23.12.2020
• Размер: 0.65 Mb.
• Имя файла: Teoria_avtomatov.docx
• Тип: Учебное пособие; #163524
• страница: 17 из 17

3. ВВЕДЕНИЕ В НЕЧЕТКУЮ МАТЕМАТИКУ

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

Пусть U-универсальное множество (универсум), А – некоторое подмножество множества U т.е. . Тот факт, что элемент х множества U принадлежит подмножеству А обозначается в виде . Для выражения этой принадлежности можно воспользоваться понятием характеристической функции

В данном случае характеристическая функция принимает только два значения 0 и 1.

Нечетким множеством А множества U называется множество упорядоченных пар

_,

где - функция принадлежности, принимающая свои значения из вполне упорядоченного множества .

Если , то нечеткое множество рассматривается, как обычное множество, являющиеся подмножеством универсального множества U.

Ф ункция принадлежности может задаваться графически. Для этого в прямоугольной системе координат по оси ординат откладывается значение и по оси абсцисс элементы множества U.

Рис. 11



В случае конечного множества используется следующая запись:

Здесь знак + обозначает объединение элементов.

Например, запись

означает, что элемент универсума:

1 принадлежит А со степенью 0

2 принадлежит А со степенью 0.1

2 принадлежит А со степенью 1.0

Множество пусто, т.е. , если . . Нечёткое множество является универсальным (A=U), если / Два множества А и В равны, т.е. А=В, если .

Множество А включается в В, т.е. если .

Множество есть дополнение А, если .

Пересечение множеств А и В, если .

Объединение .

Пример

Разность нечетких множеств .

Пример

Симметричная разность нечетких множеств

Прямое произведение нечетких множеств

Пример

.

Таблица 26

		B
		1		2
A	1		0.5	1
	2		0.5	0.7

Операция концентрации возводит функцию принадлежности в квадрат.

Операция деконцентрации извлекает квадратный корень из функции принадлежности.

3.2. Нечеткие отношения

Нечётким отношением на множестве называется нечеткое подмножество декартова произведения характеризующиеся функциями принадлежности Значение понимается как степень выполнения отношения

Если X конечно, то функция принадлежности представляет собой квадратную матрицу, элемент который означает степень выполнения отношения

Для нечеткого отношения определяется множество уровня:

Матрица множества уровня получается заменой матрицы нечеткого отношения R единицами всех элементов, значения которых не меньше а нулями все остальные элементы.

Для уровневых множеств нечетких отношений справедлива теорема от декомпозиции:

Любое нечеткое отношение R может быть представлено в форме:

Где

Запись означает, что все элементы обычного отношения умножаются на
Пример

Носителем нечеткого отношения R называется обычное отношение такое, что

Обычное отношение, ближайшее к данному нечеткому отношению определяется следующим образом:

На нечетких отношениях вводятся отношения включения и равенства, а также операции дополнения, пересечения и объединения с помощью тех же формул, что и для нечетких множеств.

Кроме того для нечетких отношений А и В, определенных на универсуме Х, вводится операция (максимальной) композиции.

.

Например

А В А В


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

Нечеткое отношение R называется:

1. 
   Рефлексивным, если
   
2. 
   Симметричным, если
   
3. 
   Антисимметричным, если или
   
4. 
   Несимметрично, если
   
5. 
   Совершенно антисимметричным, если
   
6. 
   (максимально) транзитивным, если
   

Транзитивным замыканием нечетного бинарного отношения R называется отношение . Если то
Виды нечетких отношений
Нечеткие отношения предпорядка – это то, которое обладает свойствами транзитивности и рефлективности.

Нечеткое отношение нестрогого порядка – это то, которое обладает свойствами транзитивности, антисимметричности и рефлективности.

Нечеткое отношение строгого порядка – транзитивное, антисимметричное и антирефлексивное отношение.

Рефлексивное и симметричное отношение называется отношением сходства.

Нечеткое отношение, обладающее свойствами рефлективности, симметричности и транзитивности называются отношениями подобия (нечетким отношением эквивалентности)

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

Нечетким высказыванием называется повествовательное предложение А, степень четности которого принимает значение на отрезке [0.1].

Если то, о чем говорится в предложении не определено, то это предложение называется высказывательной функцией или предикатом. Аргументом предиката являются предметные переменные. Нечеткой предметной переменной называется переменная, степень истинности которой принадлежит отрезку [0.1].

Как правило, нечеткой предметной переменной является лингвистическая переменная, значениями которой являются слова и словосочетания естественного языка. Лингвистическая переменная служит для качественного писания явления, факта или события. Множество лингвистических переменных называются терм-множеством и обозначаются T(x).

Нечеткие высказывания бывают простыми и сложными. Для формирования сложных высказываний используются логические связки отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности. В результате этого формируются нечеткие логические формулы.

Степень истинности сложного высказывания определяется по следующим правилам:

В логике нечетких высказываний операция импликации, отличается от классической. Чаще всего она используется в виде: «Если А, то В, иначе С». Такое высказывание определяется через нечеткое отношение на декартовом произведении множеств, т.е. Истинность такого высказывания определяется по формуле.

В частном случае, когда

ЗАКЛЮЧЕНИЕ

Данное пособие восполняет имеющиеся пробелы в учебной литературе по курсу дискретной математики.

Издание рекомендуется для работы студентов при самостоятельном изучении теоретического материала, на практических занятиях в качестве справочного пособия, а также при выполнении типовых расчетов и подготовки к зачетам и экзаменам, предусмотренных учебными планами по указанной дисциплине.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. 
   Яблонский С.В. Введение в дискретную математику: учеб.пособие для вузов/С.В. Яблонский.– 3-е изд. М.: Высш. шк., 2002.– 384 с.
   
2. 
   Судоплатов С.В. Элементы дискретной математики: учебник/С.В. Судоплатов, Е.В. Овчинникова. – М.: ИНФРА-М, Новосибирск, Изд-во НГТУ, 2002. - 280 с.
   
3. 
   Новиков Ф.А. Дискретная математика для программистов: учебник/Ф.А. Новиков. - СПб.: Питер, 2002.- 304с.
   
4. 
   Шелупанов А.А. Математическая логика и теория алгоритмов: учеб.пособие/А.А. Шелупанов, В.М. Зюльков. - Томск: STT, 2001. - 176 с.
   
5. 
   Столл Р. Множества, логика, аксиоматические теории/Р. Столл. - М.: Просвещение, 1968.- 231с.
   
6. 
   Криницкий Н.А. Алгоритмы вокруг нас / Н.А. Криницкий. –2-е. изд. - М.: Наука, 1984. – 224с.
   
7. 
   Биркгоф Г. Современная прикладная алгебра / Г. Биркгоф, Т. Барти. - М.: Мир, 1976. - 400с.
   
8. 
   Карпов Ю.Г. Теория автоматов: учебник для вузов /
   

Ю.Г. Карпов. - СПб.: Питер, 2003.- 208с.
ОГЛАВЛЕНИЕ

Введение 3

1. Элементы комбинаторики 5

1.1. Простейшие комбинаторные конфигурации 5

1.1.1. Основные правила комбинаторики 5

1.1.2. Выборки элементов без повторений 6

1.1.3. Выборки элементов с повторениями 8

1.2. Латинские прямоугольники, конечные проективные плоскости и блок – схемы 10

1.2.1. Латинские прямоугольники 10

1.2.2. Конечные проективные плоскости 14

1.2.3. Блок-схемы 15

1.3. Формулы включений и исключений 18

1.3.1. Объединение комбинаторных конфигураций 18

1.3.2. Принцип включения и исключения 19

1.3.3. Число булевых функций, существенно зависящих от всех своих переменных 23

1.3.4. Решето Эратосфена 23

1.4. Рекуррентные уравнения 26

1.4.1. Определение рекуррентного уравнения 26

1.4.2. Решение линейного однородного рекуррентного уравнения 26

1
(2)
.4.3. Решение линейного неоднородного рекуррентного уравнения 28

1.5. Производящие функции 31

1.5.1. Общие сведения о производящих функциях 31

1.5.2. Производящая функция для биноминальных коэффициентов 32

1.5.3. Производящая функция для чисел Фибоначчи 34

1.6. Z- преобразование 37

1.6.1. Определение Z- преобразования 37

1.6.2. Обратное Z- преобразование 38

1.6.3. Свойства Z- преобразования 40

1.6.4. Использование Z- преобразований для решения рекуррентных уравнений 40

1.6.5. Таблица односторонних Z- преобразований 41

1.7. Трансверсали и перманенты 43

1.7.1. Множества и мультимножества 43

1.7.2. Трансверсали 45

1.7.3. Перманент матрицы 46

1.7.4. Число трансверсалей 48

1.8. Матрицы Адамара 50

1.8.1. Определение матрицы Адамара и ее свойств 50

1.8.2. Эквивалентные преобразования матриц

Адамара 51

1.8.3. Построение матриц Адамара 52

2. Основы теории конечных автоматов 54

2.1. Понятие конечного автомата 54

2.1.1. Общие сведения о конечных автоматах 54

2.1.2. Абстрактное определение конечного автомата 56

2.2. Эквивалентности в автоматах 60

2.2.1. Основные определения 60

2.2.2. Покрытия и морфизмы 62

2.2.3. Эквивалентные состояния автоматов 63

2.3. Процедура минимизации конечных автоматов 66

2.4. Автоматные функции и эксперименты с автоматами 70

2.4.1. Понятие ограниченно детерминированной функции 70

2.4.2. Моделирование автоматной функции с помощью схемы из функциональных

элементов и задержки 72

2.4.3. Пример реализации конечного автомата

с помощью СФЭЗ 74

2.4.4. Эксперименты с автоматами 76

2.5. Автоматные языки 78

2.5.1. Представление о формальных языках 78

2.5.2. Алфавит, слово, язык 80

2.5.3. Классификация грамматик и языков 82

2.5.4. Понятие формальной грамматики 83

2.5.5. Автоматные грамматики 85

2.6. Модификации конечных автоматов 90

2.6.1. Частичные автоматы 90

2.6.2. Понятия недетерминированного

и вероятностного автоматов 93

2.7. Процедура минимизации частичного автомата 95

2.7.1. Совместимые состояния 95

2.7.2. Техника определения

совместимых состояний 96

2.7.3. Построение минимального автомата 98

3. Введение в нечёткую математику 101

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

3.2. Нечеткие отношения 103

3.3. Нечеткая логика 106

Заключение 108

Библиографический список 109

Учебное издание

Ююкин Николай Алексеевич
ДИСКРЕТНАЯ МАТЕМАТИКА
часть 2
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

И ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ

В авторской редакции
Компьютерный набор Н.А. Ююкина


Подписано к изданию 10. 10. 2011.

Объем данных 662 КБ
ФГБОУ ВПО «Воронежский государственный

технический университет»

394026 Воронеж, Московский просп., 14






ФГБОУ ВПО «Воронежский государственный

технический университет»
СПРАВОЧНИК МАГНИТНОГО ДИСКА

(кафедра высшей математики и физико-математического

моделирования)
Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА

Часть 2

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

И ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ

Учебное пособие


Теория автоматов .doc 662 КБ

(наименование файла) (объем файла)

10.10.2011 6,0 уч.-изд. л.

(дата) (объем издания)