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

   x   3.   rAWNOSILXNYE FORMULY ALGEBRY PREDIKATOW
       rAWNOSILXNYE FORMULY tEOREMA O PODSTANOWKAH W RAWNOSILXNYE FORMULY ALGEBRY WYSKAZY
                                .                                                                        -

       WANIJ nEZAWISIMOSTX FORMUL OT SWQZANNYH PEREMENNYH wYNESENIE OTRICANIQ ZA KWANTORY
            .                                                      .                                     .

       wYNESENIE KWANTOROW ZA OPERACII KON_@NKCII I DIZ_@NKCII pERESTANOWKA KWANTOROW
                                                                         .                           .




   3.1. rAWNOSILXNYE FORMULY ALGEBRY PREDIKATOW. pUSTX a I b | NEKOTORYE FOR-
MULY, A M | MNOVESTWO, DOPUSTIMOE DLQ \TIH FORMUL    . sOWMESTNOJ INTERPRETACIEJ FORMUL a
I b NA MNOVESTWE M NAZYWAETSQ WSQKAQ PARA ha0 
 b0 i INTERPRETACIJ DLQ a I b, PRI KOTORYH
PEREMENNYE PREDIKATY, WHODQ]IE W a I b ODNOWREMENNO, ODINAKOWO INTERPRETIRU@TSQ NA M.
   nAPOMNIM, ^TO INTERPRETACII a0 I b0 QWLQ@TSQ PREDIKATAMI NA M I POTOMU IMEET SMYSL
GOWORITX OB OB]IH LOGI^ESKIH WOZMOVNOSTQH DLQ a0 I b0 NA M.
oPREDELENIE 1. dWE FORMULY a I b NAZYWA@TSQ RAWNOSILXNYMI NA MNOVESTWE M TOGDA I
TOLXKO TOGDA, KOGDA M QWLQETSQ DOPUSTIMYM DLQ a I b I W L@BOJ SOWMESTNOJ INTERPRE-
TACII a0 , b0 PREDIKATY a0 I b0 PRINIMA@T ODINAKOWYE ZNA^ENIQ ISTINNOSTI WO WSEH OB]IH
LOGI^ESKIH WOZMOVNOSTQH DLQ a0 I b0 NA M LIBO KOGDA M NE QWLQETSQ DOPUSTIMYM NI DLQ a,
NI DLQ b. oBOZNA^AETSQ: a M b.
   iZ OPREDELENIQ NEPOSREDSTWENNO SLEDUET, ^TO ESLI MNOVESTWO M QWLQETSQ DOPUSTIMYM DLQ
ODNOJ IZ FORMUL a I b I NE QWLQETSQ DOPUSTIMYM DLQ DRUGOJ, TO a I b NA M NERAWNOSILXNY.
oPREDELENIE 2. dWE FORMULY a I b NAZYWA@TSQ RAWNOSILXNYMI, ESLI ONI RAWNOSILXNY NA
L@BOM MNOVESTWE.
   sLEDU@]AQ NIVE TEOREMA SWQZYWAET PONQTIQ RAWNOSILXNOSTI I OB]EZNA^IMOSTI.
tEOREMA 1. pUSTX DLQ FORMUL a I b L@BOE MNOVESTWO QWLQETSQ DOPUSTIMYM. tOGDA:
                              a  b () a  b | OB]EZNA^IMA.
dOKAZATELXSTWO. pUSTX M | PROIZWOLXNOE MNOVESTWO, a0  b0 | PROIZWOLXNAQ INTERPRETACIQ
FORMULY a  b NA M. |TA INTERPRETACIQ, O^EWIDNO, BUDET SOWMESTNOJ INTERPRETACIEJ     a0 , b0
FORMUL a I b NA M. zAFIKSIRUEM PROIZWOLXNU@  LOGI^ESKU@ WOZMOVNOSTX DLQ a  b . oNA BUDET
                                                                           0   0
OB]EJ LOGI^ESKOJ WOZMOVNOSTX@ DLQ a0, b0. o^EWIDNO, ^TO W \TOJ LOGI^ESKOJ WOZMOVNOSTI a0
I b0 PRINIMA@T ODINAKOWYE ZNA^ENIQ TOGDA I TOLXKO TOGDA, KOGDA a0  b0 PRINIMAET ZNA^E-
NIE, RAWNOE 1. w SILU PROIZWOLXNOSTI WYBRANNOGO MNOVESTWA M, INTERPRETACII I LOGI^ESKOJ
WOZMOVNOSTI POLU^AEM NUVNOE.
  3.2. tEOREMA O PODSTANOWKAH W RAWNOSILXNYE FORMULY ALGEBRY WYSKAZYWANIJ.
tEOREMA 1. eSLI W RAWNOSILXNYE FORMULY ALGEBRY WYSKAZYWANIJ PODSTAWITX WMESTO WYSKA                            -
ZYWATELXNYH PEREMENNYH FORMULY ALGEBRY PREDIKATOW, DLQ KOTORYH L@BOE MNOVESTWO DOPUS-
TIMO, TO POLU^ENNYE FORMULY ALGEBRY PREDIKATOW BUDUT TAKVE RAWNOSILXNY.
dOKAZATELXSTWO.
     pUSTX a(A1 
 : : :
 An)  b(B1 
 : : :
 Bm ), GDE A1 
 : : :
 An I B1 
 : : :
 Bm | WYSKAZYWATELXNYE PERE-
MENNYE, a1 
 : : :
 an I b1 
 : : :
 bm | FORMULY ALGEBRY PREDIKATOW, DLQ KOTORYH L@BOE MNOVESTWO
DOPUSTIMO, M | PROIZWOLXNO FIKSIROWANNOE MNOVESTWO I a0 = a(a1 
 : : :
 an ), b0 = b(b1 
 : : :
 bm ).
nEOBHODIMO POKAZATX, ^TO a0 M b0.
     zAFIKSIRUEM SOWMESTNU@ INTERPRETACI@ a00 , b00 DLQ FORMUL a0, b0 NA MNOVESTWE                   M. pRI \TOM
a1 
 : : :
 an, b1 
 : : :
 bm TAKVE POLU^AT NEKOTORU@ INTERPRETACI@ a01
 : : :
 a0n , b01
 : : :
 b0m NA MNOVES-
TWE M, PRI^EM a00 = a(a01
 : : :
 a0n ), b00 = 0b(b01
 : : :
 b0m ).
     zAFIKSIRUEM DLQ PREDIKATOW a00 I b0 NEKOTORU@ OB]U@ LOGI^ESKU@0 WOZMOVNOSTX                      NA M. tOGDA
W \TOJ LOGI^ESKOJ WOZMOVNOSTI KAVDYJ IZ PREDIKATOW a01 
 : : :
 a0n , b1 
 : : :
 b0m POLU^IT SOOTWET-
STWENNO ZNA^ENIE 1
 : : :
 n 1
 : : :
 m 2 f0
 1g. nO a(1
 : : :
 n) RAWNO ZNA^ENI@ a(A1 
 : : :
 An) W
LOGI^ESKOJ WOZMOVNOSTI (1 
 : : :
 n), A b(1 
 : : :
 m ) RAWNO ZNA^ENI@ b(B1 
 : : :
 Bm ) W LOGI^ESKOJ
                                                      111