- •Оглавление
- •Глава 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. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
5.1. Рекурсивные функции
Рекурсия есть способ вычисления значения функции по известным значениям аргументов и известным значениям функции в некоторых предшествующих точках.
Если речь идет о числовых функциях, области определения и значения которых заданы на множестве целых положительных чисел, это описание рекурсии задает способ ее вычисления для заданного набора числовых значений аргументов и числового значения этой функции в некоторой исходной точке.
Числовые функции, для которых существует алгоритм вычисления их значений, называют рекурсивными функциями.
Если числовая функция определена не для всех значений аргументов, ее называют частично рекурсивной функцией.
Если для всех значений - то общерекурсивной функцией.
Любое вещественное число может быть синтаксически представлено цепочкой <целое> " . " <целое>, для которой существует только одна синтаксическая переменная — <целое>.
Следовательно, любую функцию можно свести к рекурсивной, если значения аргументов и значения функции рассматривать как значения, принадлежащие синтаксической переменной <целое>.
Для формирования механизма рекурсивных функций заданы наборы элементарных объектов - три базовые функции: константы, тождества и следования и наборы элементарных шагов – три элементарные операции: суперпозиции, рекурсии и минимизации.
5.1.1. Базовые функции
Функция константа. Если f={(x1, x2, ... xn, у)| xiX; yY} =Cn, то любым значениям аргументов функции ставится в соответствие ее значение, равное постоянной величине — Сn. Чаще всего Cn=0.
Например,
если f ={(x1, x2, x3, у)} = C3, то для x1 = 5, x2 = 4, x3=7 и C3=0 имеем у = 0.
Функция тождества или выбора аргумента. Если f = {(x1, x2, ... xn, у) | xiX; yY} =J n;m, то любым значениям переменных аргумента функции ставится в соответствие ее значение, равное значению m-го независимого аргумента, где 1 m n - номер независимого аргумента.
Например,
если f ={(x1, x2, x3, у)} = J3,2 , то для x1 = 5, x2 = 4, x3 = 7 имеем у = 4;
если f={(x1, x2,, x3, у)} = J3,3, то для x1 = 5, x2 = 4, x3 = 7 имеем у = 7.
Функция следования. Если f ={(x, у)} = (x), то любому значению независимой аргумента ставится в соответствие значение функции, равное числу, непосредственно следующим за числом, являющимся значением независимой аргумента.
Например,
если f = {(x, у)} = (x), то для x = 5 имеем у = (х+1) = (5+1) = 6;
если f = {(x, у)} = (x), то для x = 7 имеем у = (х+1) = (7+1) = 8.
5.1.2. Элементарные операции
Простейшие операции, с помощью которых из базовых функций могут быть получены рекурсивные функции, называют элементарными.
Операция суперпозиции. Если даны функция h от m независимых переменных аргумента, т.е. h = (z1, z2,...zm,, у), и m функций qi от n независимых переменных аргумента, т.е. qi = {(x1i, x2i,...xni, zij)}, то в результате подстановки функций q1, q2 ... qm вместо аргументов функции h может быть получена новая функция f = (x1, x2,...xn, у) от n независимых переменных аргумента, т.е.
h = (zi, z2,...zm, y);
q1 = (x1, x2,...xn, z1);
q2 = (x1, x2,...xn, z2);
...........................
qm=(x1, x2,...xn, zm)...
h = (q1, q2,...qm, y) = f = (x1, x2,...xn, y).
Значения функций q1, q2,...qn, найденные для заданных значений независимых переменных x1, x2,...xn, принять за значения независимых переменных аргумента функции h и вычислить ее значение, которое принять за значение функции f = (x1; x2; ... xn; y).
Например,
если h = (z, y) = (z) и q = (х, z) = (х), то f = (q, у) = () = 2(х).
Следовательно, для x = 5 имеем z = 5+1 = 6 и у = 6+1= 7.
Оператор суперпозиции записывают так:
f =(x1, x2,...xn, y) = Smn(h(m), q1(n), q2(n),...qm(n)),
где h(m) = ( z1, z2,...zm, y) и q1(n) = (x1i (n), x2i (n),...xni (n), zi).
Если заданы функции тождества (In,m) и оператор суперпозиции (Smn), то заданными являются любые операторы подстановки, перестановки и переименования любых функций.
Операция рекурсии. Если даны n-местная рекурсивная функция g и (n+2)-местная рекурсивная функция h, то можно найти (n+1)-местную рекурсивную функцию f, используя схему примитивной рекурсии:
f(x1, x2,...xn, 0) = g(x1, x2,...xn);
f(x1, x2,...xn, у+1) = h(x1, x2,...xn, у, f(x1, x2,...xn, у)).
Схема примитивной рекурсии имеет главный дополнительный аргумент — у, который определяет значение функции, и вспомогательный аргумент — f (x1, x2,...xn, у), который необходим для вычисления последующих значений главного дополнительного аргумента.
Оператор рекурсии записывают так:
f = (x1, x2,...xn, у+1) = R (g(n), h(n+2)),
где gi(n)=gi (x1, x2,...xn) и h(n+2)=h(x1, x2,...xn, у, f(x1, x2,...xn, у)) .
При исполнении операции рекурсии x1 = a1, x2 = a2,...xn = an.
Значением искомой функции f для нулевого значения главного дополнительного аргумента следует считать значение функции g, а значением функции f для каждого последующего значения главного аргумента (у+1) следует считать значения функции h при предыдущих значениях главного аргумента у и при значении вспомогательного аргумента, совпадающим с предыдущим значением искомой функции.
Функции, для вычисления значений которых использовали базовые функции и операторы суперпозиции и примитивной рекурсии, называют примитивно-рекурсивными функциями.
Для вычисления функции предшествования
y - 1 при у>1;
-1(y)=(y 1)=
0 при у 1,
по схеме примитивной рекурсии использованы функции g(х)=Ci(х)=0 и h(x, у, f (x, у))=J3,2=y, т. е.
f (x, 0)=g(x)=0;
f (x, у+1) = h(x, у, f(x, у))= у.
Так как функции g и h не содержат в качестве аргумента независимую переменную х, то имеем:
f(0)=0;
f(1)=0;
f(2)=1;
f(3)=2...
f (i) = (i - 1 ).
Если i = у, то f(у)=(у-1)=-1(у).
Пусть у=6, тогда f(6)=6-1=5.
Таким образом, используя базовые функции константу и тождество, по схеме примитивной рекурсии может быть получено значение примитивно-рекурсивной функции предшествования:
-1(у)= (у 1)= R(0, у)
Для вычисления функции сложения целых чисел f+(x, y)=(x+y) по схеме примитивной рекурсии использованы базовые функции g(x)=J1,1=x и h(x, у, f(x, у))=(J3,3)=f(x, у)+1, т. е.
f(x, 0)=g(x)=x;
f(x, у+1)=h(x, у, f(x, у))= f(x, у)+1.
По схеме примитивной рекурсии имеем:
f(x, 0)=g(x)=x;
f(x, 1)=h(x, 0, f (x, 0))=x+1;
f(x, 2)=h(x, 1, f(x, 1))=x+2;
f(x, 3)=h(x, 2, f(x, 2))= x+3...
f(x, i)=h(x, (i-1), f(x, (i-1)))=x+i.
Если i=у, то f+(x, у)=(x+у).
Пусть x=3, у=6, тогда f(3, 6)=3+6=9.
Таким образом, используя базовые функции тождества и следования, по схеме примитивной рекурсии может быть получено значение примитивно-рекурсивной функции сложения:
f+(x, у)= (x+y)=R(x, (f(x, у)+1)).
Д ля вычисления функции усеченного вычитания
x - у при x>y;
f(x, y)=(x y)=
0 при x y
по схеме примитивной рекурсии использованы g(x)=J1,1=x и
-1(J3,3)=f(x, у) – 1, т. е.
f(x, 0)=g(x)=x;
f(x, 1)=h(x, 0, f(x, 0))=x-1;
f(x, 2)=h(x, 1, f(x, 1))=(x-1)-1=x-2;
f(x, 3)=h(x, 2, f(x, 2))= (x-2)-2=x-3...
f(x, i)=h(x, (i-1), f(x, (i-1)))=(x-(i-1))-1=x-1.
Если i=у, то f(x, у)=(x-у).
Пусть х=6, y=3, тогда f(6, 3)=6-3=3.
Таким образом, используя базовую функцию тождества и примитивно-рекурсивную функцию предшествования, может быть получено значение примитивно-рекурсивной функции усеченного вычитания:
(x у)= R(x, (-1(f(x, у)))) = f-(x, у).
Для вычисления функции умножения целых чисел по схеме примитивной рекурсии использованы базовая функция константа g(x)=С1=0 и примитивно-рекурсивная функция сложения h(x, у, f(x, у))=f+(I3,1, I3,3 )=x+f(x, у), т. е.
f(x, 0)=g(x)=0;
f(x, 1)=h(x, 0, f(x, 0))=x+0=x;
f(x, 2)=h(x, 1, f(x, 1))=(x+x)=2x;
f(x, 3)=h(x, 2, f(x, 2))=(x+2x)=3...
f(x, i)=h(x, (i-1), f(x, (i-1)))=(x+(i-1))-x=ix.
Если i=у, то f(x, у)=xу.
Пусть х=3, y=4, тогда f(3, 4)=3. 4=12.
Таким образом, используя базовые функции константы, тождества и примитивно-рекурсивную функцию сложения, может быть получено значение примитивно-рекурсивной функции умножения:
xу = R (0, f+(x, f(x, у)))=f+(x, у).
Для вычисления функции возведения в степень fexp(x, y)= xy по схеме примитивной рекурсии использована базовая функция g(x)=С1=1 и примитивно-рекурсивная функция умножения
h(x, у, f(x, у))=f*(I3,1, I3,3 )=xf(x, у), т. е.
f(x, 0)=g(x)=1;
f(x, 1)=h(x, 0, f(x, 0))=x1= x;
f(x, 2)=h(x, 1, f(x, l))=xx=x2;
f(x, 3)=h(x, 2, f(x, 2))=xx2=x3 ...
f(x, i)=h(x, (i-1), f(x, (i-1)))=xx(i - 1)=xi.
Если i=у, то f(x, y)=xy.
Пусть x=3, у=3, тогда f(3, 3)=33 =27.
Таким образом, используя базовую функцию константы и примитивно-рекурсивную функцию умножения, может быть получено значение примитивно-рекурсивной функции возведения в степень:
xy =R(1, f(x, f(x, y)))=fexp(x, y).
Из приведенных примеров легко можно получить примитивно рекурсивные функции:
min(x, у)=x-(x-у)=f-(x, f-(x, y));
max(x, у)=у-(x-у)=f-(y, f-(x, y));
|х-у|=(х-у)+(у-х)=f+(f-(x, y), f-(y,x));
xvy = max(x, у);
ху=min(х, у) и др.
Последовательность рекурсивного описания функции, использующая базовые функции и результаты вычисления ее значений на всех предшествующих точках с помощью операторов суперпозиции и примитивной рекурсии, называют протоколом.
Операция минимизации (поиск наименьшего корня): Если дана (n+1)-местная функция f(x1, x2,...xn, у), то значение n-местной функции (x1, x2,...xn) можно определить, придавая вспомогательному аргументу у последовательно значения 0, 1, 2, 3,.., пока не окажется, что функция
f(x1, x2,...xn, у) в первый раз (!) стала равной нулю, т.е. f(x1, x2,...xn, у)=0.
Полученное значение вспомогательного аргумента у принять за значение определяемой функции, соответствующей заданным значениям независимых переменных аргумента (x1=a1, x2=a2,...xn=an).
Поиск значений функции (x1, x2,...xn) выполняется с помощью - оператора, который имеет вид:
(x1, x2,...xn)=y(f(x1, x2,...xn, y)=0.
Пример: пусть f(x1, x2,...xn, у)=f(x1, x2, у)=x1у-x2.
Тогда (x1, x2)=y(f(x1, x2, у))=x1 у-x2= 0 или (x1, x2)= y =(x2/ x1).
Так как (x1, x2) является рекурсивной функцией, то (x2/x1) должна иметь наименьшим общим кратным значение x1 для значения x2, что принято обозначать так: (x1, x2)=[x2/ x1]. В противном случае (x1, x2) - не определена. Например, если x1=3, то (3, x2) определена только для значений x2 =3, 6, 9, 12, ... и имеет значение 1, 2, 3, 4,... соответственно. Таким образом, функция (x1, x2) является частично-рекурсивной.
Пример: пусть f (x1, x2,...xn, у)=f(x, у)=y2 -x.
Тогда (x)=y((x, y))=y2-x=0 или (x)=y=x.
Так как (x) является рекурсивной функцией, то x должен иметь значения только из множества целых положительных чисел, т. е. (x)=1, 2, 3, 4,...
Если дан алгоритм вычисления функции f(a1, a2,...an, у), то значение функции (a1, a2,...an) вычисляется следующим образом:
шаг 1: принять у=0 и вычислить функцию f(a1, a2,...an, у).
шаг 2: если f(a1, a2,...an, у)=0, то конец и значение функции
(a1, a2,...an)=у, иначе принять у=у+1 и перейти к шагу 1.
Пример: пусть f(a1, a2,...an, у)=(x1 x2 x3 y) для x1=7, x2 =1, x3 =2.
По данному алгоритму имеем:
f(7, 1, 2, 0) = 7 - 1 - 2 - 0 0;
f(7, 1, 2, 1) = 7 - 1 - 2 - 1 0;
f(7, 1, 2, 2) = 7 - 1 - 2 - 2 0;
f(7, 1, 2, 3) = 7 - 1 - 2 - 3 0;
f(7, 1, 2, 4) = 7 - 1 - 2 - 4 = 0.
Следовательно, (x1, x2,...xn) = (7, 1, 2)=4.