谓词逻辑

谓词

$def:$

• 个体词：可独立存在的客体
• 谓词：用来说明个体的性质或个体间的关系

如： 小明是个小学生
其中，小明 就是个体词，是个小学生 就是谓词, 说明了客体的性质。
再如： $6$ 大于 $5$
其中 6 与 5 为个体词，大于 为谓词，说明了客体间的关系。

---

应用

例1： 写命题的谓词表达式：

<1> 小明是个小学生
设 $A(x)$:$x$ 为小学生，$a$:小明
则命题符号化为：$A(a)$

<2> $6$ 大于 $5$
设 $H(x,y)$:$x$ 大于 $y$, $a:6,b:5$
则命题符号化为：$H(a,b)$

其中：

• $A(x)$ 为一元谓词； $H(x,y)$ 为二元谓词
• $A(a)$ 为一元谓词常项； $H(a,b)$ 为二元谓词常项

---

引入量词

$def:$ 个体域：个体变动的取值范围(类似于函数的定义域)

$def:$ 量词： 表示个体之间数量关系的词

• 全称量词：符号 “ $\forall$ “ : 任意的 $x$
• 存在量词：符号 “ $\exists$ “ : 存在这样的 $x$

例2： 用谓词逻辑将下列命题符号化：

<1> 所有的偶数均能够被 2 整除。
设 $A(x)$: $x$ 为偶数， $B(x)$: $x$ 能被 2 整除
则命题符号化为：$\forall x(A(x)\rightarrow B(x))$

<2> 有一些人登上过月球。
设 $A(x)$: $x$ 为人， $B(x)$: $x$ 登上过月球
则命题符号化为：$\exists x (A(x)\wedge B(x))$

<3> 每列火车都比某些汽车快。
设 $F(x)$: $x$ 是火车， $G(x)$: $x$ 是汽车，$H(x,y)$: $x$ 比 $y$ 快
则命题符号化为：$\forall x(F(x)\rightarrow \exists y(G(y)\wedge H(x,y))$

<4> 没有不犯错的人
设 $A(x)$ : $x$ 为人， $B(x)$: $x$ 犯过错
则命题符号化为：$\neg \exists x(A(x)\wedge \neg B(x))$

⚠️总结：不难发现

• 全称量词 “ $\forall$ “ 后加 $\rightarrow$
• 存在量词 “ $\exists$ “ 后加 $\wedge$

---

$def:$

• 量词的指导变元：$\forall /\exists + (x,y,z,…)$
• 量词的辖域： 量词的作用范围 $\forall /\exists x + (D)$, $D$ 即为辖域
• 变元由可分为：约束变元、自由变元

对于下述公式：

$$\forall \color{red}{x}\exists \color{blue}{y} (P(\color{red}{x},\color{blue}{y})\wedge Q(\color{blue}{y},z)) \wedge \exists \color{green}{x}R(\color{green}{x},\color{yellow}{y})$$

其中：

• $\color{red}{x},\color{blue}{y}$ 的辖域为：$(P(\color{red}{x},\color{blue}{y}) \wedge Q(\color{blue}{y},z))$
• $\color{green}{x}$ 的辖域为：$R(\color{green}{x},\color{yellow}{y})$
• $\color{red}{x},\color{blue}{y},\color{green}{x}$ 为约束变元
• $\color{yellow}{y},z$ 为自由变元

$def:$ 设 $A$ 和 $B$ 是任意两个谓词公式，如果 $A\rightarrow B$ 是重言式，称 $A$ 与 $B$ 等价，记为：$A\Leftrightarrow B$

⭐️需要熟记的等价式：

1. 命题逻辑中的等价式的代换实例是谓词逻辑中的等值式
   如：$A\rightarrow B \Leftrightarrow \neg A\vee B$ 相当于 $P(x)\rightarrow Q(x)\Leftrightarrow \neg P(x)\vee Q(x)$; 且 $\neg (A\wedge B)\Leftrightarrow \neg A\vee \neg B$ 相当于 $\neg(\exists xP(x)\wedge \forall xQ(x))\Leftrightarrow \neg \exists xP(x)\vee \neg \forall xQ(x)$

2. 量词否定转换
   $\neg \forall xP(x) \Leftrightarrow \exists x\neg P(x)$
   $\neg \exists xP(x) \Leftrightarrow \forall x\neg P(x)$

3. 量词辖域的扩张和收缩、
   $\forall x(A(x)\wedge \exists y B(y))\Leftrightarrow \forall xA(x) \wedge \exists y B(y)$ 收缩

4. 量词分配律
   $\color{red}{\forall} x(A(x)\color{red}{\wedge} B) \Leftrightarrow \forall xA(x) \wedge \forall x B(x)$
   $\color{green}{\exists} x(A(x)\color{green}{\vee} B) \Leftrightarrow \exists xA(x) \vee \exists x B(x)$
   ⚠️这里要注意的是只有当全称量词与合取符号，存在量词与析取符号两种情况时分配律才有效。

例3： 设个体域 $D = { a,b,c }$, 消去谓词公式中的量词

<1> $\exists xF(x) \rightarrow \forall yG(y)$
消去后：$F(a)\vee F(b)\vee F(c) \rightarrow G(a)\wedge G(b) \wedge G(c)$

<2> $\forall x\forall y(F(x)\rightarrow G(y))$
$\Leftrightarrow \forall x(F(x)\rightarrow \forall yG(y))$
$\Leftrightarrow \forall x(\neg F(x) \vee \forall y G(y))$
$\Leftrightarrow \forall x\neg F(x) \vee \forall yG(y)$; (x 辖域收缩)
$\Leftrightarrow \neg \exists xF(x)\vee \forall yG(y)$;(量词否定转换)
$\Leftrightarrow \exists xF(x)\rightarrow \forall yG(y)$;(等价式)
$\Leftrightarrow (F(a)\vee F(b)\vee F(c))\rightarrow (G(a)\wedge G(b)\wedge G(c))$

前束范式

$def:$ 一个谓词公式 $A$ , 若具有形式 $Q_1x_1Q_2x_2Q_3x_3 \cdots Q_nx_nM$ 其中每个$Q_i$ 为量词 $(\forall / \exists)$, $M$ 为不含量词的公式，则称 $A$ 为前束范式。

例4： 求谓词公式的前束范式

<1> $\neg \forall x(F(x)\rightarrow G(x))$
$\Leftrightarrow \exists x\neg(F(x)\rightarrow G(x))$
或 $\Leftrightarrow \exists x\neg (\neg F(x)\vee G(x))$
或 $\Leftrightarrow \exists x(F(x)\wedge G(x))$

<2> $\forall xF(x)\wedge \forall y G(y)$
$\Leftrightarrow \forall x \forall y(F(x)\wedge G(y))$
$\Leftrightarrow \forall xF(x)\wedge \forall x G(x)$ 换名规则
$\forall x(F(x)\wedge G(x))$

---