Дискретная математика. Кулабухов С.Ю. - 127 стр.

                                                                         x 1. rEKURSIWNYE FUNKCII

I NEKOTORAQ ^ASTI^NAQ n-MESTNAQ FUNKCIQ f = f(y1 
 : : :
 yn ). oPREDELIM PRI POMO]I FUNKCIJ
f
 f1 
 : : :
 fn NOWU@ m -MESTNU@ ^ASTI^NU@ FUNKCI@ g(x1 
 : : :
 xm ) SLEDU@]IM OBRAZOM:
                      g(x1
 : : :
 xm ) = f(f1 (x1 
 : : :
 xm)
 : : :
 fn (x1
 : : :
 xm )).
    gOWORQT, ^TO FUNKCIQ g POLU^ENA OPERACIEJ SUPERPOZICII ILI PODSTANOWKI IZ FUNKCIJ
f
 f1 
 : : :
 fn.
    lEGKO PONQTX, ^TO ESLI FUNKCII f
 f1 
 : : :
 fn WY^ISLIMY, TO I FUNKCIQ g TAKVE WY^ISLIMA,
TO ESTX REZULXTAT PRIMENENIQ OPERATORA SUPERPOZICII K WY^ISLIMYM FUNKCIQM ESTX FUNKCIQ
WY^ISLIMAQ.
   oTMETIM, ^TO W SLU^AE, KOGDA n = m = 1, MY IMEEM IZWESTNU@ SUPERPOZICI@ DWUH ODNOMEST-
NYH FUNKCIJ (ILI FUNKCI@ OT FUNKCII, ILI SLOVNU@ FUNKCI@).
pRIMER 1. n-MESTNAQ NULX-FUNKCIQ o(x1
 : : :
 xn) = 0 ESTX SUPERPOZICIQ FUNKCIJ o(x) = 0 I
I1n (x1 
 : : :
 xn):
                             o(x1
 : : :
 xn) = o(I1n (x1
 : : :
 xn)):
pRIMER 2. kONSTANTNAQ FUNKCIQ ODNOJ PEREMENNOJ f(x) = a, a 2 N, ESTX SUPERPOZICIQ FUNK-
CIJ o(x) = 0 I s(x) = x + 1:
                                    s(s(:
                                    | {z }
                                           : :s(o(x)) : : :) = a
                                          a

   1.5. oPERATOR PRIMITIWNOJ REKURSII OPREDELIM DLQ WSQKOGO n 2 N0 SLEDU@]IM OB-
RAZOM.
   pUSTX n > 0. gOWORQT, ^TO (n+1)-MESTNAQ ^ASTI^NAQ FUNKCIQ f POLU^ENA IZ DANNOJ n-MESTNOJ
FUNKCII g I DANNOJ (n + 2)-MESTNOJ ^ASTI^NOJ FUNKCII h PRI POMO]I OPERATORA PRIMITIWNOJ
REKURSII , ESLI \TA FUNKCIQ f OPREDELQETSQ SHEMOJ PRIMITIWNOJ REKURSII :
                          f(x1 
 : : :
 xn
 0) = g(x1
 : : :
 xn)

                          f(x1 
 : : :
 xn
 y + 1) = h(x1 
 : : :
 xn
 y
 f(x1 
 : : :
 xn
 y)):
   pUSTX n = 0. gOWORQT, ^TO ODNOMESTNAQ ^ASTI^NAQ FUNKCIQ f POLU^ENA IZ DANNOJ KONSTANT-
NOJ ODNOMESTNOJ FUNKCII g (g(x) = a) I DANNOJ DWUMESTNOJ FUNKCII h PRI POMO]I OPERATORA
PRIMITIWNOJ REKURSII, ESLI ONA OPREDELQETSQ SHEMOJ PRIMITIWNOJ REKURSII:
                                               f(0) = a = g(0)

                                               f(y + 1) = h(y
 f(y)):
lEGKO PONQTX, ^TO FUNKCIQ f ODNOZNA^NO OPREDELQETSQ SHEMOJ PRIMITIWNOJ REKURSII I FUNKCI-
QMI g I h.
   pREDPOLOVIM TEPERX, ^TO FUNKCII g I h WY^ISLIMY. wY^ISLIMA LI PRI \TIH PREDPOLOVE-
NIQH FUNKCIQ f?
   pUSTX a1 
 a2
 : : :
 an
 m 2 N0 . pREDPOLOVIM, ^TO PRI POMO]I SHEMY PRIMITIWNOJ REKURSII
POLU^ENA POSLEDOWATELXNOSTX ^ISEL
                                     b0 = g(a1 
 : : :
 an)

                                     b1 = h(a1 
 : : :
 0
 b0)

                                     b2 = h(a1 
 : : :
 1
 b1)

                                     : : :: : :: : :: : :: : :: : :

                                     bm+1 = h(a1 
 : : :
 m
 bm ):
tOGDA OPREDELENO I ZNA^ENIE f(a1 
 : : :
 an
 m + 1), RAWNOE bm+1 . tAK KAK g I h WY^ISLIMY, TO
SU]ESTWU@T ALGORITMY Tg I Th DLQ g I h, WY^ISLQ@]IE IH ZNA^ENIQ. tOGDA b0 MOVET BYTX
WY^ISLENO PRI POMO]I ALGORITMA Tg , b1 | PRI POMO]I ALGORITMA Tg Th GDE Tg Th | POSLEDOWA-
TELXNOE WYPOLNENIE ALGORITMOW Tg I Th . pONQTNO, ^TO b2 MOVET BYTX WY^ISLENO PRI POMO]I
ALGORITMA Tg Th Th I T. D. I, NAKONEC, bm+1 | PRI POMO]I ALGORITMA Tg T| h :{z: :Th}. eSLI VE HOTQ
                                                                             m+1
BY ODNO IZ ^ISEL b0 
 : : :
 bm+1 NE OPREDELENO, TO ODIN IZ ALGORITMOW
                                               127