- •Оглавление
- •Глава 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.1.1.5. Нормальные формы формул
В алгебре высказываний используют две нормальные формы: дизъюнктивную (ДНФ) и конъюнктивную нормальные формы формулы (КНФ).
ДНФ есть формула, равносильная формуле исходной логической функции и записанная в виде дизъюнкции элементарных конъюнкций, т.е.
F = K1 K2 K3 . ., где каждая Ki = (ABC . . .).
В элементарной коньюнкции нет двух одинаковых пропозициональных переменных, т.к. FF=F. А в ДНФ нет двух одинаковых элементарных коньюнкций, т.к. FF=F. Если одна из элементарных конъюнкций содержит (FF), то следует удалить всю элементарную конъюнкцию, т.к.(FF) = л.
Пример: если F=F1(F2F2)F2(F1F1), то F=F1F2F1F2F1F2F1F2= F1F2F1F2F1F2.
Так сформирована ДНФ.
КНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде конъюнкции элементарных дизъюнкций, построенных на пропозициональных переменных, т.е.
F = D1 D2 D3 . ., где каждая Di = (ABC . . . ).
В элементарной дизьюнкции нет двух одинаковых пропозициональных переменных, т.к. FF=F. А в КНФ нет двух одинаковых элементарных дизьюнкций, т.к. FF=F. Если одна из элементарных дизьюнкций содержит (FF), то следует удалить всю элементарную дизъюнкцию, т.к.(FF) = и.
Пример: если F=F1(F1F2) F2(F1F2), то
F=(F1F2) (F1F2).
Так сформирована КНФ.
Наибольшее распространение в логике высказываний получили формулы вида КНФ, элементарные дизъюнкции которых Di принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C –атомами.
4.1.2. Исчисление высказываний
Исчисление высказываний следует начинать с определения множества аксиом и правил вывода, обеспечивающих доказательство истинности заключения. Доказательством или выводом называют конечную последовательность высказываний, каждое из которых является либо аксиомой, либо выводится из одного или нескольких предыдущих высказываний по правилам вывода.
Задание возможного числа аксиом определяет семантическую полноту исчисления, а задание правил использования аксиом и промежуточных высказываний в процессе формирования заключения – метод дедуктивного вывода.
4.1.2.1. Интерпретация формул
Пусть набору пропозициональных переменных поставлена в соответствие некоторая формула. Определение истинного или ложного ее значения для любого набора пропозициональных переменных называют интерпретацией, а все множество формул - полем интерпретации.
Все множество формул можно разбить на три класса: тождественно истинные, тождественно ложные и выводимые. В каждом классе множество формул перечислимо и счетное.
Тождественно истинные формулы – это особый класс формул, которые принимают значение “истины” при любом значении пропозициональных переменных, входящих в эту формулу. Эти формулы играют роль аксиом и законов логики высказываний.
Например: F = ((AB)(AC)(A(BC))=и.
A |
B |
C |
AB |
AC |
BC |
45 |
16 |
78 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Л |
Л |
Л |
И |
И |
Л |
И |
И |
И |
Л |
Л |
И |
И |
И |
Л |
И |
И |
И |
Л |
И |
Л |
И |
И |
Л |
И |
И |
И |
Л |
И |
И |
И |
И |
И |
И |
И |
И |
И |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
И |
И |
Л |
И |
Л |
И |
Л |
Л |
Л |
И |
И |
И |
Л |
И |
Л |
Л |
Л |
Л |
И |
И |
И |
И |
И |
И |
И |
И |
И |
И |
Тождественно ложные формулы - это особый класс формул, которые принимают значение “ложь” при любых значениях пропозициональных переменных, входящих в формулу.
Тождественно ложные формулы – это особый класс формул, которые принимают значение “лжи ” при любом значении пропозициональных переменных, входящих в эту формулу.
Например, F=A(BC)(AB)(AC)=л.
-
A б) F = (A(BC)(AB)(AC)). A
B
C
23
14
12
13
56
87
1
2
3
4
5
6
7
8
9
Л
Л
Л
И
Л
И
И
Л
Л
Л
Л
И
И
Л
И
И
Л
Л
Л
И
Л
И
Л
И
И
Л
Л
Л
И
И
Л
Л
И
И
Л
Л
И
Л
Л
И
И
Л
Л
Л
Л
И
Л
И
И
И
Л
Л
Л
Л
И
И
Л
И
И
И
Л
И
Л
И
И
И
Л
Л
И
И
Л
Л
Выводимые формулы - это особый класс формул, которые принимают значения “истина” или “ложь” в зависимости от значений пропозициональных переменных.
Например, F=(АCВ)(CBA)(AC).
A |
B |
C |
32 |
14 |
21 |
36 |
13 |
578 |
Анализ таблицы показывает, что формула имеет значение “и” только при условии А=”л”, B=”л”, C=”и”.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Л |
Л |
Л |
Л |
Л |
Л |
Л |
И |
Л |
|
Л |
Л |
И |
И |
И |
Л |
И |
И |
И |
|
Л |
И |
Л |
Л |
Л |
И |
И |
И |
Л |
|
Л |
И |
И |
Л |
Л |
И |
И |
И |
Л |
|
И |
Л |
Л |
Л |
И |
Л |
Л |
И |
Л |
|
И |
Л |
И |
И |
И |
Л |
И |
Л |
Л |
|
И |
И |
Л |
Л |
И |
Л |
Л |
И |
Л |
|
И
|
И |
И |
Л |
И |
Л |
И |
Л |
Л |
Недостаток использования таблиц истинности состоит в том, что при большом числе пропозициональных переменных процедура построения этих таблиц становится громоздкой, так как число строк таблицы равно 2n, а число столбцов не меньше (n+m), где n – число пропозициональных переменных, а m – число логических связок.