1610906281-01dbea734f4ec795a743bdccea0de373 (824382), страница 2
Текст из файла (страница 2)
è ýêâèâàëåíòíîñòåé:Ïðåäëîæåíèå 1.10g(i, x̄) ÷àñòè÷íî ðåêóðñèâíàÿ (ïðèìèòèâPníî ðåêóðñèâíàÿ) ôóíêöèÿ, òî òàêîâà è ôóíêöèÿ f (n, x̄) =i=0 g(i, x̄).Äîêàçàòåëüñòâî.ÅñëèÔóíêöèÿfìîæåò áûòü îïðåäåëåíà ñëåäóþùåé ñõå-ìîé ïðèìèòèâíîé ðåêóðñèè:f (0, x̄)= g(0, x̄)f (n + 1, x̄) = f (n, x̄) + g(s(n), x̄).
Âîçìîæíîñòü èñïîëüçîâàíèÿ îãðàíè÷åííûõ êâàíòîðîâ, ïðåäîñòàâëÿåìàÿ ñëåäóþùèì ïðåäëîæåíèåì, ñóùåñòâåííî óïðîñòèò íàì äîêàçàòåëüñòâî ðåêóðñèâíîñòè è ïðèìèòèâíîé ðåêóðñèâíîñòè îïðåäåëÿåìûõ â äàëüíåéøåì ôóíêöèé è ïðåäèêàòîâ.Ïðåäëîæåíèå 1.11ÅñëèP (i, x̄) (ïðèìèòèâíî) ðåêóðñèâíîå îòíî-∃i 6 n P (i, x̄), ∀i 6n è i.øåíèå, òî (ïðèìèòèâíî) ðåêóðñèâíû è îòíîøåíèÿn P (i, x̄), ∃i < n P (i, x̄), ∀i < n P (i, x̄),6çàâèñÿùèå îòÄîêàçàòåëüñòâî.Ëåãêî ïðîâåðÿåòñÿ, ÷òînXχ∃i6n P (i,x̄) (i, x̄) = sg!χP (i, x̄) .i=0Ðåêóðñèâíîñòü (ïðèìèòèâíàÿ ðåêóðñèâíîñòü) îñòàëüíûõ îòíîøåíèéñëåäóåò èç ïðåäûäóùèõ óòâåðæäåíèé è ñëåäóþùèõ î÷åâèäíûõ ýêâèâàëåíòíîñòåé:∀i 6 n P (i, x̄) ⇔ ¬∃i 6 n¬P (i, x̄).∃i < n P (i, x̄) ⇔ ∃i 6 n (P (i, x̄) ∧ i 6= n).∀i < n P (i, x̄) ⇔ ¬∃i < n¬P (i, x̄).
R(y, x̄) µyR(y, x̄) âÅñëèçàïèñüðåêóðñèâíîå îòíîøåíèå, òî ìû áóäåì èñïîëüçîâàòüêà÷åñòâå ñîêðàùåíèÿ äëÿåñòåñòâåííî îçíà÷àåò ìèíèìàëüíîåyµy (|χR (y, x̄) − 1| = 0),R(y, x̄).÷òîòàêîå, ÷òîÑåé÷àñ áóäåò äîêàçàí ðÿä ðåçóëüòàòîâ î ðåêóðñèâíîñòè íåêîòîðûõôóíêöèé è îòíîøåíèé. Íà ñàìî äåëå âñå îíè ÿâëÿþòñÿ òàêæå è ïðèìèòèâíî ðåêóðñèâíûìè, íî íàì ýòî íå ïîíàäîáèòñÿ.Ïðåäëîæåíèå 1.122. Ôóíêöèÿh ixy3. Îòíîøåíèå0= x)Prime (x),i 7→ pi , ãäå pip1 = 3, p2 = 5 è ò.ä.)4.
Ôóíêöèÿx|y( x äåëèò(íåïîëíîå ÷àñòíîå îò äåëåíèÿxîïðåäåëåíèþ1. Îòíîøåíèåxy )íày.ðåêóðñèâíî.Ïðè ýòîì ïîðåêóðñèâíà.âûäåëÿþùåå ïðîñòûå ÷èñëà, ðåêóðñèâíî.åñòü iå ïðîñòîå ÷èñëî, ðåêóðñèâíà. (p0= 2,ex (i, x), ðàâíàÿ ïîêàçàòåëþ, ñ êîòîðûì pi âõîäèò â ðàçëîæåíèå ÷èñëà x íà ïðîñòûå ìíîæèòåëè, ðåêóðñèâíà. (Ìû ïîëàãàåì ïî îïðåäåëåíèþ ex (i, 0) = 0.)5. ÔóíêöèÿÄîêàçàòåëüñòâî.Äîñòàòî÷íî çàìåòèòü, ÷òîx|y ⇔ ∃t 6 y(x × t = y), x= µz(z = x ∨ (z + 1) × y > x),y7Prime (x) ⇔ (x 6= 0) ∧ (x 6= 1) ∧ ∀y 6 x(x|y → (y = 1 ∨ y = x)).Äàëåå,piìîæíî îïðåäåëèòü ñëåäóþùåé ñõåìîé ïðèìèòèâíîé ðåêóð-ñèè:p0 = 0pn+1 = µy(Prime (y) ∧ y > pn ).ex ïî÷òè ãîäèòñÿ. Åãî åäèíñòâåííûéx = 0 çíà÷åíèå ôóíêöèè íåîïðåäåëåíî: ex (i, x) = µy ¬ py+1|x.iÑëåäóþùåå îïðåäåëåíèå äëÿíåäîñòàòîê ñîñòîèò â òîì, ÷òî ïðèÄëÿ óñòðàíåíèÿ ýòîãî íåäîñòàòêà ìû íåìíîãî ïîäïðàâèì ýòî îïðåäåëåíèå:ex (i, x) = µy x = 0 ∧ ¬ py+1|x.iÏðè ýòîì îêàæåòñÿ, ÷òîex (i, 0) = 0.
Íà ïîíàäîáÿòñÿ åù¼ äâà ñïîñîáà ïîñòðîåíèÿ íîâûõ âû÷èñëèìûõ ôóíêöèé èç óæå èìåþùèåñÿ.Ïðåäëîæåíèå 1.13 (Îïðåäåëåíèå ðàçáîðîì ñëó÷àåâ)P1 (x1 , . . . , xn ),Ïóñòü. . . Pm (x1 , . . . , xn ) ðåêóðñèâíûå îòíîøåíèÿ òàêèå, ÷òîx1 , . . . , xn ñóùåñòâóåò ðîâíî îä÷òî Pi (x1 , . . . , xn ). Ïóñòü òàêæåäëÿ ëþáîãî íàáîðà íàòóðàëüíûõ ÷èñåëi ∈ {1, . . . , m} òàêîå,f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn ) ðåêóðñèâíûå ôóíêöèè.öèÿ F (x̄), îïðåäåëåííàÿ, êàêf1 (x̄), åñëè P1 (x̄)f2 (x̄), åñëè P2 (x̄)F (x̄) =···fm (x̄), åñëè Pm (x̄),íî çíà÷åíèåÒîãäà ôóíê-ðåêóðñèâíà.Äîêàçàòåëüñòâî.Ýòî ñëåäóåò èç î÷åâèäíîãî ðàâåíñòâà:F (x̄) = f1 (x̄)χP1 (x̄) + f2 (x̄)χP2 (x̄) + · · · fm (x̄)χPm (x̄).8Ïðåäëîæåíèå 1.14 (Ñîâìåñòíàÿ ðåêóðñèÿ)èf1 (y, x̄)Ïóñòü ôóíêöèèf0 (y, x̄)îïðåäåëåíû òàê íàçûâàåìîé ñõåìîé ñîâìåñòíîé ðåêóðñèè, èñ-õîäÿ èç ðåêóðñèâíûõ ôóíêöèég0 (x̄), g1 (x̄), h0 (z0 , z1 , y, x̄), h1 (z0 , z1 , y, x̄):f0 (0, x̄) = g0 (x̄) f1 (0, x̄) = g1 (x̄) f0 (y + 1, x̄) = h0 (f0 (y, x̄), f1 (y, x̄), y, x̄)f1 (y + 1, x̄) = h1 (f0 (y, x̄), f1 (y, x̄), y, x̄)Òîãäà è ôóíêöèèf0èf1ðåêóðñèâíû.Äîêàçàòåëüñòâî.
Äîêàæåì ðåêóðñèâíîñòü ôóíêöèè f (y, x̄) = hf0 (y, x̄), f1 (y, x̄)i.Îòñþäà ìû íåïîñðåäñòâåííî ïîëó÷èì, ÷òî è ôóíêöèèi = 0, 1fi (y, x̄) = (f (y, x̄))i ,òàêæå ðåêóðñèâíû.Ôóíêöèþf (y, x̄)ìîæíî îïðåäåëèòü, èñõîäÿ èç ðåêóðñèâíûõ ôóíê-öèé, ñëåäóþùåé ïðèìèòèâíî ðåêóðñèâíîé ñõåìîé:f (0, x̄) = hg0 (x̄), g1 (x̄)if (y + 1, x̄) = hh0 ((f (y, x̄))0 , f ((y, x̄))1 , y, x̄), h1 ((f (y, x̄))0 , f ((y, x̄))1 , y, x̄)i ,îòêóäà è ñëåäóåò å¼ ðåêóðñèâíîñòü.Çàìåòèì, ÷òî åñëè èñõîäíûå ôóíêöèè è îòíîøåíèÿ â ïðåäëîæåíèÿõ 1.13 è ïðèìèòèâíî ðåêóðñèâíû, òî è ïîëó÷àþùèåñÿ ôóíêöèè òàêæåáóäóò ïðèìèòèâíî ðåêóðñèâíûìè.Òåïåðü îïèøåì íåêîòîðûå ðåêóðñèâíûå ôóíêöèè è îòíîøåíèÿ, ïðèìåíÿåìûå äëÿ êîäèðîâàíèÿ êîðòåæåé íàòóðàëüíûõ ÷èñåë.Îïðåäåëåíèå 1.15Êîäîì ïîñëåäîâàòåëüíîñòè íàòóðàëüíûõ ÷èñåëx0 , .
. . , xk−1íàçîâåì íàòóðàëüíîå ÷èñëîxk−1px0 0 +1 · . . . · pk−1êîòîðîå áóäåì îáîçíà÷àòühx0 , . . . , xk−1 i.+1,Êîäîì ïóñòîé ïîñëåäîâàòåëü-íîñòè ïî îïðåäåëåíèþ áóäåì ñ÷èòàòü ÷èñëîÎ÷åâèäíî, ÷òî1,ò.å.,hi = 1.hx0 , . . . , xk−1 i ÿâëÿåòñÿ ðåêóðñèâíîé ôóíêöèåé îò x0 , . . . , xk−1 .Êðîìå òîãî, ââèäó îäíîçíà÷íîñòè ðàçëîæåíèÿ íåíóëåâûõ íàòóðàëüíûõ÷èñåë íà ïðîñòûå ìíîæèòåëè, êàæäûé êîä ÿâëÿåòñÿ êîäîì ðîâíî îäíîéïîñëåäîâàòåëüíîñòè ÷èñåë.9Ïðèìåð. h1, 2, 3i = 21+1 · 32+1 · 53+1 = 67500.Î÷åâèäíî, ÷òî äëèíà ïîñëåäîâàòåëüíîñòèåå êîäóx = hx0 , . . . ,xk−1 ix0 , . .
. ,xk−1 âû÷èñëÿåòñÿ ïîñ ïîìîùüþ ðåêóðñèâíîé ôóíêöèèlh (x) = µi (ex (i, x) = 0).x+1k−1x åñòü êîä ïîñëåäîâàòåëüíîñòè x0 , . . . , xk−1 , x = px0 0 +1 px1 1 +1 · · · pk−1òî i-ÿ êîîðäèíàòà xi ýòîé ïîñëåäîâàòåëüíîñòè òîæå âû÷èñëÿåòñÿ ñ ïîìî-Åñëèùüþ ðåêóðñèâíîé ôóíêöèè(x)i = ex (i, x)−̇1.seq (x), ñîñòîÿùåx, ÿâëÿþùèåñÿ íîìåðàìè ïîñëåäîâàòåëüíîñòè âûäåëÿþòñÿ ñëåäóþùèìè ñâîéñòâîì: x 6= 0, èåñëè x äåëèòñÿ íà pi , òî îíî äåëèòñÿ è íà âñå pj , j < i.
Ýòî ìîæåò áûòüÍàì ïîíàäîáèòñÿ òàêæå ðåêóðñèâíîñòü îòíîøåíèÿãî èç âñåõ íîìåðîâ êîðòåæåé. Î÷åâèäíî, ÷òî ÷èñëàçàïèñàíî â âèäå ñëåäóþùåé ýêâèâàëåíòíîñòè:seq (x) ⇔ (x 6= 0) ∧ ∀i∀j < i (pi |x → pj |x).∀i ìîæíî îãðàíè÷èòü ÷èñëîì x.  ñàìîìi < pi 6 . . . · pmi · . . . = x. Òàêèì îáðàçîì,Íà ñàìîì äåëå êâàíòîðåñëèpiäåëèòx 6= 0,òîäåëå,seq (x) ⇔ (x 6= 0) ∧ ∀i 6 x∀j < i (pi |x → pj |x),seq (x).seq (x) è ðåêóðñèâíûå ôóíêöèè hx0 , . .
. , xn−1 i,îòêóäà ñëåäóåò ðåêóðñèâíîñòü îòíîøåíèÿÐåêóðñèâíîå îòíîøåíèån ∈ N, lh (x), (x)i îáðàçóþò ñèñòåìó êîäèðîâàíèÿ êîíå÷íûõ êîðòåæåé íàòóðàëüíûõ ÷èñåë. Íà ñàìîì äåëå ìîæíî äîêàçàòü è ïðèìèòèâíóþ ðåêóð-ñèâíîñòü óïîìÿíóòîãî îòíîøåíèÿ è ôóíêöèé, íî ýòî âûõîäèò çà ïðåäåëûäàííîãî êóðñà.10,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
