- •Оглавление
- •Глава 1. Алгебраические системы 17
- •Глава 2. Элементы комбинаторики 88
- •Глава 3. Основы теории графов 101
- •Глава 4. Основы математической логики 169
- •4.1.1.4. Эквивалентные преобразования формул 179
- •4.1.4. Выполнить подстановку: 247
- •Глава 5. Основы теории алгоритмов 252
- •Глава 6. Конечные автоматы 289
- •Введение
- •Глава 1. Алгебраические системы
- •1.1 Множества
- •1.1.1. Четкие множества
- •1.1.2. Нечеткие множества
- •1.2. Соответствия, отображения и функции
- •1.2.1. Четкие отображения и функции
- •1.2.2. Нечеткие отображения
- •1.3. Отношение
- •1.3.1. Четкие отношения
- •1.3.2. Нечеткое отношение
- •1.4. Элементы общей алгебры
- •1.5. Булева алгебра
- •1.5.1. Булевы операции
- •1.5.2. Законы булевой алгебры
- •1.5.3. Формула булевой функции
- •1.5.4. Описание булевой функции
- •1.5.5. Суперпозиция булевых функций
- •1.5.6. Свойства булевых функций
- •1.5.6.1. Самодвойственные булевы функции
- •1.5.6.2. Монотонные булевы функции
- •1.5.6.3. Линейные булевы функции
- •1.5.6.4. Функции, сохраняющие “0”
- •1.5.6.5. Функции, сохраняющие “1”
- •1.5.6.6. Функционально полные системы
- •1.5.7. Разложение булевых функции
- •1.5.7.1. Днф булевой функции
- •1.5.7.2. Кнф булевой функции
- •Алгоритм преобразования формулы к скнф:
- •1.5.8. Минимизация булевых функций.
- •1.5.8.1.Минимизация днф булевой функции
- •1.5.8.2. Минимизация кнф булевой функции
- •1.6. Алгебра четких множеств
- •1.6.1. Операции над множествами
- •1.6.2. Законы алгебры множеств
- •1.6.3. Эквивалентные преобразования формул
- •1.6.4. Композиция отображений и отношений
- •1.6.5. Поиск неизвестного множества
- •1.7. Алгебра нечетких множеств
- •1.7.1. Операции над нечеткими множествами
- •1.7.2. Композиция нечетких отображений
- •1.7.3. Композиция нечетких отношений
- •1.7.4. Свойства нечетких отношений
- •Вопросы и задачи
- •Глава 2. Элементы комбинаторики
- •2.1. Размещение из n элементов по k
- •2.2. Перестановка элементов
- •2.3 Сочетание из n элементов по k
- •2.4. Разбиение множества
- •2. 5 Правила комбинаторики
- •Вопросы и задачи
- •Глава 3. Основы теории графов
- •3.1. Граф и его характеристики
- •3.2. Описание графа
- •3. 3. Числа графа
- •3.4. Операции над графами
- •3.4.1. Унарные операции
- •3.4.1.1 Поиск дополнительного графа
- •3.4.1.2. Введение и удаление вершин графа
- •3.4.1.3. Стягивание вершин графа
- •3.4.1.4. Введение и удаление ребер графа
- •3.4.1.5. Поиск плотности и неплотности графа
- •3.4.1.6. Поиск числа компонент связности графа
- •3.4.1.7. Поиск устойчивости графа
- •3.4.1.8. Поиск цикломатического числа графа
- •3.4.1.9. Поиск хроматического числа графа
- •3.4.2. Бинарные операции
- •3.4.2.1. Объединение графов
- •3.4.2.2. Пересечение графов
- •3.4.2.3. Композиция графов
- •3.4.2.4. Соединение графов
- •3.4.2.5. Прямое произведение графов
- •3.4.2.6. Изоморфизм графов
- •3.5. Некоторые алгоритмы на графах
- •3.5.1. Построение покрывающего остова
- •3.5.2. Построение остова минимального веса
- •3.5.3. Поиск кратчайших путей в сети.
- •3.5.4. Поиск максимального потока в сети
- •3.5.5. Метод критического пути в управлении
- •3.6. Нечеткие графы
- •Вопросы и задачи
- •Глава 4. Основы математической логики
- •4.1. Логика высказываний
- •4.1.1. Алгебра высказываний
- •4.1.1.1. Логические операции
- •4.1.1.2. Правила записи сложных формул.
- •4.1.1.3. Законы алгебры высказываний
- •4.1.1.4. Эквивалентные преобразования формул
- •4.1.1.5. Нормальные формы формул
- •4.1.2. Исчисление высказываний
- •4.1.2.1. Интерпретация формул
- •4.1.2.2. Аксиомы и правила введения и удаления логических связок
- •4.1.2.3. Метод дедуктивного вывода
- •4.1.2.4. Принцип резолюции
- •4. 2. Логика предикатов
- •4.2.1. Алгебра предикатов
- •4.2.1.1. Законы алгебры предикатов
- •4.2.1.2. Предваренная нормальная форма формулы
- •4.2.1.3 Сколемовская стандартная форма формулы
- •4. 2. 2. Исчисление предикатов
- •4.2.2.1. Правила подстановки
- •4.2.2.2. Правила введения и удаления кванторов
- •4.2.2.3. Правила заключения
- •4.2.2.4. Метод дедуктивного вывода
- •4.2.2.5. Принцип резолюции
- •4.2.2.6. Логическое программирование
- •4.3. Логика реляционная
- •4.3.1 Реляционная алгебра
- •4.3.1.1. Унарные операции
- •4.3.1.2. Бинарные операции
- •4.3.1.3. Правила реляционной алгебры
- •4.3.2. Реляционное исчисление
- •4.3.3. Языки реляционной логики
- •4.4. Нечеткая логика
- •4.4.1. Нечеткое исчисление
- •4.4.2. Экспертные системы
- •Вопросы и задачи
- •Глава 5. Основы теории алгоритмов
- •5.1. Рекурсивные функции
- •5.1.1. Базовые функции
- •5.1.2. Элементарные операции
- •5.2. Машина Тьюринга
- •5.2.1. Описание машины Тьюринга
- •5.2.2. Примеры машин Тьюринга
- •5.2.3. Композиция машин Тьюринга
- •5.3. Нормальные алгоритмы Маркова
- •5.4 Сложность вычислений
- •Вопросы и задачи
- •Глава 6. Конечные автоматы
- •6.1. Абстрактный автомат
- •6.1.1. Типы конечных автоматов
- •6.1.2. Описание автоматов
- •6.1.3. Автоматное моделирование алгоритмов
- •6.1.3.1. Автомат Мили - модель управляющего автомата
- •6.1.3.2. Автомат Мура - модель управляющего автомата
- •6.1.3.3. Микропрограммный автомат
- •6.1.4. Эквивалентность автоматов
- •6.1.5. Эквивалентность внутренних состояний автомата
- •6.1.5.1. Детерминированный автомат
- •6.1.5.2. Недетерминированный автомат
- •6.2. Структурный автомат
- •6.2.1. Произведение автоматов
- •6.2.1.1. Последовательное соединение автоматов
- •6.2.1.2. Параллельное соединение автоматов
- •Обратная связь автоматов
- •6.2.3. Сумма автоматов
- •6.2.4. Структурный автомат и кодирование
- •6.3. Логическое проектирование автоматов
- •6.3.1. Кодирование алфавитов автомата
- •6.3.2. Автоматы без “памяти”.
- •6.3.2.1. Формирование оператора
- •6.3.2.2. Формирование системы операторов
- •Логическая схема комбинационного автомата
- •6.3.3. Автоматы с “памятью”
- •6.3.3.1. Формирование оператора
- •6.3.3.2. Формирование оператора
- •.3.3.3. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
Предметный указатель
автомат 289
абстрактный 289
автономный 294
вероятностный 292
детерминированный 292, 297
инициальный 292
комбинационный 296
конечный 289
микропрограммный 314
Мили 293
минимальный 323
Мура 293
недетерминированный 292, 297
операционный 306
распознающий 295
структурный 289, 343
аксиома
ассоциативности 35
дистрибутивности 35
идемпотентности 35
коммутативности 35
поглощения 35
алгебра
общая 35
реляционная 227
алгоритм
вывода по принципу резолюции 193
минимизации детерминированного автомата 325
минимизации недетерминированного автомата 337
нормальный Маркова 253
поиска неизвестного множества 71
приведения к ССФ 208
приведения формулы к ПНФ 206
расчета позднего момента события 157
расчета раннего момента события 157
расчета резерва времени на работу 158
расчета резерва времени события 158
Форда-Фалкерсона 152
алгоритм преобразования формулы
к виду СДНФ 53
к виду СКНФ 54
алфавит
входной 289
выходной 289
состояний 290
аргумент 27
блок
разбиения 92
булеан 20
валентность
вершины графа 104
вектор
булевый 37
вершина
смежная 104
вершина графа 102
вершина-исток 104
вершина-сток 104
вершинная связность
графа 106
Включение нечеткого множества 73
выбор
комбинационных автоматов 352
элементов задержки 352
выборка 88
грань
верхняя 35
множества 34
нижняя 35
граф 102
вершинно-взвешенный 109
взвешенный 109
двудольный 109
дополнительный 105
планарный 109
плоский 109
полный 104
пустой 104
реберно-взвешенный 109
связный 105
суграф 108
типа дерево 105
частичный 108
график
функции 27
Дополнение нечеткого множества 76
Дополнение нечеткого отношения 77
дуга графа 102
законы
алгебры высказываний 178
алгебры множеств 68
алгебры предикатов 205
булевой алгебры 37
запись 225
знак
включения 19
невключения 19
непринадлежности 19
принадлежности 18
строгого включения 19
импликанта 55
имплицента 56
инциденция 103
канал
входной 289
выходной 289
квантор
всеобщности 199
существования 198
класс
неотличимых состояний 318
отличимых состояний 323
совместимых состояний 318
согласованных состояний 338
эквивалентных состояний 318
клика
графа 104
Композиция нечетких отношений 81
компонента
кортежа 22
конфигурация
машины Тьюринга 262
кортеж 21
совместимый 22
Логика 370
Логика нечетких высказываний 242
маршрут
гамильтонов 107
замкнутый 107
открытый 107
эйлеров 107
матрица
весов 113
достижимости 114
инциденции 111
разрезов 115
матрица смежности 112
машина Тьюринга 253
машиностроение 370
метод
дедуктивного вывода 183
критического пути 155
микрокоманда 314
микрооперация 314
минимизация
ДНФ 56
КНФ 58
множество 17
нечеткое 18
пустое 19
счетное 19
четкое 18
множество универсальное 20
моделирование
алгоритмов 304
модель
реляционная 224
моменты
дискретного времени 290
мощность
множества 19
нечеткие логические формулы 242
Нечеткие соответствия и отношения 29, 34
Нечетким высказыванием 241
нечеткое отношение 34
нормальная форма формулы
дизъюнктивная 51
конъюнктивная 54
Носителем нечеткого множества 23
носитель
алгебры 35
булевой алгебры 36
множества 23
область
значений 26
определения 26
отправления 25
прибытия 25
образ 26
нечеткого отображения 29
Объединение нечетких множеств 74
Объединение нечетких соответствий 74
объект
алгоритмический 252
комбинаторный 88
оператор
автоматный 292
выбора 229
деления 234
дополнения 231
естественного соединения 233
объединения 232
пересечения 233
поведения 290
проекции 230
прямого произведения 232
разности 233
соединения 234
операции
бинарные 35
логические 171
унарные 35
операция
дизъюнкции 36
конъюнкции 36
отрицания 37
операция отрицания 36
операция рекурсии 255
операция суперпозиции 254
остов 109
отношение 30
антисимметричное 32
антррефлексивное 32
асимметричное 32
бинарное 31
рефлексивное 32
симметричное 32
строгого порядка 33
транзитивное 32
унарное 31
частичного порядка 33
четкое 31
эквиваленции 33
отображение 25, 26
гомоморфное 317
изоморфное 318
память
внешняя 260
внутренняя 261
переменная
лингвистическая 24
связанная 200
переменная свободная 200
переменная-кортеж
свободная 236
переменные
пропозициональные 169
Пересечение нечетких множеств 75
Пересечение нечетких отношений 76, 78, 79
Пересечение нечетких соответствий 75, 77, 78
перестановка
элементов 90
переход графа 106
подграф 108
подмножество 19
поиск
наименьшего корня 259
поле 225
последовательность
выходных символов 290
состояний 290
построение
логической схемы 352
правила
введени логических связок 185
заключения 215
правило
произведения комбинаторики 96
суммы комбинаторики 96
правило подстановки 38
правило-
включения-исключения 97
предикат 28
преобразования
эквивалентные 179
принцип
резолюции 192
проектирование
автоматов логическое 352
произведение
автоматов 344
прямое 21
прообраз 26
нечеткого отображения 29
Прямое произведение нечетких множеств 24
путь
критический 154
Равенство нечетких множеств 73
размещение
элементов 89
Разность нечетких множеств 77
разрез графа 106
реберная связность
графа 106
ребро
смежное 104
ребро графа 102
режим
асинхронный 343
синхронный 343
связки
логические 170
связность
сильная 105
слабая 105
связь
обратная 348
семейство подмножеств 20
сигнатура
алгебры 35
булевой алгебры 36
символы
нетерминальные 261
терминальные 260
Симметрическая разность нечетких множеств 78
система
рекуррентных соотношений 290
функционально полная 49
сокращенная нормальная форма 55
соответствие 25, 26
состояние 290
начальное 291
сочетание
элементов 90
спикок
смежности 110
список
отношений 110
способность
пропускная 150
степень
вершины графа 104
принадлежности 23
суждение
общее 199
частное 198
сумма
автоматов 350
сумма прямая 22
схема
дедуктивного вывода 188
отношения 226
примитивной рекурсии 255
реляционной базы данных 226
таблица
истинности 174
терм 201
терм-множество 24
терм-множеством 241
тупиковая нормальная форма 55
файл 225
формула
интерпретация 210
предваренная нормальная форма 206
формулы
выводимые 184
тождественно истинные 184
тождественно ложные 184
функция 27
булева монотонная 47
булева самодвойственная 46
булева сохраняющая \ 49
булева, сохраняющая \ 49
вырожденная 43
высказывательная 198
выхода 290
константа 254
логическая 21
общерекурсивная 253
переходов 290
предшествования 256
принадлежности 22
рекурсивная 253
следования 254
тождества 254
усеченного вычитания 257
частично рекурсивная 253
функция булева линейная 47
функция невырожденная 43
функция-константа 39
функция-повторитель 39
фыункция-инверсия 39
число
комбинаторное 88
компонент связности 117
неплотность 119
плотность 119
Стирлинга 92
хроматическое 118
число цикломатическое 117
эквивалентность
автоматов 317
недетерминированного автомата 333
Экспертные системы 244
элемент
множества 18