Логическое и функциональное программирование (стр. 9 из 16)

Для доказательства утверждений 1-3 часто бывает удобной индукция с двойным базисом, то есть для случая 1 индукция с базисом U(1)ÙU(2) и индукционным шагом ("n) ((U(n)ÙU(n+1))®U(n+2)). Иногда удобно применять индукцию с тройным, четырехкратным и т.д. базисом.

Для доказательства утверждений вида

(8)

применяется индукция по двум переменным. Однако, утверждение (8) часто удается свести к индукции по одной переменной. Для этого формируем в качестве значения переменной mпроизвольное число и обозначаем его а. Докажем утверждение ("n)U(a,n). Из этого утверждения очевидно следует (8). Но последнее утверждение имеет вид 1 и его можно доказать индукцией. При такой схеме n называется индукционной переменной. Говорят также, что (8) доказывается по nпри фиксированном m.

3.1.1 Практические задания

1.Требуется найти ошибку в доказательстве того, что натуральные числа равны между собой.

Пусть A переменная с областью определения R(N) (множества натуральных чисел), n– переменная с областью определения N (натуральные числа). Обозначим через U(A, n) высказывание: «Если множество Aсодержит n элементов, то в Aнет двух неравных натуральных чисел». Очевидно, утверждение

равносильно утверждению задачи.

Докажем утверждение (1) индукцией по n, причем индукцию будем применять в ее простейшей форме. Базисом индукции является:

("A)U(A,1). (2)

Докажем (2). Возьмем произвольное MÌNи докажем

U(M,1). (3)

Тем самым будет доказано утверждение (2). Но на основе определения U, (3) утверждает: «Если множество M содержит один элемент, то в M нет двух неравных натуральных чисел», что очевидно. Предположим теперь в качестве предположения индукции, что ("A)U(A,n) верно для некоторого натурального k, то есть, что верно

("A)U(A,k) (4)

и докажем, что верно

("A)U(A,k+1) (5)

Тем самым утверждение (1) будет доказано. Для доказательства (5) возьмем произвольное MÍNи докажем

U(M,k+1) (6)

Тем самым (5) будет доказано. На основе определения U, (6) есть утверждение: «Если множество M содержит k+1 элементов, то в Mнет двух неравных натуральных чисел». Чтобы доказать эту импликацию, предположим, что ее посылка верна. Пронумеруем как-нибудь элементы множества M. Пусть, например:

Докажем, что в множестве M нет двух неравных натуральных чисел. Тем самым доказательство будет закончено. Рассмотрим два вспомогательных множества:

Каждое из них получено выбрасыванием из M одного элемента и, следовательно, содержит k элементов. В силу предположения индукции (4) U(K,k) – «Если множество K содержит k элементов, то в K нет двух неравных натуральных чисел». Но множество Kкак раз содержит k элементов, следовательно, в нем нет двух неравных натуральных чисел. Отсюда:

(7)

Используем еще раз предположение индукции (4). Возьмем теперь в качестве значения Aмножество L. Теперь из (4) получим утверждение U(L,k), что означает: «Если множество L содержит k элементов, то в нем нет двух неравных натуральных чисел». Но множество Lсодержит как раз k элементов, следовательно, в нем нет двух неравных натуральных чисел. В частности:

(8)

Из (7) и (8) следует, что в M нет двух неравных натуральных чисел. Доказательство закончено.

3.2Рекурсия

Особое место для систем функционального программирования приобретает рекурсия, поскольку она позволяет учитывать значения функции на предыдущих шагах.

С теоретической точки зрения рекурсивные определения являются теоретической основой всей современной теории вычислимых функций. Рассмотрим два способа вычисления f(1)+f(2)+…+f(n). При итерации сделаем следующим образом. Определим подпрограмму:

SubAdd(S,k,f)

S=S+f

k=k-1

EndSub

Тогда процедуру без использования цикла можно определить следующим образом:

S=0

k=n

I: Add(S,k,f(k))

J: If k¹0 Then Goto I

Здесь подпрограмма Add выполняется n раз последовательно и независимо, причем каждый раз используется только одна команда возврата. Это итерация.

Для рекурсии построим функцию:

If k=0 Then

Sum(f,k)=0

Else

Sum(f,k)=f(k)+Sum(f,k-1)

EndIf

Теперь достаточно просто узнать значение Sum(f,n). Рассмотрим частный случай при n=2. Из определения следует, что необходимо вычислить f(2), а затем обратиться к вычислению Sum(f,1), результат вычисления которого должен быть прибавлен к f(2). Следовательно, сохранить в памяти f(2), установить еще один возврат и обратиться еще один раз к нашему определению. Теперь вычисляем f(1), снова запоминаем результат в памяти, устанавливаем третий возврат и в третий раз обращаемся к определению для вычисления Sum(f,0). Последняя функция равна 0, и мы выходим из определения, используя возврат, установленный перед обращением к определению. Далее прибавляем 0 к f(1), снова выходим из определения, используя второй возврат, прибавляем 0+f(1) к f(2) и производим окончательный выход. Это рекурсия. Определение Sum использовалось не последовательно и независимо, а с вложением последующего использования в предыдущее (что характерно для индуктивного вывода), три команды возврата одновременно хранились в памяти и использовались по принципу «последний пришел – выполнился первый» (LIFO).

Здесь мы рассмотрели пример простой рекурсии. Другим более сложным примером рекурсии является вычисление чисел Фибоначчи. Их можно определить с помощью следующих формул:

Формально число Фибоначчи можно вычислить по следующей явной формуле:

F(n) = [(1 + Ö5)ⁿ – (1 - Ö5)ⁿ] / (2ⁿÖ5).

Эта формула относительно сложна. На самом деле в этом виде задача даже полностью не решена, поскольку алгоритм использования формулы требуется уточнить. Например, осуществлять ли раскрытие внутренних скобок по формуле бинома? Какое значение брать для числа Ö5, то есть сколько брать десятичных знаков? Очевидно, что хотя результат должен быть целым, он не будет таковым. Следовательно, встает вопрос, до какого соседнего целого нужно округлять? Как быть при этом уверенным в результате?

Для этой задачи можно использовать решение с непосредственной подстановкой:

Sub F(n)

If n > 2 Then

F(n) = F(n – 1) + F(n – 2)

Else

F(n) = 1

End If

End Sub

Для приведенных выше функций существуют алгебраические выражения, по которым их можно вычислить. Поэтому, используемые для них рекурсии, будем называть простыми. Однако, существуют функции, которые не являются простыми рекурсиями. Эти функции можно определить рекурсивно, но нельзя записать в терминах алгебраических выражений. Характерным примером является функция Аккермана. Пытаясь определить эту функцию алгебраически, получим только последовательность экспонент, записанных через многоточие. С другой стороны существует простая запись этой функции через рекурсию:

A(m,n)=iif(m=0,n+1,iif(n=0,A(m-1,1),A(m-1,A(m,n-1)))).

Вообще говоря, вычисление таких функций может быть бесконечным (характерная особенность индуктивного вывода). В качестве примера приведем функцию f(m,n), результатом которой является 1 в случае, если в десятичной записи числа p встречается фрагмент из последовательности повторяющихся цифр m длиной n.

Можно показать, что алгоритм вычисления этой функции существует, но неизвестно каков он. Мы можем последовательно вычислять знаки p в надежде, что искомая последовательность обнаружится. Такие функции еще называются общерекурсивными.

В зависимости от того, как оформлен вызов рекурсии, можно выделить еще несколько ее разновидностей. Рекурсия называется параллельной, если она встречается одновременно в нескольких аргументах функции, то есть когда тело определения функции f, содержит вызов некоторой функции g, несколько аргументов которой являются рекурсивным вызовом f:

f(…g(…,f,…,f,…)).

Рекурсия является взаимной между двумя или более функциями, если они вызывают друг друга, то есть когда в определении функции fвызывается функция g, которая в свою очередь содержит вызов функции g:

f((…)(…g…));

g((…)(…f…)).

Рекурсия более высокого порядка является рекурсией, в которой аргументом рекурсивного вызова является рекурсивный вызов: