X, y и z натуральные числа, такие, что z равно произведению х и y.

Возведение в степень определяется в виде повторяющегося умножения. Программа 3.5 для exp(N,X,Y) задает отношение Х = Y. Эта программа совпадает с программой 3.4 для times (X,Y,Z), если в последней заменить times и plus соответственно на ехр и times. Исходные факты для возведения в степень - Х = 1 для всех положительных Х и 0 = 0 для положительных значений N.

N,X и У-натуральные числа, такие, что У равно X, возведенному в степень N.

exp(s(N),X,Y)  exp(N,X,Z), times(Z,X,Y).

times(X,Y,Z)  См. программу 3-4

Программа 3.5. Возведение в степень как повторяющееся умножение.

Определение функции факториал использует определение умножения. Напомним, что N! = N*(N — 1)* . *2*1. Предикат factorial(N,F ) сопоставляет числу N его факториал F. Аксиоматизация приведена в программе 3.6.

Не все отношения, связанные с натуральными числами, определяются рекурсивно. Отношения можно также определять в духе программ гл. 2. Примером служит программа 3.7, определяющая минимум двух чисел через отношение minimum(N1,N2,Min).

factorial(N.F) 

F равно факториалу числа N.

times(X,Y,Z) Cм. программу 3.4.

Программа 3.6. Вычисление факториала.

minimum (N1, N2, Min) 

Min равен минимуму натуральных чисел N1 и N 2.

minimum(Nl,N2.NI) N1 N2.

minimum(Nl,N2,N2) N2 Nl.

Nl N2См. программу 3.2.

Программа 3.7. Минимум двух чисел.

При построении программы, определяющей остаток от деления целых чисел, возникает любопытное явление различные: математические определения одного и того же понятия приводят к разным логическим программам. Программы 3.8а и 3.8б представляют собой два различных определения отношения mod(X,Y,Z), которое истинно, если Z является вычетом Х по модулю У, т. е. Z является остатком от деления Х на К Программы используют отношение <, определенное в упражнении (1) в конце раздела.

Z остаток от деления Х на Y

mod(X,Y,Z) Z < Y, times(Y,Q,W), plus(W,Z,X).

Программа 3.8а. Нерекурсивное определение остатка.

Z-остаток от деления Х на Y.

mod(X,Y,Z) plus(Xl,Y,X), mod (X1,Y,Z).

Программа 3.8б.Рекурсивное определение остатка.

Программа 3.8а служит примером непосредственного перевода математического определения, являющегося логическим высказыванием, в логическую программу. Программа соответствует экзистенциальному определению целого остатка: “Z равно X mod Y, если Z меньше Y и существует такое число Q, что Х = Q* Y+ Z”.Математические определения в общем случае легко преобразуются в логические программы

Можно рассмотреть связь программы 3.8а с конструктивной математикой. Несмотря на то что определение внешне выглядит как определение существования, оно в то же время конструктивно ввиду конструктивности отношений <, р1us и times.Например, число 0, требуемое в определении, будет явно вычислено с помощью отношения times в любом конкретном вычислении отношения mod.

Программа 3.86 в отличие от программы 3.8а определена рекурсивно. Программа описывает алгоритм нахождения целого остатка, основанный на многократном вычитании. Первое правило утверждает, что ХmodY равно X, если X меньше У Второе правило утверждает, что ХmodY совпадает с Х — Y mod Y. Процесс вычисления при определении остатка состоит в последовательном вычитании Y из X, пока не будет получена величина, меньшая У. Ясно, что это вычисление приводит к правильному значению.

Математическая функция XmodY определена при Y= 0. Ни программа 3.8a ни программа 3.8б не включают цель mod(X,0,Z) в значение программы для любых X, Z. Проверка отношения “ < ” гарантирует это.

Наша вычислительная модель дает возможность сравнить две программы вычисления mod. Выбрав конкретные числа X, У и Z, удовлетворяющие отношению mod, мы можем сравнить деревья вывода, В общем случае дерево вывода программы 3.8б будет меньше дерева вывода программы 3.8а. В этом смысле программа 3.86 “эффективнее”. Отложим более строгое обсуждение эффективности до рассмотрения списков в программах на Прологе.

Другим примером непосредственного перевода математического определения в логическую программу служит программа, определяющая функцию Аккермана. Функция Аккермана - простейший пример рекурсивной функции, не являющейся примитивно рекурсивной. Это функция от двух аргументов, определяемая тремя равенствами:

ackermann(0,N) = N + 1.

ackermann(M,0) = ackermann(M - 1,1).

ackermann(M,N) == ackermann(M - l,ackermann(M,N - 1)).

Программа 3.9 представляет собой запись функционального определения в виде логической программы. Предикат ackermann(M,N,A) означает, что А = acker-mann(M,N). Третье правило содержит два вызова функции Аккермана, один-для вычисления второго аргумента.

ackermanfi(X,Y,A) 

А равно значению функции Аккермана для натуральных чисел Х и Y

Программа 3.9. функция Аккермана.

В функциональном определении эти два вызова выглядят очевиднее. Вообще, функциональная запись более естественна для чисто функциональных определений, как в случае функции Аккермана. Аналогичным примером является программа 3.8а. Запись выражения X=Q*Y+Z, являющегося утверждением о функциях, в виде логической программы выглядит несколько неуклюже.

Заключительным примером данного раздела является алгоритм Евклида нахождения наибольшего общею делителя двух натуральных чисел, записанный в виде логической программы. Подобно программе 3.8б, это - рекурсивная программа, не использующая рекурсивное задание целых чисел. Схема отношения - gcd(X,Y,.Z), а подразумеваемое значение Z является наибольшим общим делителем (н.о.д.) двух натуральных чисел Х и У В данной программе для задания отношения mod используется любая из двух программ-3.8а или 3.8б.

Первое правило программы 3,10 отражает логическую сущность алгоритма Евклида. Н.о.д. чисел Х и У совпадает с н.о.д. У и XmodY. Доказательство

Z является наибольшим общим делителем натуральных чисел Х и Y

Программа 3.10. Алгоритм Евклида.

корректности программы 3.10 зависит от корректности предыдущего математического утверждения о наибольшем общем делителе. Доказательство корректности алгоритма Евклида также основано на этом математическом утверждении

Второе предложение программы 3.10 является исходным фактом Следует указать, что Х должно быть больше 0, чтобы исключить gcd(0,0,0) из значения программы. Н.о.д. пары 0 и 0 не определен.

Упражнения к разд. З.1

1. Изменив программу 3.2, опишите отношения <. использования этих программ.

2. Докажите, что программа 3.2 является корректной и полной аксиоматизацией отношения .

4. Определите истинность предикатов even(X) и add(X) в случаях, когда Х четно и нечетно. (Указание: измените программу 3.1 для отношения natural_number.)

5. Напишите логическую программу, задающую отношение fib(N,F ) для определения N-го числа Фибоначчи F.

6. Предикат times может быть использован для деления без остатка с помощью вопроса вида times (s(s(0)),X,s(s(s(s(0)))))?, сводящегося к нахождению частного от деления 4 на 2. Вопрос times(s(s(0)),X,s(s(s(0))))? для нахождения 3/2 не имеет решения. Во многих при­ложениях требуется, чтобы целочисленное деление давало в качестве 3/2 результат /. Напишите программу целочисленного деления, (Указание: используйте повторяющееся вычитание.)

7. Измените программу 3.10 для нахождения н.о.д. двух целых чисел так, чтобы непосредственно использовать повторяющееся вычитание, а не функцию mod. (Указание: программа многократно вычитает меньшее число из большего, пока два числа не станут равными.)

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.