谓词逻辑

为解决命题逻辑的缺陷所以引出了谓词逻辑

谓词逻辑对简单命题进行了进一步的分析，找出所描述的对象与对象之间的关系
如：“$2$ 是偶数”可泛化描述为“$x$ 是偶数”

谓词

个体常元与个体变元

个体常元

用于表示具体或特定个体的符号称为个体常元，常用小写字母 $a,b,c,\cdots$ 表示

如：“$2$ 是偶数”中的 $2$ 就是个体常元

个体变元

定义

用于表示任意个体的变量称为个体变元，常用小写字母 $x,y,z,\cdots$ 表示

如：“$x$ 是偶数”中的 $x$ 就是个体变元

论域

个体变元的取值范围称为该变元的论域或个体域

全总个体域

所有个体变元所能代表的所有个体的集合称为全总个体域

定义

刻画单个个体特征（一元谓词）或者多个个体间关系（多元谓词）的模式称为谓词
如 “$\cdots$ 是偶数“就是谓词

1. 一元谓词
   表示个体的特征，用一个表达个体特征的大写字母和一个个体常元或变元组成的表达式表示，如 $P(a)$、$P(x)$
2. 二元谓词
   表示两个个体之间的关系，用一个表达两个个体间的关系的大写字母和两个个体常元或变元组成的表达式表示，如 $P(x,y)$
3. $n$ 元谓词
   表达 $n$ 个个体之间的关系，用一个表达 $n$ 个个体间的关系的大写字母和 $n$ 个个体常元或变元组成的表达式表示，如 $P(x_1,x_2,\cdots,x_n)$

谓词可看作是一个命题函数，设有 $n$ 元谓词 $P(x_2,x_2,\cdots,x_n)$，其中 $x_1\in D_1,x_2\in D_2,\cdots,x_n\in D_n$，则 $P(x_1,x_2,\cdots,x_n)$ 可看作是从集合 $D_1\times D_2\times\cdots\times D_n$ 到集合 $\{T,F\}$ 的映射
如下图：

由谓词的定义可知，谓词 $P(x_1,x_2,\cdots,x_n)$ 仅是一个函数，因此没有真假值。只有将每个个体变元均代入相应个体域中确定的个体常元，才得到一个具有确定真假值的命题

命题可看作是谓词的特殊形式
当 $n=0$ 时，谓词 $P$ 就退化成了命题

特性谓词

在了解特性谓词前需要对量化有所了解

引言

如命题：“所有人都是会死的”、“有些人不怕死”
设 $H(x)$ 表示“$x$ 是人”，$D(x)$ 表示“$x$ 是会死的”，$F(x)$ 表示“$x$ 不怕死”
下面对其进行符号化

• 如果论域是全人类，则符号化后结果为 $\forall xD(x)$、$\exists x F(x)$
• 如果论域为全总个体域，则符号化后结果为
  (1)“所有人都是会死的”又可等价表达为“对任意 $x$，如果 $x$ 是人，那么 $x$ 是会死的”
  因此符号化结果为 $\forall x[H(x)\rightarrow D(x)]$
  (2)“有些人不怕死”又可等价表达为“存在 $x$，$x$ 是人，并且 $x$ 不怕死”
  因此符号化结果为 $\exists x[H(x)\land D(x)]$

对于上面的例子，$H(x)$ 被称作特性谓词，用于限定 $x$ 是人

定义

特性谓词是用于限定论域为满足该谓词的个体

规则

把特性谓词加入到公式时需满足以下两条规则

• 对于全称量词，特性谓词作为条件式的前件加入
• 对于存在量词，特性谓词作为合取式的合取项加入

量词

只有谓词不能表达如“所有的人都会呼吸”、“有些有理数是自然数”等命题，还需引入量词

种类

全称量词

汉语表达“对于任意 $x$”可记作 $\forall x$，其中 $\forall$ 称为全称量词，$x$ 称为量词 $\forall$ 的作用变元或指导变元

如：$\forall xP(x)$ 表示“对于所有的 $x$ 均有 $P(x)$”

存在量词

汉语表达“存在某个 $x$”可记作 $\exists x$，其中 $\exists$ 称为存在量词，$x$ 称为量词 $\exists$ 的作用变元或指导变元

如：$\exists xP(x)$ 表示“存在某一 $x$ 满足 $P(x)$”

量化

定义

在谓词 $P(x)$ 前面加上全称量词 $\forall x$ 或存在量词 $\exists x$ 称为个体变元 $x$ 被全称量词或存在量词量化，此时若为 $P$ 指定具体含义、为 $x$ 指定论域，则 $\forall xP(x)$ 或 $\exists xP(x)$ 成为一个具有真假值的命题

量化后所得命题的真值与个体变元的论域有关，如 $\exists x(x=3)$；如果论域为自然数则为真，如果论域为负整数则为假
为统一表述，若不加说明，则默认都为全总个体域

量化的命题形式表示

如果论域是有限集合，则对于某一个体变元的量化可以用命题形式表示

设论域 $D=\{a_1,a_2,\cdots,a_n\}$，则有

• $\forall xP(x)\Leftrightarrow P(a_1)\land P(a_2)\land\cdots\land P(a_n)$
• $\exists xP(x)\Leftrightarrow P(a_1)\lor P(a_2)\lor\cdots\lor P(a_n)$

辖域

在了解量词辖域之前需先了解谓词公式

定义

在谓词公式中，量词的作用范围称为量词的作用域，又称量词的辖域

• 如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式
  如：$\forall xP(x)$ 中的 $\forall x$ 的辖域为 $P(x)$
• 如果量词后边是括号，则此括号所表示的区域就是该量词的辖域
  如：$\exists x(P(x)\rightarrow Q(x))$ 中的 $\exists x$ 的辖域为 $(P(x)\rightarrow Q(x))$
• 如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域
  如：$\forall x\exists y P(x,y)$ 中的 $\exists y$ 的辖域为 $P(x,y)$；$\forall x$ 的辖域为 $\exists y P(x,y)$

约束出现

定义

在量词 $\forall x$ 或 $\exists x$ 辖域内 $x$ 的一切出现称为约束出现

约束变元

约束出现的个体变元称为约束变元

自由变元

不是约束出现的的个体变元称为自由变元

如：谓词公式 $\forall x P(x,y)$ 中的 $x$ 为约束变元；$y$ 自由变元

谓词公式

原子公式

不出现联结词和量词的单个谓词称为谓词演算的原子公式
如：$P(x_1,x_2,\cdots,x_n)~~~~(n\geq 0)$

因命题是谓词 $n=0$ 的特殊形式，因此单个命题常元和命题变元都是谓词演算的原子公式

定义

谓词公式，又称谓词逻辑的合式公式，下面是它的递归定义

1. 基础条款：原子公式是谓词公式
2. 归纳条款
   • 若 $A$ 是谓词公式，则 $\lnot A$ 是谓词公式
   • 若 $A,B$ 是谓词公式，则 $A\land B$、$A\lor B$、$A\rightarrow B$、$A\leftrightarrow B$ 是谓词公式
   • 若 $A$ 是谓词公式，且 $A$ 中的个体变元 $x$ 未被量词量化，则量化后 $\forall xA(x)$ 和 $\exists xA(x)$ 是量词公式
3. 极小性条款：只有有限次地应用条款 1 和条款 2 生成的表达式才是谓词公式

由定义知所有的命题公式都是谓词公式

子公式

$B$ 是谓词公式 $A$ 的子公式的定义如下

• $B$ 是 $A$ 的连续段
• $B$ 是谓词公式

赋值

对谓词公式赋值需要完成以下操作：

1. 指定论域 $E$
2. 指定谓词符的含义
3. 为命题变元指定确定命题
4. 为自由变元指定论域上的个体

注意：约束变元不需要指定

永真公式

命题逻辑的等价和蕴含公式的推广

将命题逻辑中的等价或蕴含式运用代入规则，用谓词逻辑中的谓词公式代入，所得的公式就是谓词公式的等价或蕴含式

如：命题公式等价式 $P\rightarrow Q\Leftrightarrow\lnot P\lor Q$ 在谓词逻辑的推广为
$\forall xP(x)\rightarrow \exists xQ(x)\Leftrightarrow \lnot\forall xP(x)\lor \exists xQ(x)$

量词的否定律

• $\lnot\forall xP(x)\Leftrightarrow \exists x\lnot P(x)$
  即“不是所有的 $x$ 都满足 $P(x)$” 可以说成“存在 $x$ 满足非 $P(x)$”
• $\lnot\exists xP(x)\Leftrightarrow\forall x\lnot P(x)$
  即“不存在 $x$ 满足 $P(x)”可以说成“对于所有的 $x$ 都满足非 $P(x)$”

量词辖域的扩展和收缩律

• $\forall x(P(x)\land Q)\Leftrightarrow\forall xP(x)\land Q$
  $\exists x(P(x)\land Q)\Leftrightarrow\exists xP(x)\land Q$
  $\forall x(P(x)\lor Q)\Leftrightarrow\forall xP(x)\lor Q$
  $\exists x(P(x)\lor Q)\Leftrightarrow\exists xP(x)\lor Q$

• $\forall xP(x)\rightarrow Q\Leftrightarrow\exists x(P(x)\rightarrow Q)$
  $\exists xP(x)\rightarrow Q\Leftrightarrow\forall x(P(x)\rightarrow Q)$

  证明过程

  下面证明 $\forall xP(x)\rightarrow Q\Leftrightarrow\exists x(P(x)\rightarrow Q)$

  $$\begin{aligned} \forall xP(x)\rightarrow Q&\Leftrightarrow\lnot\forall xP(x)\lor Q\\ &\Leftrightarrow\exists x\lnot P(x)\lor Q\\ &\Leftrightarrow\exists x(\lnot P(x)\lor Q)\\ &\Leftrightarrow\exists x(P(x)\rightarrow Q) \end{aligned}$$

• $Q\rightarrow\forall xP(x)\Leftrightarrow\forall x(Q\rightarrow P(x))$
  $Q\rightarrow\exists xP(x)\Leftrightarrow\exists x(Q\rightarrow P(x))$

量词的分配律

• $\forall x(P(x)\land Q(x))\Leftrightarrow\forall xP(x)\land\forall xQ(x)$
  $\exists x(P(x)\lor Q(x))\Leftrightarrow\exists xP(x)\lor\exists xQ(x)$

  证明过程

  下面证明 $\forall x(P(x)\land Q(x))\Leftrightarrow\forall xP(x)\land\forall xQ(x)$
  $\exists x(P(x)\lor Q(x))\Leftrightarrow\exists xP(x)\lor\exists xQ(x)$ 同理可证
  假设论域为 $D$
  当 $\forall x(P(x)\land Q(x))$ 为真时，即对所有的 $a\in D$ 都有 $P(a)\land Q(a)$ 为真
  $\therefore P(a)$、$Q(a)$ 都为真
  $\therefore\forall xP(x)$、$\forall xQ(x)$ 都为真
  $\therefore\forall xP(x)\land\forall xQ(x)$ 为真
  当 $\forall x(P(x)\land Q(x))$ 为假时，即存在 $a\in D$ 使 $P(a)\land Q(a)$ 为假
  $\therefore P(a)$、$Q(a)$ 至少有一个为假。不妨设 $P(a)$ 为假，则 $\forall xP(x)$ 为假
  $\therefore xP(x)\land xQ(x)$ 为假
  所以 $\forall x(P(x)\land Q(x))$ 与 $\forall xP(x)\land\forall xQ(x)$ 真值相同
  即 $\forall x(P(x)\land Q(x))\Leftrightarrow\forall xP(x)\land\forall xQ(x)$

• $\forall xP(x)\lor\forall xQ(x)\Rightarrow\forall x(P(x)\lor Q(x))$
  $\exists x(P(x)\land Q(x))\Rightarrow\exists xP(x)\land\exists xQ(x)$

  证明过程

  下面证明 $\forall xP(x)\lor\forall xQ(x)\Rightarrow\forall x(P(x)\lor Q(x))$
  $\exists x(P(x)\land Q(x))\Rightarrow\exists xP(x)\land\exists xQ(x)$ 同理可证
  不妨设论域为 $D$
  当 $\forall xP(x)\lor\forall xQ(x)$ 为真时，$\forall xP(x)$、$\forall xQ(x)$ 至少有一个为真
  不妨设 $\forall xP(x)$ 为真，即对于所有的 $a\in D$，都有 $P(a)$ 为真
  $\therefore P(a)\lor Q(x)$ 为真
  $\therefore\forall x(P(x)\lor Q(x))$ 为真
  由肯定前件法得 $\forall xP(x)\lor\forall xQ(x)\Rightarrow\forall x(P(x)\lor Q(x))$
  当 $\forall x(P(x)\lor Q(x))$ 为真时，即对于所有得 $a\in D$，都有 $P(a)\lor Q(a)$ 为真
  但是却不一定有 $\forall xP(x)\lor\forall xQ(x)$ 为真
  因为假设 $D=\{a,b\}$，$P(a)$ 为真、$Q(a)$ 为假；$P(b)$ 为假、$Q(b)$ 为真时，$\forall x(P(x)\lor Q(x))$ 为真，但 $\forall xP(x)\lor\forall xQ(x)$ 为假

• $\forall x(P(x)\rightarrow Q(x))\Rightarrow \forall xP(x)\rightarrow\forall xQ(x)$
  $\forall x(P(x)\leftrightarrow Q(x))\Rightarrow\forall xP(x)\leftrightarrow\forall xQ(x)$

  证明过程

  对于 $\forall x(P(x)\rightarrow Q(x))\Rightarrow \forall xP(x)\rightarrow\forall xQ(x)$
  这里用否定后件法证明
  不妨设论域为 $D$
  当 $\forall xP(x)\rightarrow\forall xQ(x)$ 为假时，$\forall xP(x)$ 为真、$\forall xQ(x)$ 为假
  因此，存在 $a\in D$ 使 $P(a)$ 为真、$Q(a)$ 为假
  所以，$\forall x(P(x)\rightarrow Q(x))$ 为假

  对于 $\forall x(P(x)\leftrightarrow Q(x))\Rightarrow\forall xP(x)\leftrightarrow\forall xQ(x)$

  $$\begin{aligned} \forall x(P(x)\leftrightarrow Q(x))&\Leftrightarrow\forall x[(P(x)\rightarrow Q(x))\land(Q(x)\rightarrow P(x))]\\ &\Leftrightarrow\forall x(P(x)\rightarrow Q(x))\land\forall x(Q(x)\rightarrow P(x))\\ &\Rightarrow(\forall xP(x)\rightarrow\forall xQ(x))\land(\forall xQ(x)\rightarrow\forall xP(x))\\ &\Leftrightarrow\forall xP(x)\leftrightarrow\forall xQ(x) \end{aligned}$$

• $\exists x(P(x)\rightarrow Q(x))\Leftrightarrow\forall xP(x)\rightarrow\exists xQ(x)$
  $\exists xP(x)\rightarrow\forall xQ(x)\Rightarrow\forall x(P(x)\rightarrow Q(x))$

  证明过程

  下面证明 $\exists x(P(x)\rightarrow Q(x))\Leftrightarrow\forall xP(x)\rightarrow\exists xQ(x)$

  $$\begin{aligned} \exists x(P(x)\rightarrow Q(x))&\Leftrightarrow\exists x(\lnot P(x)\lor Q(x))\\ &\Leftrightarrow\exists x\lnot P(x)\lor\exists xQ(x)\\ &\Leftrightarrow\lnot\forall xP(x)\lor\exists xQ(x)\\ &\Leftrightarrow\forall xP(x)\rightarrow\exists xQ(x) \end{aligned}$$

  下面证明 $\exists xP(x)\rightarrow\forall xQ(x)\Rightarrow\forall x(P(x)\rightarrow Q(x))$

  $$\begin{aligned} \exists xP(x)\rightarrow\forall xQ(x)&\Leftrightarrow\forall x\lnot P(x)\lor\forall xQ(x)\\ &\Rightarrow\forall x(\lnot P(x)\lor Q(x))\\ &\Leftrightarrow\forall x(P(x)\rightarrow Q(x)) \end{aligned}$$

多重量词律

• $\forall x\forall yP(x,y)\Leftrightarrow\forall y\forall xP(x,y)$
  $\exists x\exists yP(x,y)\Leftrightarrow\exists y\exists xP(x,y)$
• $\exists x\forall yP(x,y)\Rightarrow\forall y\exists xP(x,y)$
  $\forall x\exists yP(x,y)\Rightarrow\exists y\exists xP(x,y)$

对于两个变元可由下图直观展示：

谓词逻辑的推理理论

推理规则

命题逻辑的推理规则在谓词逻辑中同样适用，但在谓词逻辑的推理过程中，有时需要消去或引入量词

消去量词

在消去量词时先存在指定后全称指定

存在指定规则

存在指定规则(existential specification)，简记 ES，如下

$$\frac{\exists xP(x)}{\therefore P(a)}$$

其中，$P$ 是谓词，$a$ 是论域中使得 $P(a)$ 为真的个体

该规则的含义是：如果 $\exists xP(x)$ 为真，那么该论域中存在个体常元 $a$，使得 $P(a)$ 为真

全称指定规则

全称指定规则(universal specification)，简记 US，如下

$$\frac{\forall xP(x)}{\therefore P(y)}$$

其中，$P$ 是谓词，$y$ 是自由变元

该规则的含义是：如果 $\forall xP(x)$ 为真，那么对于该论域中任何个体常元 $a$，都有 $P(a)$ 为真

引入量词

存在推广规则

存在推广规则(existential generalization)，简记 EG，如下

$$\frac{P(a)}{\therefore \exists xP(x)}$$

其中，$P$ 是谓词，$a$ 是论域中使得 $P(a)$ 为真的个体

该规则的含义是：如果论域中存在个体常元 $a$，使得 $P(a)$ 为真，那么 $\exists xP(x)$ 为真

全称推广规则

全称推广规则(universal generalization)，简记 UG，如下

$$\frac{\Gamma\Rightarrow P(y)}{\therefore\Gamma\Rightarrow\forall xP(x)}$$

其中，$\Gamma$ 是已知公理和前提的合取，$P$ 是谓词，$y$ 是自由变元

该规则的含义是：如果 $\Gamma$ 能推出对论域任意个体 $y$ 都有 $P(y)$ 为真，那么 $\forall xP(x)$ 为真

参考

[1] 离散数学西安电子科技大学出版社第二版
[2] CSDN博客