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

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

Составители: 

Рубрика: 

gLAWA   VII.   oSNOWY TEORII ALGORITMOW

   2.5. wY^ISLIMYE PO tX@RINGU FUNKCII. w DALXNEJEM BUDEM POLXZOWATXSQ OBOZNA-
^ENIEM
                                                 axi = a| i ai{z: : :a}i :
                                                                x
oPREDELENIE 1. bUDEM GOWORITX ^TO MAINA tX@RINGA T WY^ISLQET n MESTNU@ ^ASTI^NU@
                                         ,                                                   -
^ISLOWU@ FUNKCI@ f(x1  x2 : : : xn), ESLI WYPOLNENY SLEDU@]IE USLOWIQ:
   1. eSLI f(x1  x2  : : : xn ) OPREDELENO, TO



                                       q101x1 01x2 0 : : :01xn 0 )
                                                                 T Cq B
                                                                     0

GDE C , B | NEKOTORYE SLOWA W ALFAWITE f0 1g, PRI^EM Cq0B SODERVIT f(x1  x2 : : : xn) WHOV-
DENIJ SIMWOLA 1.
   2. eSLI f(x1  x2  : : : xn ) NE OPREDELENO, TO MAINA T , NA^INAQ RABOTU SO SLOWA


                                          M = q101x1 01x2 0 : : :01xn 0
RABOTAET WE^NO.
   ~ASTI^NAQ ^ISLOWAQ FUNKCIQ NAZYWAETSQ WY^ISLIMOJ PO tX@RINGU , ESLI SU]ESTWUET MAINA
tX@RINGA T , WY^ISLQ@]AQ \TU FUNKCI@.
   oTMETIM, ^TO MAINA tX@RINGA IZ PRIMERA 2.4.1 WY^ISLQET FUNKCI@ f(x) = x + 1, A IZ
PRIMERA 2.4.2 | ^ASTI^NU@ FUNKCI@ f(x) = x ; 1.
oPREDELENIE 2. bUDEM GOWORITX, ^TO MAINA tX@RINGA T PRAWILXNO WY^ISLQET n-MESTNU@
^ASTI^NU@ ^ISLOWU@ FUNKCI@ f(x1  x2 : : : xn), ESLI WYPOLNENY SLEDU@]IE USLOWIQ:
   1. eSLI f(x1  x2  : : : xn ) OPREDELENO, TO



                              q1 01x1 01x2 0 : : :01xn 0 )
                                                         T q 1f (x1 x2 :::xn ) 0 : : :0
                                                            0

I PRI \TOM NE DOSTRAIWAET Q^EEK SLEWA.
   2. eSLI f(x1  x2  : : : xn ) NE OPREDELENO, TO MAINA T , NA^INAQ RABOTU SO SLOWA


                                          M = q101x1 01x2 0 : : :01xn 0
RABOTAET WE^NO.
pRIMER 1. pUSTX T = hA Q P i, GDE: A = f0 1g, Q = fq0 q1 q2 q3 q4 q5g,
    P : q1 1 ! q2R, q10 ! q2R, q21 ! q2R
         q2 0 ! q31, q31 ! q3R, q30 ! q4L
         q4 1 ! q40, q40 ! q5L, q51 ! q5L
         q5 0 ! q00.
   uBEDITESX SAMOSTOQTELXNO, ^TO \TA MAINA tX@RINGA PRAWILXNO WY^ISLQET ^ISLOWU@ FUNK-
CI@ f(x y) = x + y.
   ~ASTI^NAQ ^ISLOWAQ FUNKCIQ NAZYWAETSQ PRAWILXNO WY^ISLIMOJ PO tX@RINGU , ESLI SU]EST-
WUET MAINA tX@RINGA T , WY^ISLQ@]AQ \TU FUNKCI@.
   mY WIDIM, ^TO PONQTIE PRAWILXNO WY^ISLIMOJ PO tX@RINGU FUNKCII QWLQETSQ BOLEE STRO-
GIM, ^EM PONQTIE WY^ISLIMOJ PO tX@RINGU FUNKCII. oNO ISPOLXZUETSQ, KAK PRAWILO, DLQ TOGO,
^TOBY POLU^ENNU@ DLQ WY^ISLENIQ DANNOJ FUNKCII MAINU tX@RINGA MOVNO BYLO KORREKTNO
ISPOLXZOWATX W KOMPOZICII S DRUGIMI MAINAMI DLQ POSTROENIQ BOLEE SLOVNYH MAIN tX@-
RINGA NA OSNOWE BOLEE PROSTYH.
   pRIWEDEM BEZ DOKAZATELXSTWA TEOREMU, SWQZYWA@]U@ PONQTIQ ^ASTI^NO REKURSIWNOJ FUNKCII
I MAINY tX@RINGA.
tEOREMA 1. ~ASTI^NAQ ^ISLOWAQ FUNKCIQ QWLQETSQ ^ASTI^NO REKURSIWNOJ TOGDA I TOLXKO
TOGDA, KOGDA ONA WY^ISLIMA PO tX@RINGU.

                                                          134

Страницы