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

gLAWA   VI.   aLGEBRA PRELIKATOW

WOZMOVNOSTI (1 
 : : :
 m ). a TAK KAK (1 
 : : :
 n 1 
 : : :
 m ) QWLQETSQ OB]EJ LOGI^ESKOJ WOZMOV-
NOSTX@ DLQ FORMUL a(A1 
 : : :
 An) I b(B1 
 : : :
 Bm ), TO ZNA^ENIQ a(A1 
 : : :
 An) I b(B1 
 : : :
 Bm )
SOWPADA@T. oTS@DA SLEDUET SOWPADENIE ZNA^ENIJ a00 I b00 W WYBRANNOJ DLQ NIH OB]EJ LOGI^ESKOJ
WOZMOVNOSTI. w SILU PROIZWOLXNOSTI LOGI^ESKOJ WOZMOVNOSTI, INTERPRETACII I MNOVESTWA M
POLU^AEM, ^TO a0  b0 .
  3.3. nEZAWISIMOSTX FORMUL OT SWQZANNYH PEREMENNYH.
tEOREMA 1. pUSTX x NEKOTORAQ SWOBODNAQ PREDMETNAQ PEREMENNAQ W FORMULE a = a(x) A
                          |                                                                             ,
BUKWA y NE WHODIT W ZAPISX FORMULY a. tOGDA
                                           8x a(x)  8y a(y)

                                           9x a(x)  9y a(y):
   dOKAZATELXSTWO NEPOSREDSTWENNO SLEDUET IZ OPREDELENIQ KWANTORNYH OPERACIJ.
  3.4. wYNESENIE OTRICANIQ ZA KWANTORY.
tEOREMA 1. pUSTX x NEKOTORAQ SWOBODNAQ PREDMETNAQ PEREMENNAQ W FORMULE a = a(x)
                           |                                                                                .
tOGDA
                                          :8x a(x)  9x :a(x)

                                          :9x a(x)  8x :a(x):
dOKAZATELXSTWO. pUSTX M | PROIZWOLXNO FIKSIROWANNOE MNOVESTWO, DOPUSTIMOE DLQ RAS-
SMATRIWAEMYH FORMUL. zAFIKSIRUEM NEKOTORU@ SOWMESTNU@ INTERPRETACI@ \TIH FORMUL NA M
I NEKOTORU@ LOGI^ESKU@ WOZMOVNOSTX W \TOJ INTERPRETACII. tOGDA W \TOJ LOGI^ESKOJ WOZMOV-
NOSTI IMEEM: :8x a0 (x) = 1 () 8x a0 (x) = 0, () NE DLQ L@BOGO a 2 M: a0 (a) = 1 () SU]ESTWUET
b 2 M: a0 (b) = 0 () SU]ESTWUET b 2 M: :a0(b) = 1 () 9x :a0(x) = 1. w SILU PROIZWOLXNOSTI
MNOVESTWA M, INTERPRETACII I LOGI^ESKOJ WOZMOVNOSTI POLU^AEM, ^TO :8x a(x)  9x :a(x).
   wTORAQ FORMULA DOKAZYWAETSQ ANALOGI^NO.
  3.5. wYNESENIE KWANTOROW ZA OPERACII KON_@NKCII I DIZ_@NKCII.
tEOREMA 1. pUSTX a(x) I b(x) NEKOTORYE FORMULY x SWOBODNAQ PREDMETNAQ PEREMENNAQ
                                   |                         ,   |
W NIH. d | FORMULA, NE SODERVA]AQ WHOVDENIJ BUKWY x. tOGDA ISTINNY SLEDU@]IE RAWNOSILX-
NOSTI:
                                    8x (a(x) & b(x))  8x a(x) & 8x b(x)
                               (1)
                                    9x (a(x) & d)  9x a(x) & d
                                        (2)
                                    9x (a(x) _ b(x))  9x a(x) _ 9x b(x)
                               (3)
                                    8x (a(x) _ d)  8x a(x) _ d:                                        (4)
dOKAZATELXSTWO. zAFIKSIRUEM PROIZWOLXNOE DOPUSTIMOE MNOVESTWO M I SOWMESTNU@ INTER-
PRETACI@ FORMUL, SOSTAWLQ@]IH RAWNOSILXNOSTX. dALEE, ZAFIKSIRUEM OB]U@ LOGI^ESKU@ WOZ-
MOVNOSTX W \TOJ INTERPRETACII. tOGDA IMEEM:
   (1) 8x(a0 (x) & b0(x)) = 1 () DLQ L@BOGO \LEMENTA a 2 M: a0 (a) & b0 (a) = 1 () DLQ L@BOGO
\LEMENTA a 2 M: a0(a)   = 1 I DLQ L@BOGO \LEMENTA a 2 M: b0 (a) = 1 () 8x a0 (x) = 1 I 8x b0 (x) = 1
() 8x a0(x) & 8x b (x) = 1.
                    0
   w SILU PROIZWOLXNOSTI M, INTERPRETACII I LOGI^ESKOJ WOZMOVNOSTI ZAKL@^AEM, ^TO FOR-
MULA (1) DOKAZANA.
   (2) 9x (a0 (x) & d0) = 1 () SU]ESTWUET \LEMENT a 2 M: a0 (a) & d0 = 1 () SU]ESTWUET a 2 M
TAKOJ, ^TO a0 (a) = 1 I d0 = 1 () 9x a0 (x) & d0 = 1.
   w SILU PROIZWOLXNOSTI M, INTERPRETACII I LOGI^ESKOJ WOZMOVNOSTI ZAKL@^AEM, ^TO FOR-
MULA (2) DOKAZANA.
   (3), (4) DOKAZYWAETSQ ANALOGI^NO.

                                                    112