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

UptoLike

ВУЗ: 

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

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

Рубрика: 

                                                                          x 2. tEOREMA O WYWODIMOSTI

   2.6. tEOREMA O WYWODIMOSTI. pUSTX a = a(B1 : : : Bk) | FORMULA OT B1 : : : Bk WY-
SKAZYWATELXNYH PEREMENNYH.  | NEKOTORAQ LOGI^ESKAQ WOZMOVNOSTX FORMULY a. pOLOVIM:
                      (
                   0
                 Bi =    Bi  ESLI Bi = 1 W LOGI^ESKOJ WOZMOVNOSTI 
                        :Bi ESLI Bi = 0 W LOGI^ESKOJ WOZMOVNOSTI :
                            (
                                      a ESLI a = 1 W LOGI^ESKOJ WOZMOVNOSTI 
                     a0 =
                                     :a ESLI a = 0 W LOGI^ESKOJ WOZMOVNOSTI :
tEOREMA 1.   B10  B20  : : : Bk0 ` a0 .
   pREVDE, ^EM PRISTUPITX K DOKAZATELXSTWU TEOREMY, PROILL@STRIRUEM EE SMYSL NA PRIMERE.
   pUSTX a(A B) = A ! (B ! :A). sOSTAWIM TABLICU ISTINNOSTI \TOJ FORMULY.
                                AB B ! :A A ! (B ! :A)
                                1 1        0                0
                                1 0        1                1
                                0 1        1                1
                                0 0        1                1
   rASSMOTRIM PERWU@ STROKU \TOJ TABLICY ISTINNOSTI. o^EWIDNO, ^TO
                       A0 = A, B 0 = B, a0 (A B) = :(A ! (B ! :A)).
tEOREMA UTWERVDAET, ^TO DLQ \TOJ LOGI^ESKOJ WOZMOVNOSTI SPRAWEDLIWA WYWODIMOSTX:
                                      A0  B 0 ` a0 (A B)
TO ESTX
                                    A B ` :(A ! (B ! :A)).
aNALOGI^NO, DLQ WTOROJ, TRETXEJ I ^ETWERTOJ STROK SOOTWETSTWU@]IE WYWODIMOSTI IME@T WID:
                                      A :B ` A ! (B ! :A)
                                     :A B ` A ! (B ! :A)
                                     :A :B ` A ! (B ! :A):
tEPERX PRISTUPIM K DOKAZATELXSTWU TEOREMY.
dOKAZATELXSTWO. iNDUKCIQ PO KOLI^ESTWU n LOGI^ESKIH SWQZOK W a.
    n = 0. tOGDA FORMULA a ESTX BUKWA B1 . tAK KAK a = B1 , TO PRI B1 = 1 I a = 1. sLEDOWATELXNO
B10 = B1 , a0 = a = B1 . o^EWIDNO, ^TO B1 ` B1 = a. pRI B1 = 0 I a = 0. sLEDOWATELXNO B10 = :B1,
a0 = :a = :B1. tAKVE O^EWIDNO, ^TO :B1 ` :B1 .
    pREDPOLOVIM TEPERX, ^TO TEOREMA WERNA DLQ L@BOGO j, 0  j < n, A FORMULA a SODERVIT n
SWQZOK. tAK KAK n  1, TO FORMULA a MOVET IMETX ODIN IZ DWUH WIDOW (SM. OPREDELENIE FORMULY):
    1. a = :b DLQ NEKOTOROJ FORMULY b.
    2. a = (b ! c) DLQ NEKOTORYH FORMUL b I c.
    rASSMOTRIM KAVDYJ IZ \TIH SLU^AEW W OTDELXNOSTI.
    1. a = :b. dLQ FORMULY b UTWERVDENIE TEOREMY WERNO, TAK KAK b SODERVIT (n ; 1) SWQZOK.
    1a. b = 1. sLEDOWATELXNO, a = 0, TOGDA b0 = b, a0 = :a = ::b. pO INDUKTIWNOMU PREDPOLOVE-
NI@
                                        B10  : : : Bk0 ` b = b
                                                      0                                          (1)
nO, PO LEMME 2.1.1 b), ` (b ! ::b). sLEDOWATELXNO
                                      B10  : : : Bk0 ` b ! ::b:                                (2)
   iZ (1) I (2) PO MP POLU^AEM:
                                                  93

Страницы