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

gLAWA   IV.   bULEWY FUNKCII

tEOREMA 2 (pOST). kLASS BULEWYH FUNKCIJ  QWLQETSQ POLNYM TOGDA I TOLXKO TOGDA KOGDA                                    ,
W \TOM KLASSE ESTX FUNKCIQ NE PRINADLEVA]AQ KLASSU T0, ESTX FUNKCIQ NE PRINADLEVA]AQ
KLASSU T1, ESTX FUNKCIQ NE PRINADLEVA]AQ KLASSU T , ESTX FUNKCIQ NE PRINADLEVA]AQ KLAS-
SU T , ESTX FUNKCIQ NE PRINADLEVA]AQ KLASSU TL , TO ESTX
                  ] = B () :(  T0 _   T1 _   T _   T _   TL ):
dOKAZATELXSTWO. nEOBHODIMOSTX pUSTX ] = B I   T0 _   T1 _   T _   T _   TL.
tOGDA SU]ESTWUET TAKOE i 2 f0
 1
 
 
 Lg, ^TO   Ti . oTS@DA, PO TEOREME 2.3.1, ] = B  Ti].
                                              .



nO TAK KAK KLASS Ti ZAMKNUTYJ PO TEOREME 2.3.2, TO B = Ti , ^TO PROTIWORE^IT TOMU, ^TO Ti
QWLQETSQ SOBSTWENNYM KLASSOM.
   dOSTATO^NOSTX pUSTX :(  T0 _   T1 _   T _   T _   TL ). tOGDA SU]ESTWUET
0  , 0 = ff0 
 f1
 f 
 f 
 fLg, GDE f0 2= T0 , f1 2= T1 , f 2= T , f 2= T , fL 2= TL , PRI^EM \TI
                        .



FUNKCII NE OBQZATELXNO RAZLI^NY I NE OBQZATELXNO 0 = .
   pOKAVEM, ^TO BULEWY FUNKCII 0 I  REALIZUEMY W WIDE FORMUL NAD 0 . pOSTROENIE BUDET
PROWODITXSQ W TRI \TAPA: NA PERWOM STROQTSQ FORMULY NAD 0 , REALIZU@]IE KONSTANTY 0 I 1,
KOTORYE NUVNY NA TRETXEM \TAPE NA WTOROM \TAPE STROITSQ FORMULA, REALIZU@]AQ OTRICANIE
NA TRETXEM \TAPE STROITSQ FORMULA, REALIZU@]AQ KON_@NKCI@.
   1. pOSTROIM FORMULU NAD 0 , REALIZU@]U@ 1. pUSTX '(x) = f0 (x
 : : :
 x). tOGDA
                                   '(0) = f0 (0
 : : :
 0) 6= 0 =) '(0) = 1:
wOZMOVNY DWA SLU^AQ '(1) = 1 I '(1) = 0.
   A) '(1) = 1. w \TOM SLU^AE FORMULA ' REALIZUET 1.
   B) '(1) = 0. w \TOM SLU^AE FORMULA ' REALIZUET OTRICANIE. tOGDA RASSMOTRIM FUNKCI@ f .
tAK KAK f 2= T , TO SU]ESTWU@T a1 
 : : :
 an 2 f0
 1g TAKIE, ^TO f (a1 
 : : :
 an) 6= f0 (a01 
 : : :
 a0n).
sLEDOWATELXNO, f (a1 
 : : :
 an) = f (a01 
 : : :
 a0n).
   oBOZNA^IM DLQ x
  2 f0
 1g                        
                                           x = x

                                                            ESLI  = 0,
                                                         x0
 ESLI  = 1.
tOGDA 0 =  I 1 = 0 . pUSTX TEPERX (x) = f (xa1 
 : : :
 xan ). tOGDA
             (0) = f (0a1 
 : : :
 0an ) = f (a1
 : : :
 an) = f (a01 
 : : :
 a0n) = f (1a1 
 : : :
 1an ) = (1):
tAKIM OBRAZOM, (0) = (1), TO ESTX (x)  1 ILI (x)  0. eSLI (x)  1, TO ISKOMAQ KONSTAN-
TA 1 POSTROENA. eSLI VE REALIZUET 0, TO FUNKCIQ '( (x)) REALIZUET EDINICU.
    pOSTROENIE KONSTANTY 0 PROWODITSQ ANALOGI^NO, TOLXKO WMESTO f0 NUVNO ISPOLXZOWATX f1 .
    2. pOSTROIM FORMULU, REALIZU@]U@ OTRICANIE. rASSMOTRIM FUNKCI@ f . tAK KAK f 2= T ,
TO SU]ESTWU@T  = (a1
 : : :
 an) I  = (b1 
 : : :
 bn), ai 
 bi 2 f0
 1g TAKIE, ^TO   I f () > f ().
iZ TOGO  , ^TO f () 6= f () SLEDUET, ^TO  6= . zNA^IT MNOVESTWO J = j 2 f1
 : : :
 ng j aj = 0

bj = 1 NEPUSTO. tO ESTX J | MNOVESTWO INDEKSOW j NA KOTORYH aj 6= bj , A NA OSTALXNYH INDEKSAH
       

k 2 f1
 : : :
 ng n J, ak = bk .
                                                                     ESLI j 2 J,
                                                      
    pUSTX '(x) = f (c1 
 : : :
 cn), GDE cj = x
        aj = bj 
 ESLI j 2= J.
    tOGDA
              '(0) = f (c1 
 : : :
 cn)f0==xg = f () > f () = f (c1 
 : : :
 cn)f1==xg = '(1)

TO ESTX '(0) > '(1). |TO OZNA^AET, ^TO '(0) = 1, A '(1) = 0, TO ESTX '(x)  x0.
    3. pOSTOIM FUNKCI@, REALIZU@]U@ KON_@NKCI@. rASSMOTRIM FUNKCI@ fL . |TA FUNKCIQ REA-
LIZUEMA NAD POLNYM KLASSOM f0
 1
 +
 g W WIDE POLINOMA vEGALKINA, NO fL 2= TL , SLEDOWATELXNO,
\TOT POLINOM NE QWLQETSQ LINEJNYM. zNA^IT fL SODERVIT NELINEJNOE SLAGAEMOE, SODERVA]EE
KON_@NKCI@ PO KRAJNEJ MERE DWUH PEREMENNYH. pUSTX, DLQ OPREDELENNOSTI, \TO x1 I x2 . tOGDA
fL (x1
 x2
 : : :
 xn) = x1  x2  fa (x3
 : : :
 xn) + x1  fb (x3 
 : : :
 xn) + x2  fc (x3 
 : : :
 xn) + fd (x3 
 : : :
 xn)

PRI^EM fa (x3
 : : :
 xn) 6 0, TO ESTX SU]ESTWU@T TAKIE a3
 : : :
 an 2 f0
 1g, ^TO fa (a3 
 : : :
 an) = 1.
oBOZNA^IM fb (a3 
 : : :
 an) = b, fc (a3 
 : : :
 an) = c, fd (a3 
 : : :
 an) = d, TO ESTX b
 c
 d 2 f0
 1g.
                                                               84