С.С. Марченков - Избранные главы дискретной математики (1124120), страница 22
Текст из файла (страница 22)
Ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè 4 ìû îïðåäåëèëè êëàññ F÷ð ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Âòåîðèè ðåêóðñèâíûõ ôóíêöèé âàæíóþ ðîëü èãðàåò ñóùåñòâåííî áîëååïðîñòàÿ ÷àñòü êëàññà F÷ð êëàññ FïðÏðèìèòèâíî ðåêóðñèâíûå ôóíêöèè ýòî ôóíêöèè, êîòîðûå ìîæíîïîëó÷èòü èç èñõîäíûõ ôóíêöèé (4.7) ñ ïîìîùüþ îïåðàöèé ñóïåðïîçèöèè(4.3) è ïðèìèòèâíîé ðåêóðñèè (4.5).Èç îïðåäåëåíèÿ ñðàçó ñëåäóåò, ÷òî âñÿêàÿ ïðèìèòèâíî ðåêóðñèâíàÿôóíêöèÿ âñþäó îïðåäåëåíà. Ðàññìîòðèì íåêîòîðûå ïðîñòûå ïðèìåðûïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé. Ôóíêöèÿ-êîíñòàíòà 0 ÿâëÿåòñÿ èñõîäíîé ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèåé. Ñ ïîìîùüþ ñóïåðïîçèöèèôóíêöèè 0 è èñõîäíîé ôóíêöèè x + 1 ìîæíî ïîëó÷èòü ëþáóþ äðóãóþôóíêöèþ-êîíñòàíòó.
Îòìåòèì, ÷òî ôóíêöèè-êîíñòàíòû ìîæíî ñ÷èòàòüçàâèñÿùèìè îò ïðîèçâîëüíîãî ÷èñëà ïåðåìåííûõ äîñòàòî÷íî âîñïîëüçîâàòüñÿ èñõîäíûìè ñåëåêòîðíûìè ôóíêöèÿìè Iin (x1 , . . . , xn ).Ïóñòü äàëåå ôóíêöèÿ sum(x1 , x2 ) îïðåäåëÿåòñÿ ñëåäóþùåé ïðèìèòèâíîé ðåêóðñèåé:ïðèìèòèâíî ðåêóðñèâíûõ ôóíê-öèé.sum(x1 , 0) = x1 ,sum(x1 , x2 + 1) = sum(x1 , x2 ) + 1(4.17)(â ïåðâîì ðàâåíñòâå ìû ïîñòàâèëè ïåðåìåííóþ x1 âìåñòî ôóíêöèè I11 (x1 ),à âî âòîðîì ïðèâåëè òîëüêî ñóùåñòâåííóþ ÷àñòü îïðåäåëåíèÿ, îïóñòèâ òå âõîæäåíèÿ ïåðåìåííûõ x1 , x2 , êîòîðûå ìîæíî ââåñòè ñ ïîìîùüþôóíêöèè I33 ). Íåòðóäíî ïîíÿòü, ÷òî ïðèìèòèâíàÿ ðåêóðñèÿ (4.17) îïðåäåëÿåò ôóíêöèþ x1 + x2 .Ïîäîáíûì îáðàçîì, ïðèìèòèâíûå ðåêóðñèèprod(x1 , 0) = 0,prod(x1 , x2 + 1) = prod(x1 , x2 ) + x1 ,pow(x1 , 0) = 1,pow(x1 , x2 + 1) = pow(x1 , x2 ) · x1îïðåäåëÿþò ôóíêöèè x1 · x2 è xx1 2 , èñïîëüçóÿ â êà÷åñòâå óæå èçâåñòíûõôóíêöèè x1 + x2 è x1 · x2 (÷òîáû íå äåëàòü èñêëþ÷åíèé â îïðåäåëåíèèôóíêöèè xx1 2 , ìû ïðèíÿëè 00 = 1).Íàì áû õîòåëîñü äîêàçàòü ïðèìèòèâíóþ ðåêóðñèâíîñòü ôóíêöèè x−y .Îäíàêî ýòî ñäåëàòü íåâîçìîæíî, ïîñêîëüêó ôóíêöèÿ x − y ïðèíèìàåò102îòðèöàòåëüíûå çíà÷åíèÿ.
Âìåñòî ôóíêöèè x−y ìû ðàññìîòðèì áëèçêóþ· y , êîòîðóþ îïðåäåëèì ñîîòíîøåíèÿìèê íåé ôóíêöèþ x −x −· y =x − y, åñëè x > y,0â ïðîòèâíîì ñëó÷àå.· y ïðîâåäåìÄîêàçàòåëüñòâî ïðèìèòèâíîé ðåêóðñèâíîñòè ôóíêöèè x −â äâà ýòàïà. Ñíà÷àëà óñòàíîâèì ïðèìèòèâíóþ ðåêóðñèâíîñòü áîëåå ïðî· 1:ñòîé ôóíêöèè x −0 −· 1 = 0,(x + 1) −· 1 = x.· 1, ïîëó÷èì ôóíêöèþ x −· y:Çàòåì, èñïîëüçóÿ ôóíêöèþ x −x −· 0 = x,x −· (y + 1) = (x −· y) −· 1.· y ìîæíî îïðåäåëèòü èçâåñòíûåÑóïåðïîçèöèÿìè ôóíêöèé x + y, x −àðèôìåòè÷åñêèå ôóíêöèè:min(x, y) = x −· (x ÷ y),max(x, y) = (x + y) −· min(x, y),|x − y| = (x −· y) + (y −· x).Íàïîìíèì åùå î äâóõ âàæíûõ ôóíêöèÿõ sg x è sg x, êîòîðûå ÷àñòîâñòðå÷àþòñÿ â òåîðèè ðåêóðñèâíûõ ôóíêöèé:sg x =0, åñëè x = 0,1, åñëè x 6= 0,sg x =1, åñëè x = 0,0, åñëè x 6= 0.Ïðèìèòèâíàÿ ðåêóðñèâíîñòü ôóíêöèé sg x, sg x ñëåäóåò èç ðàâåíñòâ· x,sg x = 1 −sg x = sg sg x.Íà îñíîâå èìåþùèõñÿ ïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé ìîæíî îïðåäåëèòü äðóãèå èíòåðåñíûå ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè.
Òàê, ñóïåðïîçèöèÿìè ôóíêöèé (4.7) è ôóíêöèé x + y, x · y ìîæíî ïîëó÷èòü ëþáîé ïîëèíîì ñ öåëûìè íåîòðèöàòåëüíûìè êîýôôèöèåíòàìè. Åùå áîëåå·øèðîêèå âîçìîæíîñòè îòêðûâàåò ïðèìåíåíèå ôóíêöèé x −y,sg x, sg x.Ïðîäåìîíñòðèðóåì îäíó èç ýòèõ âîçìîæíîñòåé.Ïóñòü a ∈ N . Ïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ sg |x − a| ïðèíèìàåò çíà÷åíèå 1 ïðè x = a è çíà÷åíèå 0 â îñòàëüíûõ ñëó÷àÿõ.
Åñëè103a1 , . . . , am , b1 , . . . , bm ÷èñëà èç N , ïðè÷åì ÷èñëà a1 , . . . , am ïîïàðíî ðàçëè÷íû, òî ôóíêöèÿb1 · sg |x − a1 | + b2 · sg |x − a2 | + . . . + bm · sg |x − am |(4.18)ïðè x = a1 , . . . , am ïðèíèìàåò ñîîòâåòñòâåííî çíà÷åíèÿ b1 , . . . , bm è ðàâíà0 â îñòàëüíûõ ñëó÷àÿõ.Èäåÿ ïîñòðîåíèÿ ôóíêöèè (4.18) ïîçâîëÿåò ¾èñïðàâëÿòü¿ çíà÷åíèÿïðèìèòèâíî ðåêóðñèâíîé ôóíêöèè â êîíå÷íîì ÷èñëå òî÷åê. Èìåííî, ðàññìîòðèì, íàïðèìåð, ïðèìèòèâíî ðåêóðñèâíóþ ôóíêöèþ f (x) îäíîé ïåðåìåííîé è ïðåäïîëîæèì, ÷òî íàì íåîáõîäèìî çàìåíèòü çíà÷åíèÿ ôóíêöèèf (x) â òî÷êàõ a1 , . . . , am çíà÷åíèÿìè b1 , .
. . , bm . Îáîçíà÷èì òàê ¾èñïðàâëåííóþ¿ ôóíêöèþ f (x) ÷åðåç f 0 (x). Òîãäàf 0 (x) = b1 · sg |x − a1 | + . . . + bm · sg |x − am |++f (x) · sg |x − a1 | · . . . · sg |x − am |. ïðåäûäóùèõ ïàðàãðàôàõ ïðè çàäàíèè ôóíêöèé ìû ïîëüçîâàëèñüîòíîøåíèÿìè (ïðåäèêàòàìè) âèäàx = y,x 6= y,x < y,x 6 y.(4.19) ïðèíöèïå ìîæíî èñïîëüçîâàòü è áîëåå ñëîæíûå îòíîøåíèÿ. Ìû õîòèì ðàññìàòðèâàòü ïðîèçâîëüíûå îòíîøåíèÿ íà ìíîæåñòâå N . ×òîáûèìåòü âîçìîæíîñòü ïðèìåíÿòü îòíîøåíèÿ ïðè çàäàíèè ôóíêöèé, óäîáíî ââåñòè õàðàêòåðèñòè÷åñêèå ôóíêöèè îòíîøåíèé.
Èìåííî, ôóíêöèþf (x1 , . . . , xn ), ïðèíèìàþùóþ ëèøü çíà÷åíèÿ 0 è 1, íàçûâàåìρ(x1 , . . . , xn ), åñëè äëÿ ëþáûõ x1 , . . . , xnçíà÷åíèå f (x1 , . . . , xn ) ðàâíî 1 â òîì è òîëüêî òîì ñëó÷àå, êîãäà èñòèííîçíà÷åíèå ρ(x1 , . . . , xn ). Îòíîøåíèå ρ ñ÷èòàåì ïðèìèòèâíî ðåêóðñèâíûì,åñëè ïðèìèòèâíî ðåêóðñèâíà åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ.Äëÿ ÷èñëîâûõ îòíîøåíèé (4.19) õàðàêòåðèñòè÷åñêèìè ôóíêöèÿìè ñëóæàò ñîîòâåòñòâåííî ôóíêöèèõàðàêòåðè-ñòè÷åñêîé ôóíêöèåé îòíîøåíèÿsg |x − y|,sg |x − y|,· x),sg (y −· y).sg (x −Ïîýòîìó îòíîøåíèÿ (4.19) ïðèìèòèâíî ðåêóðñèâíû.Êàê ìû ìîãëè óáåäèòüñÿ, ê îòíîøåíèÿì ÷àñòî ïðèáåãàþò, êîãäà íåîáõîäèìî îïðåäåëèòü ôóíêöèþ ñ ïîìîùüþ òàê íàçûâàåìîãî ðàçáîðà ñëó÷àåâ. Ñåé÷àñ ìû ðàññìîòðèì ïîäîáíóþ ñèòóàöèþ â îáùåì âèäå.104Óòâåðæäåíèå 4.2.Ïóñòü ôóíêöèÿ f îïðåäåëÿåòñÿ ñõåìîéf1 (x1 , .
. . , xn ),åñëè ρ1 (x1 , . . . , xn ) èñòèííî,...............f (x1 , . . . , xn ) =f (x , . . . , xn ), åñëè ρm (x1 , . . . , xn ) èñòèííî, m 1fm+1 (x1 , . . . , xn ) â îñòàëüíûõ ñëó÷àÿõ,ãäå îòíîøåíèÿ ρ1, . . . , ρm è ôóíêöèè f1, . . . , fm+1 ïðèìèòèâíî ðåêóðñèâíû, ïðè÷åì íèêàêèå äâà îòíîøåíèÿ íå ÿâëÿþòñÿ îäíîâðåìåííî èñòèííûìè. Òîãäà ôóíêöèÿ f òàêæå ïðèìèòèâíî ðåêóðñèâíà.Ïóñòü g1 , . .
. , gm õàðàêòåðèñòè÷åñêèå ôóíêöèèîòíîøåíèé ρ1 , . . . , ρm . Òîãäà ôóíêöèþ f ìîæíî îïðåäåëèòü ðàâåíñòâîìÄîêàçàòåëüñòâî.f (x1 , . . . , xn ) == f1 (x1 , . . . , xn ) · g1 (x1 , . . . , xn ) + . . . + fm (x1 , . . . , xn ) · gm (x1 , . . . , xm )++fm+1 (x1 , . . . , xn ) · sg (g1 (x1 , . . . , xn ) + . . . + gm (x1 , . . . , xn )).Èç íåãî ñëåäóåò, ÷òî ôóíêöèÿ f ïðèìèòèâíî ðåêóðñèâíà. Óòâåðæäåíèåäîêàçàíî. òåîðèè ðåêóðñèâíûõ ôóíêöèé äîâîëüíî ÷àñòî èñïîëüçóþòñÿ îïåðàöèèîãðàíè÷åííîãî ñóììèðîâàíèÿXf (x1 , .
. . , xn−1 , i)i6xnèîãðàíè÷åííîãî ìóëüòèïëèöèðîâàíèÿYf (x1 , . . . , xn−1 , i).i6xnÏîêàæåì, ÷òî â ñëó÷àå ïðèìèòèâíîé ðåêóðñèâíîñòè ôóíêöèè f ôóíêöèÿ g(x1 , . . . , xn−1 , xn ), ïîëó÷åííàÿ èç ôóíêöèè f ñ ïîìîùüþ îïåðàöèèîãðàíè÷åííîãî ñóììèðîâàíèÿ èëè îãðàíè÷åííîãî ìóëüòèïëèöèðîâàíèÿ,òàêæå ÿâëÿåòñÿ ïðèìèòèâíî ðåêóðñèâíîé. Äëÿ îïåðàöèè îãðàíè÷åííîãîñóììèðîâàíèÿ ýòî ñëåäóåò èç ñîîòíîøåíèé ïðèìèòèâíîé ðåêóðñèè äëÿôóíêöèè g :g(x1 , . .
. , xn−1 , 0) = f (x1 , . . . , xn−1 , 0),g(x1 , . . . , xn−1 , xn + 1) = g(x1 , . . . , xn−1 , xn ) + f (x1 , . . . , xn−1 , xn + 1).Àíàëîãè÷íûå ïîñòðîåíèÿ ïðèìåíèìû â ñëó÷àå îãðàíè÷åííîãî ìóëüòèïëèöèðîâàíèÿ.105Ïðèìåíåíèå îïåðàöèé îãðàíè÷åííîãî ñóììèðîâàíèÿ è îãðàíè÷åííîãîìóëüòèïëèöèðîâàíèÿ ïîçâîëÿåò â ðÿäå ñëó÷àåâ çíà÷èòåëüíî óïðîñòèòüäîêàçàòåëüñòâî ïðèìèòèâíîé ðåêóðñèâíîñòè íåêîòîðûõ ôóíêöèé. Ïðîäåìîíñòðèðóåì ýòî íà ïðèìåðàõ.Ïóñòü [x/y] åñòü öåëàÿ ÷àñòü îò äåëåíèÿ x íà y , åñëè y 6= 0, è åñòü 0,åñëè y = 0 (âûáîð ÷èñëà 0 â êà÷åñòâå çíà÷åíèÿ ôóíêöèè [x/0] ñóùåñòâåííîé ðîëè íå èãðàåò, ñ ðàâíûì óñïåõîì ìîæíî áûëî áû âçÿòü ëþáîå äðóãîå ÷èñëî). Ìû õîòèì óñòàíîâèòü ïðèìèòèâíóþ ðåêóðñèâíîñòü ôóíêöèè[x/y]. Çàìåòèì, ÷òî ïðè y 6= 0 âåëè÷èíà [x/y] åñòü òàêîå (åäèíñòâåííîå)÷èñëî i, ÷òî iy 6 x è (i + 1)y > x.
Îáîçíà÷èì ÷åðåç g1 (x, y, i) è g2 (x, y, i)õàðàêòåðèñòè÷åñêèå ôóíêöèè îòíîøåíèé iy 6 x è (i + 1)y > x (îíè, î÷åâèäíî, ïðèìèòèâíî ðåêóðñèâíû). Ïîñêîëüêó [x/y] 6 x, ïîëó÷àåì òåïåðü[x/y] =Xi · g1 (x, y, i) · g2 (x, y, i).i6xÑ ïîìîùüþ ôóíêöèè [x/y] ëåãêî îïðåäåëèòü ôóíêöèþ rm(x, y), ðàâíóþ îñòàòêó îò äåëåíèÿ x íà y , åñëè y 6= 0, è ðàâíóþ x, åñëè y = 0 (âíîâüçíà÷åíèå x ïðè y = 0 âûáèðàåì ëèøü äëÿ òîãî, ÷òîáû ïîëó÷èòü áîëååïðîñòóþ ôîðìóëó äëÿ âûðàæåíèÿ ôóíêöèè rm(x, y)).
 ñàìîì äåëå, èìååì· [x/y] · y.rm(x, y) = x −Íàéäåííûé âûøå ïðèåì ïðèìåíèì äëÿ äîêàçàòåëüñòâà ïðèìèòèâíîé√ðåêóðñèâíîñòè åùå äâóõ ôóíêöèé [ x] è [log2 x] (çäåñü âíîâü äëÿ ïðîñòîòû ïîëîæèì log2 0 = 0). Åñëè g1 (x, i), g2 (x, i) õàðàêòåðèñòè÷åñêèåôóíêöèè ïðèìèòèâíî ðåêóðñèâíûõ îòíîøåíèé i2 6 x è (i + 1)2 > x, òîX√[ x] =i · g1 (x, i) · g2 (x, i).i6xÀíàëîãè÷íî, åñëè h1 (x, i), h2 (x, i) õàðàêòåðèñòè÷åñêèå ôóíêöèè ïðèìèòèâíî ðåêóðñèâíûõ îòíîøåíèé 2i 6 x è 2i+1 > x, òî[log2 x] =Xi · h1 (x, i) · h2 (x, i).i6xÎáîçíà÷èì ÷åðåç x|y îòíîøåíèå ¾x äåëèò íàöåëî y ¿ (îòíîøåíèå 0|yñ÷èòàåì èñòèííûì òîëüêî ïðè y = 0).
Íåòðóäíî âèäåòü, ÷òî îòíîøåíèåx|y ýêâèâàëåíòíî îòíîøåíèþ[y/x] · x = y,106îòêóäà âûòåêàåò åãî ïðèìèòèâíàÿ ðåêóðñèâíîñòü.Èñïîëüçóÿ îòíîøåíèå x|y , ïîäñ÷èòàeì êîëè÷åñòâî äåëèòåëåé ÷èñëà x.Ñîîòâåòñòâóþùóþ ôóíêöèþ îáîçíà÷èì ÷åðåç d(x). Åñëè g(x, i) õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ îòíîøåíèÿ i|x, òî, î÷åâèäíî,d(x) =Xg(x, i).i6xÎáîçíà÷èì ÷åðåç Pr(x) îòíîøåíèå ¾x åñòü ïðîñòîå ÷èñëî¿. Òîãäà Pr(x)èñòèííî â òîì è òîëüêî òîì ñëó÷àå, êîãäà x > 1 è d(x) = 2. Ñëåäîâàòåëüíî, õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ îòíîøåíèÿ Pr(x) ðàâíà ïðîèçâåäåíèþõàðàêòåðèñòè÷åñêèõ ôóíêöèé îòíîøåíèé x > 1 è d(x) = 2. Îòñþäà âûòåêàåò ïðèìèòèâíàÿ ðåêóðñèâíîñòü îòíîøåíèÿ Pr(x).Ïóñòü a ïðîñòîå ÷èñëî è expa (x) ðàâíî ïîêàçàòåëþ ÷èñëà a â ðàçëîæåíèè x íà ïðîñòûå ìíîæèòåëè (ïðè x = 0, 1 çíà÷åíèå expa (x) ìîæíîâûáðàòü ïðîèçâîëüíî). Äîêàæåì ïðèìèòèâíóþ ðåêóðñèâíîñòü ôóíêöèèexpa (x). Îáîçíà÷èì ÷åðåç g(x, i) õàðàêòåðèñòè÷åñêóþ ôóíêöèþ îòíîøåíèÿ ai |x.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
