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

（国外经典教材）离散数学及其应用 第七版Discrete Mathematics and Its Applications 7th，作者是Kenneth H.Rosen，袁崇义译，机械工业出版社离散数学 第二版，武波等编著，西安电子科技大学出版社，离散数学 第三版，方世昌等编著，西安电子科技大学出版社，（经典参考书及其题解）离散数学/离散数学——理论•分析•题解，左孝凌、李为鉴、刘永才编著，上海科学技术文献出版社离散数学习题集：数理逻辑与集合论分册，耿素云；图论分册，耿素云；抽象代数分册， 张立昂。北京大学出版社

文章目录

3. 逻辑等价与蕴含、谓词演算的永真公式3.1 谓词逻辑的逻辑等价与蕴含3.2 谓词演算的永真公式3.2.1 命题逻辑的等价式和蕴含式在谓词逻辑中的推广应用3.2.2 量词的否定律3.2.3 量词辖域的扩张与收缩律3.2.4 量词的分配律3.2.5 多重量词律3.2.6 常用等价公式和蕴含公式3.3 前束范式

3. 逻辑等价与蕴含、谓词演算的永真公式

3.1 谓词逻辑的逻辑等价与蕴含

定义3.1.1 给定任意两个谓词公式 AAA 和 BBB ，若对于任何赋值，AAA 和 BBB 的真值均相同，则称谓词公式 AAA 和 BBB 等价，记为 A⇔BA\Leftrightarrow BA⇔B 。

定义3.1.2 给定任意两个谓词公式 AAA 和 BBB ，若 A→BA\to BA→B 是永真式，则称 AAA 蕴含 BBB ，记为 A⇒BA \Rightarrow BA⇒B 。

类似于命题逻辑的逻辑等价与蕴含，对于谓词公式 A,B,CA, B, CA,B,C ，有如下结论：

A⇔BA \Leftrightarrow BA⇔B 当且仅当 A↔BA \leftrightarrow BA↔B 是重言式。A⇔BA \Leftrightarrow BA⇔B 当且仅当 A⇒BA \Rightarrow BA⇒B 且 B⇒AB \Rightarrow AB⇒A 。A⇔BA \Leftrightarrow BA⇔B 且 B⇔CB \Leftrightarrow CB⇔C ，则 A⇔CA \Leftrightarrow CA⇔C（谓词逻辑等价关系的传递规则）。A⇒BA \Rightarrow BA⇒B 且 B⇒CB \Rightarrow CB⇒C ，则 A⇒CA \Rightarrow CA⇒C（谓词逻辑蕴含关系的传递规则）。

命题逻辑中的代入规则、替换规则，在谓词逻辑中同样适用。

3.2 谓词演算的永真公式

3.2.1 命题逻辑的等价式和蕴含式在谓词逻辑中的推广应用

对于命题逻辑中的任一等价/蕴含公式，对其应用代入规则，即用谓词逻辑的任意公式代入命题逻辑等价/蕴含公式中的某个命题变元，所得结果是谓词逻辑的一个等价/蕴含公式。例如，对 E10E_{10}E10​ 德摩根律 ¬(A∧B)⇔¬A∨¬B\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B¬(A∧B)⇔¬A∨¬B ，用 ∀xP(x)\forall xP(x)∀xP(x) 代入 AAA 、∃xQ(x)\exist xQ(x)∃xQ(x) 代入 BBB ，则有 ¬(∀xP(x)∧∃xQ(x))⇔¬∀xP(x)∨¬∃xQ(x)\lnot (\forall xP(x) \land \exist xQ(x)) \Leftrightarrow \lnot \forall xP(x) \lor \lnot \exist xQ(x)¬(∀xP(x)∧∃xQ(x))⇔¬∀xP(x)∨¬∃xQ(x)

3.2.2 量词的否定律

量词的否定律（2个公式），说明全称量词和存在量词可以相互表达。

¬∀xP(x)⇔∃x¬P(x)¬∃xP(x)⇔∀x¬P(x)\begin{aligned} &\lnot \forall xP(x) \Leftrightarrow \exist x\lnot P(x)\\ &\lnot \exist xP(x) \Leftrightarrow \forall x\lnot P(x) \end{aligned} ​¬∀xP(x)⇔∃x¬P(x)¬∃xP(x)⇔∀x¬P(x)​

证明：

（1）设论域为 DDD ，ttt 是任一赋值。

如果 ttt 使得 ¬∀xP(x)\lnot \forall xP(x)¬∀xP(x) 为真，则 ttt 使得 ∀xP(x)\forall xP(x)∀xP(x) 为假，即存在个体 a∈Da \in Da∈D 使得 P(a)P(a)P(a) 为假，从而有 ¬P(a)\lnot P(a)¬P(a) 为真，故有 ∃x¬P(x)\exist x\lnot P(x)∃x¬P(x) 为真。如果 ttt 使得 ¬∀xP(x)\lnot \forall xP(x)¬∀xP(x) 为假，则 ttt 使得 ∀xP(x)\forall xP(x)∀xP(x) 为真，即对于任一个体 a∈Da \in Da∈D ，均有 P(a)P(a)P(a) 为真，从而有 ¬P(a)\lnot P(a)¬P(a) 为假，故有 ∃x¬P(x)\exist x\lnot P(x)∃x¬P(x) 为假。综上所述，¬∀xP(x)⇔∃x¬P(x)\lnot \forall xP(x) \Leftrightarrow \exist x\lnot P(x)¬∀xP(x)⇔∃x¬P(x) 成立。再给出等价公式 ¬∀xP(x)⇔∃x¬P(x)\lnot \forall xP(x) \Leftrightarrow \exist x\lnot P(x)¬∀xP(x)⇔∃x¬P(x) 在一个有限论域上的证明。设有限论域为 D={a1,a2,…,an}D = \{ a_1, a_2, \dots, a_n\}D={a1​,a2​,…,an​} ，则对某个个体变元 xxx 的量化可以用命题形式表示，于是有：

¬∀xP(x)⇔¬(P(a1)∧P(a2)∧⋯∧P(an))⇔¬P(a1)∨¬P(a2)∨⋯∨¬P(an)⇔∃x¬P(x)\begin{aligned} \lnot \forall xP(x) &\Leftrightarrow \lnot (P(a_1) \land P(a_2) \land \dots \land P(a_n)) \\ &\Leftrightarrow \lnot P(a_1) \lor \lnot P(a_2) \lor \dots \lor \lnot P(a_n) \\ &\Leftrightarrow \exist x\lnot P(x) \end{aligned}¬∀xP(x)​⇔¬(P(a1​)∧P(a2​)∧⋯∧P(an​))⇔¬P(a1​)∨¬P(a2​)∨⋯∨¬P(an​)⇔∃x¬P(x)​

（2）设论域为 DDD ，ttt 是任一赋值。

如果 ttt 使得 ¬∃xP(x)\lnot \exist xP(x)¬∃xP(x) 为真，则 ttt 使得 ∃xP(x)\exist xP(x)∃xP(x) 为假，即对于任一个体 a∈Da \in Da∈D ，均有 P(a)P(a)P(a) 为假，从而有 ¬P(a)\lnot P(a)¬P(a) 为真，故有 ∀x¬P(x)\forall x\lnot P(x)∀x¬P(x) 为真。如果 ttt 使得 ¬∃xP(x)\lnot \exist xP(x)¬∃xP(x) 为假，则 ttt 使得 ∃xP(x)\exist xP(x)∃xP(x) 为真，即存在个体 a∈Da \in Da∈D 使得 P(a)P(a)P(a) 为真，从而 ¬P(a)\lnot P(a)¬P(a) 为假，故有 ∀x¬P(x)\forall x\lnot P(x)∀x¬P(x) 为假。综上所述，¬∃xP(x)⇔∀x¬P(x)\lnot \exist xP(x) \Leftrightarrow \forall x\lnot P(x)¬∃xP(x)⇔∀x¬P(x) 成立。再给出等价公式 ¬∃xP(x)⇔∀x¬P(x)\lnot \exist xP(x) \Leftrightarrow \forall x\lnot P(x)¬∃xP(x)⇔∀x¬P(x) 在一个有限论域上的证明。设有限论域为 D={a1,a2,…,an}D = \{ a_1, a_2, \dots, a_n\}D={a1​,a2​,…,an​} ，则对某个个体变元 xxx 的量化可以用命题形式表示，于是有：

¬∃xP(x)⇔¬(P(a1)∨P(a2)∨⋯∨P(an))⇔¬P(a1)∧¬P(a2)∧⋯∧¬P(an)⇔∀x¬P(x)\begin{aligned} \lnot \exist xP(x)&\Leftrightarrow \lnot (P(a_1) \lor P(a_2) \lor \dots \lor P(a_n)) \\ &\Leftrightarrow \lnot P(a_1) \land \lnot P(a_2) \land \dots \land \lnot P(a_n) \\ &\Leftrightarrow \forall x\lnot P(x) \end{aligned}¬∃xP(x)​⇔¬(P(a1​)∨P(a2​)∨⋯∨P(an​))⇔¬P(a1​)∧¬P(a2​)∧⋯∧¬P(an​)⇔∀x¬P(x)​

3.2.3 量词辖域的扩张与收缩律

设 P(x)P(x)P(x) 是谓词公式，QQQ 是不含自由变元 xxx 的谓词公式。于是有：

（1）∀x(P(x)∧Q))⇔∀xP(x)∧Q\forall x(P(x) \land Q)) \Leftrightarrow \forall xP(x) \land Q∀x(P(x)∧Q))⇔∀xP(x)∧Q

（2）∀x(P(x)∨Q))⇔∀xP(x)∨Q\forall x(P(x) \lor Q)) \Leftrightarrow \forall xP(x) \lor Q∀x(P(x)∨Q))⇔∀xP(x)∨Q

（3）∃x(P(x)∧Q)⇔∃xP(x)∧Q\exist x(P(x) \land Q) \Leftrightarrow \exist xP(x) \land Q∃x(P(x)∧Q)⇔∃xP(x)∧Q

（4）∃x(P(x)∨Q)⇔∃xP(x)∨Q\exist x(P(x) \lor Q) \Leftrightarrow \exist xP(x) \lor Q∃x(P(x)∨Q)⇔∃xP(x)∨Q

上面一组比较简单，下面一组比较复杂：

（5）∃xP(x)→Q⇔∀x(P(x)→Q)\exist xP(x) \to Q \Leftrightarrow \forall x(P(x) \to Q)∃xP(x)→Q⇔∀x(P(x)→Q)

（6）∀xP(x)→Q⇔∃x(P(x)→Q)\forall xP(x) \to Q \Leftrightarrow \exist x(P(x) \to Q)∀xP(x)→Q⇔∃x(P(x)→Q)

（7）Q→∃xP(x)⇔∃x(Q→P(x))Q\to \exist xP(x) \Leftrightarrow \exist x(Q \to P(x))Q→∃xP(x)⇔∃x(Q→P(x))

（8）Q→∀xP(x)⇔∀x(Q→P(x))Q \to \forall xP(x) \Leftrightarrow \forall x(Q \to P(x))Q→∀xP(x)⇔∀x(Q→P(x))

证明（5）∃xP(x)→Q⇔¬∃xP(x)∨Q⇔∀x¬P(x)∨Q⇔∀x(¬P(x)∨Q)⇔∀x(P(x)→Q)\begin{aligned} \exist xP(x) \to Q &\Leftrightarrow \lnot \exist xP(x) \lor Q \\ &\Leftrightarrow \forall x \lnot P(x) \lor Q \\ &\Leftrightarrow \forall x(\lnot P(x) \lor Q) \\ &\Leftrightarrow \forall x(P(x) \to Q)\end{aligned}∃xP(x)→Q​⇔¬∃xP(x)∨Q⇔∀x¬P(x)∨Q⇔∀x(¬P(x)∨Q)⇔∀x(P(x)→Q)​

证明（6）∀xP(x)→Q⇔¬∀xP(x)∨Q⇔∃x¬P(x)∨Q⇔∃x(¬P(x)∨Q)⇔∃x(P(x)→Q)\begin{aligned} \forall xP(x) \to Q &\Leftrightarrow \lnot \forall xP(x) \lor Q \\ &\Leftrightarrow \exist x \lnot P(x) \lor Q \\ &\Leftrightarrow \exist x(\lnot P(x) \lor Q) \\ &\Leftrightarrow \exist x(P(x) \to Q)\end{aligned}∀xP(x)→Q​⇔¬∀xP(x)∨Q⇔∃x¬P(x)∨Q⇔∃x(¬P(x)∨Q)⇔∃x(P(x)→Q)​

证明（7）Q→∃xP(x)⇔¬Q∨∃xP(x)⇔∃x(P(x)∨¬Q)⇔∃x(Q→P(x))\begin{aligned} Q\to \exist xP(x) &\Leftrightarrow \lnot Q\lor \exist xP(x) \\ &\Leftrightarrow \exist x(P(x) \lor \lnot Q) \\ &\Leftrightarrow \exist x(Q \to P(x)) \end{aligned}Q→∃xP(x)​⇔¬Q∨∃xP(x)⇔∃x(P(x)∨¬Q)⇔∃x(Q→P(x))​

证明（8） Q→∀xP(x)⇔¬Q∨∀xP(x)⇔∀x(P(x)∨¬Q)⇔∀x(Q→P(x))\begin{aligned} Q\to \forall xP(x) &\Leftrightarrow \lnot Q \lor \forall xP(x) \\ &\Leftrightarrow \forall x(P(x) \lor \lnot Q) \\ &\Leftrightarrow \forall x(Q \to P(x)) \end{aligned}Q→∀xP(x)​⇔¬Q∨∀xP(x)⇔∀x(P(x)∨¬Q)⇔∀x(Q→P(x))​

3.2.4 量词的分配律

有限论域中易证（1）和（2）：

（1）∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)\forall x(P(x) \land Q(x)) \Leftrightarrow \forall xP(x) \land \forall xQ(x)∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)

（2）∃x(P(x)∨Q(x))⇔∃xP(x)∨∃xQ(x)\exist x(P(x) \lor Q(x)) \Leftrightarrow \exist xP(x) \lor \exist xQ(x)∃x(P(x)∨Q(x))⇔∃xP(x)∨∃xQ(x)

（3）∀xP(x)∨∀xQ(x)⇒∀x(P(x)∨Q(x))\forall xP(x) \lor \forall xQ(x) \Rightarrow \forall x(P(x) \lor Q(x))∀xP(x)∨∀xQ(x)⇒∀x(P(x)∨Q(x))

（4）∃x(P(x)∧Q(x))⇒∃xP(x)∧∃xQ(x)\exist x(P(x) \land Q(x)) \Rightarrow \exist xP(x) \land \exist x Q(x)∃x(P(x)∧Q(x))⇒∃xP(x)∧∃xQ(x)

上面一组比较简单，下面一组比较复杂：

（5）∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x)\forall x(P(x) \to Q(x)) \Rightarrow \forall xP(x) \to \forall xQ(x)∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x)

（6）∃x(P(x)→Q(x))⇔∀xP(x)→∃xQ(x)\exist x(P(x) \to Q(x)) \Leftrightarrow \forall xP(x) \to \exist xQ(x)∃x(P(x)→Q(x))⇔∀xP(x)→∃xQ(x)

（7）∀x(P(x)↔Q(x))⇒∀xP(x)↔∀xQ(x)\forall x(P(x) \leftrightarrow Q(x)) \Rightarrow \forall xP(x) \leftrightarrow \forall xQ(x)∀x(P(x)↔Q(x))⇒∀xP(x)↔∀xQ(x)

（8）∃xP(x)→∀xQ(x)⇒∀x(P(x)→Q(x))\exist xP(x) \to \forall xQ(x) \Rightarrow \forall x(P(x) \to Q(x))∃xP(x)→∀xQ(x)⇒∀x(P(x)→Q(x))

证明（1）设 ttt 是谓词公式 ∀x(P(x)∧Q(x))\forall x(P(x) \land Q(x))∀x(P(x)∧Q(x)) 的任一赋值，其论域为 DDD 。

如果 ttt 使得 ∀x(P(x)∧Q(x))\forall x(P(x) \land Q(x))∀x(P(x)∧Q(x)) 为真，则对于任一个体 a∈Da \in Da∈D ，使得 P(a)∧Q(a)P(a) \land Q(a)P(a)∧Q(a) 为真，即 P(a)P(a)P(a) 和 Q(a)Q(a)Q(a) 的真值均为真，从而有 ∀xP(x)\forall xP(x)∀xP(x) 和 ∀xQ(x)\forall xQ(x)∀xQ(x) 均为真，即 ∀xP(x)∧∀xQ(x)\forall xP(x) \land \forall xQ(x)∀xP(x)∧∀xQ(x) 为真；如果 ttt 使得 ∀xP(x)∧Q(x))\forall xP(x) \land Q(x))∀xP(x)∧Q(x)) 为假，则存在个体 a∈Da \in Da∈D ，使得 P(a)∧Q(a)P(a) \land Q(a)P(a)∧Q(a) 为假，即 P(a)P(a)P(a) 或 Q(a)Q(a)Q(a) 的真值为假，从而有 ∀xP(x)\forall xP(x)∀xP(x) 或 ∀xQ(x)\forall xQ(x)∀xQ(x) 为假，即 ∀xP(x)∧∀xQ(x)\forall xP(x) \land \forall xQ(x)∀xP(x)∧∀xQ(x) 为假综上所述，∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)\forall x(P(x) \land Q(x)) \Leftrightarrow \forall xP(x) \land \forall xQ(x)∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x) 成立

证明（5）任给一个赋值 ttt ，其论域为 DDD 。假设在 ttt 下，∀xP(x)→∀xQ(x)\forall xP(x) \to \forall xQ(x)∀xP(x)→∀xQ(x) 的真值为 FFF ，则 ∀xP(x)\forall xP(x)∀xP(x) 为 TTT ，∀xQ(x)\forall xQ(x)∀xQ(x) 为 FFF 。由 ∀xQ(x)\forall xQ(x)∀xQ(x) 为 FFF ，得到存在 a∈Da\in Da∈D ，使得 Q(a)Q(a)Q(a) 为 FFF ，又因为 ∀xP(x)\forall xP(x)∀xP(x) 为 TTT ，有 P(a)P(a)P(a) 为 TTT ，从而推出 P(a)→Q(a)P(a) \to Q(a)P(a)→Q(a) 为 FFF ，即 ∀x(P(x)→Q(x))\forall x(P(x) \to Q(x))∀x(P(x)→Q(x)) 为 FFF 。由否定后件法得到，∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x)\forall x(P(x) \to Q(x)) \Rightarrow \forall xP(x) \to \forall xQ(x)∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x) 。

证明（8）∃xP(x)→∀xQ(x)⇔¬∃xP(x)∨∀xQ(x)⇔∀x¬P(x)∨∀xQ(x)⇒∀x(¬P(x)∨Q(x))⇔∀x(P(x)→Q(x))\begin{aligned} \exist xP(x) \to \forall xQ(x) &\Leftrightarrow \lnot \exist xP(x) \lor \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) \to Q(x)) \end{aligned} ∃xP(x)→∀xQ(x)​⇔¬∃xP(x)∨∀xQ(x)⇔∀x¬P(x)∨∀xQ(x)⇒∀x(¬P(x)∨Q(x))⇔∀x(P(x)→Q(x))​

3.2.5 多重量词律

对于多个量词的情况，量词出现的先后次序不能随意调换。为了便于说明，这里只讨论两个量词的情况，更多量词的使用方法与此类似。若设 P(x,y)P(x, y)P(x,y) 表示 x,yx, yx,y 是同乡，xxx 的论域为一班学生，yyy 的论域为二班学生，则：

∀x∀yP(x,y)\forall x\forall yP(x, y)∀x∀yP(x,y) 表示“一班每个学生和二班每个学生都是同乡”，∀y∀xP(x,y)\forall y\forall xP(x, y)∀y∀xP(x,y) 表示“二班每个学生和一班每个学生都是同乡”，二者都表示“一班和二班所有的学生都是同乡”，含义相同，所以 ∀x∀yP(x,y)⇔∀y∀xP(x,y)\forall x\forall yP(x, y) \Leftrightarrow \forall y\forall xP(x, y)∀x∀yP(x,y)⇔∀y∀xP(x,y) 。∃x∃yP(x,y)\exist x\exist yP(x, y)∃x∃yP(x,y) 表示“一班的某些学生和二班的某些学生是同乡”，例如一班的小明和二班的小李是同乡，也可以说“二班的某些学生和一班的某些学生是同乡”，即 ∃y∃xP(x,y)\exist y\exist xP(x, y)∃y∃xP(x,y) ，所以 ∃x∃yP(x,y)⇔∃y∃xP(x,y)\exist x\exist yP(x, y) \Leftrightarrow \exist y\exist xP(x, y)∃x∃yP(x,y)⇔∃y∃xP(x,y) 。∀x∃yP(x,y)\forall x \exist yP(x, y)∀x∃yP(x,y) 表示“对于一班任意学生，二班至少有一个学生和他是同乡”，∃y∀xP(x,y)\exist y\forall xP(x, y)∃y∀xP(x,y) 表示“二班存在某个学生，和一班所有学生是同乡”。显然，二者的含义是不同的，如果后者为真，则前者也为真，即 ∃y∀xP(x,y)⇒∀x∃yP(x,y)\exist y\forall xP(x, y) \Rightarrow \forall x\exist yP(x, y)∃y∀xP(x,y)⇒∀x∃yP(x,y) 。但是如果前者为真，后者不一定为真，即 ∀x∃yP(x,y)⇏∃y∀xP(x,y)\forall x\exist yP(x, y) \nRightarrow \exist y\forall xP(x, y)∀x∃yP(x,y)⇏∃y∀xP(x,y) ，所以二者不等价。

对于二元谓词前置量词，有以下8个等价公式和蕴含公式，可见，全称量词和存在量词在谓词公式中出现的次序不能随意改变：

（1）∀x∀yP(x,y)⇔∀y∀xP(x,y)\forall x\forall yP(x, y) \Leftrightarrow \forall y\forall xP(x, y)∀x∀yP(x,y)⇔∀y∀xP(x,y)

（2）∀x∀yP(x,y)⇒∃y∀xP(x,y)\forall x\forall yP(x, y) \Rightarrow \exist y\forall xP(x, y)∀x∀yP(x,y)⇒∃y∀xP(x,y)

（3）∀y∀xP(x,y)⇒∃x∀yP(x,y)\forall y\forall xP(x, y) \Rightarrow \exist x\forall yP(x, y)∀y∀xP(x,y)⇒∃x∀yP(x,y)

（4）∃x∀yP(x,y)⇒∀y∃xP(x,y)\exist x\forall yP(x, y) \Rightarrow \forall y \exist xP(x, y)∃x∀yP(x,y)⇒∀y∃xP(x,y)

（5）∃y∀xP(x,y)⇒∀x∃yP(x,y)\exist y\forall xP(x, y) \Rightarrow \forall x\exist yP(x, y)∃y∀xP(x,y)⇒∀x∃yP(x,y)

（6）∀x∃yP(x,y)⇒∃y∃xP(x,y)\forall x\exist yP(x, y) \Rightarrow \exist y\exist xP(x, y)∀x∃yP(x,y)⇒∃y∃xP(x,y)

（7）∀y∃xP(x,y)⇒∃x∃yP(x,y)\forall y\exist xP(x, y) \Rightarrow \exist x\exist yP(x, y)∀y∃xP(x,y)⇒∃x∃yP(x,y)

（8）∃x∃yP(x,y)⇔∃y∃xP(x,y)\exist x\exist yP(x, y) \Leftrightarrow \exist y\exist xP(x, y)∃x∃yP(x,y)⇔∃y∃xP(x,y)

其关系图如下所示：

3.2.6 常用等价公式和蕴含公式

谓词逻辑中常用的等价公式和蕴含公式如下所示。结合替换规则和传递规则，可以比较方便地推导证明谓词逻辑中的一些等价公式和蕴含公式：

3.3 前束范式

对于一个谓词公式，如果所有量词都非否定地集中出现在整个公式的最前端，它们的辖域为整个公式，则称该公式为前束范式，如 ∀x∀y∃z(Q(x,y)→R(z))\forall x\forall y\exist z(Q(x, y) \to R(z))∀x∀y∃z(Q(x,y)→R(z)) 。应用量词的否定律和量词辖域的扩张公式，结合换名规则，任何一个谓词公式都可以变换为前束范式。

【离散数学】数理逻辑 第二章 谓词逻辑(3) 谓词公式的逻辑等价与蕴含 谓词演算的永真公式