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

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

  3.2. nEPROTIWORE^IWOSTX iw.
oPREDELENIE 1. tEORIQ T SODERVA]AQ iw W KA^ESTWE PODTEORII NAZYWAETSQ PROTIWORE
                          ,                                          ,                     -
^IWOJ, ESLI DLQ NEKOTOROJ FORMULY a \TOJ TEORII WYPOLNQETSQ:
                                       ` a I ` :a:
   w PROTIWNOM SLU^AE TEORIQ T NAZYWAETSQ NEPROTIWORE^IWOJ.
tEOREMA 1. iw QWLQETSQ NEPROTIWORE^IWOJ TEORIEJ.
dOKAZATELXSTWO. pUSTX DLQ NEKOTOROJ FORMULY a WYPOLNQ@TSQ WYWODIMOSTI: ` a I ` :a. eSLI
b | PROIZWOLXNAQ FORMULA iw, TO IMEEM:
                                            `a                                         (8)
                                           ` :a                                        (9)
                               ` a ! (:a ! b) | LEMMA 2.2.1                           (10)
   pRIMENQQ MP K (8) I (10), A ZATEM K (9) I POLU^ENNOJ FORMULE, POLU^IM: ` b, TO ESTX MY
POLU^ILI, ^TO WSQKAQ FORMULA iw WYWODIMA. pO TEOREME O POLNOTE \TO OZNA^AET, ^TO WSQKAQ
FORMULA iw QWLQETSQ TAWTOLOGIEJ, NO \TO NE TAK.
   iZ DOKAZATELXSTWA \TOJ TEOREMY WIDNO, ^TO W PROTIWORE^IWOJ TEORII L@BAQ FORMULA QWLQ-
ETSQ WYWODIMOJ. |TO ZNA^IT, ^TO PROTIWORE^IWYE TEORII NE IME@T PRAWA NA SU]ESTWOWANIE W
MATEMATIKE, TAK KAK NIKAKOJ SODERVATELXNOJ INFORMACII NE NESUT.
  3.3. rAZREIMOSTX iw.
oPREDELENIE 1. fORMALXNAQ AKSIOMATI^ESKAQ TEORIQ T NAZYWAETSQ RAZREIMOJ ESLI SU  ,        -
]ESTWUET ALGORITM, POZWOLQ@]IJ DLQ KAVDOJ FORMULY USTANOWITX, QWLQETSQ ONA WYWODIMOJ
ILI NET.
tEOREMA 1. iw | RAZREIMAQ TEORIQ.
dOKAZATELXSTWO. pUSTX a | FORMULA. sOSTAWIW TABLICU ISTINNOSTI (KONE^NAQ PROCEDURA)
MOVNO USTANOWITX, QWLQETSQ ONA TAWTOLOGIEJ ILI NET. pO TEOREME O POLNOTE ZAKL@^AEM, ^TO
ESLI a | TAWTOLOGIQ, TO ONA WYWODIMA. eSLI VE a NE TAWTOLOGIQ, TO ONA NE WYWODIMA.
  3.4. nEZAWISIMOSTX SISTEMY AKSIOM iw.
oPREDELENIE 1. pUSTX # SISTEMA AKSIOM NEKOTOROJ TEORII T  2 # aKSIOMA  NAZYWA
ETSQ NEZAWISIMOJ, ESLI ONA NE WYWODIMA IZ #nfg. sISTEMA AKSIOM # NAZYWAETSQ NEZAWISIMOJ,
                          |                                      ,       .                 -


ESLI WSE AKSIOMY \TOJ SISTEMY NEZAWISIMY.
tEOREMA 1. kAVDAQ IZ SHEM AKSIOM iw NEZAWISIMA.
dOKAZATELXSTWO. nEZAWISIMOSTX aKSIOMY . bUDEM S^ITATX, ^TO BUKWY iw MOGUT PRINIMATX
3 ZNA^ENIQ: 0, 1, 2. oPREDELIM SWQZKI : I ! SLEDU@]IMI TABLICAMI.
                                          1




                                               A B A!B
                                               0 0      0
                                               0 1      2
                                 A :A          0 2      2
                                 0 1           1 0      2
                                 1 1           1 1      2
                                 2 0           1 2      0
                                               2 0      0
                                               2 1      0
                                               2 2      0

                                              97