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

                   x 3. pOLNOTA, NEPROTIWORE^IWOSTX I RAZREIMOSTX iw. nEZAWISIMOSTX AKSIOM iw

   3.6. k-ZNA^NYE LOGIKI. nAZOWEM ^ISLA 0
 1
 : : :
 k ; 1 \ISTINNOSTNYMI ZNA^ENIQMI" I
WYBEREM KAKOE-NIBUDX ^ISLO m S USLOWIEM 1  m  k ; 1. ~ISLA 0
 1
 : : :
 m BUDEM NAZYWATX
WYDELENNYMI ISTINNOSTNYMI ZNA^ENIQMI. wOZXMEM NEKOTOROE KONE^NOE ^ISLO \ISTINNOSTNYH
TABLIC", PREDSTAWLQ@]IH FUNKCII, OTOBRAVA@]IE MNOVESTWO f0
 1
 : : :
 k ; 1g W SEBQ. dLQ KAV-
DOJ TABLICY WWEDEM ZNAK, KOTORYJ BUDEM NAZYWATX SOOTWETSTWU@]EJ \TOJ TABLICE LOGI^ESKOJ
SWQZKOJ. s POMO]X@ \TIH SWQZOK I PROPOZICIONALXNYH BUKW MY MOVEM STROITX FORMULY. kAV-
DAQ TAKAQ FORMULA OPREDELQET NEKOTORU@ \ISTINNOSTNU@ FUNKCI@", OTOBRAVA@]U@ MNOVES-
TWO f0
 1
 : : :
 k ; 1g W SEBQ. fORMULA, PRINIMA@]IE TOLXKO WYDELENNYE ZNA^ENIQ, NAZYWAETSQ
WYDELENNOJ. gOWORQT, ^TO ^ISLA k, m I OSNOWNYE ISTINNOSTNYE TABLICY OPREDELQ@T NEKOTORU@
k-ZNA^NU@ LOGIKU M.
pRIMER 1. aLGEBRA WYSKAZYWANIJ QWLQETSQ 2-ZNA^NOJ LOGIKOJ, SOOTWETSTWU@]EJ SLU^A@ k = 2,
m = 0 I ISTINNOSTNYMI TABLICAMI DLQ SWQZOK :, &, _, !, , KOTORYE WWODQTSQ ANALOGI^NO
TABLICAM GLAWY III S ZAMENOJ SIMWOLA 0 NA 1 I NAOBOROT. wYDELENNYE FORMULY \TOJ LOGIKI
NAZYWALISX TAWTOLOGIQMI.
pRIMER 2. dWE RAZLI^NYE 3-ZNA^NYE LOGIKI, SOOTWETSTWU@]IE SLU^A@ k = 3, m = 0 I WWEDEN-
NYMI ISTINNOSTNYMI TABLICAMI DLQ SWQZOK :, ! (SM. P. V.3.4.). |TI LOGIKI ISPOLXZOWALISX DLQ
DOKAZATELXSTWA NEZAWISIMOSTI SHEM AKSIOM a1 I a2 IS^ISLENIQ WYSKAZYWANIJ.
   dLQ MNOGOZNA^NYH LOGIK TAK VE KAK I DLQ ALGEBRY WYSKAZYWANIJ MOVNO OPREDELITX PONQTIQ
LOGI^ESKOJ WOZMOVNOSTI, SOWMESTNOJ LOGI^ESKOJ WOZMOVNOSTI, RAWNOSILXNOSTI FORMUL I T. D.
   lEGKO PONQTX, ^TO KAVDAQ TABLICA ISTINNOSTI OT n PROPOZICIONALXNYH BUKW OPREDELQET BES-
KONE^NO MNOGO RAWNOSILXNYH FORMUL k-ZNA^NOJ LOGIKI M. tAKIM OBRAZOM, KOLI^ESTWO WSEWOZ-
MOVNYH TAKIH TABLIC ISTINNOSTI RAWNO ^ISLU WSEH POPARNO NERAWNOSILXNYH FORMUL LOGIKI M
OT n BUKW.
   oBOZNA^IM ^EREZ Pk MNOVESTWO WSEH POPARNO NERAWNOSILXNYH FORMUL LOGIKI M OT n PROPO-
ZICIONALXNYH BUKW A1 
 A2
 : : :
 An. tAK KAK ^ISLO RAZLI^NYH NABOROW (1
 2
 : : :
 n) ZNA^ENIJ
BUKW A1
 A2 
 : : :
 An RAWNO kn , TO IMEEM SLEDU@]IJ REZULXTAT
tEOREMA 1. ~ISLO FORMUL LOGIKI M , ZAWISQ]IH OT n BUKW W Pk RAWNO kkn .
oPREDELENIE 1. fORMALXNAQ AKSIOMATI^ESKAQ TEORIQ, SODERVA]AQ PROPOZICIONALXNYE BUK-
WY I SWQZKI k-ZNA^NOJ LOGIKI M NAZYWAETSQ PODHODQ]EJ DLQ LOGIKI M , ESLI MNOVESTWO TE-
OREM \TOJ TEORII SOWPADAET S MNOVESTWOM WYDELENNYH FORMUL LOGIKI M .
   o^EWIDNO, ^TO WSE \TI PONQTIQ MOGUT BYTX OBOB]ENY NA SLU^AJ BESKONE^NOGO MNOVESTWA
ISTINNOSTNYH ZNA^ENIJ.
pRIMER 3. pUSTX M 0 | 2-ZNA^NAQ LOGIKA POLU^ENNAQ IZ ALGEBRY WYSKAZYWANIJ M ZAMENOJ
WSEH FORMUL W M NA RAWNOSILXNYE IM FORMULY, SODERVA]IE W KA^ESTWE LOGI^ESKIH SWQZOK TOLX-
KO : I !, DLQ KOTORYH W TABLICAH ISTINNOSTI 0 ZAMENEN NA 1 I NAOBOROT. tOGDA IS^ISLENIE
WYSKAZYWANIJ BUDET PODHODQ]EJ FORMALXNOJ AKSIOMATI^ESKOJ TEORIEJ DLQ M 0, TAK KAK, W SILU
TEOREM O POLNOTE (SM. P. V.3.1.), MNOVESTWO WSEH TEOREM IS^ISLENIQ WYSKAZYWANIJ SOWPADAET S
MNOVESTWOM WSEH WYDELENNYH FORMUL (TAWTOLOGIJ) LOGIKI M 0.
   3.7. nOWYE TERMINY. pOLNOTA FORMALIZACII T0 TEORII T OTNOSITELXNO T. nEPROTI-
WORE^IWOSTX I RAZREIMOSTX FORMALXNYH AKSIOMATI^ESKIH TEORIJ. nEZAWISIMOSTX AKSIOMY OT
DRUGIH AKSIOM. nEZAWISIMOSTX SISTEMY AKSIOM. mNOGOZNA^NYE LOGIKI.
   3.8. kONTROLXNYE WOPROSY.
  1. dAJTE OPREDELENIE POLNOJ FORMALXNOJ AKSIOMATI^ESKOJ TEORII T0 OTNOSITELXNO SODERVA-
     TELXNOJ TEORII T. kAKOWO PREDPOLAGAEMOE W OPREDELENII SOOTNOENIE MEVDU TEORIQMI T
     I T0?
  2. kAKIE FORMULY aw W TEOREME 3.1.1 S^ITA@TSQ TEOREMAMI iw?

                                               99