Navoiy davlat pedagogika instituti fizika matematika fakulteti

Mulohazalar hisobining zidsizlig

.9.1 - ta’rif. Agar aksiomatik nazariyada ℑ va ù ℑ

formulalarning ko‘pi bilan bittasi keltirib chiqariluvchi bo‘lsa, bunday aksiomatik nazariya zidsiz deyilad

.9.2 - teorema. Mulohazalar hisobi zidsiz nazariyadir.

Isbot. Haqiqatdan ham, mulohazalar hisobida ℑ va ù ℑ keltirib chiqariluvchi formulalar bo‘lsalar, u holda ℑ vaù ℑ formulalar .8.1 teoremaga asosan, mulohazalar algebrasining aynan rost formulalari bo‘lar edilar. Buning bo‘lishi mumkin emas.

Mulohazalar hisobining to‘liqlig

Mulohazalar algebrasining ℑ ( A ₁, . . . , A _n) formulasida A ₁, . . . , A _n o‘zgaruvchi mulohazalarni 0 va 1 qiymatlar qabul qiluvchi i ₁, . . . , i _n qiymatlar tizimi bilan almashtirib chiqamiz. Natijada ℑ formula yo 0 , yo 1 qiymat qabul qilad Agar A _i - o‘zgaruvchi mulohazani 1 bilan almashtirgan bo‘lsak, A _i o‘rniga mulohazalar hisobining ℛ formulasini, A _i ni 0 bilan almashtirgan bo‘lsak, A _i o‘rniga mulohazalar hisobining ℱ formulasini qo‘yib, mulohazalar algebrasining ℑ formulasi qiymatiga mos keladigan mulohazalar hisobining ℑ* formulasini hosil qilamiz.

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

ℑ* ~ ℛ , 0 ga teng qiymat qabul qilsa, ℑ* ~ ℱ bo‘lishini kûrsatamiz.

Isbotni matematik induksiya metodi bilan olib boramiz.

ℑ formula o‘zgaruvchi mulohazadan iborat bo‘lsa, isbot ravshan.

ℑ , ℬ - formulalar uchun YUqoridagi tasdiq ûrinli bo‘lsin. U holda ℑ Ù ℬ , ℑ Ú ℬ , ℑ Þ ℬ , ù ℑ formulalar uchun ham tasdiq ûrinli ekanligini kûrsatamiz.

ℑ* orqali ℑ ga mos, ℬ* orqali ℬ ga mos mulohazalar hisobining formulalarini belgilab olamiz.

ℑ Ù ℬ uchun isbotni to‘liqkeltiramiz :

ℑ = 1, ℬ = 1 bo‘lsin. U holda induksiya faraziga kûra

ℑ* ~ ℛ, ℬ* ~ ℛ .

ℑ* Ù ℬ* ~ ℛ bo‘lishini kûrsatamiz. ℑ* Ù ℬ* ~ ℛ Ù ℛ.

⊢ ℛ Ù ℛ Þ ℛ ; ⊢ ℛ bo‘lgani uchun, kon’yunksiyani kiritish qoidasiga kûra ⊢ ℛ Ù ℛ , u holda , ⊢ ℛ Þ ℛ Ù ℛ.

Demak, ℛ Ù ℛ ~ ℛ.

ℑ = 1 , ℬ = 0 bo‘lsin. U holda ℑ* Ù ℬ* ~ ℛ Ù ℱ , ℱ = ù ℛ bo‘lgani uchun ℛ Ù ℱ ~ ℛ Ù ù ℛ. Absurdga keltirish qoidasiga kûra, ℛ Ù ù ℛ ~ ℱ.

ℑ = 0 , ℬ = 1 bo‘lgan hol YUqoridagidek isbot qilinad

ℑ = 0 , ℬ = 0 bo‘lsa, ℑ* Ù ℬ* ~ ℱ Ù ℱ , ℱ Ù ℱ ~ ù ℛ Ù ù ℛ .

ù ℛ Ù ù ℛ ~ ù ℛ bo‘lishini isbot qilaylik.

₁ aksiomaga asosan ⊢ ù ℛ Ù ù ℛ Þ ù ℛ .

₃ aksiomaga asosan

⊢ ( ù ℛ Þ ù ℛ ) Þ (( ù ℛ Þ ù ℛ ) Þ ù ℛ Þ ù ℛ Ù ù ℛ ).

MR qoidasini ikki marta qo‘lllasak, ⊢ ù ℛ Þ ù ℛ Ù ù ℛ hosil bo‘ladi.

qolgan A Ú V , A Þ V , ù A formulalar uchun teorema isbotini û=uvchilar mustaqil bajarishlari mumkin.

Biz oldingi paragraflarda mulohazalar hisobining har bir keltirib chiqariluvchi formulasi mulohazalar algebrasining aynan rost formulasi bo‘lishini kûrdik. Endi aksincha, mulohazalar algebrasining aynan rost formulasi mulohazalar hisobining keltirib chiqariluvchi formulasi bo‘ladimi degan masalani qaraylik. Bu masala keng ma’nodagi to‘liqlik muammosi deyilad

.10.1 - teorema. Mulohazalar hisobi keng ma’noda to‘liqaksiomatik nazariyadir. YA’ni mulohazalar algebrasining har bir aynan rost formulasi mulohazalar hisobining keltirib chiqariluvchi formulasi bo‘lad

Isbot. ℑ ( A ₁ , . . . , A _n ) mulohazalar algebrasining aynan rost formulasi bo‘lsin, u holda YUqorida isbot qilganimizga ko‘ra A ₁, . . . , A _n larni o‘rniga ℛ va ℱ lardan iborat ixtiyoriy d ₁ , . . . , d _n tizimni qo‘ysak,

⊢ ℑ ( d ₁ , . . . , d _n ) hosil bo‘lad U holda

⊢ ╱╲ ℑ ( d ₁ , . . . , d _n ) . 2.7.10 teoremaga asosan

d₁, . . . , d_n = ℛ , ℱ

⊢ ╱╲ ℑ ( d ₁ , . . . , d _n ) Þ ℑ ( A ₁ , . . . , A _n ) .

d₁, . . . , d_n = ℛ , ℱ

MR qoidasini qo‘lllasak ⊢ ℑ ( A ₁ , . . . , A _n ) bo‘lad

.10.2 - natija. Mulohazalar algebrasining barcha teng kuchli formulalari mulohazalar hisobida ham teng kuchli formulalardir.

Masalan : A Þ B ~ ù B Þ ù A ,

A Þ B ~ ù A Ú B ,

ù ( A Ú B) ~ ù A Ù ù B ,

ù ( A Ù B ) ~ ù A Ú ù B .

Biz ishlatgan keng ma’nodagi to‘liqlik tushunchasidan tashqari matematik mantiqda tor ma’nodagi to‘liqlik tushunchasining kiritilishi taby holdir. Haqiqatdan ham , mulohazalar hisobining aksiomalari sistemasiga yana bitta mulohazalar hisobida keltirib chiqarilmaydigan formulani aksioma sifatida kiritsak ziddiyat kelib chiqsa, u holda mulohazalar hisobi tor ma’noda to‘liqdeyilad

.10.3 - teorema. Mulohazalar hisobi tor ma’noda to‘liqaksiomatik nazariyadir.

Isbot. ℑ ( A ₁ , . . . , A _n ) formula mulohazalar hisobida keltirib chiqarilmaydigan formula bo‘lsin. ℑ ( A ₁ , . . . , A _n ) formulani mulohazalar hisobining aksiomalar ro‘yxatiga kiritib, yangi aksiomalar sistemasini hosil qilamiz.

ℑ ( A ₁ , . . . , A _n ) mulohazalar hisobida keltirib chiqarilmaydigan bo‘lganligi uchun A ₁ , . . . , A _n propozitsional o‘zgaruvchilarning ℛ va ℱ lardan iborat shunday qiymattizimi d ₁ , . . . , d _n mavjud bo‘lib ,

ℑ ( d ₁ , . . . , d _n ) ~ ℱ bo‘ladi, u holda ⊢ ù ℑ ( d ₁, . . . , d _n ) . Demak, yangi aksiomalar sistemasidan ham ù ℑ ( d ₁ , . . . , d _n ) keltirib chiqariluvchi formula bo‘lad Lekin,

ℑ ( A ₁ , . . . , A _n ) aksioma bo‘lganligi uchun, yangi aksiomalar sistemasida ℑ ( d₁, . . . , d_n ) keltirib chiqariluvchi formuladir. Ziddiyat.

MAVZU. Mulohazalar hisobi aksiomalarining erkinlig

Agar ℑ ₁ , . . . , ℑ _n- aksiomalar sistemasi berilgan bo‘lib, ℑ₁ aksiomani ℑ₂ , . . . , ℑ_n aksiomalar sistemasidan keltirib chiqarib bo‘lmasa, ℑ₁ aksioma qolganlaridan erkin deyilad Agar aksiomalar sistemasidagi har bir aksioma qolganlaridan erkin bo‘lsa, u holda aksiomalar sistemasi erkin deyilad

.11.1 - teorema. Mulohazalar hisobining aksiomalar sistemasi erkindir.

Isbot. ℑ_i aksioma qolganlaridan erkin ekanligini isbot qilish uchun ℑ_i bajarilmaydigan ,qolgan barcha aksiomalar bajariladigan interpretatsiyani kûrsatish etarl Haqiqatdan ham, agar ℑ_i qolgan aksiomalardan keltirib chiqarilganida edi bunday interpretatsiya mavjud bo‘lmas ed

Interpretatsiya qurish uchun mulohazalar hisobining o‘zgaruvchi mulohazalarini a , b - qiymatlarni qabul qiladigan o‘zgaruvchideb =araymiz, bu erda a - rost, b - yolg‘on mulohaza qiymatini bildirad Ù , Ú , Þ , ù - amallarini quyidagi shartlar bajariladigan qilib aniqaymiz :

1. ℑ_i aksiomadan boshqa barcha aksiomalar a qiymatni qabul qilsin.

2. ℑ_i dan tashqari barcha aksiomalar va keltirib chiqarish qoidalari yordamida isbot qilish mumkin bo‘lgan har qanday formula ham a ga teng qiymat qabul qilsin.

3. ℑ_i aksiomada qatnashgan propozitsional o‘zgaruvchilarning kamida bitta qiymattizimida, ℑ_i ning qiymati b ga teng bo‘lsin.

ℑ va ℬ formulalar, formulalarga kirgan barcha propozitsional o‘zgaruvchilarning iùtiyoriy qiymattizimida bir ùil qiymat qabul qilsalar, ℑ = ℬ deb belgilashni kelishib olamiz.

Endi misol tariqasida ₁ aksioma erkinligining isbotini kûrib chiqamiz.

Buning uchun mulohazalar hisobining quyidagicha interpretatsiyasini tuzamiz :

Ù amalini A Ù V = V ko‘rinishda, qolgan amallarni esa, mulohazalar algebrasida qanday aniqagan bo‘lsak, xuddi shunday aniqaymiz :

A	B	A Ù B	A Ú B	A Þ B	ù A
a	a	a	a	a	b
a	b	b	a	b	b
b	a	a	a	a	a
b	b	b	b	a	a

I, I, IY gruppa aksiomalarida Ù amali qatnashmaganligi hamda Ú , Þ , ù amallari mulohazalar algebrasidagidek aniqanganligi sababli bu aksiomalarning rostlik qiymatfaqat a ga teng bo‘lishi ravshan.

Masalan, ₂. ( A Þ ( B Þ C )) Þ (( A Þ B ) Þ ( A Þ C )) aksiomani ( 1 ) jadval yordamida tekshirib, faqat a ga teng bo‘lishini ko‘rish qiyin emas.

₁. A Þ ( B Þ A ) aksioma A = a , V = b qiymatlar qabul qilganda b ga teng bo‘ladi (jadvalga =arang). .8.1 – teorema isbotida mulohazalar algebrasining aynan rost formulalariga keltirib chiqarish qoidalari ni qo‘lllaganimizda yana aynan rost formula hosil bo‘lishini kûrsatganmiz.

SHunday qilib, ₁ aksioma uchun YUqorida kûrsatilgan 1,2,3 shartlarni qanoatlantiradigan interpretatsiya qurild Demak, ₁ aksioma qolgan aksiomalardan erkl Kolgan aksiomalarning erkinliligini qo‘uvchilar mustaqil isbot qilishlari , teoremaning to‘liqisbotini esa [1] dan topishlari mumkin.