Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

\)х+у, 2)х*у; Ъ)^Г 4) X-J ,еслих>0, S(x) = 0 , если х=0; 5) ^х-у, Х^, 6) х-у, х^ х-у = -< U-J/I 0, х<у; — у-х, х<у; 7) ^ 0, х=0, 8) ^ 1, х=0, sg(x) = -< 1, х^; 0, х^; 9) гт(х,^ = остатку от деления у на х; 10) qt(x,y) = частному от деления у на х; П)х! 9 \2) min (х,у): 13) min (^Ь^2} • } 14) max (х,у): 15) max (^1}^2} • • •}^г) • Доказательство. 1) Обозначим первую функцию через/ Имеем f(x,0)=x+0=x=j/ (х), f(x,y+l)=x+(y+l)=(x+y)+l=f(x,y) + l=N(f(x,y))=h(x,y,f(x,y)), где h(x,y,z) = N(z). В результате f(x,y)=x+y получается рекурсией из примитивно рекурсивных функций g(x)=j/(x) и h(x,y,z)=N(z), следовательно,/- примитивно рекурсивна. 2) Обозначим функцию умножения х на через у/. Тогда у/(х,0)=х*0 = О = Z(x); у/(х,у+1) =х•(у+1) =х•у+х= у/(х,у) +x=f(y/(x,y),x) =h у/(х,у)), где h^(x,y,z) = f(x,z). Итак, \lf (x,y) получается рекурсией из примитивно рекурсивных функций g^fxJ=ZfxJ и h^(x,y,z)=f(x,z), следовательно, функция у/- примитивно рекурсивна. 3) Обозначим функцию возведения в степень через (р. Для арифметических функций полагаем, что х^=1 для любых целых х, в том числе и для х=0, т.е. 0^=1 ((р(0,0)=1). Получим (р (x,0)=x °=l=N(Z(x)); ( р(х,у+•х=(р(х,у) •х= y/((p(x,y),x)=h^^(x,y, (р(х,у)), h^^(x,y,z) = \i/(x,z), т.е. (р получается рекурсией из примитивно рекурсивных функций g'^'^(x)=N(Z(x)) и h^^^^(x,y,z) = y/(x,z), следовательно, (р - примитив рекурсивна. Аналогичным образом доказывается и для функций 4)-15). 171