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

                                                                                  x 2. pOLNYE KLASSY BULEWYH FUNKCIJ

TO UTWERVDENIE TEOREMY SPRAWEDLIWO DLQ n = 1.
   pUSTX TEOREMA WERNA DLQ WSEH FUNKCIJ OT k ARGUMENTOW. dOKAVEM EE DLQ FUNKCIJ OT k + 1
ARGUMENTOW. pUSTX f(x1 
 : : :
 xk+1) | PROIZWOLXNAQ BULEWA FUNKCIQ OT k + 1 ARGUMENTA. tOGDA,
PO PREDYDU]EJ LEMME 2.1.1,
                 f(x1 
 : : :
 xk+1) = f(x1 
 : : :
 xk
 1)  xk+1           _ ;f(x1
 : : :
 xk
 0)  x0k+1

                                      ;                                  



lEGKO PONQTX, ^TO FIKSIROWANIE W BULEWOJ FUNKCII ODNOGO ARGUMENTA PRIWODIT K BULEWOJ FUNK-
CII S ^ISLOM ARGUMENTOW NA EDINICU MENXIM ^ISLA ARGUMENTOW ISHODNOJ FUNKCII. pO\TOMU
KAVDAQ IZ BULEWYH FUNKCIJ f(x1 
 : : :
 xk
 1) I f(x1 
 : : :
 xk
 0) QWLQETSQ BULEWOJ FUNKCIEJ OT k AR-
GUMENTOW. nO, PO PREDPOLOVENI@ INDUKCII, KAVDAQ TAKAQ FUNKCIQ WYRAVAETSQ ^EREZ OTRICANIE,
KON_@NKCI@ I DIZ_@NKCI@. pRINIMAQ \TO WO WNIMANIE WIDIM, ^TO PRAWAQ ^ASTX POSLEDNEGO RA-
WENSTWA RAWNOSILXNA BULEWOJ FUNKCII PREDSTAWLQ@]EJ SUPERPOZICI@ OTRICANIQ, KON_@NKCII
I DIZ_@NKCII.
   oTMETIM, ^TO DOKAZATELXSTWO \TOJ TEOREMY PRAKTI^ESKI PREDOSTAWLQET ALGORITM DLQ NA-
HOVDENIQ FORMULY NAD BAZISOM f0
 
 _g REALIZU@]EJ DANNU@ BULEWU FUNKCI@. dLQ POQSNENIQ
PRIWEDEM SLEDU@]IJ
pRIMER 1. zAPIEM FORMULU, WYRAVA@]U@ BULEWU FUNKCI@ f(x
 y) = x + y ^EREZ OTRICANIE,
KON_@NKCI@ I DIZ_@NKCI@.
   wOSPOLXZUEMSQ FORMULOJ (1)
                                   f(x
 y)  f(x
 1)  y         _ ;f(x
 0)  y0 
:
                                               ;             

                                                                                                                 (3)
nO, PO TOJ VE FORMULE
                                f(x
 1)  ;f(1
 1)  x
 _ ;f(0
 1)  x0


                                               ;             
       ;                


                                f(x
 0)  f(1
 0)  x _ f(0
 0)  x0 :
tAK KAK f(1
 1) = f(0
 0) = 0, f(1
 0) = f(0
 1) = 1, TO
                                       f(x
 1)  ;0  x
 _ ;1  x0
  x0

                                                   ;     
       ;           


                                       f(x
 0)  1  x _ 0  x0  x:
pODSTAWLQQ W (3), POLU^IM
                                     f(x
 y) = x + y  (x0  y) _ (x  y0 ):

   2.2. nORMALXNYE FORMY BULEWYH FUNKCIJ. nA OSNOWE TEOREMY 2.1.1, WSQKAQ BULEWA
FUNKCIQ MOVET BYTX PREDSTAWLENA NEKOTOROJ FORMULOJ ALGEBRY WYSKAZYWANIJ. lEGKO PONQTX,
^TO I WSQKAQ FORMULA ALGEBRY WYSKAZYWANIJ, PREDSTAWLQET NEKOTORU@ BULEWU FUNKCI@. w ^AST-
NOSTI, ODNOJ IZ TAKIH PREDSTAWLQ@]IH FORMUL BUDET SOWERENNAQ DIZ_@NKTIWNAQ NORMALX-
NAQ FORMA (ESLI DANNAQ BULEWA FUNKCIQ NE QWLQETSQ TOVDESTWENNYM NULEM) ILI SOWERENNAQ
KON_@NKTIWNAQ NORMALXNAQ FORMA (ESLI BULEWA FUNKCIQ NE TOVDESTWENNAQ EDINICA). oTYSKAW
SOWERENNYE NORMALXNYE FORMY DLQ FORMULY ALGEBRY WYSKAZYWANIJ, PREDSTAWLQ@]EJ DAN-
NU@ BULEWU FUNKCI@, MOVNO PEREJTI OT \TOJ FORMULY K FORMULXNOMU WYRAVENI@ DLQ DANNOJ
BULEWOJ FUNKCII. eGO BUDEM NAZYWATX SOWERENNOJ DIZ_@NKTIWNOJ (ILI KON_@NKTIWNOJ) NOR-
MALXNOJ FORMOJ DANNOJ BULEWOJ FUNKCII. kAVDAQ IZ NIH DLQ DANNOJ BULEWOJ FUNKCII, ELI ONA
SU]ESTWUET, EDINSTWENNA S TO^NOSTX@ DO PERESTANOWOK.
   nAHOVDENIE SOWERENNYH FORM DLQ BULEWYH FUNKCIJ, ZADANNYH TABLICEJ ZNA^ENIJ, PROWO-
DITSQ ANALOGI^NO TOMU, KAK \TO DELAETSQ W ALGEBRE WYSKAZYWANIJ. eSLI FUNKCIQ ZADANA W WIDE
FORMULY, TO NEOBHODIMO SNA^ALA NAJTI FORMULU, WYRAVA@]U@ DANNU@ FUNKCI@ ^EREZ OTRICA-
NIE, KON_@NKCI@ I DIZ_@NKCI@.
   2.3. zAMKNUTYE I SOBSTWENNYE KLASSY BULEWYH FUNKCIJ. wYE BYLO POKAZANO,
^TO L@BAQ BULEWA FUNKCIQ WYRAVAETSQ ^EREZ FUNKCII BAZISA f0 
 
 _g. |TO OZNA^AET, ^TO MOVNO
POSTROITX L@BOJ DWOI^NYJ PROCESSOR, IMEQ W RASPORQVENII \LEMENTY, REALIZU@]IE OTRICANIE,
                                                        81