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

gLAWA   IV.   bULEWY FUNKCII

KON_@NKCI@ I DIZ_@NKCI@. |TOT I SLEDU@]IJ PUNKTY POSWQ]ENY NAHOVDENI@ KRITERIEW, KO-
TORYM DOLVEN UDOWLETWORQTX BAZIS BULEWYH FUNKCIJ, ^TOBY ^EREZ FUNKCII \TOGO BAZISA MOVNO
BYLO WYRAZITX L@BU@ BULEWU FUNKCI@.
   wWEDEM WNA^ALE NESKOLXKO OPREDELENIJ, OBOZNA^AQ ^EREZ B MNOVESTWO WSEH BULEWYH FUNKCIJ
OT PROIZWOLXNOGO ^ISLA ARGUMENTOW.
oPREDELENIE 1. pUSTX  = ff1
 : : :
 fm g, fi 2 B, zAMYKANIEM ] KLASSA  NAZYWAETSQ MNO-
VESTWO WSEH BULEWYH, REALIZUEMYH FORMULAMI NAD , TO ESTX
                                      ] = ff 2 B j f = func F]g:
   sWOJSTWA ZAMYKANIJ, FORMULIRUEMYE W SLEDU@]EJ TEOREME O^EWIDNYM OBRAZOM SLEDU@T IZ
OPREDELENIQ.
tEOREMA 1. dLQ L@BYH (NE OBQZATELXNO KONE^NYH) KLASSOW BULEWYH FUNKCIJ , 1 I 2 WY-
POLNQ@TSQ SWOJSTWA:
  1.    ],
   2. ]] = ],


   3. 1  2 =) 1 ]  2 ],


        1] 2]  1 2 ].
      ;              

   4.


oPREDELENIE 2. kLASS BULEWYH FUNKCIJ  NAZYWAETSQ ZAMKNUTYM, ESLI  = ].
oPREDELENIE 3. kLASS BULEWYH FUNKCIJ  NAZYWAETSQ SOBSTWENNYM, ESLI ON NE PUST I NE
SOWPADAET S KLASSOM WSEH BULEWYH FUNKCIJ, TO ESTX  6= ? I  6= B .
    w KA^ESTWE PRIMERA RASSMOTRIM SLEDU@]IE KLASSY BULEWYH FUNKCIJ, KOTORYE NEOBHODIMY
DLQ DALXNEJEGO IZLOVENIQ.
    T0 = ff 2 B j f(0
 : : :
 0) = 0g | KLASS FUNKCIJ, SOHRANQ@]IH NULX.
    T1 = ff 2 B j f(1
 : : :
 1) = 1g | KLASS FUNKCIJ, SOHRANQ@]IH EDINICU.
    T = ff 2 B j f  f g | KLASS SAMODWOJSTWENNYH FUNKCIJ.
    T = ff 2 B j    ! f()  f()g | KLASS MONOTONNYH FUNKCIJ, GDE  = (a1 
 : : :
 an),
 = (b1
 : : :
 bn) I ai 
 bi 2 f0
 1g. pRI \TOM    TOGDA I TOLXKO TOGDA, KOGDA ai  bi , i 2 f1
 : : :
 ng.
    TL = ff 2 B j f(x1 
 : : :
 xn)  a0 + a1x1 + a2x2 + : : : + anxn g | KLASS LINEJNYH FUNKCIJ, GDE
ai 2 f0
 1g I W ZAPISI ai xi OPU]EN ZNAK KON_@NKCII. pRO FUNKCI@ f(x1 
 : : :
 xn) W \TOM SLU^AE
GOWORQT, ^TO ONA PREDSTAWIMA W WIDE LINEJNOGO POLINOMA vEGALKINA.
tEOREMA 2. kLASSY T0, T1, T, T, TL QWLQ@TSQ SOBSTWENNYMI ZAMKNUTYMI KLASSAMI BULEWYH
FUNKCIJ.
dOKAZATELXSTWO. dLQ TOGO, ^TOBY UBEDITXSQ W TOM, ^TO \TI KLASSY SOBSTWENNYE, PRIWEDEM
SLEDU@]U@ TABLICU, W KOTOROJ ZNAKOM + (;) OBOZNA^AETSQ PRINADLEVNOSTX (NE PRINADLEVNOSTX)
FUNKCII SOOTWETSTWU@]EMU KLASSU. oBOSNOWATX \TU TABLICU PREDLAGAETSQ SAMOSTOQTELXNO.
                                                 T0 T1 T T TL
                                         0       + ; ; + +
                                         1       ; + ; + +
                                         x0      ; ; + ; +
                                         x1  x2 + + ; + ;
                                         x       + + + + +
iZ TABLICY WIDNO, ^TO WSE \TI KLASSY NEPUSTY I NE SOWPADA@T S B, PRI^EM f(x) = x PRINADLE-
VIT WSEM \TIM KLASSAM, TO ESTX ONI QWLQ@TSQ SOBSTWENNYMI.
    ~TOBY DOKAZATX ZAMKNUTOSTX NADO POKAZATX, ^TO ESLI FUNKCIQ REALIZOWANA NAD KLASSOM, TO
ONA PRINADLEVIT \TOMU KLASSU.
                                                      82