Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 79
Текст из файла (страница 79)
1) Об зтоы см. с. 380. 25* 1гл. Уп РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 389 г г1 РекуРсиВнАИ АРНФМИТНКА иэ которых затев1, на основании альтернативы а < Ъ '1/ Ь < а, мы получим формулы шах (а, Ь) = а '1/ шах (а, Ь) = Ь и шах (а, Ь) = шах (Ь, а), так что в целом у нас для шах (а, Ь) получается следующая фор- мальная характеризация: а < Ь-+ шах (а, Ь) = Ь, Ь < а-+ шах (а, Ь) = а, а < шах(а, Ь), Ь < гпах (а, Ь), а < 0 81 Ь < с -ю- вгах (а, Ь) -< с. Максимум а, Ь и с определяется равенством шах (а, Ь, с) = шах (шах (а, Ь), 0). Аналогичным образом мы получим представление и для максиму- ма нескольких чисел. Теперь, чтобы для данного терма 1(с) посредством рекурсии определить максимум 1(0), 1(1), ..., 1(п) (с переменным я), мы возьмем в качестве символа выражение шах1 (х), в котором к<» буква х снова будет играть роль связанной переменной и которое будет являться термом с аргументом и.
Соответствующие рекур- сивные равенства будут иметь следующий вид: шах г (х) =1(0), к<0 шах Ф (х) = шах (шах 1 (х), 1(п')). хя» С помощью этих равенств индукцией по л могут быть выведены формулы а <и -э 1(а) < шах 1(л), к<» ~~', (1(х) — ' с) =0-» шах1(л)<с; х<» хя» посредством этих формул значение шах 1 (х) может быть охаракх<» теризовано как наименьшее число, которое не меньше любого из значений 1(0), 1 (1),..., 1(п). Аналогично максимуму 1(0), 1(1),..., 1(я) мы можем рекурсивно определить н минимум этих термов. Исходная функция ш1п (а, Ь) задается посредством явного определения шш(а, Ь) =а — '(а — 'Ь), из которого получается формула а < Ь-к.шгп(а, Ь) =-а. Кроме того, на основании ранее выведенной 1) формулы Ь вЂ” 'аФΠ— ~Ь вЂ” '(Ь вЂ” а) = а (после перестановки а и Ь) мы получаем Ь < а -А- шш (а, Ь) = Ь.
Теперь для любой формулы Я (а) с помощью рекурсивных равенств можно определить такую функцию, что в товг случае, когда хотя бы одно из чисел от 1 до Ь обладает свойством Я (а), она принимает в качестве аначения наименьшее из этих чисел, а в протиином случае — число О. Эта функция от я, которую мы будем обозначать символом Мш Я (х), получается с помощью 0<к»а перевода формулы Я (а) в соответствующее равенство 1(а) = О. Определяющие эту функцию рекурсивные равенства записываются в виде М1п Я(х) =О, 0<к<0 Мш Я(е)= Мш Я(х)+п'.зяп( Мгп Я(х)+1(п')). 0<к<»' 0<к<» 0<хк» Следует обратить внимание на то, что функция М1п Я (х) 0< я» наряду с выделенной в этой рекурсии переменной п может дополнительно содержать какие-нибудь параметры. Характеристическое свойство атой функции формально представляется посредством следующих двух, выводимых с помощью схемы индукции формул: М1п Я (х) =0-к-(0(абка<й-к.
1 Я (а)), 0<к<А 0< а о1 а~<Ь80 Я (а)-ъ Мш Я (х)<а б1 Я ( М1п Я (х)). 0<х<а 0<хи<а Терм й — ' М1п Я (й — 'л) 0<к<А 1! См. с. 375. 391 РЕКУРСИВНАЯ АРИ«змвтИКА сгл, тн с з) РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 390 в том случае, если среди чисел, меньших Й, имеются числа со свойством Я (а), представляет собой наибольшее ие таких чисел, а в противном случае он равен числу Й. Затем, используя рекурсивно определенную ') функцию здп и, мы получим функцию Мгпи (х) = Мш Я (х) знп(с(0)), к<А О<к<А которая в том случае, когда среди чисел от 0 до Й имеются числа со свойством Я (а), равна наименьшему из этих чисел, а в противном случае равна 0: 3.
Делимость; деление с остатком; наименьший отличный от 1 делитель; последовательность простых чисел; рааложение числа на простые множители; нумерация конечных последовательностей чисел; нумерация числовых пар; наибольший общий делитель; наименьшее общее кратное. Полученные в результате этого формально-изобразительные и дедуктивные возможности позволяют наы без особого труда перевести в наш формализм многие понятия и доказательства элементарной арифметики.
Пронллюстрируем зту мысль на нескольких примерах. 11ачнем с понятия делимости. Высказывание «а делится на Ь» или «Ь делит а» выражает ту мысль, что с у щ е с т в у е т ч и ело с, пе превосходящее а и такое, что имеет место равенство а = Ь.с. По виду етого выскааывания мы без труда можем догадаться, что в нашем формализме оно изобразимо посредством равенства с — -- 0 такого, что участвующий в нем терм С построен из рекурсивно определенных функций.
Такого рода терм мы будем кратко называть рекурсивным термам, а равенство 1=0 или же где й и с — рекурсивные термы, мы будем называть рекурсивной формулой. Подобно этому, всякую функцию, введенную рекурсивно или составленную нз такого рода функций, мы также будем казьшать рекурсивной функцией з). ') Повторно зта рекурсия приведена яз с. 3!П. ') В современной терминологии девяти« р е я у р с я з я е с т и чаще всего употребляется з смысле о б щ е р е в у р с и е я е ет я (з сеетзетстевя с ояределевием, прязеденяым е т. 11; см. указавяе б после еглазлеияя т.
П), з те время как термы м формулы, рекурсивные в смысле данного нами здесь еяределеяия, обычно вазызаются п р и м я т и в и е р е к у рс и з я ы м я. Для понятия делимости представление при помощи рекурсивной формулы мы можем получить очень просто, формализовав деление с остатком введением двух рекурсивных функций р (а, Ь) и п (а, Ъ).
Чтобы написать рекурсивные равенства для этих функций, мы сначала введем следующие явные определения: а (а, Ь) =-зип ((а — Ь)+(Ь вЂ” ' а)) и р (а, Ь) = зяп ((а — ' Ь) + (Ь вЂ” ' а)), в которых зап и и зип и — функции, уже ранее введенные нами посредством рекурсивных равенств зяп 0=0, ядп0=-0, здп и' = 0', зяп и' = О. Для функций сс (а, Ь) и р (а, Ь) могут быть выведены следующие формулы: а = Ъ вЂ а (а, Ь) = 0 дс р (а, Ь) =- 0', а ~ Ь -ь а (а, Ь) = 0' дс() (а, Ь) = О. Теперь мы напишем рекурсивные равенства для р (а, Ь) и сс (а, Ь): р (О, Ь) = О, р (п', Ь) = р (и, Ъ)' ° с« (Ь, р (и, Ь)'); и (О, Ь) = О, 11 (и', Ь) = гс (п, Ь) + р (Ь, р (и, Ь)'). Из этих рекурсивных равенств индукцией по а мы выведем фор- мулы а = Ь.п (а, Ь) + р (а, Ь), Ь~О-»р(а, Ь) <Ь, а из них — формулу а = Ь с + г дс г ( Ь -+.
с = я (а, Ъ) 8 г = р (а, Ь). Функция р (а, Ь) изображает о с т а т о к от деления а на Ь. В соответствии со скааанным, делимость числа а на Ь изображается равенством р(а,Ь) =О. Равенство р (а, Й) = р (Ь, Й) 393 2гл. Рп РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 392 РЕКУРСИВНАЯ АРИФМЕТИКА 2 2! выражает тот факт, что а и Ь при делении на й дают один и тот же остаток.
Для этого в теории чисел обычно применяется запись а — Ь (шой й). Таким образом, эту запись мы можем ввести посредством явного определения а — Ь (шой й) р (а, й) р (Ь, й). Понятие делимости ведет нас к понятию просто»о числа. Высказывание «и является простым числом» означает «и отлично от 1 и от О, и для всякого числа а из ряда чисел от 1 до п имеет место альтернатива а =1 ~/а =п ~/р(и,а)~О». Легко видеть, что зто высказывание выразимо посредством некоторой рекурсивной формулы р (и) = О.
Теперь мы покажем, что всякое число, начиная с 2, делится по крайней мере на одно простое число и что для всякого числа п существуют простыв числа, ббльшие п. С этой целью мы сначала сформулируем определение для наименьшего из тех чисел от О до п, которые делят пи отличны от 1, если иФ1, Это понятие тоже может быть изображено посредством некоторой рекурсивной функции Ч(п). Исходя из определения этой функции и пользуясь равенством р (и, п) = О, мы получим формулы Ч(п) ~( п, р (и, Ч (п)) = О.
Кроме того, можно вывести импликацию и ) 1 -1- Р (Ч (и)) = О. Две последние формулы выражают тот факт, что при п ) 1 Ч(п) является простым числом и одновременно делит п. Кроме того, из этих формул мы можем также получить п)1-~-(Р(п) = О ° Ч(п) = и). Далее, введем функцию и! с помощью рекурсивных равенств О! = 1, (ис)! = (и!) и'. Из этих равенств можно вывести формулы п)+1~1, 1 «-а & а ~( и-~- р (и! + 1, а) чь О, которые в сочетании с приведенными для Ч(п) формулами дают формулы Ч (и! + 1) ( и! + 1, п ( Ч (и! + 1) р (Ч (и! + 1)) = О. Эти формулы выражают тот факт, что Ч (и! + 1) есть простое число, большее и и не превосходящее и! + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
