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

1. Следующие функции называются исходными(простейшими) функциями: 1) нуль функция: Z(x)=0 при У х (х>0), 2) функция прибавления единицы: N(x)=x+\ при Vx(x>0), ясно, что, используя функции Z я N, можно получить любую функцию- константу, например: 3) проектирующие функции J " (.1 £ :ьХ2.--Дп)'=^( при всех xi,x2,...,x „>0 ( г=1,2,...,и; и=1,2,...) 2. Следующие правила служат для получения новых функций, исходя из уже имеющихся функций. Подстановка: fiXl^2,-.X,i )=g (hiiXi,X2,...,X>,),...,h, „iXuX2,...,X,;)), тогда говорят, что функция/получена с помощью подстановки из функций g, hi, кг,..., h, „. Рекурсия: а) Г /(л:ьл:2,..„л:„,0)=я(д:ьл:2,...л,), при этом исключается случай и=0, для которого: б) 1иксированное целое неотриидтельное число. Будем говорить, что в случае а) функция / получена т g тлh с помощью рекурсии, а хьх2,...,х„ - параметры рекурсии, а в слу­ чае б) - из одной функции h с помощью рекзфсии. 1=адх)), 2=ад2(х))), Ъ=ЩМ{М(2(х)))), У ( Х ] , Х 2 , . ) Н { Х \ , р С 2 ^ . . - ) Х п ' ) У л У ) ) з I J{y+\)^h(y,f{y)). 254