一元谓词演算

维基百科,自由的百科全书
跳转至: 导航搜索

逻辑中,一元谓词演算是所有谓词字母都是一元(就是只接受一个参数)并且没有函数字母谓词演算。所有原子公式都有形式 P(x),这里的 P 是谓词字母而 x变量

性质[编辑]

向一元逻辑增加一个单一二元谓词字母将导致一个有完全谓词演算表达能力的系统。所以缺乏多元谓词严格的限定了在一元谓词演算中都能表达什么。不像完全谓词演算,这个演算是如此的弱,这个演算的一个给定公式是否有效(对于非空论域为真)是可判定性的。[1] 因为一元谓词演算是可判定性的,它不胜任一般的数学推理,比如叫做皮亚诺算术的微型数学片段就已知是不可判定性的。

尽管有上述缺陷,超越一元逻辑的需求没有得到赞赏,直到奥古斯都·德·摩根查尔斯·皮尔士在十九世纪关于关系逻辑的著作和弗雷格1879年的《概念文字》的出版。在他们三人之前,三段论词项逻辑被广泛认为足够用于形式演绎推理

在词项逻辑中的推理都可以在一元谓词演算中表示。例如三段论

所有的狗都是哺乳动物
没有哺乳动物是草食动物
所以没有狗是草食动物

可以在一元谓词演算中符号表示为

(\forall x\,D(x)\rightarrow M(x))\land \neg(\exists y\,M(y)\land H(y)) \Rightarrow \neg(\exists z\,D(z)\land H(z))

这里的 D, MH 分别指示存在事物的谓词,这里是狗(dog)、哺乳动物(mammal)和草食动物(herbivore)。

反过来,一元谓词演算引人注意的不比词项逻辑更有表达力。可以容易的证明在一元谓词逻辑中的所有公式都等价量词只出现在如下形式的闭合子公式中的公式

\forall x\,P_1(x)\lor\cdots\lor P_n(x)\lor\neg P'_1(x)\lor\cdots\lor \neg P'_m(x)

\exists x\,\neg P_1(x)\land\cdots\land\neg P_n(x)\land P'_1(x)\land\cdots\land P'_m(x),

每个这种公式都是另一个的否定,并且量词不嵌套。这些公式还稍微推广了在词项逻辑中考虑的基本判断的形式。例如,这个形式语言陈述比如“所有哺乳动物要么是草食动物要么是肉食动物(carnivore)要么二者都是”为 \forall x\,\neg M(x)\lor H(x)\lor C(x)

脚注[编辑]

  1. ^ Heinrich Behmann, Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem, in Mathematische Annalen (1922)