半可判定谓词

也叫半可计算谓词或递归可枚举谓词。指外延集为递归可枚举集的谓词。也可如下直接定义：

设P是n元谓词，如果函数

是部分递归函数，则称P为半可判定谓词。P(x，…，x)是半可判定谓词当且仅当其外延集

S=｛(x，…，x)｜P(x，…，x)为真｝是递归可枚举集。

可判定的(递归的)谓词都是半可判定的，但反之不然。例如二元谓词

就是半可判定而非可判定的。

半可判定谓词的类对∨、∧两种运算封闭，但对乛不封闭：如果P、Q是半可判定谓词，则(P∧Q)、(P∨Q)也都是半可判定谓词。而乛P却未必是半可判定的。

如果P和乛P都是半可判定谓词，则P是可判定谓词。反之亦然。

半可判定谓词的类对存在量词运算封闭：

若Q(x，…，x，y)是n+1元半可判定谓词，则

也是半可判定谓词。

事实上，每个半可判定谓词都可以通过在可判定谓词上施加存在量词而得到：

设P(x，…，x)是n元半可判定谓词，则存在n+1元可判定谓词Q(x，…，x，y)，使得