|
(a) ;
(b) ;
(c) ;
(d) ;
(e) ;
(f) ;
(g) ;
(h) .
Isbot.
(a) ├ .
(1) gipoteza
(2) aksioma sxemasi;
(3) ; (1) va (2) ga MP qo‘llandi;
(4) aksioma sxemasi;
(5) (3) va (4) ga MP qo‘llandi;
(6) sxemasi;
(7) (5) va (6) ga MP qo‘llandi;
(8) aksioma sxemasi;
(9) 2.2-natija a) ni (8) va (7)qo'llashdan kelib chiqadi.
(10) (1) va (9) ga MP 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 MP qo‘llandi;
Demak, ├ hosil bo‘ldi.
├ .
(1) gipoteza;
(2) gipoteza.
(3) aksioma sxemasi;
(4)
(5) aksioma sxemasi;
(6) (4) va (5) ga MP qo‘llandi;
(7) (2) va (6) ga MP 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 2.2. (a);
(5) (2) va (4) ga Natija 2.2. (a);
(6) aksioma sxemasi;
(7)
Demak, ├ dan deduksiya teoremasiga asosan ├ ni hosil qilamiz:
(e)├ .
Ma’lumki ├ o‘rinlidir. Bunga ikki marta deduksiya teoremasini qo‘llasak: ├ ni hosil qilamiz..
(d) punkt sxemasi;
Oxirgi ikki ifodaga 2.2-Natija (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 MP qo‘llandi;.
(4) 2.1-lemma. ga asosan;
(5) (3) va (4) ga MP qo‘llandi;
(6) aksioma sxemasi;
(7) (5) va (6) ga MP qo‘llandi;
(g). ├
(1) gipoteza;
(2) gipoteza;
(3) aksioma sxemasi;
(4) (1) va (3) ga MP qo‘llandi;
(5) (a) punkt;
(6) (f) punkt;
(7) (5) va (6) ga MP qo‘llandi;.
Endi esa, ├ ga ikki marta deduksiya teoremasini qo‘llasak.
├ .
(h) ├ .
(1) gipoteza
(2) gipoteza
(3) (d) punkt
(4) (1) va (3) ga MP qo‘llandi;
(5) (2) va (4) ga 2.2-Natija (a) ni qo‘llandi;
(6) (f) punkt
(7) (5) va (6) ga MP 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. .
NAZARIYA UCHUN GYODELNING TOLIQLIK HAQIDA TEOREMASI.
Quyidagi lemma har bir tavtologiyaning teorema bo‘lishligini isbotlashda qo‘llaniladi.
4.1-lemma. Faraz qilaylik formula lar esa formula tarkibiga kiruvchi propozitsional xarflar bo‘lsin va bundan tashqari lar uchun rostlik (chin) qiymatlarining qandaydir taqsimoti berilgan bo‘lsin. orqali agar rost qiymat qabul qilsa ni, agar yolg‘on qiymat qabul qilsa belgilaymiz. Xudi shunday orqali agar shu taqsimotda formula rost qiymat qabul qilsa ni, agar formula yolg‘on qiymat qabul qilsa ni belgilaylik. U holda
├ .
Agar, masalan formula ko‘rinishda bo‘lsa, u holda
rostlik jadvalining har bir satri uchun 4.1-lemma ularga mos kelgan keltirib chiqarishni bildiradi.
Xususan, uchinchi satr uchun
├ ,
to‘rtinchi satr uchun esa
├
tasdiqlar mos keladi.
Isbot. Isbotni formulaning tarkibiga kiruvchi primitiv bog‘lovchilar soni bo‘yicha olib boriladi (tabiiyki, formula soddalashtirishlarsiz yozilgan deb faraz qilamiz).
Agar bo‘lsa, u holda formula propozitsional xarf ko‘rinishda bo‘ladi va lemmaning tasdig‘i ├ va ├ ko‘rinishda bo‘ladi.
Endi esa, faraz qilaylik lemma barcha lar uchun o‘rinli bo‘lsin.
1a-hol. formula ko‘rinishda bo‘lsin. ning tarkibiga kiruvchi primitiv bog‘lovchilar soni dan kichikdir.
Rostlik qiymatlarining berilgan taqsimotida rost qiymat qabul qilsin. U holda yolg‘on qiymat qabul qiladi. Shunday qilib, formula ko‘rinishda, formula esa ko‘rinishda bo‘ladi. Induksiya faraziga bilan ├ ga ega bo‘lamiz.
3.1-teoremaning (b) punktiga va MP qoidasiga asosan ├ . kelib chiqadi. Ammo esa ni bildiradi.
1b-hol. G rost qiymat qabul qilsin. U holda formula , bo‘lib esa bilan ustma-ust tushadi. Induksiya faraziga asosan ├ hosil bo‘ladi. formula esa dan iborat bo‘lgani uchun bu hol ham isbotlandi.
2-hol. formula ko‘rinishda bo‘lsin. U holda . va lar tarkibiga kiruvchi primitiv bog‘lovchilar soni dagi bog‘lovchilar sonidan kichik.
Shuning uchun induksiya farazga asosan
├
va
├ .
larga ega bo‘lamiz.
2a-hol. rost qiymat qabul qilsin. U holda formula va formula ko‘rinishga ega bo‘ladi. Shunday qilib, ├ ga
va 3.1-teorema (c) punktga asosan
├
hosil bo‘ladi. formula bo‘lgani uchun, bu hol ham isbotlandi.
2b-hol. H rost qiymat qabul qilsin. U holda formula ham rost qiymat qabul qiladi va formula va formula ko‘rinishga ega bo‘ladi.
├
dan va aksiomadan
├
ni hosil qilamiz. esa dan iboratdir.
2s-hol. rost va yolg‘on qiymat qabul qilsin. U holda formula yolg‘on qiymat qabul qiladi va u ko‘rinishda bo‘ladi, esa va formula ko‘rinishda bo‘ladi.
├
va ├ larga ega bo‘lamiz.
Bu erda 3.1-teorema (e) punktga asosan ├ , hosil bo‘ladi. formula esa dan iboratdir.
1-teorema. nazariyaning har qanday teoremasi tavtologiya bo‘ladi.
Isbot. nazariyaning har bir aksiomasi tavtologiya bo‘lishini osongina tekshirib ko‘rish mumkin. Ravshanki, MP qoidasini tavtologiyalarga qo‘llash natijasida hosila bo‘lgan formulalar ham tavtologiya bo‘ladi. Demak, nazariyaning har qanday teoremasi tavtologiya bo‘lar ekan.
4.2-teorema. (Gyodelning to‘liqlik haqidagi teoremasi).
Agar formula nazariyada tavtologiya bo‘lsa, u holda u nazariyaning teoremasi bo‘ladi.
Isbot (Kalmar). Faraz qilaylik, formula tavtologiya va lar tarkibiga kiruvchi propozitsional xarflar bo‘lsin. xarflarning har bir chinlik taqsimoti uchun 4.1-lemma. ga asosan
├ .
ga ega bo‘lamiz, chunki tavtologiya bo‘lgani uchun formula dan iboratdir. Shuning uchun, rost qiymat qabul qilsa
, ├ ga,
yolg‘on qiymat qabul qilganda esa
├ ga
ega bo‘lamiz. Bularga deduksiya teoremasini qo‘llab,
, ├ .
, .
larni hosil qilamiz.
3.1-teorema (h) punktga asosan
├ .
ni hosil qilamiz.
Xuddi shu jarayonni takrorlab, ni ham yo‘qotish mumkin. Umuman qadamda keyin esa biz ├ ga ega bo‘lamiz.
4.1-natija. Agar ifoda belgilarni o‘z ichiga olsa va nazariyaning qandaydir formulasining soddalashtirilgani ( ) ta’riflarga qarang) bo‘lsa, u holda formula tavtologiya bo‘lishi uchun formula nazariyaning teoremasi bo‘lishi zarur va etarlidir.
Do'stlaringiz bilan baham: |
