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

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

Составители: 

Рубрика: 

   x    3.   pOLNYE SISTEMY SWQZOK
        oPREDELENIE POLNOJ SISTEMY SWQZOK sWOJSTWA POLNYH SISTEM SWQZOK oPISANIE P S S IZ
                                        .                             .          .   .   .   .

        oDNO\LEMENTNYE P S S iSKL@^ITELXNOSTX SWQZOK I _
                        .   .   .                     &     .




   3.1. oPREDELENIE POLNOJ SISTEMY SWQZOK. rANEE BYLI ODNOZNA^NO OPREDELENY PQTX
OSNOWNYH LOGI^ESKIH SWQZOK, ISPOLXZUEMYH W QZYKE ALGEBRY WYSKAZYWANIJ DLQ ZAPISI FORMUL.
oBOZNA^IM:
                                       = f: & _ ! g:
   oTMETIM, ^TO ^TO MOVNO WWESTI I DRUGIE SWQZKI (OPREDELITX TABLICAMI ISTINNOSTI), OT-
LI^NYE OT SWQZOK IZ .
   wSEGO RAZLI^NYH UNARNYH SWQZOK MOVNO OPREDELITX 4, A BINARNYH | 16 (SM. UPR. 1). w  VE
WSEGO ODNA UNARNAQ SWQZKA I 4 BINARNYH. sWQZKI IZ  BUDEM NAZYWATX OSNOWNYMI SWQZKAMI. mNO-
VESTWO WSEH UNARNYH I BINARNYH SWQZOK (A WSEGO IH 20) OBOZNA^IM ^EREZ !. pONQTNO, ^TO  !.
eSLI !1 | NEKOTOROE MNOVESTWO SWQZOK, TO ESTX !1  !, TO OBOZNA^IM ^EREZ f!1 g MNOVESTWO
WSEWOZMOVNYH FORMUL aw, W ZAPISI KOTORYH MOGUT U^ASTWOWATX LIX SWQZKI IZ !1. iNA^E GO-
WORQ, f!1 g SOSTOIT IZ FORMUL, NE SODERVA]IH W SWOEJ ZAPISI SWQZOK IZ ! n !1 . tAK, NAPRIMER,
PROSTEJIE FORMULY, TO ESTX BUKWY LATINSKOGO ALFAWITA, SNABVENNYE, BYTX MOVET, TRIHA-
MI ILI INDEKSAMI, WHODQT W f!1g DLQ L@BOGO PODMNOVESTWA !1 MNOVESTWA !. iZ OPREDELENIQ
f!1g NEPOSREDSTWENNO SLEDU@T O^EWIDNYE SWOJSTWA 1{2.
   1. fg | MNOVESTWO WSEWOZMOVNYH FORMUL ALGEBRY WYSKAZYWANIJ (aw).
   2. eSLI !1  !2  !, TO f!1 g  f!2g.
oPREDELENIE 1. mNOVESTWO !1 SWQZOK IZ ! NAZYWAETSQ POLNOJ SISTEMOJ SWQZOK (P. S. S.),
ESLI WSQKAQ FORMULA IZ fg RAWNOSILXNA NEKOTOROJ FORMULE IZ f!1g.
pRIMER 1. eSLI W KA^ESTWE !1 WOZXMEM , TO PONQTNO, ^TO WSQKAQ FORMULA IZ () RAWNOSILXNA
NEKOTOROJ FORMULE IZ fg. tAKIM OBRAZOM,  | POLNAQ SISTEMA SWQZOK.
pRIMER 2. pOLXZUQSX PRAWILOM ISKL@^ENIQ \KWIWALENCII
                                     a  b  (a ! b) & (b ! a)
RAWNOSILXNYMI PREOBRAZOWANIQMI WSQKU@ FORMULU MOVNO PRIWESTI K WIDU, W KOTOROM NET OPERA-
CII . sLEDOWATELXNO, WSQKAQ FORMULA IZ fg RAWNOSILXNA NEKOTOROJ FORMULE IZ f: & _ !g.
|TO OZNA^AET, ^TO MNOVESTWO f: & _ !g | P. S. S.
  3.2. sWOJSTWA POLNYH SISTEM SWQZOK.
tEOREMA 1. pOLNYE SISTEMY SWQZOK OBLADA@T SLEDU@]IMI SWOJSTWAMI            :
   1) ESLI KAKOE-TO MNOVESTWO SWQZOK !1 SODERVIT NEKOTORU@ P. S. S., TO !1 | TOVE P. S. S.
   2) ESLI !1 | P. S. S. I WSQKAQ FORMULA IZ (!1 ) RAWNOSILXNA KAKOJ-TO FORMULE IZ (!2 )
DLQ NEKOTOROJ SISTEMY SWQZOK !2, TO !2 TOVE P. S. S.
dOKAZATELXSTWO. 1) nEPOSREDSTWENNO SLEDUET IZ OPREDELENIQ P. S. S.
   2) pUSTX a 2 (). tAK KAK !1 | P. S. S., TO a  b DLQ NEKOTOROJ FORMULY b IZ (!1). pO
USLOWI@ b  c DLQ NEKOTOROJ c IZ (!2 ). pO TRANZITIWNOSTI OTNOENIQ RAWNOSILXNOSTI IMEEM:
                                       a  c I c 2 (!2 )
   |TO OZNA^AET, ^TO !2 | P. S. S.
pRIMER 1. pOLXZUQSX PRAWILOM ISKL@^ENIQ IMPLIKACII
                                        a ! b  :a _ b
RAWNOSILXNYMI PREOBRAZOWANIQMI WSQKU@ FORMULU aw IZ f: & _ !g MOVNO PRIWESTI K WIDU,
W KOTOROM NET OPERACII !. |TO OZNA^AET, ^TO WSQKAQ FORMULA IZ f: & _ !g RAWNOSILXNA
NEKOTOROJ FORMULE IZ f: & _g I f: & _ !g | P. S. S., SM. PRIMER 3.1.2. pRIMENQQ P. 2
TEOREMY 3.2.1, POLU^AEM, ^TO f: & _g | P. S. S.
                                                69

Страницы