O’ O`zbekiston respublikasi

3-misol. Quyidagi funksiyaning primitiv rekursiv ekanligi isbot qilinsin: φ(x)=x! (bu erda 0!=1);
Echish: Avvalo, berilgan funksiyaning aniqlanishidan 0!=1, ya’ni φ(0)=1 tengliklar o’rinli. Bular primitiv rekursiya sxemasining birinchi tengligini beradi. Bu erda n=0, f=1 – o’zgarmas funksiya. So’ngra berilgan x! funksiya ifodasidan (x+1)!=1∙2∙…x∙ (x+1)=x! ∙(x+1)=f(x)∙S(x)=S(x) ∙f(x). Ushbu tenglikni quyidagicha ifodalash mumkin: f(x+1)=P(S(x),f(x)). Bu erda P(u,v)=u∙v. Ushbu ifoda primitiv rekursiya sxemasining ikkinchi tenglamasini beradi, ya’ni g(y,z)=P(S(y),z) - P va S primitiv rekursiv funksiyalarning superpozitsiyasidan iborat. Bundan g funksiyaning primitiv rekursiligi kelib chiqadi. Shunday qilib, φ(x)=x! funksiya 1,P va S rekursiv funksiyalarga superpozitsiya va primitiv rekursiya operatorlarining qo’llanilishi natijasida olinganligi va primitiv rekursivligi kelib chiqadi.
4-misol. Kesik ayirma funksiyasining quyidagi xossasi isbotlansin: x_{ }(y+z)= (x_{ }y)_{ }z.
Echish: x_{ }(y+z) = (x_{ }y)_{ }z; Isbotni y bo’yicha induksiya orqali bajaramiz. y=0 bo’lganda x_{ }(0+z)= x_{ }z =(x_{ }0)_{ } z ifodaga egamiz. x_{ }(y+z) = (x_{ }y)_{ }z tasdiq y uchun bajariladi deb faraz qilib, uning y+1 uchun ham to’g’riligini isbotlaymiz: x_{ }((y+1)+z)= (x_{ }(y+1)) _{ } z (*). Bu vazifani o’z navbatida x bo’yicha induksiya orqali amalga oshiramiz. Ushbu induksiyani tasdiqlovchi 0_{ }((y+1)+z) = (0_{ }(y+1)) _{ } z ifoda kesik ayirmaning 0_{ }y=0 xossasiga ko’ra to’g’ridir. Faraz qilaylik, bu ifoda x uchun ham to’g’ri bo’lsin: x_{ }((y+1)+z)= (x_{ }(y+1)) _{ } z. Uning x+1 uchun ham to’g’ri ekanligini ko’rsatamiz: (x+1)_{ }((y+1)+z)= ((x+1)_{ }(y+1))_{ }z. Ushbu ifodani shakl almashtirsak, (x+1)_{ }((y+1)+z)=(x+1)_{ }((y+z)+1)=S(x)_{ }S(y+z)=( x_{ }y=S(x)_{ } S(y) xossasiga asosan)=x _{ } (y+z)= (y bo’yicha induksiyaga asosan)=(x_{ } y)-z=( x_{ }y=S(x)_{ }S(y) ekanligiga asosan)= ((x+1) _{ } (y+1))_{ }z (*). x bo’yicha induksiyani yakunlab, (*) tenglikni isbotiga erishamiz. Oxirgi tenglik y bo’yicha induksiyani tugallab

x_{ }(y+z)= (x_{ }y)_{ }z ifodaning to’g’ri ekanligini isbotlaydi.

5-misol. Ushbu funksiyaning primitiv rekursivligini qo’shish va kesik ayirma amallarining superpozitsiyasi orqali ifodalash yo’li bilan isbotlang: _{ } .
Echish: _{ } ekanligini isbotlaymiz. Haqiqatan ham, x>y bo’lsa (x-y>0), _{ } =x-y va _{ }=(x-y)+0=x-y. Agar x=y bo’lsa, ushbu tenglikning har ikkala tomoni 0 ga teng. Nihoyat, agar x  =-(x-y)=y-x va _{ }=0+(y-x)=y-x. x+y va _{ } larning primitiv rekursivligidan, ushbu ularning superpozitsiyasidan iborat bo’lgan _{ } funksiyaning primitiv rekursivligi kelib chiqadi.