题记

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

对谓词的介绍

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

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

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

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

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

  1. A set of predicate symbols 谓词符号 P (谓词符号是定义域D,值域{0,1}的映射.这一点区别于函数)
  2. A set of function symbols 函数符号 F
  3. A set of constant symbols 常量符号 C (其实常量就是没有自变量的函数,不过为了方便,还是称作常量)

为方便起见,我们先定义的概念,如下图所示:

项的定义
项的定义

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

formulas
formulas

一个谓词逻辑公式的例子

一个谓词逻辑公式的例子
一个谓词逻辑公式的例子

自由变量和约束变量

定义见下图:

自由变量和约束变量的定义
自由变量和约束变量的定义

如下图,是公式$(\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道证明题作为例子。

谓词逻辑证明的例子(中文版教材第80页)
谓词逻辑证明的例子(中文版教材第80页)

谓词逻辑证明的例子(中文版教材第75页)
谓词逻辑证明的例子(中文版教材第75页)

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

只要有一个x满足性质P,则所有x都满足P
只要有一个x满足性质P,则所有x都满足P

相关资料