Примитивно рекурсивный предикат.

Определение. Функция называется представляющей функцией для предиката , если выполняются следующие условия:

1) , т.е. их область определения совпадают;

2) для любого набора из области определения D

(17)

Определение. Предикат р(х) называется примитивно рекурсивным, если его представляющая функция является примитивно рекурсивной функцией.

Определение.Функция называется ПРФ относительно совокупности функций и предикатов , если она ПРФ относительно совокупности функций , где - представляющая функция предиката .

Определение.Предикат называется ПРФ относительно совокупности функций и предикатов , если представляющая функция предиката p является примитивно рекурсивной относительно совокупности функций , где - представляющая функция предиката .

Теорема 2. Логические операции над предикатами сохраняют свойства примитивной рекурсивности предикатов.

10. Операция навешивания ограниченного квантора над предикатами

Пусть задан двуместный предикат p(x,y), где в общем случае .

Определение. Говорят, что предикат R(x,z) получен из предикат p(x,y) с применением операции навешивания ограниченного квантора существования, т.е. , если выполняется следующее равенство:

. (27)

Определение. Говорят, что предикат Q(x,z) получен из предиката p(x,y) с применением операции навешивания ограниченного квантора всеобщности, т.е. , если выполняется следующее равенство:

. (28)

Приведем пример. Пусть

.

Рассмотрим

и .

Очевидно

Теорема 3. Операция навешивания ограниченных кванторов существования и всеобщности сохраняет свойство примитивной рекурсивности функций относительно совокупности{p}.

Доказательство. Пусть задан предикат p(x,y) и –представляющая его функция и пусть

.

Представляющую функцию предиката R(x, z) обозначим через и покажем, что ее можно представить следующим образом

. (29)

Действительно:

1) пусть предикат .

Тогда по определению операции навешивания ограниченного квантора существования,

найдется такое, что и , следовательно

. Отсюда следует, что .

2) Предположим, что предикат .

Тогда по определению операции навешивания ограниченного квантора существования, для любого набора (x,y), p(x,y)=л, следовательно и

.

Т. к. ранее у нас было доказано, что операция конечного произведения обладает свойством примитивной рекурсивности, то является примитивно рекурсивной относительно совокупности .

Пусть .

Аналогично доказывается случай, когда задана операция навешивания ограниченного квантора всеобщности. Легко можно доказать, что в качестве представляющей функции предиката Q(x,z) можно брать

(30)

и является ПРФ относительно совокупности . В виде упражнение докажите самостоятельно.

Пусть задана совокупность функций и совокупность предикатов .

Определение. Ф-я f , наз-cя ПРФ относит-о заданной совокупности функций и предикатов, если она ПРФ относительно совок-ти , где представляющая функция предиката ,