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

                                                                         x 3. pOLNYE SISTEMY SWQZOK

   sWQZKU & PRINQTO NAZYWATX \{TRIH {EFERA" I OBOZNA^ATX SIMWOLOM j. sWQZKU _ INOGDA
NAZYWA@T \OPERACIQ pIRSA" I OBOZNA^A@T #. oDNAKO MY PREDPO^TEM MNEMONI^ESKIJ PODHOD K
OBOZNA^ENI@ \TIH SWQZOK.
tEOREMA 1. mNOVESTWA f&g I f_g QWLQ@TSQ POLNYMI SISTEMAMI SWQZOK.
dOKAZATELXSTWO. 1. iZ TABLICY ISTINNOSTI DLQ SWQZKI & LEGKO USMATRIWAETSQ RAWNOSILXNOSTX:
                                             :(a & b)  a & b:
   wOSPOLXZOWAWISX E@, POLU^IM:
                         :a  :(a & a)  a & a

                         a _ b  :(:a & :b)  :(:(a & a) & :(b & b)) 
                                 :((a & a) & (b & b))  (a & a) & (b & b):
   tAKIM OBRAZOM, POLU^ENY RAWNOSILXNOSTI:
                                        :a  a & a

                                        a _ b  (a & a) & (b & b):
   iSPOLXZUQ IH, RAWNOSILXNYMI PREOBRAZOWANIQMI KAVDU@ FORMULU IZ f:
 _g MOVNO PRIWES-
TI K NEKOTOROJ FORMULE IZ f&g, TO ESTX WSQKAQ FORMULA IZ f:
 _g RAWNOSILXNA NEKOTOROJ
FORMULE IZ f&g. kROME TOGO, f:
 _g | P. S. S. pO TEOREME 3.2.1, P. 2, f&g | TOVE P. S. S.
   2. pOLNOTA SISTEMY SWQZOK f_g DOKAZYWAETSQ ANALOGI^NO PREDYDU]EMU. pO\TOMU MY PRIWE-
DEM LIX NEOBHODIMYE DLQ RASSUVDENIQ RAWNOSILXNOSTI, KOTORYE TAKVE NEOBHODIMO PROWERITX.
                                     :a  (a _ a)

                                     a & b  (a _ a) _ (b _ b):

   3.5. iSKL@^ITELXNOSTX SWQZOK & I _.
tEOREMA 1. eSLI  2 ! I fg P S S TO  = & ILI  = _
                               |    .    .   .,                      .

dOKAZATELXSTWO. 1. pREDPOLOVIM, ^TO SWQZKA  ODNOMESTNAQ. tOGDA WSQKAQ FORMULA IZ fg
IMEET WID: a =   : : :  A, GDE A | NEKOTORAQ WYSKAZYWATELXNAQ PEREMENNAQ. tOGDA PRI A = 1,
a = 1 LIBO a = 0.
   pUSTX PRI A = 1, a = 1. fORMULA A & B PRI A = 1, B = 0 PRINIMAET ZNA^ENIE A & B = 0, A
PRI A = 1, B = 1, A & B = 1, TO ESTX FORMULA A & B PRI A = 1 MOVET PRINIMATX KAK ZNA^ENIE
RAWNOE 0, TAK I RAWNOE 1. tOVE SAMOE WERNO I DLQ WSQKOJ FORMULY WIDA b =   : : :  B. tAKIM
OBRAZOM, FORMULA A & B NERAWNOSILXNA NIKAKOJ FORMULE IZ fg. sLEDOWATELXNO, ODNOMESTNYE
SWQZKI NE MOGUT UDOWLETWORQTX USLOWI@ TEOREMY.
   2. pUSTX  | DWUMESTNAQ SWQZKA, A I B | WYSKAZYWATELXNYE PEREMENNYE.
   A) pREDPOLOVIM, ^TO A  B = 1, PRI A = 1 I B = 1. tOGDA L@BAQ FORMULA a = a(A1
 A2 
 : : :An ),
SODERVA]AQ LIX SWQZKU , PRI A1 = A2 =  = An = 1 PRINIMAET ZNA^ENIE, RAWNOE 1, I POTOMU
NERAWNOSILXNA, NAPRIMER, FORMULE b(A1 
 A2) = :A1 & A2, TAK KAK b(1
 1) = 0. tAKIM OBRAZOM,
A  B = 0 PRI A = B = 1.
   b) tEPERX PREDPOLOVIM, ^TO A  B = 0, PRI A = B = 0. w \TOM SLU^AE WSQKAQ FORMULA
a = a(A1 
 A2
 : : :
 An) 2 fg, PRI A1 = A2 =  = An = 0 PRINIMAET ZNA^ENIE, RAWNOE 0, A
POTOMU NE MOVET BYTX RAWNOSILXNA, NAPRIMER, FORMULE b(A1 
 A2) = :A1 _ A2 , TAK KAK b(0
 0) = 1.
tAKIM OBRAZOM, A  B = 1, PRI A = B = 0
   c) tAKIM OBRAZOM, DLQ A  B IMEEM SLEDU@]U@, NE DO KONCA OPREDELENNU@, TABLICU ISTIN-
NOSTI.
                                              A   B AB
                                              1   1  0
                                              1   0
                                              0   1
                                              0   0  1

                                                    71