谓词逻辑

2019-12-15 约 1060 字预计阅读 3 分钟

题记

由于有些東西是命题逻辑没办法表示的，所以引出谓词逻辑，需要说明的是不管是命题逻辑也好，谓词逻辑也好，只是逻辑学中被广泛使用的其中的分支而已，根据实际应用需要可以使用其中的方法，自己创造一种新的逻辑(虽然不容易)也是完全没问题的。

谓词逻辑也被称为一阶逻辑(first-order logic), 谓词(predicate)其实就是一种关系，只是为了方便起见我们规定一些符号，并给符号一些定义。

S(x)就是一个一元关系，它可以表示x是一个学生。

Y(x,y)是一个二元关系，它可以是x比y年龄更老。

为什么计算机专业要学谓词逻辑：其实一个计算机语言(C、java等)的实现离不开包括谓词逻辑在内的各种逻辑，比如一个等号=可以看作一个二元的谓词，更直观的说，a=b可以看作=(a,b)。其实谓词逻辑还有各种用途，比如Type Theory类型理论，这里不做过多介绍。

和命题逻辑一样，我们给出谓词逻辑的formal的形式，首先formal的谓词逻辑语言包括三个部分：

为方便起见，我们先定义项的概念，如下图所示：

谓词逻辑的公式定义，如下图所示，其中t_1,t_2等是项：

定义见下图：

如下图，是公式$(\forall x(P(x) \wedge Q(x))) \rightarrow(\neg P(x) \vee Q(y))$的语法树，并标注自由变量和约束变量。

也就是说，虽然在公式中都写作x，但是其实有可能是不同的(如上图右边自由的x和左边约束的x是不同的)。

代换(substitution)定义：给定一个变量$x$, 一个项$t$，和公式$\phi $。我们就可以定义公式$\phi[t / x]$，它是通过将$\phi $中所有是自由变量的$x$替换成$t$得来的。

Example: 将上图[自由变量和约束变量的例子]，使用替换，表示成公式$\phi[f(x, y) / x]$，代换之后的结果如下图所示：

和命题逻辑一样，谓词逻辑也有自然推演的规则，命题推演规则在谓词逻辑里同样适用，这里就不列出全部的规则，只给出2道证明题作为例子。

这里需要注意的一个要点是，假设的条件只能在框内有效，否则会引发"只要有一个x满足性质P，则所有x都满足P"的经典逻辑语义危机，见下图例子。