Kirish dissertatsiya mavzusining dolzarbligi va zarurati

Isbot. bo’lsin. Avval, shartni qanoatlantiradigan qo’shni va n liklar mavjudligini ko’rsatamiz. bo’lgani uchun shunday va n liklar mavjudki, shart bajariladi. Agar ular qo’shni bo’lsa, maqsad bajariladi. Agar va lar qo’shni bo’lmasa, ular k ta koordinatasi bilan farq qiladi. usbu koordinatalarda 0 qiymatga ega, esa 1 qiymatga ega. Bunga asoslanib, va lar orasiga k-1 ta turli n liklarni shunday joylashtirish mumkinki

shart o’rinli bo’ladi. Ushbu qatorda yonma-yon turgan n liklar qo’shni bo’ladi. bo’lgani uchun, o’rinli. deb olamiz. Aytaylik, ular i- koordinata bo’yicha qo’shni bo’lhsin, ya’ni


Quyida aniqlangan funksiyani qaraymiz:
.
Bu funksiya funksiyadan 0, 1 va funksiyalarni o’zgaruvchilar o’rniga qo’yish bilan hosil qilindi va . Haqiqatan,
Demak va , yani . Lemma isbotlandi.

5. 
   Barcha chiziqli Bul funksiyalari sinfi quyidagi sinf bo’ladi. .
   

Masalan, funksiyalar L sinfiga tegishli bo’ladi.
5-jumla. L – yopiq sinfdir.
Quyidagi lemma chiziqli bo’lmagan funksiya haqidagi lemma deb yuritiladi.
3-lemma. Agar bo’lsa, u holda ushbu funksiyadan funksiyalarni o’rniga qo’yish, shuningdek, yo’ki f funksiyaning inkorini olish yo’li bilan funksiyani hosil qilish mumkin.
Isbot. funksiyaning Jegalkin ko’phadiga yoyilmasini qaraymiz:
Funksiya chiziqli bo’lmagani uchun ushbu ko’phadning hech bo’lmaganda bitta hadi ikkitadan ko’p ko’paytuvchiga ega bo’ladi. Umumiylikdan chiqmagan holda, ushbu ko’paytuvchilarning orasida x₁ va x₂ o’zgaruvchilar mavjud deb hisoblaymiz. Shunda ko’phadni quyidagi ko’rinishga keltirish mumkin:

Aytaylik, bo’lsin. U holda
deb olamiz.
Quyida aniqlangan funksiyani qaraymiz:
.
Bu funksiya funksiyadan 0, 1, va funksiyalarni o’zgaruvchilar o’rniga qo’yish bilan hosil qilindi. Endi funksiya yordamida quyida aniqlangan funksiyani qaraymiz:
.
Bu funksiya funksiyadan va funksiyalarni o’zgaruvchilar o’rniga qo’yish va balki dan inkor qilish bilan hosil qilindi va . Haqiqatan,

Lemma isbotlandi.
Quyidagi jadval sinflarni o’zaro turlicha ekanligini ko’rsatadi.

0	+	-	-	+	+
1	-	+	-	+	+
	-	-	+	-	+

2.10-teorema(Post). funksiyalar sistemasi to’liq bo’lishi uchun B yuqoridagi beshta sinflarning hech birining qism to’plami bo’lmasligi zarur va yetarli.
Isbot. Zaruriyligi. B to’liq sistema bo’lsin. Faraz qilaylik biror-bir uchun . U holda . Demak , bu esa farazga zid. Zaruriylik isbotlandi.
Yetarlilik. B funksiyalar sistemasi sinflardan hech birining qism to’plami bo’lmasin. B funksiyalar sistemasidan sinflarning hech birining qism to’plami bo’lmaydigan, beshtadan ko’p bo’lmagan funksiyani o’z ichiga olgan B₁ qism sistema ajratish mumkin. Buning uchun B funksiyalar sistemasidan sinflariga mos ravishda tegishli bo’lmagan funksiyalarni tanlaymiz va deb olamiz.
Yetarlilikni uchta bosqichda isbotlaymiz.

1. 
   Konstantalar 0 va 1 larni funksiyalar yordamida hosil qilamiz. bo’lganiuchun 2 ta hol bo’lishi mumkin:
   

1. 
   Bunda , chunki
   

Ikkinchi konstantani funksiyadan olamiz: .

2. 
   Bunda , chunki
   

Endi biz funksiyaga egamiz va dan 5.1-lemmaga asosan konstantani hosil qilishimiz mumkin. funksiyaga ega bo’lganimiz uchun ikkinchi konstantani ham topamiz. Ikki holda ham 0 va 1 konstantalarni hosil qildik.

2. 
   2-lemmaga asosan 0,1 va funksiyalar yordamida funksiyani hosil qilamiz.
   
3. 
   3-lemmaga asosan 0,1, xva funksiyalar yordamida funksiyani hosil qilamiz.
   

Shunday qilib, va funksiyalarni B₁ ustida formula ko’rinishida ifodaladik. 4.1-teoremaga ko’ra B₁ – to’liq sistema. Yetarlilik isbotlandi.
Teorema isbotlandi.
Post teoremasidan kelib chiqadigan natijalarga o’z e’tiborimizni jalb etaylik.Zeroki, har bir teoremaning mohiyati undan kelib chiqadigan natijalar bilan o’lchanadi. Quyida biz Post teoremasidan kelib chiqadigan uch natija ustida to’xtalamiz.
2.13-ta’rif. Bizga, berilgan bo’lsin.
-birkam to’liq deyiladi, agarda
1) to’liq bo’lmasa, ya’ni
2) ixtiyoriy uchun bo’lsa.