Və avtomatlar nəZƏRİYYƏSİ (Məşğələ dərsləri üşün vəsait)

II. Primitiv rekursiya operatorundan istifadə edilməsi
2.1.Primitiv rekursiya operatorundan istifadə etməklə məsələ həllinin nümunələrinə baxaq:

Məsələ1. f(x, y) = x + y primitiv rekursiv funksiyanın isbatı.

Həlli.

f(x, 0) = x,

f(x, y+1) = x + y + 1 = f(x, y) +1.

Bu rekursiv sxemin primitiv rekursiya uyğunluğunu göstərmək üçün seçim və təqibetmə funksiyasından istifadə edək

f(x, 0) = x = I(x),

f(x, y+1) = f(x, y) + 1 = S(f(x, y)) = S(I3(x, y, f(x, y))).

Məsələ2. f(x, y) = x ⋅ y primitiv rekursiv funksiyanın isbatı

Həlli Verilmiş funksuyanın rekursiv təyininə baxaq

f(x, 0) = 0,

f(x, y+1) = x ⋅ (y + 1) = x ⋅ y + x = f(x, y) +x,

buradan aydın olur ki,Z(x) = x ⋅ 0.

x ⋅ y = p(x, y) ilə işarə etsək,onda:

p(x, 0) = Z(x);

p(x, y+1) = p(x, y) +x = S(p(x, y), x) = S( I³₁ (x, y, p(x, y)), I³₃ (x, y, p(x, y))).

Məsələ3.Aşağıdakı primitiv rekursiv funksiyanın isbat edin

Sg(x)= əgər

Həlli. Verilmiş funksiyanın rekursiv olmasına baxaq

Sg(0) = 0 = Z(x),

Sg(x+1) = Z(x) +1 = 1 = S(Z(x)).
Məsələ4. Aşağıdakı primitiv rekursiv funksiyanın isbat edin f(x) = 2^x.

Həlli. Verilmiş funksiyanın rekursiv olmasına baxaq

f(0) = 1 = S(Z(x)),

f(x+1) = 2 ⋅ 2^x =2 ⋅ f(x) = S(S(Z(x))).
Məsələ5. Aşağıdakı primitiv rekursiv funksiyanın isbat edin f(x, y) = x^y.

Həlli. Verilmiş funksiyanın rekursiv olmasına baxaq

f(x, 0) = 1 = S(Z(x));

f(x, y+1) = x^y+1 = x^y ⋅x = f(x, y) ⋅I²₁ (x, y) = p(I³₃ (x, y, f(x, y)), I³₁ (x, y, f(x, y))).