原始递归谓词

特征函数为原始递归函数的谓词。设P为n元谓词，如下定义的n元函数

G(x，…，x)

　　　=｛1 当P(x，…，x)为真

　　　　 0 当P(x，…，x)为假

称为谓词P的特征函数。如果G(x，…，x)是原始递归函数，则称P为原始递归谓词。

原始递归谓词类对逻辑联结词及有界量词运算都是封闭的。即：若P(x，…，x)，Q(x，…，x)是原始递归谓词，则P，P∧Q，P∨Q，以及

也都是原始递归谓词。其中