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

UptoLike

ВУЗ: 

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

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

Рубрика: 

   x   3.   pOLNOTA, NEPROTIWORE^IWOSTX I RAZRE IMOSTX iw nEZAWISI-
            MOSTX AKSIOM iw
       pOLNOTA iw OTNOSITELXNO aw nEPROTIWORE^IWOSTX iw rAZREIMOSTX iw nEZAWISIMOSTX
                                   .                                       .   .

       SHEM AKSIOM iw mNOGOZNA^NYE LOGIKI
                     .                         .




  3.1. pOLNOTA iw OTNOSITELXNO aw.
oPREDELENIE 1. pUSTX0 T NEKOTORAQ SODERVATELXNAQ AKSIOMATI^ESKAQ TEORIQ
                             |                                                  | EE ,   T0
FORMALIZACIQ. tEORIQ T NAZYWAETSQ POLNOJ OTNOSITELXNO TEORII T, ESLI WYWODIMYE FORMU-
LY TEORII T0 I TOLXKO ONI QWLQ@TSQ TEOREMAMI TEORII T.
tEOREMA 1. iw QWLQETSQ POLNOJ TEORIEJ OTNOSITELXNO aw, TO ESTX FORMULA aw QWLQETSQ
TAWTOLOGIEJ TOGDA I TOLXKO TOGDA, KOGDA SU]ESTWUET RAWNOSILXNAQ EJ FORMULA, WYWODIMAQ
W iw.
dOKAZATELXSTWO. 1. rANEE POKAZANO, ^TO WSE AKSIOMY iw QWLQ@TSQ TAWTOLOGIQMI. kROME TOGO,
LEGKO POKAZATX, ^TO PRIMENENIE PRAWILA MP K TAWTOLOGII DAET W REZULXTATE TAKVE TAWTOLOGI@.
|TO I OZNA^AET, ^TO WSQKAQ FORMULA, WYWODIMAQ W iw QWLQETSQ TAWTOLOGIEJ W aw.
   2. pUSTX c | TAWTOLOGIQ aw. tAK KAK SISTEMA SWQZOK f: !g QWLQETSQ POLNOJ, TO L@BU@ FOR-
MULU aw RAWNOSILXNYMI PREOBRAZOWANIQMI MOVNO PRIWESTI K FORMULE, SODERVA]EJ W KA^ESTWE
LOGI^ESKIH SWQZOK LIX f: !g. pO\TOMU
                                                     c  a
GDE a | FORMULA OT SWQZOK f: !g I POTOMU a | FORMULA iw.
   pUSTX a = a(B1  B2  : : : Bk ). pO TEOREME O WYWODIMOSTI
                                           B10  B20  : : : Bk0 ` a0 :
TAK KAK a | TAWTOLOGIQ, TO W L@BOJ LOGI^ESKOJ WOZMOVNOSTI a0 = a, TO ESTX
                                           B10  B20  : : : Bk0 ` a:                        (1)
pRI Bk = 1 POLU^AEM
                                          B10  : : : Bk0 ;1 Bk ` a                        (2)
A PRI Bk = 0 POLU^AEM
                                  B10  : : : Bk0 ;1 :Bk ` a:                               (3)
   pRIMENQQ TEOREMU DEDUKCII K (2) I (3), POLU^AEM:
                                       B10  : : : Bk0 ;1 ` (Bk ! a)                         (4)
                                       B10  : : : Bk0 ;1 ` (:Bk ! a)                        (5)
pO LEMME 2.5.1 IMEEM:
                                   ` (Bk ! a) ! ((:Bk ! a) ! a)                               (6)
   pRIMENQQ MP K (4), (6), A ZATEM K (5) I POLU^ENNOJ FORMULE, POLU^IM, ^TO
                                            B10  : : : Bk0 ;1 ` a:                          (7)
   sRAWNIWAQ (7) S (1) ZAME^AEM, ^TO Bk0 MOVNO PROSTO UDALITX IZ POSYLKI BEZ U]ERBA DLQ
ISTINNOSTI WYWODIMOSTI. nO TOVE SAMOE MOVNO SDELATX I S Bk0 ;1 , ZATEM S Bk0 ;2 I T. D. w KONCE
KONCOW MY PRIDEM K SLEDU@]EJ WYWODIMOSTI: ` a.
                                                       96

Страницы