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

gLAWA   VII.   oSNOWY TEORII ALGORITMOW

f | \TO OTOBRAVENIE MNOVESTWA N
                              |0
                                  
                                   {z
                                        N0} (PODMNOVESTWA Xf MNOVESTWA N
                                                                       |0
                                                                           
                                                                            {z
                                                                                 N0}) W N0 .
                                           n                                          n
Xf NAZYWAETSQ OBLASTX@ OPREDELENIQ ^ASTI^NOJ ^ISLOWOJ FUNKCII f. oBLASTX ZNA^ENIJ ^ISLO-
WOJ FUNKCII (^ASTI^NOJ ^ISLOWOJ FUNKCII) f BUDEM OBOZNA^ATX Yf . oTMETIM, ^TO ^ISLOWAQ
FUNKCIQ f ESTX ^ASTI^NAQ ^ISLOWAQ FUNKCIQ, DLQ KOTOROJ Xf = N
                                                            |0
                                                                
                                                                 {z
                                                                      N0}.
                                                                              n
oPREDELENIE 1. ~ASTI^NAQ ^ISLOWAQ FUNKCIQ NAZYWAETSQ WY^ISLIMOJ ESLI SU]ESTWUET AL,        -
GORITM, POZWOLQ@]IJ WY^ISLQTX EE ZNA^ENIQ DLQ TEH NABOROW ZNA^ENIJ ARGUMENTOW, DLQ KO-
TORYH ONA OPREDELENA, I RABOTA@]IJ WE^NO NA NABORAH ZNA^ENIJ ARGUMENTOW, DLQ KOTORYH
\TA FUNKCIQ NE OPREDELENA.
   kAK PRAWILO, OTYSKANIE TOGO ILI INOGO ALGORITMA W MATEMATIKE MOVNO SWESTI K NAHOVDENI@
ALGORITMA, WY^ISLQ@]EGO NEKOTORU@ ^ASTI^NU@ ^ISLOWU@ FUNKCI@ ILI HOTQ BY DOKAZATELXSTWU
PRINCIPIALXNOJ WY^ISLIMOSTI \TOJ FUNKCII.
   1.2. nEOBHODIMOSTX UTO^NENIQ PONQTIQ ALGORITMA. pERIOD DO NA^ALA XX STOLE-
TIQ MOVNO S^ITATX PERIODOM NAKOPLENIQ KONKRETNYH ALGORITMOW W MATEMATIKE. oTMETIM, ^TO
INTUITIWNOE PONQTIE ALGORITMA QWLQETSQ DOSTATO^NO QSNYM I POTOMU SREDI MATEMATIKOW, KAK
PRAWILO, NE WOZNIKALO RAZNOGLASIJ PO POWODU TOGO, QWLQETSQ LI DANNAQ PROCEDURA ALGORITMOM
ILI NE QWLQETSQ. oDNAKO, UVE W KONCE XIX WEKA STALO INTUITIWNO QSNO, ^TO MNOGIE ZADA^I OB
OTYSKANII ALGORITMOW, PO-WIDIMOMU, NE IME@T REENIQ. oDNAKO, ESLI DLQ DOKAZATELXSTWA SU-
]ESTWOWANIQ ALGORITMA DOSTATO^NO EGO PRED_QWITX, TO DLQ DOKAZATELXSTWA OTSUTSTWIQ ALGORIT-
MA NEOBHODIMO IMETX EGO STROGOE OPREDELENIE. tAK KAK W MATEMATIKE PONQTIE ALGORITMA TESNO
SWQZANO S PONQTIEM WY^ISLIMOJ FUNKCII, TO WPERWYE STROGOE OPREDELENIE BYLO DANO NE SAMOMU
PONQTI@ ALGORITMA, A PONQTI@ WY^ISLIMOJ FUNKCII. gOWORQ BOLEE TO^NO, KLASS WY^ISLIMYH
FUNKCIJ BYL FORMALIZOWAN ILI AKSIOMATIZIROWAN . |TO BYLO SDELANO WPERWYE k. gEDELEM I,
PO^TI ODNOWREMENNO, a. ~ER^EM W 1935{1936 GODAH. pRI \TOM KLASS WSEH WY^ISLIMYH FUNKCIJ
BYL FORMALIZOWAN TO^NO TAKVE, KAK KLASS WSEH TAWTOLOGIJ ALGEBRY WYSKAZYWANIJ W IS^ISLENII
WYSKAZYWANIJ. a IMENNO, BYLI WYDELENY NEKOTORYE PROSTEJIE FUNKCII , KOTORYE, O^EWIDNYM
OBRAZOM, QWLQ@TSQ WY^ISLIMYMI. zATEM WWEDENY TRI PRAWILA POLU^ENIQ IZ IME@]IHSQ FUNK-
CIJ NOWYH. |TI PRAWILA, PRIMENENNYE K WY^ISLIMYM FUNKCIQM, DA@T W REZULXTATE FUNKCII
WY^ISLIMYE. tAKIE PRAWILA NAZWANY OSNOWNYMI WY^ISLIMYMI OPERATORAMI . tAKIM OBRAZOM,
KLASS FORMALIZOWANNYH UKAZANNYM WYE SPOSOBOM FUNKCIJ SOSTOIT IZ WY^ISLIMYH FUNKCIJ.
wOZNIKAET WOPROS, A WSQKAQ LI WY^ISLIMAQ FUNKCIQ POPADAET W \TOT KLASS? pRIMERA INTUITIWNO
WY^ISLIMOJ FUNKCII NE POPAWEJ W UKAZANNYJ KLASS, NE POSTROENO. i, BOLEE TOGO, DALXNEJIE
ISSLEDOWANIQ W \TOM NAPRAWLENII POZWOLILI WYDWINUTX GIPOTEZU O TOM, ^TO TAKIH PRIMEROW NE
SU]ESTWUET (TEZIS ~ER^A).
   1.3. pROSTEJIE FUNKCII. pRISTUPIM K POSTROENI@ FORMALIZOWANNOGO KLASSA FUNK-
CIJ, KAVDAQ IZ KOTORYH QWLQETSQ WY^ISLIMOJ. fUNKCII IZ \TOGO KLASSA BUDEM NAZYWATX REKUR-
SIWNYMI.
   sLEDU@]IE NIVE FUNKCII BUDEM NAZYWATX PROSTEJIMI:
    s(x) = x + 1                       | FUNKCIQ SLEDOWANIQ,
    o(x) = 0                           | NULX-FUNKCIQ,
    Im (x1 
 : : :xn) = xm 
 1  m  n | PROEKTIRU@]AQ FUNKCIQ.
      n
   lEGKO PONQTX, ^TO KAVDAQ IZ PROSTEJIH FUNKCIJ QWLQETSQ WY^ISLIMOJ.
   1.4. oPERATOR SUPERPOZICII. pUSTX ZADANO n ^ASTI^NYH FUNKCIJ OT m PEREMENNYH:
                                          f1 = f1 (x1
 : : :
 xm ),
                                          f2 = f2 (x1
 : : :
 xm ),
                                           : : :: : :: : : : : :: : :: : :,
                                          fn = fn (x1
 : : :
 xm ).

                                                       126