Matematika fakulteti

2-hossa. ├ bo‘lishi uchun ning qandaydir chekli qism to‘plami topilib, ├ bo‘lishi zarur va etarlidir.

3-hossa. Agar ├ bo‘lib to‘plamning ixtiyoriy elementi uchun ├bo‘lsa, u holda ├ bo‘ladi.

Ikkinchi va uchinchi xossalarning iboti ham xuddi birinchi xossadagidek bevosita ├ ning ta’rifidan kelib chiqadi.

├ ning bu uchta xossasidan kelajakda juda ko‘p marta foydalanamiz.

Mulohazalar xisobi uchun aksiomalar sistemasi.

Biz endi mulohazalar xisobining aksiomatik nazariyasini kiritamiz.

(1) ning simvollari sifatida , va butun musbat indeksli propozitsional xarflarni olamiz: .

Bu erda  va lar primitiv bog‘lovchilar deyiladi. Mulohazalar xisobining muhim tushunchasi hisoblangan formula tushunchasini kiritamiz.

(2) (a) Barcha propozitsional harflar formulalardir:

(b) agar va lar formulalar bo‘lsa, u holda lar ham formulalardir.

(3) nazariyaning formulalari qanday bo‘lishidan qat’iy nazar quyidagi formulalar ning aksiomalaridir:



(4) YAgona keltirib chiqarish qoidasi bo‘lib, u ham bo‘lsa, modus ponens qoidasi xizmat qiladi: va formulalarning bevosita natijasi dir. Bu qoidani qisqacha ko‘rinishda belgilaymiz.

Xuddi mulohazalar algebrasigidek qavslarni soddalashtirishga kelishib olaylik.

nazariyaning cheksiz aksiomalari to‘plami faqat yuqoridagi 3 ta aksiomalar qolini orqali beriladi.

Har bir formulaning aksioma bo‘lish yoki bo‘lmasligini osongina tekshirish mumkin va shuning uchun effektiv aksiomalashtirilgan nazariyadir.

Bizning maqsadimiz sistemani shunday qurishdan iboratki, unda uning barcha teoremalari sinfi mulohazalar mantiqini barcha tavtologiyalari sinfi bilan ustma-ust tushish.

Boshqa bog‘lovchilarni quyidagicha aniqlaymiz:

formula   ekanini;

formula ( ekanini;

formula

ekanini bildiradi.

Bu ta’riflarning ma’nosi, masalan da, va formulalar qanday bo‘lganda ham ifoda formulaning qisqartirilgan ifodasi ekanini bildiradi.

Lemma 3.1. ├ , bu erda ixtiyoriy formuladir.

Isbot. nazariyada formulani keltirib chiqarishini quramiz.

aksioma sxemasi)

aksioma sxemasi)

va (2) ga MR qo‘llandi)

aksioma sxemasi)

((3) va (4) ga MR qo‘llandi)

SHunday qilib, biz (1), (2), (3), (4), (5) formulalardan iborat chekli ketma-ketlikni qurdik. Bunda har bir formula yo aksioma, yoki o‘zidan oldingi formulalardan MR qoidasi bo‘yicha hosil qilindi va oxirgi formula teorema ekanini isbotlanishi kerak bo‘lgan formula bilan ustma-ust tushdi.

quyidagi teorema gipotezalardan ko‘p uchraydigan formulalarni keltirib chiqarishga imkon beradi.

Teorema 3.2. (Deduksiya teoremasi). Agar -formulalar to‘plami, va lar esa formulalar bo‘lib , ├ bo‘lsa, u holda ├ bo‘ladi. Xususan, agar ├ bo‘lsa, u holda ├ bo‘ladi.

Isbot. Faraz qilaylik ketma-ketlik  dan ni keltirib chiqarish bo‘lib, bo‘lsin. bo‘yicha induksiya metodidan foydalanib ├ ekanini isbotlaymiz.

bo‘lsin. U holda formula ni  dan keltirib chiqarishi bo‘ladi. U holda, ma’lumki formula yo aksioma, yoki  ning elementi, yoki bilan ustma-ust tushadi.

ifoda aksioma sxemasidir. SHuning uchun, dastlabki ikki holda quyidagi ketma-ketlik ning  dan keltirib chiqarilishi bo‘ladi:

(() aksioma sxemasi)

((1), (2) ga MR qo‘llandi)

ya’ni, (dastlabki ikki holda) (1), (2), (3) ketma-ketlik formulaning  to‘plamdan keltirib chiqarilishi bo‘ladi.

Eslatma. Uchinchi holda formulaning  dan keltirib chiqarilishi lemma 3.1 ning isbotida qurilgan formulalar ketma-ketligidan isborat.

SHunday qilib bo‘lgan xol isbotlandi.

Endi faraz qilaylik ixtiyoriy bo‘lgan holda ├ bo‘lsin. uchun quyidagi to‘rtta xol bo‘lishi mumkin:

aksioma, yoki , yoki formula bo‘ladi, yoki formula qandaydir va , bu erda formulalardan MR qoidasi bo‘yicha kelib chiqadi va formula ko‘rinishda bo‘ladi. Dastlabki uchta holda ├ ekani xudi dagidek isbotlanadi. Oxirgi xolda esa ├ va ├ larga asoslangan induktiv farazni qo‘llaymiz. aksioma sxemasiga asosan

├

ga ega bo‘lamiz. Bulardan esa ikki marta MR qiodasini qo‘llab, avval ├ ni, so‘ngra ├ ni hosil qilamiz.

SHunday qilib, induksiya metodi bo‘yicha bo‘lgan xol ham isbotlandi.

Natija 3.3. Agar ├ bo‘lsa, u holda , ├ bo‘ladi.

Isbot. Faraz qilaylik ketma-ketlik formulaning  dan keltirib chiqarilishi bo‘lsin. U holda, keltirib chiqarishning ta’rifiga asosan formula dan iboratdir. Endi esa ning  dan keltirib chiqarilishini quramiz:

.

Endi va larga MR qoidasini qo‘llab ga ega bo‘lamiz. Bu esa G dan ning keltirib chiqarilgani ko‘rsatadi.

Natija 3.4. nazariyaning ixtiyoriy formulalari uchun quyidagilar o‘rinlidir:

├

├

isbot. Masalan ning isbotlaylik.

gipoteza

gipoteza

gipoteza

(1) va (3) lar MR qo‘llandi.

(2) va (4) lar MR qo‘llandi.

Demak, ├

Bunga deduksiya teoremasini qo‘llab

├ ni hosil qilamiz.

(a) bandning isbotini mustaqil bajarish uchun o‘quvchi e’tiboriga xavola etiladi.

nazariyaning asosiy keltirib chiqariladigan formulalari.

Teorema 3.5. nazariyaning ixtiyoriy formulalari uchun quyidagi formulalar ning teoremalaridir:

(a) ;

(b) ;

(c) ;

(d) ;

(e) ;

(f) ;

(g) ;

(h) .

Isbot.

(a) ├ .

(1) gipoteza

(2) aksioma sxemasi;

(3); (1) va (2) ga MR qo‘llandi;

(4) aksioma sxemasi;

(5) (3) va (4) ga MR qo‘llandi;

(6) sxemasi;

(7) (5) va (6) ga MR qo‘llandi;

(8) aksioma sxemasi;

(9) Natija 3.4. kelib chiqadi.

(10) (1) va (9) ga MR qo‘llandi;

Demak, ├ hosil bo‘ldi. Bunga deduksiya teoremasini qo‘llasak ├ hosil bo‘ladi.

(b) ├.

(1) (a) punkt;

(2)

aksioma sxemasi;

(3) (1) va (2) ga MR qo‘llandi;

Demak, ├ hosil bo‘ldi.

3. 
   ├.
   

(1) gipoteza;

(2) gipoteza.

(3) aksioma sxemasi;

(4)

(5) aksioma sxemasi;

(6) (4) va (5) ga MR qo‘llandi;

(7) (2) va (6) ga MR qo‘llandi;

SHunday qilib, ├, ga ikki marta deduksiya teoremasini qo‘llasak ├ hosil bo‘ladi.

(d)├.

(1) gipoteza.

(2) (b) punkt;

(3) (a) punkt;

(4) (1) va (3) ga Natija 3.4. (a);

(5) (2) va (4) ga Natija 3.4. (a);

(6) aksioma sxemasi;

(7)

Demak, ├ dan deduksiya teoremasiga asosan ├ ni hosil qilamiz:

1. 
   ├.
   

Ma’lumki ├ o‘rinlidir. Bunga ikki marta deduksiya teoremasini qo‘llasak: ├ ni hosil qilamiz..

(d) punkt sxemasi;

Oxirgi ikki ifodaga Natija 3.4. (a) ni qo‘llab ├ ni hosil qilamiz.

Xususan, bu ning o‘rniga ni, ning o‘rniga esa ni qo‘yib

├

ni ham hosil qilishimiz mumkin.

(f) ├.

1. punkt;

2. aksioma sxemasi;.

3. (1) va (2) ga MR qo‘llandi;.

(4) lemma 3.1. ga asosan;

(5) (3) va (4) ga MR qo‘llandi;

(6) aksioma sxemasi;

(7) (5) va (6) ga MR qo‘llandi;

(g). ├

(1) gipoteza;

(2) gipoteza;

(3) aksioma sxemasi;

(4) (1) va (3) ga MR qo‘llandi;

(5) (a) punkt;

(6) (f) punkt;

(7) (5) va (6) ga MR qo‘llandi;.

Endi esa, ├ ga ikki marta deduksiya teoremasini qo‘llasak.

├.

(h) ├.

(1) gipoteza

(2) gipoteza

(3) (d) punkt

(4) (1) va (3) ga MR qo‘llandi;

(5) (2) va (4) ga Natija 3.4. (a) qo‘llandi;

(6) (f) punkt

(7) (5) va (6) ga MR qo‘llandi;

SHunday qilib, ├, ni hosil qildik. Bunga ikki marta deduksiya teoremasini qo‘llasak:

├ kelib chiqadi.

Mashqlar. Quyidagi formulalar nazariyaning teoremalari bo‘lishini isbotlang.

1. .

2. .

3. ├.

4. .

5. .