Производные операции над функциями.

1.)Пусть задана некоторая функция g(x,y) и функция φ(x,y,z)=g(x,y).

Говорят, что функция φ получена из функции g с помощью операции введения фиктивной переем-й ( ).

При этом функция φ(x,y,z) является ПРФ относительно совокупности . Действительно,φ можно представить следующим образом:

φ(x,y,z)=g( , ).

Как видим, функция φ получена из функции g и операцией подстановки, т.е. .

2) Пусть задана функция g(x,y,z) и если φ(x,y)=g(x,y,a), то говорят, что функция φ получена из функции g с помощью операции замены константы.

Действительно φ(x,y) можно представить следующим образом:

и называется операция замены константы.

3) Пусть задана функция g(x,y) и φ(x,y)=g(x,y), то говорят, что функция φ получена из функции g с применением операции перестановки переменных. Действительно функцию φ(x,y) можно представить следующим образом:

φ(x,y)= .

4) Пусть дана функция g(x) и φ(x)=g(x,x), то говорят, что функция φ получена из функции g с помощью операции отождествленной переменной.

Действительно, функцию φ можно представить следующим образом:

т.е. .

5.) Пусть заданы функции , где – некоторые функции различного количества переменных. Если , то говорят, что функция φ получена из функции g с помощью операции произвольной подстановки (суперпозиции).

Определение. Операция F называется примитивно рекурсивной операцией,если из равенства φ=F ) следует, что функция φ есть ПРФ относительно совокупности ψ.

Рассмотрим пример.

Пусть задана функция g(x,y) и функция φ(x,y,z)=g(x,y).

Функция φ получена из функции g с помощью операции введения фиктивной переменной.

При этом функция φ(x,y,z) является ПРФ относительно совокупности {g}.

Действительно, φ можно представить следующим образом: φ(x,y,z)=g( , )..Как видим, функция φ получена из функции g и операцией подстановки, т.е. .