Математическая логика и теория алгоритмов

§ 1,6. Ириммтивио-рекурсивность некоторых функций . Час'1'ично-рекурсивные функции Теорема 6.8. Следующие функции являются примитивно- рекурсивными: 1) х+у; 3) 5) х~у 7) ,4g(xy 2) х^у, х-1, если х>0, 4) О , если х=0; х-у, х>у, о, '"о, х=0, , Хт^О; 6) U">'i •-у. х^У> у-х, х<у; 8 ) s g \ x ) = 1, х=0, О, '9) г т { х , у ) равна остатку от деления > на х; 10) q t ( x , y ) равна частному от деления у на х; 1 1 ) х ! ; 12) min {х,уУ, 13) mm(xi,x2....,x „); 14) гаах(х,у); 15) max (xi ,X2 ,...,x „). Доказательство. 1. Обозначим первую функцию через/ Имеем /(x,0)=x+0=x==./i' (х), Д х , у + 1 )=х+(уН-1)=(x^ .у)+1 ' = A x . y ) + l = N ( J ( x , y ) ) = h i x , y ^ x , y ) ) , где h ( x , y ; / ) =N { z ) .