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

                                       x 1. bULEWY FUNKCII. rEALIZACIQ BULEWYH FUNKCIJ FORMULAMI

   g8 (x
 y) = x  y | \KWIWALENCIQ,
   g11(x
 y) = x _ y | DIZ_@NKCIQ,
   g12(x
 y) = x j y | TRIH {EFFERA,
   g13(x
 y) = x ! y | IMPLIKACIQ.
   tABLICA ZNA^ENIJ BULEWOJ FUNKCII NAZYWAETSQ TABLICEJ ISTINNOSTI. l@BU@ BULEWU FUNK-
CI@ OT n PEREMENNYH f(x1 
 x2
 : : :
 xn) MOVNO ZADATX TABLICEJ ISTINNOSTI:
                                  x1 x2 : : : xn f(x1 
 x2
 : : :
 xn)
                                   0 0 ::: 0                   1
                                   1 0 ::: 0                   2
                                   0 1 ::: 0                   3
                                  ::: ::: ::: :::            :::
                                   1 1 ::: 1                  2n

GDE i 2 f0
 1g, i = 1
 2
 : : :
 2n. w \TOJ TABLICE IMEETSQ 2n STROK, SOOTWETSTWU@]IH RAZLI^NYM
KOMBINACIQM ZNA^ENIJ PEREMENNYH, KOTORYM MOVNO SOPOSTAWITX 22n RAZLI^NYH STOLBCOW. nO
KAVDYJ TAKOJ STOLBEC SOOTWETSTWUET KAKOJ-TO BULEWOJ FUNKCII OT n PEREMENNYH. tAKIM OBRA-
ZOM, DOKAZANA
tEOREMA 1. ~ISLO RAZLI^NYH BULEWYH FUNKCIJ OT n PEREMENNYH RAWNO 22n ILI jPnj = 22n .
  1.2. sU]ESTWENNYE I NESU]ESTWENNYE PEREMENNYE.
oPREDELENIE 1. gOWORQT ^TO BULEWA FUNKCIQ f 2 Pn SU]ESTWENNO ZAWISIT OT PEREMEN
                             ,                                                                      -
NOJ xi, ESLI SU]ESTWUET TAKOJ NABOR ZNA^ENIJ PEREMENNYH a1 
 : : :
 ai;1
 ai+1
 : : :
 an, ^TO
                  f(a1 
 : : :
 ai;1
 0
 ai+1
 : : :
 an) 6= f(a1 
 : : :
 ai;1
 1
 ai+1
 : : :
 an):
   w \TOM SLU^AE xi NAZYWAETSQ SU]ESTWENNOJ PEREMENNOJ, W PROTIWNOM SLU^AE xi | NESU]EST-
WENNAQ (FIKTIWNAQ) PEREMENNAQ.
pRIMER 1. pUSTX BULEWY FUNKCII f1, f2 I f3 ZADANY TABLICAMI ISTINNOSTI:
                                             x y f1 f2 f3
                                              1 1 0 1 1
                                              1 0 0 1 0
                                              0 1 1 1 0
                                              0 0 1 1 0
wIDNO, ^TO DLQ f1 PEREMENNAQ x QWLQETSQ SU]ESTWENNOJ, A y | NESU]ESTWENNOJ DLQ f2 OBE
PEREMENNYE NESU]ESTWENNYE DLQ f3 OBE PEREMENNYE SU]ESTWENNYE.
   pO OPREDELENI@ BUDEM S^ITATX BULEWY FUNKCII RAWNYMI, ESLI ODNA IZ DRUGOJ POLU^AETSQ
UDALENIEM ILI WWEDENIEM NESU]ESTWENNYH PEREMENNYH. pO\TOMU DALEE BULEWY FUNKCII RASSMAT-
RIWA@TSQ S TO^NOSTX@ DO NESU]ESTWENNYH PEREMENNYH. |TO POZWOLQET S^ITATX, ^TO WSE BULEWY
FUNKCII DANNOGO MNOVESTWA BULEWYH FUNKCIJ OT OGRANI^ENNOGO W SOWOKUPNOSTI ^ISLA PEREMEN-
NYH ZAWISQT OT ODNIH I TEH VE PEREMENNYH. tAKOE MNOVESTWO BULEWYH FUNKCIJ MOVNO TAKVE
OBOZNA^ATX Pn , n = maxmi , GDE mi | KOLI^ESTWO SU]ESTWENNYH PEREMENNYH i-OJ FUNKCII IZ Pn.
   1.3. rEALIZACIQ BULEWYH FUNKCIJ FORMULAMI. pUSTX  = ff1
 f2
 : : :
 fmg | MNO-
VESTWO BULEWYH FUNKCIJ.
oPREDELENIE 1. fORMULOJ NAD  NAZYWAETSQ WYRAVENIE WIDA
                                    F] = f(t1 
 t2
 : : :
 tn)

GDE f 2  I ti LIBO PEREMENNAQ, LIBO FORMULA NAD .

                                                   75