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

                                                                                 x 3. nORMALXNYE ALGORITMY mARKOWA

   2. pUSTX n
 m 2 N0 , m > 1. rASSMOTRIM N. A. m. W ALFAWITE f1g:
                                            8
                                            >
                                            >
                                            >
                                            >
                                              11 : : :1}
                                              | {z                  ! I
                                            >    m
                                            >
                                            >
                                            >
                                            >
                                            >
                                            >
                                            >
                                              11 : : :1}
                                              | {z                  ! I
                                            >  m  ;1
                                            <
                                            >
                                              11 : : :1}
                                              | {z                  ! I
                                            >
                                            >
                                            >  m ;2
                                            >
                                            >
                                            >                       :::
                                                                    ! I
                                            >
                                            >
                                            >
                                            >
                                            >         1
                                            >
                                            :
                                                              I     ! 1
   lEGKO PONQTX, ^TO DANNYJ N. A. m. PERERABATYWAET WSQKOE SLOWO 11 : : :1} = 1n W 1, ESLI n ... m,
                                                                 | {z
                                                                    n
I W I, ESLI n NE DELITSQ NA m.
  3.4. nORMALXNO WY^ISLIMYE FUNKCII.
oPREDELENIE 1. ~ASTI^NAQ FUNKCIQ f ZADANNAQ NA MNOVESTWE SLOW W ALFAWITE X SLOWAR
NAQ FUNKCIQ), NAZYWAETSQ NORMALXNO WY^ISLIMOJ, ESLI NAJDETSQ TAKOE RASIRENIE X (X  X)
                                                ,                                                         (      -


ALFAWITA X I TAKOJ N. A. m., KOTORYJ WSQKOE SLOWO A IZ OBLASTI OPREDELENIQ FUNKCII f PE-
RERABATYWAET W SLOWO f(A) I KOTORYJ NEPRIMENIM K SLOWAM IZ F (X), NE WHODQ]IM W OBLASTX
OPREDELENIQ FUNKCII f .
   nA OSNOWE OPREDELENIQ NORMALXNO WY^ISLIMOJ SLOWARNOJ FUNKCII MOVNO DATX OPREDELENIE
NORMALXNO WY^ISLIMOJ ^ASTI^NOJ ^ISLOWOJ FUNKCII, NAPRIMER, NIVESLEDU@]IM OBRAZOM.
oPREDELENIE 2. ~ASTI^NAQ ^ISLOWAQ FUNKCIQ f(x1 
 : : :
 xn) NAZYWAETSQ NORMALXNO WY^ISLI
MOJ, ESLI NAJDETSQ TAKOE RASIRENIE X ALFAWITA X = f0
 1g I TAKOJ N. A. m. P , KOTORYJ
                                                                                                                 -


   1) ESLI f(x1 
 : : :
 xn ) OPREDELENO, TO


      P SLOWO 01x1 0 : : :01xn 0 PERERABATYWAET W SLOWO 01f (x1 
:::
xn ) 0 (PO-PREVNEMU 10 = I)
                                                                                       x        x
   2) ESLI VE f(x1 
 : : :
 xn ) NE OPREDELENO, TO N. A. m. P NEPRIMENIM K SLOWU 01 1 0 : : :01 n 0.


pRIMER
  x+1
       1. w ALFAWITE f1g N. A. m. fI! 1 NORMALXNO WY^ISLQET SLOWARNU@ FUNKCI@ f(1x ) =
=1     .
pRIMER 2. ~ISLOWAQ FUNKCIQ SLEDOWANIQ s(x) = x + 1 QWLQETSQ NORMALXNO WY^ISLIMOJ, TAK
KAK SU]ESTWUET N. A. m., UDOWLETWORQ@]IJ OPREDELENI@:
                                                              ! 11
                                                (
                                                     1
                                                     0        ! 01
pRIMER 3. pOKAVEM, ^TO FUNKCIQ f(x
 y) = x+y QWLQETSQ NORMALXNO WY^ISLIMOJ. rASSMOTRIM
N. A. m., OPREDELQEMYJ SHEMOJ:              8
                                            >
                                            >       101       ! 11
                                            >
                                            <
                                                    001       ! 01  :
                                            >
                                            >       100       ! 10  :
                                            >
                                            :
                                                    000       ! 00  :
   o^EWIDNO, ^TO
                                  0 11 : : :1} 0 11
                                    | {z            : : :1} 0 ) 0 11
                                                 | {z                : : :1} 0
                                                                  | {z
                                        x                 y                x+y
   |TO I OZNA^AET, ^TO RASSMOTRENNYJ N. A. m. NORMALXNO WY^ISLQET FUNKCI@ f(x
 y) = x + y.

                                                              139