22-mavzu rekursiv va rekursiv sanalucshi to’plamlar

5-ta’rif. Agar funksiya va funksiyalardan (1) munosabat orqali hosil etilsa, u holda funksiya va funksiyalardan primitiv (o’ta sodda) rekursiya sxemasi orqali hosil etilgan deyiladi.
Agar va funksiyalar intuitiv hisoblanuvchi funksiyalar bo’lsa, u holda ham intuitiv hisoblanuvchi funksiya bo’ladi.
Haqiqatan ham, argumentlarning qiymatlar majmuasi bo’lsin. U vaqtda ketma-ket quyidagilarni topamiz:
,
,
va hokazo.
Ravshanki, agar va funksiyalar argumentlarning barcha qiymatlarida aniqlangan bo’lsa, u holda funksiya ham argumentlarning barcha qiymatlarida aniqlangan bo’ladi.
Endi misollarda primitiv rekursiya sxemasi orqali yangi funksiyalarni hosil etishni ko’raylik.
1-misol. va bo’lsin hamda funksiya quyidagi tengliklar orqali aniqlansin:
(2)
funksiyaning qiymatini argumentlarning , qiymatlarida hisoblab chiqaylik. bo’lganligi uchun (2) formulalarning ikkinchisidan ketma-ket ravishda quyidagilarni hosil qilamiz:

ekanligini osongina ko’rsatish mumkin. Haqiqatan ham, . Bu tenglikda deb qabul qilib, yoki ni hosil qilamiz.
2-misol. funksiya quyidagi tengliklar bilan berilgan deylik:
(3)
Bu yerda , bo’ladi.
funksiyaning qiymatini argumentlarning , qiymatlari uchun hisoblaymiz.
bo’lganligi uchun bo’ladi. Funksiyaning va qiymatlarini ketma-ket topamiz:

Bu misolda ekanligini ko’rsatish mumkin. Haqiqatan ham, . Bu tenglikda deb qabul qilib, yoki ni hosil qilamiz.
3.Minimallash operatsiyasi ( -operator). Ixtiyoriy funksiya berilgan bo’lsin. Quyidagi masalani ko’rib chiqamiz: har qanday argumentning qiymatlari uchun hech bo’lmaganda shunday bitta argumentning qiymatini topish kerakki, bo’lsin. Yana ham murakkabroq holda masalani qo’yamiz: berilgan funksiya va uning muayyan qiymatli argumenti uchun qila oladigan argumentlarning eng kichik qiymatlisini topish kerak bo’lsin. Masalaning yechimi ga bog’liq bo’lganligi uchun qila oladigan ning eng kichik qiymati ham ning funksiyasi bo’ladi, ya’ni
. (4)
(4) ifoda quyidagicha o’qiladi: «Shunday eng kichik ki, ».
Xuddi shu tarzda ko’p argumentli funksiya aniqlanadi:
. (5)