递归谓词

特征函数为递归函数的谓词。设P为n元谓词，如果P的特征函数

是递归函数，则称P为递归谓词。如果C(x，…，x)不是递归函数，则称P为非递归谓词。

一个谓词是递归的，当且仅当它是可判定的。

原始递归谓词都是递归谓词，但反之不然。

递归谓词类对逻辑联结词及有界量词运算是封闭的。设P(x，…，x)、Q(x，…，x)是递归谓词，则P．P∧Q，P∨Q以及如下定义的R、S都是递归谓词：