- •Оглавление
- •Глава 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. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
4.4. Нечеткая логика
Основные понятия и характеристики нечетких множеств, отображений и отношений были изложены в 1.1.2, 1.2.2 и 1.3.2, а алгебраические операции над ними в 1.7. Поэтому в настоящем разделе рассмотрены только проблемы и правила вывода в нечетком исчислении высказываний.
4.4.1. Нечеткое исчисление
Нечеткие высказывания есть предложения А’, степень истинности (А’) или ложности (А’) которых также принимает значение на интервале [0; 1]. Например, высказывание: “сегодня хорошая погода”. По каким признакам и кто дал такую оценку? Ведь “у природы нет плохой погоды...”.
Нечеткие предикаты есть высказывательные функции, аргументами которых являются предметные переменные и предметные постоянные. Степень истинности предметных переменных и высказывательных функций также принадлежит интервалу [0; 1].
Например, высказывание “Петров выполняет ответственное задание”. Как понимать “ответственное задание”?
Лингвистические переменные. Как правило, нечеткими предметными постоянными и переменными являются слова и словосочетания естественного языка. Лингвистическая переменная служит для качественного описания явления, факта или события. Множество лингвистических переменных, описываемых также лингвистической переменной, называют терм-множеством и обозначают Т(x).
Так терм-множества ”возраст”, ”количество”, ”частота”, “расположение” и т. п. могут быть представлены лингвистическими переменными:
T’1(“возраст”)={ ребенок, подросток, юноша, молодой человек, человек средних лет, пожилой человек, старик, ...};
T’2(”количество”)={ малое, среднее, большое,...};
T’3(“частота”)={почти всегда, часто, редко, иногда, почти_никогда...};
T’4(“расположение”)={вплотную; близко, рядом, далеко,...}.
Для того, чтобы согласовать мнения различных экспертов, степень истинности лингвистической переменной удобно определять по значению функции принадлежности этой переменной какому-то интервалу. Это позволит для каждого конкретного факта или события количественно оценивать ее значение в конкретном высказывании.
Нечеткие формулы. Для формирования сложных высказываний используют логические связки отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции. Так формируются нечеткие логические формулы.
Степень истинность сложного высказывания определяется как степень принадлежности результатов исполнении операций над нечеткими множествами:
(A’)=(1 - (A’));
(A’B’)=min{(A’); (B’)};
(A’B’)=max{(А’); (B’)};
(A’B’)=max{(1-(А’)); (B’)};
(A’B’)=min{max{(1-(А’)); (B’)}; max{(1-(B’)); (A’)}}.
Следует обратить внимание, что законы противоречия и “третьего не дано” для нечетких высказываний не выполняются.
Так для четких высказываний: (AA)=л, (AA)=и, а для нечетких высказываний:
(A’A’)=min{(A’); (1-(A’))}, (A’A’)=max{(А’); (1-(A))}.
Нечеткие правила вывода. Так же как в логике четких высказываний, в логике нечетких высказываний выводима теорема:
F1’F1’.. F1’B’.
Для нечетких высказываний это удобно пояснить на формировании заключения с помощью условного нечеткого высказывания “если A’, то B’, иначе С’”.
Очевидно, что нечеткое высказывание “если A’, то B’” можно определить как нечеткое отношение между нечеткими высказываниями A’ и B’, т. е. (А’B’), а нечеткое высказывание “если не А, то С” – как нечеткое отношение между высказываниями A’ и С’. Объединение этих двух отношений есть формула условного нечеткого высказывания:
((A’В’), C’) = ((А’B’)(A’C’)).
Если даны значения степеней истинности нечетких высказываний (A’), (B’) и (C’), , то истинность высказывания “если A’, то B’ иначе C’” может быть определена, как для нечетких отношений, по формуле: ((A’ В’), C’) = max{min{(A’), (B’)}; min{(A’), (C’)}}.
Пример: “Если сегодня вечером будет дождь, то завтра будет солнечная погода иначе завтра будет пасмурный день”.
Пусть для высказывания A’:=”сегодня вечером будет дождь” (A’)=0,3, для высказывания B’=”завтра будет солнечная погода”- (B’)=0,5, для высказывания C’:=”завтра будет пасмурный день”- (C’)=0,2 .
Следовательно,
((A’В’), C’)= max{min{(A’), (B’)}; min{(A’), (C’)}}=
max{min{0,3; 0,5}; min{0,7; 0,2}= max{0,3; 0,2}=0,3.
Если (C’)=1, т.е. высказывание C’ истинно для любых значений истинности высказывания A’, то формула условного высказывания принимает вид, т.е. ((А’B’)A’), что соответствует высказыванию “если A’, то B’”
Степень истинности такого высказывания есть
(A’В’)= max{min{(A’), (B’)}; (A’)}.
Так можно определить истинность импликации по известным значениям истинности посылки A’ и заключения B’.
Пример: “Если сегодня вечером будет дождь, то завтра будет солнечная погода”.
Пусть для высказывания A’:=”сегодня вечером будет дождь” (A’)=0,3, для высказывания B’=”завтра будет солнечная погода” принято (B’)=0,5.
Следовательно,
(A’В’)= max{min{(A’), (B’)}; (A’)}=max{min{0,3, 0,5}; 0,7}=
max{0,3; 0,7}=0,7.
Если даны множества нечетких высказываний {A’=(ui)/ui} и {B’=(vj)/vj} о фактах {u1, u2, u3, u4, u5, u6} и {v1, v2, v3, v4, v5, v6} то истинность (A’В’) необходимо определять для каждой пары (ui, vj) по формуле: (A’В’)= max{min{(ui), (vj)}; ( ui)}.
Пример: пусть даны нечеткие высказывания
(A’)={0,6/u1; 0,4/u2; 0,8/u3; 0,2/u4; 1,0/u5; 0,3/u6};
(B’)={0,9/v1; 0,4/v2; 1,0/v3; 0,7/v4; 0,3/v5; 0,5/v6}
Для каждой позиции таблицы (A’В’) нужно вычислить значение (uivj)=max{min{(ui), (vj)}; (ui)}.
Например, (u4v2)=max{min{0,2; 0,4}; 0,8}=max{0,2; 0,8}=0,8.
Все результаты вычислений (uivj) сведены в таблицу.
v1
v2
v3
v4
v5
v6
u1
0,6
0,4
0,6
0,6
0,4
0,5
u2
0,6
0,6
0,6
0,6
0,6
0,6
u3
0,8
0,4
0,8
0,7
0,3
0,5
u4
0,8
0,8
0,8
0,8
0,8
0,8
u5
0,9
0,4
1,0
0,7
0,3
0,5
u6
0,7
0,7
0,7
0,7
0,7
0,7
Основным правилом вывода, как и в обычном исчислении, является modus ponens, согласно которому истинность заключения (В’) определяют по обобщенной схеме этого правила:
(A’); (A’В’)
(B’)=(A’) (A’В’),
где (A’) (A’В’) – композиция нечетких высказываний A’ и (A’В’).
В этом случае истинность высказывания B’ определяется формулой:
(B’)= (A’)(A’В’)=max{min{(A’); (A’В’)}}.
Пример: пусть (A’В’) задано предыдущей таблицей, а
(A’)={0,36/u1; 0,16/u2; 0,64/u3; 0,04/u4; 1,0/u5; 0,09/u6}.
Тогда истинность заключения:
(B’)=(A’)(A’В’)={max v1{min{0,36/u1; 0,6/(u1,v1)},
min{0,16/u2; 0,6/(u2,v1)}, min{0,64/u3; 0,8/(u3,v1)},
min{0,04/u4; 0,8/(u4,v1)}, min{1,0/u5; 0,9/(u5,v1)}, min{0,09/u6; 0,7/(u6,v1)}}, maxv2{min{0,36/u1; 0,4/(u1,v2)}, min{0,16/u2; 0,6/(u2,v2)}, min{0,64/u3; 0,4/(u3,v2)}, min{0,04/u4; 0,8/(u4,v2)}, min{1,0/u5; 0,4/(u5,v2)}, min{0,09/u6; 0,7/(u6,v2)}}, maxv3{min{0,36/u1; 0,6/(u1,v3)}, min{0,16/u2; o,6/(u2,v3)}, min{0,64/u3; 0,8/(u3,v3)}, min{0,04/u4; 0,8/(u4,v3)}, min{1,0/u5; 1,0/(u5,v3)}, min{0,09/u6; 0,7/(u6,v3)}}...=maxv1{0,36, 0,16, 0,64, 0,04, 0,9, 0,09}, maxv2{0,36, 0,16, 0,4, 0,04, 0,4, 0,09}, maxv3{0,36, 0,16, 0,64, 0,04, 1,0, 0,09},..= {0,9/v1, 0,4/v2, 0,64/v3, 0,7/v4, 0,64/v5, 0,5/v6}.