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

UptoLike

ВУЗ: 

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

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

Рубрика: 

gLAWA   III.   aLGEBRA WYSKAZYWANIJ

tEOREMA 2. wSQKAQ POLNAQ SISTEMA SWQZOK IZ  SODERVIT SWQZKU :         .


dOKAZATELXSTWO. pUSTX M | MNOVESTWO WSEH FORMUL aw, NE SODERVA]IH W SWOEJ ZAPISI
SWQZKI :, TO ESTX M = f& _ ! g. lEGKO UBEDITXSQ W TOM, ^TO ESLI a(A1  : : : An) 2 M,
TO a(1 : : : 1) = 1. rASSMOTRIM FORMULU b(A B) = :A & B. o^EWIDNO, b(1 1) = 0, ZNA^IT
b(A B) 2 fg, NO b(A B) NERAWNOSILXNA NIKAKOJ FORMULE IZ f& _ ! g. |TO OZNA^AET,
^TO MNOVESTWO f& _ ! g NE QWLQETSQ P. S. S. pO TEOREME 3.2.1, P. 1, NIKAKOE PODMNOVESTWO
MNOVESTWA f& _ ! g NE QWLQETSQ P. S. S. |TO I OZNA^AET, ^TO WSQKAQ P. S. S. IZ  OBQZANA
SODERVATX OPERACI@ :.
    3.3. oPISANIE POLNYH SISTEM SWQZOK IZ . pO TEOREME 3.2.2, WSQKAQ P. S. S. IZ 
SODERVIT :. wOZNIKAET WOPROS O TOM, A NE QWLQETSQ LI ODNO\LEMENTNOE MNOVESTWO f:g P. S. S.?
oTWET DAET
tEOREMA 1. mNOVESTWO f:g NE QWLQETSQ P. S. S.
dOKAZATELXSTWO. oTMETIM, ^TO f:g SOSTOIT IZ WSEH BUKW ALFAWITA I FORMUL WIDA ::  | {z: : : :} A,
                                                                                      n
n 2 N. oDNAKO, NI ODNA IZ \TIH FORMUL NE QWLQETSQ TAWTOLOGIEJ. sLEDOWATELXNO, FORMULA A_:A,
NAPRIMER, NERAWNOSILXNA NIKAKOJ FORMULE IZ f:g. sLEDOWATELXNO, MNOVESTWO f:g NE QWLQETSQ
P. S. S.
tEOREMA 2. sLEDU@]IE NIVE MNOVESTWA SWQZOK IZ  QWLQETSQ P. S. S.:
        f: &g
        f: _g
   1)            


        f: !g
   2)            
   3)                .


dOKAZATELXSTWO. 1) f: &g. w PRIMERE 3.2.1 POKAZANO, ^TO MNOVESTWO f: & _g | P. S. S. pOLX-
ZUQSX RAWNOSILXNOSTX@
                                          a _ b  :(:a & :b)
WSQKU@ FORMULU IZ f: & _g RAWNOSILXNYMI PREOBRAZOWANIQMI MOVNO PRIWESTI K FORMULE, W
ZAPISI KOTOROJ NET OPERACII _. |TO OZNA^AET, ^TO WSQKAQ FORMULA IZ f: & _g RAWNOSILXNA
NEKOTOROJ FORMULE IZ f: &g. a TAK KAK f: & _g | P. S. S., TO PO TEOREME 3.2.1, P. 2, f: &g |
TOVE P. S. S.
   2) f: _g. rASSUVDENIQ TAKIE VE, KAK I W PREDYDU]EM PUNKTE S ISPOLXZOWANIEM RAWNOSILX-
NOSTI a & b  :(:a _ :b).
   3) f: !g. pOLXZUQSX RAWNOSILXNOSTX@ a _ b  :a ! b, WSQKU@ FORMULU IZ f: _g RAWNO-
SILXNYMI PREOBRAZOWANIQMI MOVNO PRIWESTI K FORMULE IZ f: !g, TO ESTX WSQKAQ FORMULA
IZ f: _g RAWNOSILXNA NEKOTOROJ FORMULE IZ f: !g I f: _g | P. S. S. sLEDOWATELXNO, PO
TEOREME 3.2.1, P.2, f: !g | TOVE P. S. S.
sLEDSTWIE 1. wSQKAQ SISTEMA SWQZOK IZ !, SODERVA]AQ SWQZKU : I HOTQ BY ODNU IZ SWQZOK
&, _, !, QWLQETSQ P. S. S.
   dOKAZATELXSTWO SLEDUET NEPOSREDSTWENNO IZ PREDYDU]EJ TEOREMY I TEOREMY 3.2.1, P. 1.
   3.4. oDNO\LEMENTNYE POLNYE SISTEMY SWQZOK. w P. III.3.3. DOKAZANO, ^TO SREDI SWQZOK
IZ  NET TAKOJ SWQZKI, KOTORAQ SOSTAWLQLA BY P. S. S. eSTX LI TAKIE SWQZKI NE W ? oTWET
POLOVITELXNYJ. wWEDEM DWE SWQZKI, KOTORYE OBOZNA^IM & I _, A SMYSL IH OPREDELIM TABLICAMI
ISTINNOSTI:
                                      A     B A&B A_B
                                      1     1  0   0
                                      1     0  1   0
                                      0     1  1   0
                                      0     0  1   1

                                                 70

Страницы