半可判定谓词
书籍:逻辑百科辞典
也叫半可计算谓词或递归可枚举谓词。指外延集为递归可枚举集的谓词。也可如下直接定义:
设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),使得