Логические операции над предикатами. Ограниченные кванторы. Постановка функции в предикат. Кусочное задание функции

Над предикатами, заданными на множестве натуральных чисел N будем использовать операции отрицания (), конъюнкции(^), дизъюнкции(, импликации(→) и эквивалентности, а также ограниченные кванторы:

Например, запись  означает предикаты «для любого у такого, что y<z и ».

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

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

Определение: функция  называется кусочно заданной, если она удовлетворяет условиям:

При этом предполагается, что для каждого набора  значений переменных истинно одно и только одно из высказываний  .

Теорема. Если функции  и предикаты  примитивно рекурсивны (рекурсивны), то функция  примитивно рекурсивна (рекурсивна).