Yaxshi kitob diskret pdf

---

9-§.  Mulohazalar  hisobining  zidsizligi

9 A - t a ’rif.  Agar  aksiom atik  nazariyada  Я  va  1  Я 

formulalarning  k o ‘pi  bilan  bittasi  keltirib  chiqariluvchi 

bo ‘Isa,  bunday  aksiomatik  nazariya  zidsiz  deyiladi.

9.2-teorema.  Mulohazalar  hisobi  zidsiz  nazariyadir.

Isbot. Haqiqatan ham, mulohazalar hisobida Я va ] Я keltirib 

chiqariluvchi  formulalar bolsalar,  u  holda Я  va] Я  formulalar

8.1-teoremaga  asosan,  mulohazalar  algebrasining  aynan  rost 

formulalari  bo‘lar edilar.  Buning bo‘lishi mumkin  emas.

Takrorlash  uchun  savollar

1.9.  1.  Qanday  m atem atik  nazariya  zidsiz  matematik 

nazariya  deyiladi?

1.10. 

2. 

Mulohazalar  hisobining  zidsizligini  isbotlang.

10-§.  Mulohazalar  hisobining  to ‘liqligi

M ulohazalar  algebrasining  Я  (A t,...,  A J   formulasida 

A  r ...,  Ar  o'zgaruvchi  mulohazalarni  0  va  1  qiymatlar 

qabul  qiluvchi  ir ...,  in  qiymatlar  tizimi  bilan  almashtirib 

chiqamiz.  Natijada  Я  formula  yo  0,  yo  1  qiymat  qabul 

qiladi.  A gar  A  -  o'zg aruvc h i  m uloha z ani  1  bilan 

almashtirgan  bo'lsak,  A . o'rniga  mulohazalar  hisobining  X 

formulasini,  Ai  ni  0  bilan  almashtirgan  bo'lsak,  A. o'rniga 

mulohazalar hisobining  7   formulasini qo'yib,  mulohazalar 

alg ebrasining  Я  form ulasi  qiym atiga  mos  kelad igan 

mulohazalar  hisobining  Я*  formulasini  hosil  qilamiz.

Agar  Я  formula  1  ga  teng  qiymat  qabul  qilsa,  u  holda 

Я 

*  ~  ‘Л.,  0  ga  teng  qiymat  qabul  qilsa,  Я  *  ~  T   bo'lishini 

ko'rsatamiz.

64

---

Isbotni  matematik  induksiya  metodi  bilan  olib  boramiz.

Я 

formula  o'zgaruvchi  mulohazadan  iborat  bo'lsa,  isbot 

ravshan.

Я,  В 

formulalar  uchun  yuqoridagi  tasdiq  o'rinli  bo'lsin. 

U  holda  Я 

л  

В, 

я  

v  

В, Я =>  В,  ] Я  formulalar uchun  ham 

tasdiq  o'rinli  ekanligini  ko'rsatamiz.

Я* 

orqali  я   ga  mos,  в *  orqali  в   ga  mos  mulohazalar 

hisobining  formulalarini  belgilab  olamiz.

Я 

л  В  uchun  isbotni  to'liq keltiramiz:

Я 

=  1,  В -   1  bo'lsin.  U  holda  induksiya  faraziga  ko'ra

Я  *  ~  Я ,  <3*  ~  Я-

Я 

* 

а  

В* 

~  Я.  bo'lishini  ko'rsatamiz.  Я*  л  3*  ~ 

а  

Я-

|—  

л  5(_  => 

I—  Я.  bo'lgani  uchun,  konyunksiyani 

kiritish qoidasiga k o'ra  |— Я. 

a

 

Я.-  u holda,  |— Я.=>Я.лЯ.

Demak,  Я,  ^  Я  ~  Я..

Я  =  1,  В -   0 bo'lsin.  U  holda Я * л В * ~ 9 ^ л 7 ,   7  - 1 я  

bo'lgani  uchun 

З ^ а ^ - З ^ а ] ^ .   Absurdga  keltirish 

qoidasiga ko'ra,  В л~\ 3  ~~  ‘f .

Я 

=  О,  В =  1  bo'lgan  hoi  yuqoridagidek  isbot  qilinadi.

Я 

= О, В ~ 0 bo'lsa,  Я  * a 0* ~ T  a  ‘j-',  

1 ®

a

]

s

~ ]

s

  bo'lishini isbot qilaylik.

II,  aksiomaga  asosan

II, aksiomaga  asosan

Я.

  (1  31 => 1 

Я.) =>

 (d 

Я  =>

 1 

’Я.)

 =» 1 ^ => 1 

я

 

A 

1 SU-

MP 

qoidasini ikki marta  qo'llasak, 

hosil  bo'ladi.

Qolgan  я   v  в,  Я  =>  В,  1  j?  formulalar  uchun  teorema 

isbotini  o'quvchilar  mustaqil  bajarishlari  mumkin.

Biz  oldingi  paragraflarda  mulohazalar  hisobining  har 

bir  keltirib  chiqariluvchi  formulasi  m ulohazalar  algebra-

sining  ay n an   ro st  form ula si  b o 'l ish in i   k o 'r d ik .  Endi 

aksincha,  mulohazalar  algebrasining  aynan  rost  formulasi

65

---

m ulohazalar  hisobining  keltirib  chiqariluvchi  formulasi 

bo 'lad im i,  degan  m as alan i  qara ylik .  Bu  m as ala   k en g  

m a ’nodagi  to'Iiqlik  m uam m osi 

deyiladi.

10.1 

-teorema  M ulohazalar  hisobi  keng  m a ’noda  to'liq

a ks io m a tik  nazariyadir.  Ya 

’ni  m ulohazalar  algebrasining 

har  bir  aynan  rost  formulasi,  mulohazalar  hisobining  keltirib 

chiqariluvchi  form ulasi  bo ‘ladi.

Isbot. 

Я  (A 

A  J   mulohazalar  algebrasining  aynan 

rost  formulasi  bo'lsin,  u  holda  yuqorida  isbot  qilganimizga

ko 'ra   A  !.....  A  n  larni  o'rniga  ^   va  f   lardan  iborat

ixtiyoriy  d  ,...,  d  n tizimni  qo'ysak,

|—   Я (d  ,....  d  n)  hosil bo'ladi.  U holda 

|—   А  Я  (d  ,...,  d  n).  7.10-teoremaga  asosan

d ......d n= ^ , /

I—   Л  Я (d 

d  n)=> Я  (J? ,...,  Я п).

MP  qoidasini  qo'llasak  |— Я  (A  ; ...,  A  J   bo'ladi.

\0  2-natija.  M u lo h a zalar  algebrasining  barcha  teng 

kuchli  formulalari  mulohazalar  hisobida  ham  teng  kuchli 

formulalardir.

Masalan:  A  =>  В  ~  1 В  =>  1 A,

A  =>  В  ~  1 A  v  B,

] (A  

v  

В)  ~  1 А 

л  

]  B,

1 (А  л  B)  ~ 1 A  v  1 B.

Biz ishlatgan keng m a ’nodagi to'Iiqlik  tushunchasidan 

tashqari.  m atem atik  m a ntiqd a  tor  m a ’nodagi  to'Iiqlik 

tushunchasining kiritilishi  tabiiy holdir.  H a qiqa tan  ham. 

m ulo haz ala r  h isobinin g  a ks iom ala ri  sistem asiga  yana 

bitta  m u lohaza lar  h isob ida   keltirib  chiqarilm aydigan 

fo rm u la n i  a k s io m a   s ifa ti d a   k i r its a k ,  z id d i y a t  kelib 

chiqsa.  u  holda  m ulo ha zalar  hisobi  tor  m a ’noda  to 'liq  

deyiladi.

66

---

10.3-teorema.  Mulohazalar  hisobi  tor  m a ’noda  to'liq 

aksiomatik  nazariyadir.

Isbot.  Я  (A r ... A J   formula mulohazalar hisobida keltirib 

chiqarilmaydigan  formula  bo'lsin.  Я  ( Ar ..,  A J   formulani 

mulohazalar hisobining aksiomalar  ro'yxatiga kiritib,  yangi 

aksiomalar  sistemasini  hosil  qilamiz.

Я 

( A r ..,  A J   mulohazalar hisobida keltirib chiqarilmay-

digan  b o 'lg a n lig i   u ch un  A r ..,  A n  p ro p o z i ts io n a l 

o'zgaruvcxilarning  S^va^F  lardan iborat shunday qiymatlari

tizimi  d ,.....dn  mavjud  bo'lib,  Я  (d]V..,dn)  ~  T   bo'ladi,  u

ho ld a  |—   1  я   ( d ,,...,d n).  D em ak ,  yangi  a k s io m a la r 

sistemasidan  ham   ]  Я  (d |;...,dn)  keltirib  chiqariluvchi 

formula  bo'ladi.  Lekin,  Я  (A,,...,  An)  aksioma  bo'lganligi 

uchun,  yangi  aksiomalar  sistemasida  Я  (d,,...,dn)  keltirib 

chiqariluvchi  formuladir.

Takrorlash  uchun  savollar

1.  M ulo h aza la r  hisobi  uchun  to'Iiqlik  m uam m osini 

tushuntiring.

2.  Keng  m a’noda  to'liq  nazariyaga  misol  keltiring.

3.  Tor  m a’noda  to'liq  nazariyaga  ta’rif bering.

11-§.  Mulohazalar  hisobi  aksiomalarining  erkinligi

Agar  Л,,...,  Я  -   aksiomalar  sistemasi  berilgan  bo'lib,  я  

aksiomani  Я2,..., Яп  aksiomalar sistemasidan keltirib chiqarib 

bo'lmasa,  Я  ,  aksioma  qolganlaridan  erkin  deyiladi.  Agar 

aksiomalar sistemasidagi har bir aksioma qolganlaridan erkin 

bo'lsa,  u  holda  aksiomalar  sistemasi  erkin  deyiladi.

11.1 -teorema.  M ulohazalar  hisobining  aksiom alar 

sistemasi  erkindir.

67