- •Оглавление
- •Глава 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. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
1.5.2. Законы булевой алгебры
Аксиомы общей алгебры формируют законы булевой алгебры:
коммутативности: xixj=xjxi и xixj=xjxi,
ассоциативности: xi(xjxk)=(xjxj)xk и xi(xjxk)=(xjxj)xk,
дистрибутивности: xi(xjxk)=(xixj)(xixk) и xi(xjxk)=(xixj)(xixk),
идемпотентности: (xixi)=xi и (xixi)=xi,
поглощения: xi(xixj)=xi и xi(xixj)=xi,
противоречия: (xx)=1 и (xx)=0,
двойного отрицания: (x)=x,
склеивания: xFxF=F, (xF)(xF)=F,
де Моргана: (xixj)=xixj и (xixj)=xixj,
Порецкого xxy=xy, xxy=xy,
константы: (x0)=x, (x0)=0,
(x1)=1, (x1)=x.
1.5.3. Формула булевой функции
Функцию y=f(x1, x2,..xn), значение которой и значения компонент аргумента принадлежат множеству {0, 1}, называют булевой, а аргумент – булевым вектором. Компоненты булевого вектора называют булевыми (или двоичными) переменными.
Алгебраическое выражение булевой функции, использующее только булевы переменные булевого вектора и только логические связки конъюнкции, дизъюнкции и отрицания, называют формулой.
Если даны булевы переменные xi, xj, то элементарными формулами являются F=xi, F=xj, F=(xixj), F=(xixj), а производными формулами F=F, F=(FiFj), F=(FiFj).
Для описания функции формулами используют два правила: подстановки и замещения.
Пусть даны равносильные формулы Fi и Fj, т. е. (Fi=Fj), которые содержат переменную x. Если всюду в формулы Fi и Fj вместо x подставить произвольную формулу F, то будут получены также равносильные между собой формулы F’i и F’j, т. е. F’i=F’j.
Пусть дана формула (Fi=Fj) и существует формула Fk, равносильная только одной подформуле Fi, т. е. (Fi=Fk). Тогда Fi может быть замещена формулой Fk и получена новая формула (Fk=Fj). При этом не обязательно ее замещение всюду в алгебраическом выражении булевой функции.
1.5.4. Описание булевой функции
При табличном описании булевой функции необходимо для каждого набора двоичного переменных булевого вектора указывать её значение. Если значение функции определено не для всех наборов булевого вектора, то функцию называют частично определённой.
Число строк таблицы детерминированной функции от n компонентов аргумента равно 2n.
таблица
1.13.
x1
x2
¼
xn
f(x1;x2;¼…xn)
0 1 0 1 … 1
0 0 1 1 … 1
…¼ …¼ ¼
0 0 0 0 … 1
0 0
1 1 …¼ 0
Число логических функций для n компонентов аргумента определяется выражением: 2p, где p=2n.
таблица
1.14.
X
y=f(x)
f0(x)
f1(x)
f2(x)
f3(x)
0
0
0
1
1
1
0
1
0
1
Анализ таблицы позволяет дать определение каждой из четырёх логических функций:
f0(x) – функция-константа “0”, т.к. она не изменяет своего значе- ния при изменении аргумента, т.е. (y=0);
f1(x) – функция-повторитель, т.к. она принимает значения, равные значению аргумента, т.е. (y=x);
f2(x) - функция-инверсия (или отрицания), т.к. она принимает значения противоположные значению аргумента, т.е. (y=`x);
f3(x) - функция-константа “1”, т.к. она не изменяет своего значения при изменении аргумента, т.е. (y=1).
таблица
1.15
Аргумент
Функция
y=fi(x1,
x2)
x1
x2
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
В таблице 1.16 приведены алгебраические выражения функции по законам булевой алгебры. Некоторые функций имеют достаточно сложное алгебраическое описание.
Например для f6(x1;x2) и f9(x1;x2).
таблица
1.16.
y=f(x1
; x2)
Формула
логической функции в базисе булевой
алгебры. y=fi(x1;
x2)
f(0;0)
f(0;1)
f(1;0)
f(1;1)
0
0
0
0
y=f0(x1;
x2)=0
– константа “0”
0
0
0
1
y=f1(x1;
x2)=(x1×x2)
– конъюнкция
0
0
1
0
y=f2(x1;
x2)=(x1×`x2)
- конъюнкция
0
0
1
1
y=f3(x1;
x2)=x1
=повторитель
0
1
0
0
y=f4(x1;
x2)=(`x1×x2)
- конъюнкция
0
1
0
1
y=f5(x1;
x2)=x2
- повторитель
0
1
1
0
y=f6(x1;
x2)=(x1×`x2)Ú(`x1×x2)
–дизъюнкция конъюнкций
0
1
1
1
y=f7(x1;
x2)=x1Úx2
- дизъюнкция
1
0
0
0
y=f8(x1;
x2)=ù(x1Úx2))
– отрицание дизъюнкции
1
0
0
1
y=f9(x1;
x2)=(x1×x2)Ú(`x1×`x2)
- дизъюнкция конъюнкций
1
0
1
0
y=f10(x1;
x2)=`x2
- инверсия
1
0
1
1
y=f11(x1;
x2)=x1Ú`x2
дизъюнкция
1
1
0
0
y=f12(x1;
x2)=`x1
-инверсия
1
1
0
1
y=f13(x1;
x2)=`x1Úx2
-дизъюнкция
1
1
1
0
y=f14(x1;
x2)=ù(x1×x2)
–отрицание конъюнкции
1
1
1
1
y=f15(x1;
x2)=1
– константа “1”
« - эквиваленции, когда y=1 только при условии x1=x2;
® - импликации, когда y=0 только при условии x1=1 и x2=0;
- сложения по модулю “2”, когда y=1 только при условии x1x2;
¯ - стрелка Пирса, когда y=1 только при условии x1=x2=0;
ç- штрих Шеффера, когда y=0 только при условии x1=x2=1;
Множество логических связок, определяющих исполнение любых логических операций, есть сигнатура алгебры логики, т.е.
F0 = { ; ; ; ; «; ®; ¯; ½}.
В таблице 1.17 приведены алгебраические выражения логических функций, использующих сигнатуру алгебры логики.
таблица
1.17.
y=f(x1;x2)
Формула
логической функции в базисе алгебры
логики. y=fi(x1;
x2)
f(0;0)
f(0;1)
f(1;0)
f(1;1)
0
0
0
0
y=f0(x1;
x2)=0
– константа “0”
0
0
0
1
y=f1(x1;
x2)=(x1×x2)
- конъюнкция
0
0
1
0
y=f2(x1;
x2)=ù(x1®x2)
– отрицание прямой импликации
0
0
1
1
y=f3(x1;x2)=x1
-повторитель
0
1
0
0
y=f4(x1;x2)=ù(x2®x1)
–отрицание обратной импликации
0
1
0
1
y=f5(x1;x2)=x2
-
повторитель
0
1
1
0
y=f6(x1;x2)=ù(x1«x2)=(x1Åx2)
–сложение по модулю 2
0
1
1
1
y=f7(x1;x2)=x1Úx2
- дизъюнкция
1
0
0
0
y=f8(x1;x2)=(x1¯x2)
– стрелка Пирса
1
0
0
1
y=f9(x1;x2)=(x1«x2)
- эквиваленция
1
0
1
0
y=f10(x1;x2)=`x2
– инверсия x2
1
0
1
1
y=f11(x1;x2)=x2®x1
– обратная импликация
1
1
0
0
y=f12(x1;x2)=`x1
– инверсия x1
1
1
0
1
y=f13(x1;x2)=x1®x2
– прямая импликация
1
1
1
0
y=f14(x1;x2)=(x1½x2)
– штрих Шеффера
1
1
1
1
y=f15(x1;x2)=1
- константа “1”
Функция, которая сводится к зависимости от меньшего числа двоичных переменных, называется вырожденной, а функция, существенно зависящая от всех двоичных переменных, - невырожденной.
Двоичная переменная xi в функции f(x1; x2;…;xi-1; xi; xi+1;…;xn) называется фиктивной, если выполняется условие:
f(x1; x2;...xi-1; 0; xi+1;…xn)=f(x1; x2;…xi-1; 1; xi+1;…xn).
Удаление фиктивной переменной упрощает анализ функции, а её введение позволяет всякую функцию сделать функцией от большего числа переменных. Это необходимо при совмещении двух или нескольких логических функций по аргументам.