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

   x   2.       pOLNYE KLASSY BULEWYH FUNKCIJ
      rAZLOVENIE BULEWOJ FUNKCII PO PEREMENNOJ wYRAVENIE BULEWYH FUNKCIJ ^EREZ OTRICANIE
                                                                    .                                                  ,

      KON_@NKCI@ I DIZ_@NKCI@ sOWERENNYE NORMALXNYE FORMY BULEWYH FUNKCIJ zAMKNU
                                              .                                                                    .   -

      TYE SOBSTWENNYE M POLNYE KLASSY BULEWYH FUNKCIJ pRIMERY POLNYH KLASSOW tEOREMA O
            ,                                                                    .                             .

      POLNOTE SISTEMY BULEWYH FUNKCIJ                    .


   w SOWREMENNYH |wm SISTEMA KOMAND CENTRALXNOGO PROCESSORA PREDSTAWLQET SOBOJ, FAKTI^ES-
KI, NEKOTOROE KONE^NOE MNOVESTWO BULEWYH FUNKCIJ. w SWQZI S \TIM WOZNIKAET WOPROS: SU]ESTWU-
@T LI (I ESLI SU]ESTWU@T, TO KAKIE) KLASSY BULEWYH FUNKCIJ, OBLADA@]IE TEM SWOJSTWOM, ^TO
S IH POMO]X@ MOVNO WYRAZITX WSE DRUGIE BULEWY FUNKCII? w \TOM PARAGRAFE BUDET DOKAZANA
TEOREMA pOSTA O POLNOTE KLASSA BULEWYH FUNKCIJ W KOTOROJ USTANAWLIWA@TSQ NEOBHODIMYE I
DOSTATO^NYE USLOWIQ TOGO, ^TOBY KLASS BULEWYH FUNKCIJ OBLADAL \TIM SWOJSTWOM
   2.1. wYRAVENIE BULEWYH FUNKCIJ ^EREZ OTRICANIE, KON_@NKCI@ I DIZ_@NKCI@.
w \TOM PUNKTE DOKAZYWAETSQ, ^TO WSE BULEWY FUNKCII (OT L@BOGO KOLI^ESTWA ARGUMENTOW) REA-
LIZU@TSQ FORMULAMI NAD BAZISOM f0
 
 _g.
lEMMA 1 (O RAZLOVENII FUNKCII PO PEREMENNOJ). dLQ PROIZWOLXNOJ BULEWOJ FUNKCII OT n PE-
REMENNYH f(x1 
 : : :
 xn) WERNY SLEDU@]IE FORMULY, NAZYWAEMYE FORMULAMI RAZLOVENIQ \TOJ
FUNKCII PO PEREMENNOJ xn :
                   f(x1 
 : : :
 xn)  f(x1 
 : : :
 xn;1
 1)  xn _ f(x1 
 : : :
 xn;1
 0)  x0n
                                          ;                                  
   ;                         

                                                                                                                           (1)
                  f(x1 
 : : :
 xn)  f(x1 
 : : :
 xn;1
 1) _ x0n  f(x1 
 : : :
 xn;1
 0) _ xn
                                      ;                           
 ;                             

                                                                                                                           (2)
dOKAZATELXSTWO. dOKAVEM FORMULU (1). nUVNO PROWERITX, ^TO FUNKCII, STOQ]IE W LEWOJ I PRA-
WOJ ^ASTQH RAWNOSILXNOSTI, PRI ODINAKOWYH ZNA^ENIQH ARGUMENTOW IME@T RAWNYE ZNA^ENIQ. rAS-
SMOTRIM SNA^ALA WSEWOZMOVNYE NABORY ARGUMENTOW WIDA (a1 
 : : :
 an;1
 1), GDE a1 
 : : :
 an;1 2 f0
 1g
I WY^ISLIM KAKIE ZNA^ENIQ PRINIMA@T NA NABORAH TAKOGO WIDA FUNKCII, STOQ]IE W PRAWOJ I
LEWOJ ^ASTQH DOKAZYWAEMOJ RAWNOSILXNOSTI.
                     f(a1 
 : : :
 an;1
 1)  1          _ ;f(a1 
 : : :
 an;1
 0)  0
 = f(a1
 : : :
 an;1
 1):
                    ;                             



wIDNO, ^TO NA \TOM NABORE PEREMENNYH LEWAQ I PRAWAQ ^ASTX DOKAZYWAEMOJ RAWNOSILXNOSTI SOW-
PADA@T.
   dLQ WSEWOZMOVNYH NABOROW ZNA^ENIJ PEREMENNYH WIDA (a1 
 : : :
 an;1
 0) TAKVE LEWAQ I PRAWAQ
^ASTI SOWPADA@T, TAK KAK
                        f(a1 
 : : :
 an;1
 1)  0       _ ;f(a1 
 : : :
 an;1
 0)  1
 = f(a1
 : : :
 an;1
 0):
                    ;                                



iTAK, FUNKCII IZ OBEIH ^ASTEJ DOKAZYWAEMOJ RAWNOSILXNOSTI PRINIMA@T ODINAKOWYE ZNA^ENIQ
PRI ODINAKOWYH ZNA^ENIQH IH ARGUMENTOW. sLEDOWATELXNO, \TI FUNKCII RAWNOSILXNY I RAWNO-
SILXNOSTX (1) SPRAWEDLIWA.
   rAWNOSILXNOSTX (2) DOKAZYWAETSQ ANALOGI^NO. pRODELAJTE \TO SAMOSTOQTELXNO.
   zAMETIM, ^TO PODOBNYE FORMULY WERNY I DLQ OSTALXNYH PEREMENNYH x1 
 : : :
 xn;1.
tEOREMA 1. wSQKAQ BULEWA FUNKCIQ MOVET BYTX PREDSTAWLENA W WIDE SUPERPOZICII OTRI-
CANIQ, KON_@NKCII I DIZ_@NKCII, TO ESTX L@BAQ BULEWA FUNKCIQ REALIZUETSQ FORMULOJ NAD
BAZISOM f0
 :_g.
dOKAZATELXSTWO. mETOD MATEMATI^ESKOJ INDUKCII PO ^ISLU n ARGUMENTOW BULEWOJ FUNKCII.
w PREDYDU]EM PARAGRAFE PERE^ISLENY WSE BULEWY FUNKCII OT ODNOGO ARGUMENTA. tAK KAK
                                                             f0 (x) = 0  x  x0
                                                             f1 (x) = x
                                                             f2 (x) = x0
                                                             f3 (x) = 1  x _ x0


                                                                        80