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

                                                                                 x 2. pOLNYE KLASSY BULEWYH FUNKCIJ

    1. pUSTX f
 f1 
 : : :
 fn 2 T0 I F(x1
 : : :
 xn) = f(f1 (x1
 : : :
 xn)
 : : :
 fn(x1 
 : : :
 xn)). tOGDA
                       F(0
 : : :
 0) = f(f1 (0
 : : :
 0)
 : : :
 fn(0
 : : :
 0)) = f(0
 : : :
 0) = 0:
sLEDOWATELXNO, func F 2 T0 , TO ESTX T0 ZAMKNUT.
    2. pUSTX f
 f1 
 : : :
 fn 2 T1 I F(x1
 : : :
 xn) = f(f1 (x1
 : : :
 xn)
 : : :
 fn(x1 
 : : :
 xn)). tOGDA
                       F(1
 : : :
 1) = f(f1 (1
 : : :
 1)
 : : :
 fn(1
 : : :
 1)) = f(1
 : : :
 1) = 1:
sLEDOWATELXNO, func F 2 T1 , TO ESTX T1 ZAMKNUT.
    3. pUSTX f
 f1 
 : : :
 fn 2 T I F (x1
 : : :
 xn) = f(f1 (x1 
 : : :
 xn)
 : : :
 fn (x1
 : : :
 xn)). tOGDA, PO
TEOREME 1.6.1, F  = f  (f1 (x1 
 : : :
 xn)
 : : :
 fn (x1
 : : :
 xn))  f(f1 (x1 
 : : :
 xn)
 : : :
 fn (x1
 : : :
 xn)) =
= F(x1
 : : :
 xn). sLEDOWATELXNO, func F 2 T , TO ESTX T ZAMKNUT.
    4. pUSTX f
 f1 
 : : :
 fn 2 T I F(x1
 : : :
 xn) = f(f1 (x1
 : : :
 xn)
 : : :
 fn(x1 
 : : :
 xn)). tOGDA, DLQ

  2 f0
 1gn, IZ    SLEDUET (f1 ()
 : : :
 fn())  (f1 ()
 : : :
 fn()), A OTS@DA SLEDUET, ^TO
f(f1 ()
 : : :
 fn())  f(f1 ()
 : : :
 fn ()), TO ESTX F ()  F (). |TO OZNA^AET, ^TO func F 2 T , TO
ESTX T ZAMKNUT.
    5. pUSTX f
 f1 
 : : :
 fn 2 TL I F(x1
 : : :
 xn) = f(f1 (x1 
 : : :
 xn)
 : : :
 fn (x1
 : : :
 xn)). tOGDA
                                          f  a0 + a1x1 + : : : + an xn
                                          f1  a10 + a11x1 + : : : + a1nxn
                                                               :::
                                          fn  an0 + an1x1 + : : : + ann xn
pODSTAWLQQ \TI WYRAVENIQ W ZAPISX FORMULY F POLU^IM
       F (x1
 : : :
 xn)  a0 + a1 (a10 + a11x1 + : : :a1nxn ) + : : : + an(an0 + an1x1 + : : :annxn) 
                                                                                        d0 + d1x1 + : : : + dnxn:
sLEDOWATELXNO, func F 2 TL , TO ESTX TL ZAMKNUT.
  2.4. pOLNYE KLASSY BULEWYH FUNKCIJ.
oPREDELENIE 1. kLASS BULEWYH FUNKCIJ  NAZYWAETSQ POLNYM ESLI EGO ZAMYKANIE SOWPADAET ,
S KLASSOM WSEH BULEWYH FUNKCIJ, TO ESTX
                                                ] = B:
   tAKIM OBRAZOM, MNOVESTWO BULEWYH FUNKCIJ  OBRAZUET POLNYJ KLASS, ESLI L@BAQ BULEWA
FUNKCIQ REALIZUEMA W WIDE FORMULY NAD .
tEOREMA 1. pUSTX ZADANY DWA KLASSA BULEWYH FUNKCIJ 1 I 2. tOGDA, ESLI KLASS 1 POLNYJ
I WSE FUNKCII IZ 1 REALIZUEMY FORMULAMI NAD 2 , TO KLASS 2 TAKVE POLNYJ.
dOKAZATELXSTWO. pUSTX h | PROIZWOLXNAQ BULEWA FUNKCIQ. tOGDA, TAK KAK KLASS 1 POL-
NYJ, TO h = func F 1]. pUSTX ff1
 : : :
 fn g | WSE BULEWY FUNKCII IZ KLASSA 1 , KOTORYE WHO-
DQT W ZAPISX FORMULY F 1]. tOGDA, PO USLOWI@, fi = func Gi 2]. zNA^IT h = func G2], GDE
G2] = F 1]fGi==fi gni=1 . tAKIM OBRAZOM, PROIZWOLXNAQ BULEWA FUNKCIQ h REALIZUEMA NAD BA-
ZISOM 2 , TO ESTX 2 QWLQETSQ POLNYM.
pRIMER 1. kLASSY BULEWYH FUNKCIJ f0
 g, f0
 _g, fjg, f#g, f0
 1
 
 +g QWLQ@TSQ POLNYMI W SILU
TOLXKO ^TO DOKAZANNOJ TEOREMY, TAK KAK W SILU RAWNOSILXNOSTEJ TEOREMY 1.4.1 KAVDAQ IZ FUNK-
CIJ KLASSA f0 
 
 _g WYRAVAETSQ ^EREZ FUNKCII \TIH KLASSOW, A POLNOTA KLASSA f0
 
 _g DOKAZANA
W P. IV.2.1.
   zAMETIM, ^TO FORMULA NAD BAZISOM f0
 1
 
 +g NAZYWAETSQ POLINOMOM vEGALKINA I \TOT PRI-
MER POKAZYWAET, ^TO KAVDAQ BULEWA FUNKCIQ RAWNOSILXNA NEKOTOROMU (NE OBQZATELXNO LINEJNO-
MU) POLINOMU vEGALKINA.
   sLEDU@]AQ TEOREMA USTANAWLIWAET NEOBHODIMYE I DOSTATO^NYE USLOWIQ POLNOTY KLASSOW
BULEWYH FUNKCIJ I BYLA DOKAZANA AMERIKANSKIM MATEMATIKOM |. pOSTOM W 1921 GODU.
                                                               83