Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 80
Текст из файла (страница 80)
Теперь при помощи некоторого рекурсивного герма «(и) мы можем изобразить также и наименьшее нз тех чисел от 1 до п(+1, которые превосходят и н одновременно являются простыми числ а м и. С помощью этого терка мы определим последовательность простых кисел посредством рекурсии у»=2 В ° =«Ф,). Для п чь О ь«„представляет собой и-е н е ч е т н о е и р ос т о е чи с л о. Можно формально докааать, что д л я к а ждого числа т->2,являющегося простым числом, существует число й из ряда чисел от 1 до т, для которого Для того чтобы получить раелохсение чисел на простпые множителис мы сначала с помоЩью обычной РекУРсии а»=1, Вс с введем св2еиень а». На основе атой рекурсии индукцией по с можно вывести следующие законы, которым подчиняется зта операция: ь с Ьсс а' Ь'=(а Ь)'! затем индукцией по Ь может быть получена формула а > 1 -+ Ь < а».
Затем мы определим функцию т (и, Ь), которая в том случае, когда среди чисел, меньших и, имеется число а, такое что Ьз» является делителем и (при и ~ О это всегда имеет место), дает наибольшее из таких чисел, а в противном случае принимает значение О. Это определение (в соответствии с нашим предшествующим изложением) также может быть формализовано с по- РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 1Гл. чп 394 з 2] РекуРсиВнАя АРиФметикА мощью рекурсивных равенств, и из этих равенств и формулы а >1 — Ь <а' получаются формулы р(и, фв~ ' ~) = — О, и ~ 0-+ р (и, $'А оч ы ) Ф О, которые выражают тот факт, что (для и ~ 0) наибольшая степень числа Леь, делящая и, равна ч (и, Ь).
[Если и не делится на В„ то ч (и, й) = 0.] Возможность разложекия иа простъ1е множители для любого отличного от 0 числа изображается теперь с помощью выводимой формулы т чь 0 - т = Ц у',~ х<т а однозначность разложения изображается формулами ч(ьеь, Й).=а, й ~ [ — ~ ч (1АА, () = О, а-ЬФ 0 — ~ч(а.Ь, й) = ч(а, й)+ч(Ь, и). При выводе указанных формул существеппую роль играет фор- мула р(р) = 0 А р (а Ь, р) = 0 -ъ- р (а, р) = 0 ~/ р (Ъ, р) = О.
Она соответствует теореме о том, что если произведение а Ь делится ка простое число, то по крайкей мере один из сомкожи- телей а и Ь делится ка зто простое число. Для того чтобы вывести зту формулу, пам надо будет формалиаовать содержательное доказательство этой теоремы, которое сводится к доказательству того, что если а яе делится иа простое число р, то каждое число с такое, что а.с делится еа р, само делится на наименьшее иа чисел от 1 до р, обладающих тем же свойством.
Номер наибольшего простого делителя числа и (для и) 1) можно рекурсивио определить как и а и б о л ь ш е е и з ч и- сел й таких, что и (пи ч(и,н))0, если такие числа существуют, и число и в противном с л у ч а е. Если эту функцию от иобозиачить Л (и), то мы получим (и, Л (и)) ~ О, Л (и) ( й -+- ч (и, Ь) = О. Функция ч (и, й) устанавливает взаимно однозначное соответствие между чис ми, ббльшими едини~4ы, и конечными последовательностями чисел с последним членом, отличным от О. С содержатель- иой точки зрения это соответствие состоит в следующем: всякому числу т ) 1 однозначно соответствует последовательность зиачений функции ч (т, Ь) для й =.
О, 1, 2,..., Л (т), последнее из которых ч (т, Л (т)) отлично от О, и, обратно, каждая последовательиость чисел аю..., а ь у которой а ~ ~ О, однозяачно определяет число т=ИйГ хя! такое, что Л (т) = Х и ч (т, Ь) = ае для всех й ( Х. В отношении определения отображающей функции это отображение более элегантно, чем те, с помощью которых обычно в теории мкожеств доказывается счетность множества всех конечных последовательностей целых чисел.
После этого отображения, осуществляющего нумерацию конечпых последовательностей чисел, мы рассмотрим нумерацию числовых пар. Зта задача — устроить с помощью рекурсивной функции нумерацию числовых пар, т. е. взаимно однозначиое соответствие между числовыми парами и числами,— является сравнительно легкой и может быть решена различными способами. Наиболее естественным способом нумерации является тот, который соответствует следующему перечислепию: ит.д В этом перечислеиии номер пары (а, Ь) иаображается следующей явно определенной функцией: о (а, Ь) = (Ь' + 2а) зип (а — ' Ь) + (а' + 2Ь + 1) зйп (а — ' Ь).
а фуикции аг (и) и и (и), обращающие функцию о (а, Ь), определяются следующим образом. Сначала дается рекурсивное определение для функции [~/и), значеиие которой равняется наи- (0,0) (0,1) (1,0) (1,1) (0,2) (2,0) (1,2) (2,1) (2,2) (0,3) (3,0) (1,3) (3,1) (2.,3) (3,2) (3,3) (0,4) (4,0) (1,4) (4,1) (2,4) (4,2) (3,4) РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 397 РЕКУРСИВНАЯ АРИЮМЕТНКА 99В $2) )гл. Рп большему из тех чисел, квадрат которых не превосходит п. Это определение может быть дано с помощью равенств []т О] О, []/и'] [[ти]+[) ((Ц/и]+1)2, и').
Теперь, используя функцию []/и], для ог (и) и аз (п) можно дать следующие явные определения '): о, (п) = [']Уи] р (п — ' [~~ п]2, 2)+ п(и —; []/и]з, 2) ~(р(п —.' []т и]2, 2)), аз(и)=и(и —; [[т'п]2, 2) р(и — ' [[тп]2, 2)+ []) и] р (р (и —: []ти]2, 2)). На основании этих определений могут быть выведены следую- щие формулы: а (аг (п), о, (и)) = и, а, (а (а, Ь)) = а, аз (а (а, Ь)) = Ь. Любая функция нашего формализма, зависящая от двух или большего числа аргументов, с помощью функции о (а, Ь) может быть выражена через функцию, зависящую только от одного аргумента. В самом деле, рассмотрим произвольную функцию ф (а, Ь) от двух аргументов.
Выбрав какой-нибудь функциональный знак с одним аргументом, например ф положим 2р (е) = ф (аг (е), а, (2)). Тогда имеем ф (о (а, Ь)) = ф (а, Ь). Для того чтобы с помощью функции одного аргумента и функции а (а, Ь) выразить функцию ф (а, Ь, с), мы положим )((т) = ф (а, (а, (т)), а, (о, (г)), ас (т)); тогда получится й (а .(а (а, Ь), с)) = ф (а, Ь, с), Тем же самым способом функции а (а, Ь), а, (п), а, (п) можно использовать и для того, чтобы рекурсии с несколькими параметрами свести к рекурсиям только с одним параметпром и к явным определениям. Пусть, например, у нас имеется рекурсия с тремя ') Определеннв фуннцнй с, (н) к о, (и) с помощью одновременной рекурснн см. на с.
403. параметрами ф (а, Ь, с, О) = п(а, Ь, с), ф (а, Ь, с, и') = Ь(а, Ь, с, и, ф (а, Ь, с, п)). Тогда мы можем свести ев к рекурсии с двумя параметрами, введя сначала с помощью рекурсивных равенств ф (а, Ь, О) = с(а, от (Ь), оз (Ь)), ф(а, Ь, и')=Ъ(а,а,(Ь), оз(Ь), и,ф(а, Ь, п)) некоторую новую функцию 2Р (а, Ь, и) и применив затем явное определение ф (а, Ь, с, и) = ф (а, а (Ь, с), и). Действительно, если в рекурсивные равенства для функции ф (а, Ь, и) вместо Ь подставить терм о (Ь, с) и воспользоваться равенствами ог (о (Ь, с)) = Ь, а, (о (Ь, с)) = с, то, опираясь на данное нами определение функции ф, можно будет покааать, что приведенные выше рекурсивные равенства для ф (а, Ь, с, п) являются выводимыми формулами.
Подобным образом можно любую рекурсию с несколькими параметрами заменить рекурсией с числом параметров, меньшим на единицу, и поэтому повторное применение этого приема позволяет свести любую рекурсию с несколькими параметрами к рекурсии только с одним параметром и к явным определениям. Для определения испольауемых при этом функций а (а, Ъ), о, (и) и а, (п) тоже требуются рекурсии не более чем с одним параметром, а именно рекурсии для функций а+ Ь, а.Ь, б (п), а — ' Ь, р (а, Ь), и (а, Ь) и []/и]. [Встречающиеся в определениях функций о (а, Ь), о, (и), а, (и) н [ I и] функции здп п, зуп и и р (а, Ь) могут быть явно определены через а — ' Ь с помощью равенств зуп п = 1 — ' и, зуп п = 1 — ' (1 — ' и), ]1 (а, Ь) = здп ((а — ' Ь) + (Ь вЂ” ' а)).] Другая простая нумерация числовых пар, отличная от той, которую нам дает функция о (а, Ь), может быть произведена при помощи функции т (а, Ь), которая явно определяется равенством т(а, Ь)= ( + + )+а, 399 РекуРсиВКАя АРНФметнкА игл.
Рн $2] РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 398 Сап где функция (2) вводится рекурсивными равенствами (2) =О, (2 ) (2)+ Теперь рассмотрим вкратце теорию наибольисеео общего делиснеля. Понятие наибольшего общего делителя двух чисел а и Ь (ив которых хотя бы одно отлично от 0) прямым путем ведет нас к рекурсивному определению.
Однако для того, чтобы добраться до существенных свойств наибольшего общего делителя по воэможности более просто, целесообразно исходить ив некоторого другого определения. Пусть а Ь ~ О. Среди чисел от 1 до а.Ь мы рассмотрим те числа с, для которых существуют числа Й и с такие, что Й(Ь, с(а и Й а — ' с Ь = с. При условии, что а.Ь ~ О, такое число с имеется всегда; в качестве такого числа можно взять, например„а.
Мы построим рекурсивный терм, который ивображает наименьшее ив таких чисел с, если а Ь ~ О, и число 0 в противном случае. Прибавлением терма внв а Ь + внп Ь а мы можем еще добиться того, чтобы при а = 0 получалось вначение Ь, а при Ь = 0 — значение а. Обовначим полученный таким образом терм Ъ(а, Ь). Основываясь на выводимости формулы Й ( Ь дс с ( а — ~ Й а — ' с Ь = (а — ' с).Ь вЂ” (Ь вЂ” Й) а и используя формулы а — 'с(а, Ь вЂ” 'Й(Ь, мы получим формулу д(а, Ь) = д(Ь, а).
Затем можно получить формулу г .а †' г .Ь = с ~l е Ь вЂ ' г а = с -э с = 0 ~ д(а, Ь) ( с н с ее помощью вывести формулу р(Ь, Ь(а,Ь)) =О, ив которой, ввиду того, что д(а, Ь) = Ь(Ь, а), можно получить и равенство р (а, Ъ(а, Ь)) = О. Кроме того, окавывается выводимой формула р (а, д) = 0 дс р(Ь, с() = 0-» р (д(а, Ь), с() = О, Полученные нами формулы выражают тот факт, что д(а, Ь) является общим делителем а и Ь н что каждый общий делитель а и Ь делит также и д(а, Ь). Тем самым получается, что, ва исключением случая, когда а = 0 и Ь = О, Ь(а, Ь) представляет собой наибольший общий делитель чисел а и Ь, что и выражается формулой а + Ь ~ 0 ос р (а, сС) = 0 х р(Ь, сС) = 0 -ь сС ( д(а, Ъ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
