В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 50
Текст из файла (страница 50)
13.2. Докажите, что функция, полученная суперпозицией примитивно рекурсивных функций, сама примитивно рекурсивна. Р е ш е н и е. В самом деле, компоненты этой функции получены из простейших функций О, Я, .(„" с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Чтобы получить рассматриваемую функцию, нужно добавить еще одну суперпозицию. В итоге эта функция также получается из простейших функций в результате конечного числа применений операторов суперпозиции и примитивной рекурсии, т.е.
примитивно рекурсивна. 13.3. Докажите, что следующие функции примитивно рекурсивны, руководствуясь определением примитивно рекурсивной функции и теоремой, установленной в предыдущей задаче: а) гр(х) = х! (здесь О! = 1); б) чг(х, у) = хг (здесь Ои = 1); (О, если х = О, в) зя(х) = и ' 11, если х > 0; (О, если х>0, г) зя(х) =! ' 11, если х = 0; 9 игошин 241 О , если х = О, д) х — '1= х — 1, если х >0; О , если х < у, е) х-у= х — у,еслих>у. Функция х — у называется усеченной разностью. Решение. а) Во-первых, по определению данной функции О! = 1, т.е. ~р(0) = 1. Это есть первое равенство схемы примитивной рекурсии, где и = 0 и ~ = 1 — постоянная функция.
Далее, по определениюданной функции х!, (х+1)! = 1 2.... х (х+ 1) =х! я я (х+ 1) =~(х) Я(х) = Ю(х) Дх). Это равенство можно представить так: Ях+ 1) = р(Я(х), Ях)), где функция р(и, и) = ии. Оно представляет собой второе равенство схемы примитивной рекурсии, где я(у, ~) = р(Я(у), ~) — суперпозиция функций р и Я, каждая из которых примитивно рекурсивна (первая — по задаче 13.1, г, вторая — простейшая). Значит, функция я примитивно рекурсивна (по задаче 13.2).
Окончательно, данная функция <р получена в результате применения операторов суперпозиции и примитивной рекурсии к примитивно рекурсивным функциям 1, р, Я, а значит, по определению является примитивно рекурсивной функцией. 13.4. Докажите следующие свойства усеченной разности: а) 0 — у=О; б) х —. у = Я(х) — Я(у); в) х+ (у — х) =у+ (х —. у); г) х — (у + я) = (х — у) —. д) (х —.
у) —. ~ = (х — ~) — у. Р е ш е н и е. г) Доказательство проведем индукцией по у. При у = 0 очевидно имеем: х —. (О + я) = х — ~ = (х — 0) — ~. Предположим, что утверждение верно для у: х — (у+ ~) = (х — у) — ~. Докажем, что оно верно для у+ 1: х — ((у + 1) + я) = (х — (у + 1))— () Последнее утверждение, в свою очередь, докажем индукцией по х.
Базисное утверждение этой индукции 0 —. ((у+ 1) + ~) = (Π—. —. (у+1)) —. ~ верно в силу свойства а). Предположим теперь, что утверждение верно для х: х — ((у + 1) + я) = (х —. (у + 1)) — х. Докажем, что оно верно для х+ 1: (х+ 1) —. ((у+ 1) + ~) = ((х+ 1) —. (7+ 1)) — ' ~. Вычисляем: (х+ 1) — ' ((у+ 1) + 2) = (х+ 1) — ' ((у+ ~) + + 1) = Я(х) —.
Х(у + ~) = (по свойству б)) = х — (у + ~) = (по предположению индукции по у) = (х — у) — ~ = (по свойству б)) = = ((х+ 1) — (у+ 1)) — ~. Индукция по х завершена, чем доказано утверждение (*). Последнее, в свою очередь, завершает индукцию по у, что и доказывает исходное утверждение. 242 13.5. Докажите, что следующие функции примитивно рекурсивны, для чего представьте их в виде суперпозиции сложения и усеченной разности: а) ~ х — у ~; б) ппп(х, у); в) шах(х, у). Решение. а) Покажем, что ~х-у(= (х — у)+ (у — х).
В самом деле, еспих> у, то~х — у~=х — у(так какх — у > 0) и (х — у)+ + (у —. х) = (х — у) + 0 =х — у. Если х= у, то обе части рассматриваемого равенства дают О. Наконец, если х < у, то 1 х — у ) = — (х— — у) = у — х и (х — у) + (у — х) = 0 + (у — х) = у — х. Поскольку функция х+ у (задача 13.1, в) и х —. у (задача 13.3, е) примитивно рекурсивны, поэтому и данная функция ~ х — у ~, являющаяся их суперпозицией, также примитивно рекурсивна (задача 13.2). 13.6.
Докажите, что следующие функции примитивно рекурсивны: ~х1 а) д(х, у) = ~ — ~ — целая часть дроби — ~ здесь | — ~ = х; Ы у ~ ~01= б) г(х, у) — остаток от деления у на х (здесь г(х, 0) = х); в) т(х) — число делителей числа х, где т(0) = 0; г) п(х) — сумма делителей числа х, где о(0) = 0; д) т (х) — число простых делителей числа х, где т (0) = 0; е) я(х) — число простых чисел, не превосходящих х. Решение. а) Схема примитивной рекурсии для указанной функции имеет следующий вид: д(х, 0) = О, д(х, у+ 1) = д(х, у) + + зК(~х — (г(х, у) + 1)~). Смысл второго равенства схемы состоит в следующем: второе слагаемое в нем зависит от делимости у + 1 пах.
Если у+ 1 не делится на х, то д(х, у+ 1) на единицу больше, чем д(х, у); если же у + 1 делится на х, то д(х, у+ 1) = д(х, у). Задачу можно решить и по-другому, выразив данную функцию через суперпозицию известных примитивно рекурсивных функций. Согласно определению функции 1х/у1, при у > О число (х/у1 = = и удовлетворяет неравенствам: пу < х < (л + 1)у. Отсюда видно, что и равно числу нулей в последовательности 1у = х, 2у — х, ..., пу — х, ..., ху — х. Поэтому для у > 0 имеем формулу с г — ~ = , 'зй()у-х). У~ Непосредственная проверка показывает, что эта формула верна и при у = О.
Ввиду примитивной рекурсивности всех функций, участвующих в этой суперпозиции, примитивно рекурсивной будет (на основании задачи 13.2) и результирующая функция [х/у). 13.7. Докажите, что примитивно рекурсивны булевы функции: а) отрицание х', б) конъюнкция х у; в) дизъюнкция х ~ у; г) все булевы функции. Р е ш е н и е.
Примитивная рекурсивность отрицания, конъюнкции и дизъюнкции устанавливается посредством их «арифмети- 243 зации» вЂ” выражения через числовые функции, которые на числовом двухэлементном множестве [О, 1) ведут себя как указанные булевы функции. Вот, например, выражение для отрицания: х' = = 1 —. х. (Найдите выражения для конъюнкции и дизъюнкции.) В силу того что всякая булева функция может быть представлена в виде суперпозиции указанных функций, заключаем, что всякая булева функция примитивно рекурсивна. 13.8.
Ограниченный и-оператор задает примитивно рекурсивные функции. Р еще н ие. Для краткости записей будем считать, что и = 1. Пусть Дх) = р~ < а[я(х, я) = О]. Покажем, что функция у(х) примитивно рекурсивна. Рассмотрим конечную совокупность последовательных произведений значений функции я(х, ~) (все эти значения определены): я(х, 0), я(х, 0)я(х, 1), я(х, 0)я(х, 1) я(х, 2), ..., я(х, 0)8(х, 1) ... 8(х, й), ..., я(х, 0)8(х, 1) ...
«(х, а). Если я(х, /с) = 0 — первое нулевое значение функции я(х, я) в последовательности я(х, 0), я(х, 1), ..., я(х, а), то по определению ограниченного р-оператора Г'(х) = )с Это число нетрудно выразить через известные примитивно рекурсивные функции. В рассмотренной совокупности произведений первые х членов не равны О, а остальные равны О. По определению функции з8() (см. задачу 13.3, в) для каждого ненулевого произведения значение этой функции на нем равно 1, а для каждого нулевого равно О. Поэтому, чтобы найти число ненулевых произведений и тем самым найти число 1г, являющееся значением функции г(х), нужно сложить значения функции з8() на всех произведениях рассмотренной совокупности: а / г(х) = lс = рг. < а[8(х, я) = О] = ~~' з8(П8(х О). ла 13.9.
Используя ограниченный р-оператор, докажите, что следующие функции примитивно рекурсивны: а) р(п) = р„— и-е простое число (р(0) = 2, р(1) = 3, р(2) = 5, р(3) = 7,...); б) 1(п) — номер наибольшего простого делителя числа л в его каноническом разложении на простые множители; в) ехр(х, у) — показатель степени х-го простого числа р(х) в каноническом разложении на простые множители числа у, где ехр(х, 0) = 0; г) НОК(х, у) — наименьшее общее кратное чисел х и у, где НОК(х, 0) = НОК(0, у) = 0; д) НОД(х, у) — наибольший общий делитель чисел х и у, где НОД(0, 0) = 0; е) [ Гх] — целая часть числа /х; ж) [(Гх] — целая часть числа 4х, где ~ОГх = х; 244 з) [х Г21 — целая часть числа х Г2. Решение.
а) Чтобы применить ограниченный р-оператор, нужно доказать, что значения функции р(л) ограничены: р(л) < < а(п). Покажем, что Р„= р(л) < 2'. Доказательство проведем индукцией по л. Для малых и имеем: 2 = Р» < 2' = 2; 3 = Р, < 2' = = 4. Предположим, что так продолжается до л включительно: Р„= = р(п) ~ 2' . Покажем, что тогда неравенство будет выполняться и для и + 1: Р„,, < 2м' .
Для этого перемножим почленно все л ~- 1 неравенства, выполняющиеся по предположению индукции (проделаем вычисления получившейся правой части): г'<г"'-о Р,Р, Р <22'22' 22" 220-в.,:а" 2 21 2»"'ч (,) Оценим величину разности: 2 2 так как показатель степени 2"" — 1 > 0 при л > О. Заменив в левой части этого неравенства вычитаемое 2'" ' на число Р,Р, ... Р„, которое не больше (согласно неравенству (»)), чем это вычитаемое, получим 2' — Р»Рь - Рл > 1, т е Р»Рь..Рп + 1 < 2'"' (~*) Разложим число в левой части неравенства (**) на простые множители: ,, оч 2'"' > Р»Рп Рв+1= Р»» " Ра"+и > Р» > Р-~ (»»») Последнее неравенство р» > р„„, обусловлено тем, что число Р»Р,...Р„+ 1, очевидно, не делится ни на одно простое число р», Рь ..., Р„и потомУ его наименьший (пеРвый) пРостой делитель Р„ не может быть меньше (л + 1)-го простого числа Р»„ь Итак, шаг индукции доказан.
Ограниченность функции Р„= р(л) позволяет получить (вычислить) ее с помощью ограниченного 1»-оператора: п-е простое число — это такое простое число, меньше которого имеется ровно и простых чисел, т.е. это наименьшее из чисел х„которые не превосходят и + 1 простых чисел (включая само число х), т.е. для которых х(х) = и + 1 (см. задачу 6, е) или для которых [х(х) — (и + + 1)~ = О. При этом, согласно предыдущему доказательству, не нужно перебирать все натуральные числа, чтобы найти такое ~ оно находится среди натуральных чисел, меньших числа 2»". Итак, окончательно получаем: р(л) = 1»Х < 2'"[[ х(Х) — (и + 1)! = 0[. Следовательно, на основании предыдущей задачи функция р(и) примитивно рекурсивна. 13.10.
Докажите, что все примитивно рекурсивные функции всюду определены. Примитивно рекурсивные предикаты. Пусть п-местный предикат Р(х„..., х„) задан над множеством Мо ..., М„. Характеристической функцией этого предиката называют следующую функцию, заданную на тех же множествах и принимающую значения в двух- элементном множестве (О, 1): (О, если высказывание Р(х„..., х„) ложно, те(хп ..., х„) = 11, если высказывание Р(х„..., х„) истинно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
