- •Оглавление
- •Глава 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.6. Свойства булевых функций
Часто возникает вопрос: всякая ли булева функция представима суперпозицией формул f0, f1,..f15? Для того, чтобы определить возможность формирования любой булевой функции с помощью суперпозиции этих формул, необходимо определить их свойства и условия использования функционально полной системы.
1.5.6.1. Самодвойственные булевы функции
Функция f(x1; x2;…xn) называется самодвойственной, если f(x1;x2;…xn)=`f(`x1;`x2;…`xn).
Например, функции f3(x1;x2)=x1, f5(x1;x2)=x2, f10(x1;x2)=`x2 и f12(x1;x2)=`x1 являются самодвойственными, т. к. при изменении значения аргумента они изменяют свое значение.
Любая функция, полученная с помощью операций суперпозиции из самодвойственных булевых функций, сама является самодвойственной. Поэтому множество самодвойственных булевых функций не позволяет формировать не самодвойственные функции.
1.5.6.2. Монотонные булевы функции
Функция f(x1; x2;…xn) называется монотонной, если для каждого s1i£s2i булевых векторов (s11; s12;……;s1n) и (s21;s22;……;s2n) выполняется условие: f(s11;s12;…;s1i;…;s1n)£f(s21;s22;…;s2i;…;s2n).
Например, для функций f(x1; x2) монотонными функциями являются:
если (0; 0)£(0; 1), то f(0; 0)£f(0; 1),
если (0; 0)£(1; 0), то f(0; 0)£f(1; 0),
если (0; 1)£(1; 1), то f(0; 1)£f(1; 1),
если (1; 0)£(1; 1), то f(1; 0)£f(1; 1).
Таким условиям удовлетворяют следующие функции:
f0(x1; x2)=0; f1(x1; x2)=(x1×x2); f3(x1; x2)=x1; f5(x1; x2)=x2; f7(x1;x2)=(x1Úx2); f15(x1; x2)=1.
Любая функция, полученная с помощью операции суперпозиции из монотонных булевых функций, сама является монотонной. Поэтому множество монотонных функций не позволяет формировать не монотонные функции.
1.5.6.3. Линейные булевы функции
Алгебра Жегалкина, опирающаяся на базис F4={×; Å; 1}, позволяет любую логическую функцию представить полиномом, каждый член которого есть конъюнкция I булевых переменных булевого вектора в пределах 0in:
P(x1; x2;…xn)=b0×1 Å bi×xi Å1£j¹k£n bj×xj×xk Å……Å b2n-1×x1×x2×...×xn.
Например, для логических функций f8(x1; x2)
полином Жегалкина имеет вид: P(x1; x2)=1Å x1Å x2Å x1×x2.
Преимущества алгебры Жегалкина состоят в “арифметизации” логических формул, а недостатки - в сложности, особенно при большом числе двоичных переменных.
Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x1; x2;…;xn)=b0×1Åb1×x1Å…Åbn×xn называют линейными.
Например, f9(x1; x2)=1Åx1Åx2, или f12(x1;x2)=1Åx1.
Основные свойства операции сложения по модулю 2 приведены в таблице 1.18.
Если логическая функция задана таблицей или формулой в любом базисе, т.е. известны значения булевой функции для различных наборов булевых переменных, то можно вычислить все
коэффициенты bi полинома Жегалкина, составив систему уравнений по всем известным наборам двоичных переменных.
-
таблица 1.18
Наименование закона
Эквивалентные формулы
коммутативности
x1 Å x2=x2 Å x1
ассоциативности
x1Å (x2 Å x3)=(x1Å x2) Å x3;
дистрибутивности
x1×(x2 Å x3)=x1×x2 Å x1×x3;
свойство “1”
xÅ 1=`x;
свойство “0”
xÅ 0=x;
сложение по модулю 2
xÅ x=0; xx=1.
Пример: дана булева функция f(x1;x2)=x1Úx2 . Значение этой функции известны для всех наборов булевых переменных.
f(0;0)=0=b0×1Å b1×0 Å b2×0 Å b3×0×0;
f(0;1)=1=b0×1Å b1×0 Å b2×1Å b3×0×1;
f(1;0)=1=b0×1Å b1×1Å b2×0Å b3×1×0;
f(1;1)=1=b0×1Å b1×1Å b2×1Å b3×1×1;
Откуда находим b0=0; b1=1; b2=1; b3=1.
Следовательно, (x1Úx2)=x1Åx2Åx1×x2, т. е. дизъюнкция есть нелинейная булева функция.
Пример: дана булева функция f(x1;x2)=(x1®x2). Значение этой функции также известны для всех наборов двоичных переменных.
f(0;0)=1=b0×1Å b1×0 Å b2×0 Å b3×0×0;
f(0;1)=1=b0×1Å b1×0 Å b2×1Å b3×0×1;
f(1;0)=0=b0×1Åb1×1Åb2×0Åb3×1×0;
f(1;1)=1=b0×1Åb1×1Åb2×1Åb3×1×1;
Откуда находим b0=1; b1=1; b2=0; b3=1.
Следовательно, (x1®x2)=1Å x2 Å x1×x2.
В таблице 1.19 приведены полиномы Жегалкина для основных представителей булевых функций из таблицы 1.15.
-
таблица 1.19
fi
эквивалентные формулы
f7
(x1Úx2)=x1Å x2Å x1×x2;
f8
(x1¯x2)=ù(x1Úx2)=1Å x1Å x2Å x1×x2;
f9
(x1«x2)=(`x1×`x2Úx1×x2)=1Å x1Å x2;
f12
`x1=1Å x1;
f13
(x1¯x2)=(`x1Úx2)=1Å x1Å x2Å x1×x2;
f14
(x1½x2)=ù(x1×x2)=1Å x1×x2.
Если дано аналитическое выражение логической функции и неизвестны ее значения для различных наборов двоичных переменных, то можно построить полином Жегалкина, опираясь на конъюнктивный базис алгебры Буля F2={` ; ×}:
Пусть f(x1; x2)=(x1Úx2).
Тогда (x1Úx2)=ù(`x1×`x2)=((x1Å 1)×(x2Å 1))Å 1=x1×x2Å x1×1Å x2×1Å 1×1Å1=
(x1Åx2Åx1×x2).
Пусть f(x1;x2)=(x1 ®x2).
Тогда (x1 ®x2)=(`x1Úx2)=ù(x1×`x2)=x1×(x2Å 1)Å 1=x1×x2Å x1×1Å 1= =(1Åx1Åx1×x2).
Пусть f(x1;x2)=(x1 «x2).
Тогда (x1«x2)=(`x1×`x2Úx1×x2)=ù(ù(`x1×`x2)×ù(x1×x2))=(((x1Å1)×(x2Å1))Å1) ×(x1×x2Å)Å1=(x1×x2Åx1Åx2Å1Å1)×(x1×x2Å1)Å1=x1×x2Åx1×x2Åx1×x2Åx1Å
x1×x2Åx2Å1=(1Åx1Åx2).
Любая функция, полученная с помощью операции суперпозиции из линейных логических функций, сама является линейной. Поэтому множество линейных функций не позволяет формировать нелинейные функции.