【离散数学】数理逻辑第二章谓词逻辑(4) 谓词逻辑的推理理论

谓词逻辑的推理理论

memcpy0

5673人浏览 · 2021-10-14 22:27:04

memcpy0 · 2021-10-14 22:27:04 发布

本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

（国外经典教材）离散数学及其应用第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen ，袁崇义译，机械工业出版社

离散数学第二版，武波等编著，西安电子科技大学出版社，2006年

离散数学第三版，方世昌等编著，西安电子科技大学出版社，2013年

（经典参考书及其题解）离散数学/离散数学——理论•分析•题解，左孝凌、李为鉴、刘永才编著，上海科学技术文献出版社

离散数学习题集：数理逻辑与集合论分册，耿素云；图论分册，耿素云；抽象代数分册，张立昂。北京大学出版社

文章目录

4. 谓词逻辑的推理理论

4. 谓词逻辑的推理理论

类似于命题逻辑的推理理论，在谓词逻辑中，设 $H_1, H_2, \dots, H_n, C$ 是谓词公式，若 $H_1 \land H_2 \land \dots \land H_n \Rightarrow C$ ，则称 $C$ 是由一组前提 $H_1, H_2, \dots, H_n$ 的有效结论 valid conclusion ，或称 $C$ 可由前提 $H_1, H_2, \dots , H_n$ 逻辑地推出。从前提 $H_1, H_2, \dots, H_n$ 推出结论 $C$ 的过程，称为推理 reasoning 、论证 argument 或证明 proof 。

谓词逻辑的推理方法，可以看作是命题逻辑的推理理论的扩充。命题逻辑的推理规则和证明方法，如 $P$ 规则、 $T$ 规则、 $C P$ 规则和无义证明法、平凡证明法、直接证明法、归谬法（反证法）、CP规则法，在谓词逻辑中同样适用。

只是在谓词逻辑中，某些前提和结论可能是带量词约束的，在推理过程中有时需要消去或引入量词。下面介绍消去或引入量词的四种常见推理规则。

4.1 消去或引入量词的常见推理规则

4.1.1 存在指定规则 `existential specification` 消去存在量词

这一规则简记为 $E S$ 。其中 $P$ 是谓词， $a$ 是论域中使得 $P (a)$ 的真值为真的个体。存在指定规则的含义是：如果 $\exist xP(x)$ 为真，则该论域中存在个体常元 $a$ ，使得 $P (a)$ 的真值为真，此处应将 $\exist x$ 辖域内所有变元 $x$ 统一指定为个体常元 $a$ ：
$\frac {\exist xP(x) }{ \therefore P(a)}$

实际应用本规则时，通常指定为论域中某一确定的个体 $a$ ，前提是所指定的个体使得谓词的真值为真。例如，设 $P (x)$ 为 $x$ 是食草动物，论域为全体动物，则对 $\exist xP(x)$ 应用 $E S$ 可以得到 $P (山羊)$ ，但不能得到 $P (老虎)$ 。

4.1.2 全称指定规则 `universal specification` 消去全称量词

这一规则简记为 $U S$ 。其中 $P$ 是谓词， $y$ 在 $P (y)$ 中是自由变元。全称指定规则的含义是：如果 $\forall xP(x)$ 为真，那么 $x$ 的论域中的每个确定个体 $a$ 必然满足 $P (a)$ 的真值为真，故而全称指定规则也可以指定到确定的个体常元。
$\frac {\forall xP(x) }{ \therefore P(y)}$

需要注意的是，对谓词公式 $\exist xP(x)$ 和 $\forall xQ(x)$ 均应用指定规则、且指定为同一个体时，应该先进行存在指定，再进行全称指定。因为 $\exist xP(x)$ 和 $\forall xQ(x)$ 两者都成立时，若 $P (a)$ 为真，则 $Q (a)$ 为真；但若 $Q (a)$ 为真，并不一定满足 $P (a)$ 为真。

4.1.3 存在推广规则 `existential generalization` 引入存在量词

这一规则简记为 $E G$ 。存在推广规则的意义是：如果论域内某一确定个体 $a$ 能使 $P (a)$ 的真值为真，那么一定有 $\exist xP(x)$ 为真。应用 $E G$ 并不要求将个体常元 $a$ 出现的每一处都推广为 $x$ 。例如，由 “ $1 = 1$ ” 可以推广为“存在 $x$ 使得 $x = x$ ” ，也可以推广为“存在 $x$ 使得 $x = 1$ ” 。但要求推广后的 $x$ 都受存在量词的约束。
$\frac {P(a)}{ \therefore \exist xP(x) }$

4.1.4 全称推广规则 `universal generalization` 引入全称量词

这一规则简记为 $U G$ 。其中 $\Gamma$ 是已知公理和前提的合取， $\Gamma$ 中没有变元 $x$ 的自由出现（即全是约束出现）。全称推广规则的意义是：如果从 $\Gamma$ 可推出 $P (x)$ ，那么从 $\Gamma$ 也可以推出 $\forall xP(x)$ 。或者说，如果能从已知的公理和前提，证明对于论域中的任一个体 $x$ 都使 $P (x)$ 为真，则可以得到 $\forall xP(x)$ 为真。
$\frac {\Gamma \Rightarrow P(x) }{ \therefore \Gamma \Rightarrow \forall xP(x)}$

下面的例子很好地说明了全称推广规则的内涵。

4.2 推理理论的实际运用

应用命题逻辑中给出的基本推理规则和证明方法，结合命题逻辑和谓词逻辑的等价公式和蕴含公式、量词的否定律、量词辖域的扩张和收缩律、量词的分配律以及上述四条规则，就可以完成谓词逻辑的推理证明。

例1：证明线段中垂线上所有的点到线段两端点的距离相等。
证明：如下图所示，从线段 $A B$ 的中垂线上任意选取一点 $X$ ，连接点 $X$ 到线段两个端点，则 $∣ X A ∣, ∣ X B ∣$ 即为 $X$ 到两端点的距离。由于线段的中垂线过线段的中点 $O$ ，并且与线段垂直，因此有 $∣ O A ∣ = ∣ O B ∣$ 。根据勾股定理知：
$\sqrt{|OA|^2 + |OX|^2} = \sqrt{|OB|^2 + |OX|^2} = |XB| \quad \blacksquare \ Q.E.D$
请添加图片描述
例2：证明苏格拉底三段论——“所有的人都是要死的”，“苏格拉底是人”，“所以，苏格拉底是要死的”。
证明：设论域为全总个体域， $H (x)$ ： $x$ 是人， $D (x)$ ： $x$ 是要死的， $s$ ：苏格拉底。现要证明以下蕴含公式： $\forall x(H(x) \to D(x)), H(s) \Rightarrow D(s)$ 。
$\begin{aligned} &(1)\ \forall x(H(x) \to D(x)) \quad& P\\ &(2)\ H(s) \to D(s) \quad& US, (1)\\ &(3)\ H(s) \quad& P\\ &(4)\ D(s) \quad& T, (3), (4), I(假言推理) \end{aligned}$

例3：证明 $\forall x(C(x) \to W(x) \land R(x)) \land \exist x(C(x) \land Q(x)) \Rightarrow \exist x(Q(x) \land R(x))$ 。
证明：
$\begin{aligned} &(1)\ \exist x(C(x) \land Q(x)) \quad& P\\ &(2)\ \forall x(C(x) \to W(x) \land R(x)) \quad& P\\ &(3)\ C(a) \land Q(a) \quad& ES, (1)\\ &(4)\ C(a) \to W(a) \land R(a) \quad& US, (2)\\ &(5)\ C(a) \quad& T, (3), I(化简式)\\ &(6)\ W(a) \land R(a) \quad& T, (4), (5), I(假言推理)\\ &(7)\ R(a) \quad& T, (6), I(化简式)\\ &(8)\ Q(a) \quad& T, (3), I(化简式)\\ &(9)\ Q(a) \land R(a) \quad& T, (7), (8), I(直推式)\\ &(10)\ \exist x(Q(x) \land R(x)) \quad& EG, (9) \end{aligned}$
注意，这里的步骤(3)和步骤(4)的次序不能颠倒，即应用指定规则指定为同一个体时，应该先进行存在指定，再进行全称指定。

例4：证明 $\forall x(P(x) \lor Q(x)) \Rightarrow \forall xP(x) \lor \exist xQ(x)$ 。
证明方法一归谬法（反证法）：
$\begin{aligned} &(1)\ \lnot (\forall xP(x) \lor \exist xQ(x)) \quad& P(假设前提)\\ &(2)\ \lnot \forall xP(x) \land \lnot \exist xQ(x) \quad& T, (1), E(德摩根律)\\ &(3)\ \lnot \forall xP(x) \quad& T, (2), I(化简式)\\ &(4)\ \lnot \exist xQ(x) \quad& T, (2), I(化简式)\\ &(5)\ \exist x\lnot P(x) \quad& T, (3), E(量词的否定律) \\ &(6)\ \lnot P(a) \quad& ES, (5)\\ &(7)\ \forall x\lnot Q(x) \quad& T, (4), E(量词的否定律)\\ &(8)\ \lnot Q(a) \quad& US, (7)\\ &(9)\ \lnot P(a) \land \lnot Q(a) \quad& T, (6), (8), I(直推式)\\ &(10)\ \lnot (P(a) \lor Q(a)) \quad& T, (9), E(德摩根律)\\ &(11)\ \forall x(P(x) \lor Q(x))) \quad& P\\ &(12)\ P(a) \lor Q(a) \quad& US,(11)\\ &(13)\ \lnot (P(a) \lor Q(a)) \land (P(a) \lor Q(a))\ (矛盾) \quad& T, (10), (12), 直推式 \end{aligned}$
证明方法二 CP规则法：将原式变换为 $\forall x(P(x) \lor Q(x))\Rightarrow \lnot \forall xP(x) \to \exist xQ(x)$
$\begin{aligned} &(1)\ \lnot \forall xP(x) \quad& P(附加前提) \\ &(2)\ \exist x\lnot P(x) \quad& T,(1), E(量词的否定律) \\ &(3)\ \lnot P(a) \quad& ES, (2)\\ &(4)\ \forall x(P(x) \lor Q(x)) \quad& P \\ &(5)\ P(a) \lor Q(a) \quad& US, (4)\\ &(6)\ Q(a) \quad& T, (3), (5), I(析取三段论)\\ &(7)\ \exist xQ(x) \quad& EG, (6)\\ &(8)\ \lnot \forall xP(x) \to \exist xQ(x) \quad& CP规则\\ \end{aligned}$

例5：指出下列推理中的错误，并说明理由。
$\begin{aligned} &(1)\ \forall x(A(x) \to B(x)) \quad &P前提引入&\\ &(2)\ A(y) \to B(y) \quad &US, (1)&\\ &(3)\ \exist xA(x) \quad &P前提引入&\\ &(4)\ A(y) \quad &ES, (3)&\\ &(5)\ B(y) \quad &T, (2), (4), I \\ &(6)\ \exist xB(x) \quad &T, (5), EG \end{aligned}$
解：第(2)步和第(4)步之间的次序出了错误。因为既要使用全称指定规则 $U S$ ，又要使用存在指定规则 $E S$ ，还要指定为相同的变元，所以应先作 $E S$ 后作 $U S$ 。
$\begin{aligned} &(1)\ \exist xA(x) \quad &P&\\ &(2)\ A(y) \quad &ES, (1)&\\ &(3)\ \forall x(A(x) \to B(x)) \quad &P&\\ &(4)\ A(y) \to B(y) \quad &US, (3)&\\ &(5)\ B(y) \quad &T, (2), (4), I \\ &(6)\ \exist xB(x) \quad &EG,(5) \end{aligned}$

例6：判断下列推理是否正确，并证明你的结论。
前提： $\forall x(P(x) \to R(x))$ ， $\forall x(Q(x) \to \lnot R(x))$
结论： $\forall x(Q(x) \to \lnot P(x))$
解：推理是正确的，证明过程如下：
$\begin{aligned} &(1)\ \forall x(Q(x) \to \lnot R(x)) \quad& P \\ &(2)\ Q(y) \to \lnot R(y) \quad& US, (1)\\ &(3)\ \forall x(P(x) \to R(x)) \quad& P \\ &(4)\ P(y) \to R(y) \quad& US, (3)\\ &(5)\ \lnot R(y) \to \lnot P(y) \quad& T, (4), E(逆反律) \\ &(6)\ Q(y) \to \lnot P(y) \quad& T, (2), (5), I(前提三段论) \\ &(7)\ \forall x(Q(x) \to \lnot P(x)) \quad& UG, (6)\\ \end{aligned}$

例7：证明下列推理的有效性。
前提： $\exist x(S(x) \land \forall y(T(y) \to L(x, y)))$ ， $\forall x(S(x) \to \forall y(P(y) \to \lnot L(x, y)))$
结论： $\forall x(T(x) \to \lnot P(x))$
解：
$\begin{aligned} &(1)\ \exist x(S(x) \land \forall y(T(y) \to L(x, y))) \quad& P \\ &(2)\ S(a) \land \forall y(T(y) \to L(a, y)) \quad& ES, (1)\\ &(3)\ S(a) \quad& T, (2), I(化简式) \\ &(4)\ \forall y(T(y) \to L(a, y)) \quad& T, (2), I(化简式) \\ &(5)\ T(y) \to L(a, y) \quad& US, (4)\\ &(6)\ \forall x(S(x) \to \forall y(P(y) \to \lnot L(x, y))) \quad& P \\ &(7)\ S(a) \to \forall y(P(y) \to \lnot L(a, y)) \quad& US, (6)\\ &(8)\ \forall y(P(y) \to \lnot L(a, y)) \quad& T, (3), (7), I(假言推理)\\ &(9)\ P(y) \to\lnot L(a, y) \quad& US, (8)\\ &(10)\ L(a, y) \to \lnot P(y) \quad& T, (9), E(逆反律)\\ &(11)\ T(y) \to \lnot P(y) \quad& T, (5), (10),I(假言推理)\\ &(12)\ \forall x(T(x) \to \lnot P(x)) \quad& UG, (11) \end{aligned}$

例8：判断推理是否有效——所有事业有成就的人都是勤劳的人；存在一些勤劳的人，他们爱好业余写作；所以，有些事业有成就的人爱好业余写作。
解：设 $S (x)$ ： $x$ 是事业有成就的人， $Q (x)$ ： $x$ 是勤劳的人， $Z (x)$ ： $x$ 爱好业余写作，则符号化为： $\forall x(S(x) \to Q(x)), \exist x(Q(x) \land Z(x)) \Rightarrow \exist x(S(x) \land Z(x))$
经过分析，该论证是无效的，可以通过找出一个反例进行说明。取论域 $D = \{a, b\}$ ， $\land S(b) = 0 \land Q(a) = 1\land Q(b) = 1 \land Z(a) = 0 \land Z(b) = 1$ ，则 $\forall x(S(x) \to Q(x))$ 为真， $\exist x(Q(x) \land Z(x))$ 为真，所以前提为真，而 $\exist x(S(x) \land Z(x))$ 为假，不是永真式。

例9：设论域是某班所有学生，用给定的命题及谓词将以下句子符号化，并推理其结论。
（1）如果今天有选修课，有些学生就不能按时到会；当且仅当所有学生都按时到会，干部选举才能准时进行。所以，如果干部选举准时进行，那么今天没有选修课。（ $P$ ：今天没有选修课， $Q$ ：干部选举准时进行， $A (x)$ ： $x$ 按时到会）
解：命题可符号化为
$\lnot P \to \exist x\lnot A(x),\ \forall xA(x) \leftrightarrow Q \Rightarrow Q \to P \\ {} \\ \begin{aligned} &(1)\ \lnot P \to \exist x\lnot A(x) \quad& P \\ &(2)\ P\lor \exist x\lnot A(x) \quad& T, (1),E(蕴含律) \\ &(3)\ \exist x(\lnot A(x) \lor P) \quad& T, (2), E(量词辖域的扩张律) \\ &(4)\ \lnot A(a) \lor P \quad& ES, (3) \\ &(5)\ A(a) \to P \quad& T, (4), E(蕴含律)\\ &(6)\ \forall xA(x) \leftrightarrow Q \quad& P \\ &(7)\ (\forall xA(x) \to Q) \land (Q \to \forall xA(x)) \quad& T, (6), E(双条件律)\\ &(8)\ Q\to \forall xA(x) \quad& T, (7), I(化简式)\\ &(9)\ \forall x(Q \to A(x)) \quad& T, (8), E(量词辖域的扩张律)\\ &(10)\ Q \to A(a) \quad& US, (9)\\ &(11)\ Q \to P \quad& T, (5), (8), I(前提三段论)\\ \end{aligned}$

（2）每个研究生或者是推荐免试者，或者是统考选拔者；所有的推荐免试者的本科课程都学得好，但并非所有研究生本科课程都学得好。所以一定有研究生是统考选拔者。（ $P (x)$ ： $x$ 是研究生， $Q (x)$ ： $x$ 本科课程学得好， $A (x)$ ： $x$ 是推荐免试者， $B (x)$ ： $x$ 是统考选拔者）。
解：命题可符号化为
$\forall x(P(x) \to (A(x) \lor B(x))), \forall x(A(x) \to Q(x)), \lnot \forall x(P(x) \to Q(x))\\ \Rightarrow \exist x(P(x) \land B(x))\\ \\ {} \\ \begin{aligned} &(1)\ \lnot \forall x(P(x) \to Q(x))\ \quad& P \\ &(2)\ \exist x\lnot (P(x) \to Q(x)) \quad& T, (1), E(量词的否定律) \\ &(3)\ \lnot (P(a) \to Q(a)) \quad& ES, (2) \\ &(4)\ P(a) \land \lnot Q(a) \quad& T, (3), E(蕴含律,德摩根律) \\ &(5)\ P(a) \quad& T, (4), I(化简式)\\ &(6)\ \lnot Q(a) \quad& T, (4), I(化简式) \\ &(7)\ \forall x(P(x) \to (A(x) \lor B(x))) \quad& P\\ &(8)\ P(a) \to (A(a) \lor B(a)) \quad& US, (7)\\ &(9)\ A(a) \lor B(a) \quad& T, (5), (8), I(假言推理)\\ &(10)\ \forall x(A(x) \to Q(x)) \quad& P\\ &(11)\ A(a) \to Q(a) \quad& US, (10)\\ &(12)\ \lnot A(a) \quad& T, (6), (11), I(拒取式)\\ &(13)\ B(a) \quad& T, (9), (12), I(析取三段论)\\ &(14)\ P(a) \land B(a) \quad& T, (5), (13), I(直推式)\\ &(15)\ \exist x(P(x) \land B(x)) \quad& EG, (14) \end{aligned}$

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

UFW防火墙安全指南

UFW（Uncomplicated Firewall）是Ubuntu/Debian系统中简化防火墙管理的工具，通过直观命令帮助用户有效控制网络流量，提升系统安全性。文章详细介绍了UFW的基本命令，包括启停防火墙、添加规则、限制连接速率和日志配置等操作，并提供了安全最佳实践，如默认拒绝策略、IP地址限制和服务级规则管理。同时，还涵盖高级配置技巧，例如多网络接口设置、规则优先级调整、IPv6支持及与f