- •1. Исчисление высказываний
- •1.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2. Метод резолюций в исчислении высказываний
- •1.3. Метод резолюций для хорновских дизъюнктов
- •Задачи и упражнения
- •2. Логика и исчисление предикатов
- •2.1. Логика предикатов
- •2.2. Алгебра предикатов
- •2.2.1. Логические операции
- •2.2.2. Правила записи сложных формул
- •2.2.3. Законы алгебры предикатов
- •2.2.4. Предваренная нормальная форма
- •2.2.4.1. Алгоритм приведения формулы к виду пнф
- •2.2.5. Сколемовская стандартная форма
- •2.2.5.1. Алгоритм Сколема
- •2.3. Исчисление предикатов
- •2.3.1. Интерпретация формул
- •2.3.2. Правила вывода
- •2.3.3. Метод дедуктивного вывода
- •2.3.4. Метод резолюций в исчислении предикатов
- •2.4. Проблемы в исчислении предикатов
- •2.5. Логическое программирование
- •Задачи и упражнения
- •3. Элементы теории алгоритмов
- •3.1. Рекурсивные функции
- •3.1.1. Базовые функции
- •3.1.2. Элементарные операции
- •3.2. Машина Тьюринга
- •3.2.1. Описание машины Тьюринга
- •3.2.2. Примеры машин Тьюринга
- •3.2.3. Условные обозначения и схемные соединения машин Тьюринга
- •3.2.4. Рекурсивные функции и вычисления на машинах Тьюринга
- •3.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
3.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 = (z1; 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(х). Следовательно, для х = 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 не только через значения функций g и h, но и через значения функций f во всех предшествующих точках аргумента.
Схема примитивной рекурсии содержит главный дополнительный аргумент – у, который войдет в значение определяемой функции, и один вспомогательный аргумент – 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; x2; ... xn при выполнении операции рекурсии играют роль фиксированных параметров, т.е.
x1 = ai; x2 = a2; ... xn = аn.
Итак, значением искомой функции f для нулевого значения главного дополнительного аргумента следует считать значение исходной функции g, значением функции f для каждого последующего значения главного аргумента (у+1) следует считать значения функции h при предыдущих значениях главного аргумента у и при значении вспомогательного аргумента, совпадающим с предыдущим значением искомой функции.
Пример. Пусть g (х) = Ci (х) = 0; h (х; у; f (х; у)) = J3,2 = y. Тогда по схеме примитивной рекурсии имеем:
f (х, 0) = g (х) = 0;
f (х; у+1 ) = h (х; у; f (х; у)) = у;
Так как функции g и h не содержат в качестве аргумента независимую переменную х, то имеем:
f(0) = 0;
f(1) = 0;
f(2) = 1;
f(3) = 2;
..............
f (i) = (i - 1 ); если i = у, то f (у) = (у – 1 ) = (у).
Пусть у = 6, тогда f (6) = 6 – 1 = 5.
Так как рекурсивная функция принимает значения на множестве целых положительных чисел, то функция предшествования реализует усеченное вычитание, формула которого имеет вид:
Таким образом, в дополнение функции следования получена функция предшествования. Для получения функции предшествования использованы две базовые функции (константа и тождества) и операция примитивной рекурсии: (у – 1) =R (0; у) = -1 (у).
Пример. Пусть g(x)=J1,1=x;
h (х; у; f (х; у)) = (J3,3) = f (x; у) + 1.
По схеме примитивной рекурсии имеем:
f (х; 0) = g(х) = х;
f (х; 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.
Таким образом, для получения значений функции сложения двух независимых переменных использованы две базовые функции (тождества и следования) и операция примитивной рекурсии:
(х + у) = R (х; (f (х; у) + 1)) = f+ (х; у).
Пример. Пусть g(x) = I1,1 = x;
h (х; у; f (х; у)) = -1 (J3,3) = f (x; у) – 1.
По схеме примитивной рекурсии имеем:
f (х; 0) = g(х) = х;
f (х; 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.
Формула усеченного вычитания имеет следующие значения:
Таким образом, для получения значений функции вычитания двух независимых переменных использованы базовая функция тождества, примитивно рекурсивная функция предшествования и операция примитивной рекурсии:
(х – у) = R (х; (-1 (f(х; у))) = f+ (х; у).
Пример. Пусть g(x) = С1 = 0;
h (х; у; f (х; у)) = f+ (J3,1 ; J3,3 ) = x + f (x; у).
По схеме примитивной рекурсии имеем:
f (х; 0) = g(х) = 0;
f (х; 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) = 3x;
..................................................................
f (x; i) = h (x; (i – 1); f (x; (i –1))) = (x + (i – 1)) – x = i – x.
Если i = у, то f (x; у) = x . у.
Пусть х = 3, y = 4, тогда f (3; 4) = 3 . 4 = 12.
Таким образом, для получения значений функции умножения двух независимых переменных использованы базовая функция константы и примитивно рекурсивная функция сложения:
x . у = R (0; f+ (х; f (x; у))) = f+ (х; у).
Пример. Пусть g(x) = С1 = 1;
h (х; у; f (х; у)) = f* (J3,1 ; J3,3 ) = x . f (x; у).
По схеме примитивной рекурсии имеем:
f (х; 0) = g (х) = 1;
f (х; 1) = h (х; 0; f (х; 0)) = х . 1= х;
f(x; 2) = h (x; 1; f (х; l)) x . x = x2;
f (õ; 3) = h (õ; 2; f (õ; 2)) = х . x2 = x3 ;
..........................................................
f (x; i) = h (x; (i - 1); f (x; (i - 1))) = x . x(i - 1) = xi.
Если i = у, то f (x; y) = xy.
Пусть x = 3, у = 3, тогда f (3; 3) = 33 = 27.
Таким образом, для получения значений функции возведения в степень использованы базовая функция константы и примитивно рекурсивная функция умножения:
хy = R (1; f* (x; f (x; y)))=fexp(x; y).
Из приведенных примеров легко можно получить примитивно рекурсивные функции:
a) min (х; у) = х – (х – у);
б) mах (х; у) = у – (х – у);
в) | х – у| = (х – у) + (у – х);
г) х = 1 – х;
д) х v у = mах (х; у);
е) х . у = 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.
Использование оператора y-удобное средство для поиска обратных рекурсивных функций.
Как правило, область определения функции (x1; x2; ... xn) меньше области определения функции f (x1; x2; ... xn; у), что позволяет утверждать о частичной рекурсивности функции (x1; x2; ... xn).
Пример. Пусть 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) определена только для значения х = 1, 4, 9, 16... и имеет значение, соответственно, 1, 2, 3, 4, ... Таким образом, функция (x) также является частично рекурсивной.
Если дан алгоритм вычисления функции 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, xз = 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.
Операция итерации. Повторное выполнение какого-либо процесса до тех пор, пока не будет удовлетворено заданное условие, называют итерацией. При этом выполнение процесса производится каждый раз полностью. Однократное выполнение процесса называют шагом итерации.