谓词逻辑

谓词

def:

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

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

应用

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

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

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

其中： * A(x) 为一元谓词；H(x,y) 为二元谓词 * A(a) 为一元谓词常项；H(a,b) 为二元谓词常项

## 引入量词 >

> \forall" : 任意的 x > * 存在量词：符号 "\exists" : 存在这样的 x

** 例 2：** 用谓词逻辑将下列命题符号化： <1> 所有的偶数均能够被 2 整除。 设 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> 没有不犯错的人 设 x 为人，B(x): x 犯过错 则命题符号化为：\neg \exists x(A(x)\wedge \neg B(x))

> ⚠️总结：不难发现 > * 全称量词 "\rightarrow > * 存在量词 "\exists" 后加 \wedge

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

对于下述公式：

其中： *

> 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> \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))

### 前束范式

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

** 例 4：** 求谓词公式的前束范式 <1> \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> \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))