2.5 谓词演算的等价式和蕴含式

02谓词逻辑2.5谓词演算的等价式和蕴含式PredicateLogic/Equivalences&Implications目录CONTENTS01基本概念介绍等价式与蕴含式的数学定义，建立本章学习的基础逻辑框架。02命题演算推广探讨命题逻辑中的等价式如何扩展并应用于谓词逻辑的分析场景。03谓词演算特有公式重点讲解消去量词、量词否定、辖域收缩与扩张及量词分配律等核心公式。04综合例题解析通过具体例题，掌握运用等价式和蕴含式进行逻辑推理证明和符号化的技巧。定义2.12：等价式(Equivalence)▍定义内容给定任何两个谓词公式A和B,设它们有共同的个体域E,若对A和B的任一组变元进行赋值,所得命题的真值都相同,即是A↔B

永真式,则称谓词公式A和B在E上是等价的(也叫等值的),并记作A⇔B。▍核心解读涉及谓词和量词的语句是逻辑等价的，当且仅当无论用什么谓词代入这些语句，也无论为这些命题函数里的变量指定什么论域，它们都有相同的真值。“等价关系如同天平，无论两边承载何物，

只要它们的逻辑真值相同，天平即保持平衡。”蕴含式(Implication)▍逻辑定义蕴含式表示一个命题逻辑上必然推出另一个命题，在数理逻辑中用符号⇒表示。若逻辑公式A→B为永真式，则称A蕴含B，记作A⇒B。这代表着一种逻辑上的必然性推导。等价式Equivalence|⇔核心特点：逻辑关系“双向成立”，即两个命题的真值完全相同，互为充要条件。经典示例：¬∀xA(x)⇔∃x¬A(x)（全称量词的否定⇔存在量词的否定）蕴含式Implication|⇒核心特点：逻辑关系“单向推导”。若前提为真，结论必然为真；反之则不一定成立。它是推理规则的基础。经典示例：∀xA(x)⇒A(a)（全称指定规则：全称真⇒个体真）命题演算公式的推广第1章的第1.5.1节中，表1.18所列的基本等价公式E1到E24在谓词演算中仍然成立。当谓词演算中的公式代替命题演算中永真公式的变元时，所得的谓词公式即为有效公式。我们可以将此看作是“代入规则”在谓词逻辑中的自然推广。蕴含等值式推广：A(x,y)→B(x,y)⇔¬A(x,y)∨B(x,y)双重否定律推广：¬¬A(x)⇔A(x)全称量词下的蕴含转化：∀x(P(x)→Q(x))⇔∀x(¬P(x)∨Q(x))德·摩根定律推广至混合量词：

xF(x)→

yG(y)⇔

xF(x)∨

yG(y)谓词演算特有公式：消去量词等值式前提条件：个体域为有限集，记为D={a₁,a₂,...,aₙ}全称量词∀UniversalQuantifier(∀x)A(x)⇔A(a₁)∧A(a₂)∧...∧A(aₙ)解读：要求论域中“对每一个”x都必须满足A(x)性质，因此需要把所有个体逐一进行“且”判断，即逻辑合取(Conjunction)。存在量词∃ExistentialQuantifier(∃x)A(x)⇔A(a₁)∨A(a₂)∨...∨A(aₙ)解读：只要论域中“存在一个”x满足A(x)性质即可成立，因此只需要找到任意一个个体满足，即逻辑析取(Disjunction)。谓词演算特有公式：量词否定等值式核心思想：“否定所有⇔至少有一个非”｜“否定存在⇔所有非”设A(x)是含x自由出现的公式，则逻辑等价式成立：¬(∀x)A(x)⇔(∃x)¬A(x)，¬(∃x)A(x)⇔(∀x)¬A(x)全称量词否定(¬∀⇔∃¬)“不是所有的同学今天来上课了”⇔逻辑等价于⇔“今天有同学没来上课”存在量词否定(¬∃⇔∀¬)“不存在会飞的人”⇔逻辑等价于⇔“所有人都不会飞”谓词演算特有公式：量词辖域收缩与扩张等值式设A(x)是含x自由出现的公式，B中不含x的出现。∀关于全称量词的等值式∀x(A(x)∨B)

∀xA(x)∨B∀x(A(x)∧B)

∀xA(x)∧B∀x(A(x)→B)

∃xA(x)→B∀x(B→A(x))

B→∀xA(x)∃关于存在量词的等值式∃x(A(x)∨B)

∃xA(x)∨B∃x(A(x)∧B)

∃xA(x)∧B∃x(A(x)→B)

∀xA(x)→B∃x(B→A(x))

B→∃xA(x)例题2.14：证明∃x(A(x)→B)⇔∀xA(x)→B逻辑推导过程∀xA(x)→B⇔¬∀xA(x)∨B⇔∃x¬A(x)∨B⇔∃x(¬A(x)∨B)⇔∃x(A(x)→B)证明思路解析1利用蕴含等值式：将条件命题转换为析取式(P→Q⇔¬P∨Q)。2利用量词否定等值式：全称量词的否定转换为存在量词否定(¬∀x⇔∃x¬)。3利用量词辖域扩张：由于B中不含变元x，可将析取项并入量词辖域内。4还原蕴含形式：再次使用蕴含等值式，将¬A(x)∨B还原为A(x)→B。谓词演算特有公式：量词分配的等值式全称量词对合取(∧)的分配∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)💡直观解读：“所有人都既唱歌又跳舞”与“所有人都唱歌，并且所有人都跳舞”，这两句话描述的逻辑事实完全是等价的。存在量词对析取(∨)的分配∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)“人群中存在会唱歌或跳舞的人”⇔“有人会唱歌或有人会跳舞”谓词演算特有公式：量词分配的蕴含式全称量词对析取的蕴含∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x))💡逻辑解读：“所有学生都聪明”或“所有学生都努力”，必然能推导出“所有学生都是聪明的，或者是努力的”。⚠️注意：反之不成立。“全班学生都聪明或努力”不能推出“全班都聪明”或“全班都努力”。存在量词对合取的蕴含∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x)💡逻辑解读：如果“存在一个学生既聪明又努力”，那么必然能推导出“存在聪明的学生”且“存在努力的学生”。⚠️注意：反之不成立。“存在聪明的学生且存在努力的学生”，不代表有一个学生同时具备两种特质。多个量词的使用：等价关系两个全称量词(∀∀)可交换(∀x)(∀y)A(x,y)⇔(∀y)(∀x)A(x,y)💡逻辑解读：“对于论域中的所有x和所有y，性质A(x,y)都成立”与“对于论域中的所有y和所有x，性质A(x,y)都成立”在语义上完全一致。两个存在量词(∃∃)可交换(∃x)(∃y)A(x,y)⇔(∃y)(∃x)A(x,y)💡逻辑解读：“在论域中存在x和存在y满足性质A(x,y)”与“在论域中存在y和存在x满足性质A(x,y)”在语义上完全一致。多个量词的使用：蕴含关系蕴含关系公式链1.∀x∀yA(x,y)⇒∃y∀xA(x,y)2.∀y∀xA(x,y)⇒∃x∀yA(x,y)3.∃y∀xA(x,y)⇒∀x∃yA(x,y)4.∃x∀yA(x,y)⇒∀y∃xA(x,y)5.∀x∃yA(x,y)⇒∃y∃xA(x,y)6.∀y∃xA(x,y)⇒∃x∃yA(x,y)💡核心记忆点强关系⇒弱关系全称量词越多，限制越强，陈述越有力。强度排序：∀∀(最强)>∃∀>∀∃>∃∃(最弱)顺序决定含义混合量词中，∃∀和∀∃表达的含义截然不同。特别注意：∃∀是强于∀∃的，不可随意交换。常用谓词等价式与蕴含式汇总表(表2.2)量词否定等值式E25:¬(∀x)A(x)⇔(∃x)¬A(x)“并非对所有x,A(x)为真”⇔“存在x,使A(x)为假”E26:¬(∃x)A(x)⇔(∀x)¬A(x)“不存在x,使A(x)为真”⇔“对所有x,A(x)为假”量词分配等值式E27:∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)全称量词∀对合取∧可分配E28:∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)存在量词∃对析取∨可分配量词分配的蕴含式I22:∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x))全称量词∀对析取∨只有蕴含关系I23:∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x)存在量词∃对合取∧只有蕴含关系例题2.15：证明∃x(A(x)→B(x))

∀xA(x)→∃xB(x)证明

∃x(A(x)→B(x))

∃x(

A(x)∨B(x))

∃x(

A(x))∨∃xB(x)

∀xA(x)∨∃xB(x)

∀xA(x)→∃xB(x)第一步：利用蕴含等值式将公式中的蕴含联结词转化为“非”与“或”的组合，便于后续使用量词分配律。第二步：利用存在量词分配律存在量词对析取具有分配律，将量词分别作用于两个子公式，完成逻辑拆分。第三步：利用量词否定等值式即德摩根定律在量词上的推广，将“存在非A”转换为“并非对所有都A”。第四步：还原蕴含联结词再次应用蕴含等值式，将公式还原回蕴含形式，从而完成两边公式的等价证明。例题2.16：证明∀xA(x)∨∀xB(x)

(∀x)(∀y)(A(x)∨B(y))证明

∀xA(x)∨∀xB(x)

∀xA(x)∨∀yB(y)(先改名)

(∀x)(∀y)(A(x)∨B(y))(再扩张量词辖域)Step1.变元换名（关键步骤）由于原式左右两边的全称量词指导变元均为x，直接合并会导致变元冲突。因此，第一步需要对第二个全称量词进行换名，将其中的约束变元x替换为y，消除同名歧义，为后续合并做准备。Step2.量词辖域扩张换名后，A(x)和B(y)的约束变元已相互独立。此时可以应用“量词辖域扩张等值式”，将两个独立的全称量词(∀x)和(∀y)依次向外扩张，最终将它们合并到整个析取式的最外层，形成双重量词形式。例题2.17：将下面命题用两种形式符号化(1)没有不犯错误的人令F(x)：x是人,G(x)：x犯错误。¬∃x(F(x)∧¬G(x))⇔∀x¬(F(x)∧¬G(x))⇔∀x(F(x)→G(x))(2)不是所有的人都爱看电影令F(x)：x是人,G(x)：爱看电影。¬∀x(F(x)→G(x))⇔∃x¬(F(x)→G(x))⇔∃x(F(x)∧¬G(x))例题2.18：证明不等值关系（一）证明逻辑式∀x(A(x)∨B(x))与∀xA(x)∨∀xB(x)不等值构造具体解释(Counterexample)1.设定解释I：个体域D={自然数集N}；

令A(x)表示“x是奇数”，B(x)表示“x是偶数”。2.分别求真值：

•∀x(A(x)∨B(x))：所有自然数非奇即偶→真(T)

•∀xA(x)∨∀xB(x)：全是奇数或全是偶数→假(F)逻辑推导与结论根据一阶逻辑等值的定义，两个公式等值当且仅当在所有解释下真值都相同。此处我们找到了一个特定的解释I，使得两个公式的真值不相同（一真一假）。因此，这两个公式不满足“所有解释下都同真同假”的条件。➔结论：两式不等值。例题2.18：证明不等值关系（二）证明

∃x(A(x)∧B(x))与∃xA(x)∧∃xB(x)不等值公式一：