离散数学 课件 1.6 蕴含公式

CHAPTER01命题逻辑1.6蕴含公式深入理解命题逻辑中的蕴含关系本节内容概览01定义与核心概念•蕴含公式的定义与详细解读

•关键逻辑符号辨析：

区分`⇒`与`→`的含义与用法02证明方法与实例•证明蕴含关系的两种核心思路

•通过经典逻辑题进行实例解析

•掌握推导过程中的常见技巧03常用基本蕴含关系•构建常用蕴含定律速查表

•逻辑推理过程的形式化表达

•学会灵活运用定律进行转换04蕴含的性质与总结•总结蕴含关系的传递性与反身性

•梳理易错点与常见误区

•归纳本章核心知识点，建立知识体系定义1.23：蕴含公式的严格定义定义内容对于任意两个公式G和H，当且仅当G→H是一个重言式的时候，称“G蕴含H”，记作G⇒H。逻辑本质`G⇒H`表示的是一种逻辑推导关系，而非一个命题公式。它断言：“只要前提G为真，那么结论H必然为真”。判定准则`G⇒H`成立的充分必要条件是：在任何解释下，条件命题`G→H`的真值永远为真（T），即`G→H`是一个重言式。辨析：蕴含符号⇒与条件联结词→蕴含符号⇒●名称：蕴含关系符号●性质：表示两个命题公式之间关系的元语言符号。●含义：断言一个逻辑真理：A的真值永远“强于”或“等于”B的真值。条件联结词→●名称：条件联结词(Implication)●性质：用于构造命题公式的标准逻辑联结词。●含义：本身具有真值，其真值完全依赖于P和Q的具体取值。核心区别`P→Q`是一个公式，它本身可以为真或为假；而`P⇒Q`是一个断言，它要么成立，要么不成立。当且仅当公式`P→Q`是逻辑永真式时，断言`P⇒Q`才成立。证明A⇒B的两种核心思路01/正向推导(肯定前件ModusPonens)📝方法描述直接假定前提A的真值为真(True)，严格依据逻辑公理与推理规则进行演绎，最终推导出结论B的真值也必然为真(True)。🔑逻辑原理基于蕴含式A→B的真值表定义：A→B为假，当且仅当A=T且B=F。若能证明在A=T的情况下，B不可能为F，则该蕴含式即为重言式。02/反向推导(否定后件ModusTollens)📝方法描述利用逻辑等价式A→B⇔¬B→¬A（逆否命题等价）。先假设结论B为假(False)，再推导出前提A也必须为假(False)。🔑逻辑原理这是“反证法”的一种应用形式。若“结论不成立”的假设导致“前提不成立”，则说明原蕴含关系在逻辑上必然成立。例题1.51：推证¬Q∧(P→Q)⇒¬P方法一：正向推导法1假设前提为真：假定命题公式¬Q∧(P→Q)的真值为T(True)。2分解合取式：根据合取运算的定义，必须同时满足¬Q为T且(P→Q)为T。3推导Q的值：因为¬Q为T，根据否定运算的定义，Q的真值必为F(False)。4推导P的值：根据蕴含词“→”的真值表，当后件Q为F且(P→Q)为T时，前件P必须为F。5得出结论：P为F，故¬P为T，结论得证。推导结论上述推导严格遵循了逻辑运算的真值表规则。成功证明了：只要前提合取式为真，结论必然为真。¬Q∧(P→Q)⇒¬P例题1.51：推证¬Q∧(P→Q)⇒¬P方法二：反向推导法（反证法）1.假设与推导●假设结论为假：假定结论¬P的真值为F。●推导前提：若¬P为F，则P的真值必为T。接下来分析在此条件下，前提是否成立。2.前提逻辑分析(P=T)✦情况1(Q=F):P=T且Q=F→(P→Q)=F→合取式¬Q∧(P→Q)=F。✦情况2(Q=T):Q=T→¬Q=F→合取式¬Q∧(P→Q)=F。无论Q取何值，前提结果均为假。结论：如果结论¬P为假，那么前提¬Q∧(P→Q)必然为假。∴根据“逆否命题等价”的逻辑原理，原蕴含关系¬Q∧(P→Q)⇒¬P成立。例题1.52：判断推理P→Q,P⇒Q是否有效方法一：真值表技术为了验证推理的有效性，将前提与结论构成蕴含式：((P→Q)∧P)→Q。若该公式对所有真值指派结果均为真，则它是重言式，推理有效。PQP→Q(P→Q)∧P整体结果TTTTTTFFFTFTTFTFFTFT结论与逻辑意义1.逻辑判定：从左侧真值表可见，最后一列的结果在所有四种情况下均为T(真)。这证明了公式((P→Q)∧P)→Q是一个逻辑重言式。2.推理有效性：根据重言式的性质，推理形式(P→Q)∧P⇒Q在逻辑上是绝对有效的。这就是经典逻辑中著名的假言推理(ModusPonens)，

也被称为“分离规则”，是构建逻辑证明的基石。例题1.52：公式转换法证明方法二：公式转换法（等值演算）((P→Q)∧P)→Q⇔((¬P∨Q)∧P)→Q(蕴含表达式E₁₄:A→B⇔¬A∨B)⇔¬((¬P∨Q)∧P)∨Q(蕴含表达式E₁₄)⇔¬(¬P∨Q)∨¬P∨Q(德摩根定律E₁₀:¬(A∧B)⇔¬A∨¬B)⇔¬(¬P∨Q)∨(¬P∨Q)(结合律与交换律整理)⇔T

(互补律E₆:¬A∨A⇔T)💡证明结论通过上述的等值演算，将原命题公式一步步化简，最终推导出逻辑真（T）。结论：该命题公式是一个重言式(Tautology)，故蕴含关系成立。例题1.52：主析取范式法证明方法三：主析取范式法将逻辑公式转换为主析取范式。若范式包含所有极小项，则公式为重言式，原蕴含关系得证。((P→Q)∧P)→Q⇔¬((¬P∨Q)∧P)∨Q//蕴含等值式与德摩根律⇔(P∧¬Q)∨¬P∨Q//分配律展开⇔(P∧¬Q)∨(¬P∧(¬Q∨Q))∨((¬P∨P)∧Q)//补元律补全变元⇔(¬P∧¬Q)∨(¬P∧Q)∨(P∧¬Q)∨(P∧Q)//整理合并⇔m₀∨m₁∨m₂∨m₃结论上述主析取范式包含了两个命题变元下所有可能的极小项（共4个）。这说明，无论对P和Q赋予何种真值（0或1），该逻辑公式的取值都为真。因此，该公式为重言式，蕴含关系成立。常用基本蕴含关系（表1.22）序号逻辑表达式命题蕴含定律/规则名称I1P∧Q⇒P简化规则(Simplification)I2P∧Q⇒Q简化规则(Simplification)I3P⇒P∨Q添加规则(Addition)I4Q⇒P∨Q添加规则(Addition)I5P∨Q,¬P⇒Q选言三段论(DisjunctiveSyllogism)I6P∨Q,¬Q⇒P选言三段论(DisjunctiveSyllogism)I7P,Q⇒P∧Q合取引入规则(Conjunction)I8P→Q,P⇒Q假言推理/分离规则(ModusPonens)I9P→Q,¬Q⇒¬P否定后件式(ModusTollens)I10P→Q,Q→R⇒P→R假言三段论(HypotheticalSyllogism)逻辑推理的基石掌握上述蕴含关系对于构建严谨的数学证明和逻辑推导至关重要。它们不仅是命题逻辑系统中的基本定理，也是日常推理、计算机科学（如人工智能、编译原理）以及哲学论证中的常用工具。熟练运用这些规则，能够显著提升分析和解决问题的逻辑性。常用基本蕴含关系（续）I11P∨Q,P→R,Q→R⇒R二难推论I12P∨Q,P→R,Q→S⇒R∨S二难推论I13¬(R∨¬S),P→R,Q→S⇒¬P∨¬Q破坏二难推论I14P↔Q,Q↔R⇒P↔R双条件三段论I15¬P⇒P→Q假前件蕴含任何结论I16Q⇒P→Q真后件被任何前件蕴含I17¬(P→Q)⇒P蕴含为假的必要条件I18¬(P→Q)⇒¬Q蕴含为假的必要条件I19:P→Q,R→S⇒(P∧R)→(Q∧S)I20:Q→R⇒(P∨Q)→(P∨R)I21:Q→R⇒(P→Q)→(P→R)例题1.53：将自然语言推理形式化“如果a是偶数，则a能被2整除；a是偶数。所以，a能被2整除。”形式化：P→Q,P⇒Q所用定律：I8-假言推理规则(ModusPonens)“如果一个人是单身汉，则他不幸福；如果一个人不幸福，则他死得早。所以，单身汉死得早。”形式化：P→Q,Q→R⇒P→R所用定律：I10-假言三段论(HypotheticalSyllogism)“若你发电子邮件告诉我密码，则我将完成程序的编写；我没有完成程序的编写。所以，你没有发邮件告诉我密码。”形式化：P→Q,¬Q⇒¬P所用定律：I9-否定后件式(ModusTollens)“这个案件的凶手肯定是王某或陈某；经过调查，王某不是凶手。所以，陈某是凶手。”形式化：P∨Q,¬P⇒Q所用定律：I5-选言三段论(DisjunctiveSyllogism)蕴含的性质（1）01重言式的传递性若A⇒B，且A是重言式，则B必是重言式。02蕴含关系的传递性若A⇒B且B⇒C，则A⇒C。这体现了逻辑推理中最基础的链条关系。03结论的合取若A⇒B且A⇒C，那么A⇒(B∧C)。即同一个前提能推出的多个结论可以同时成立。蕴含的性质（2）性质04·前提的析取若A⇒B且C⇒B，那么A∨C⇒B。逻辑含义：多个独立前提均可推导出同一结论时，前提的“或”关系（析取）依然能推出该结论。性质05·CP规则基础若A∧B⇒C，则A⇒(B→C)。逻辑含义：条件证明（CP）规则的核心依据，用于将结论中的蕴含式转化为前提中的合取式，简化推导过程。性质06·反证法基础若A⇒B，则A∧¬B是矛盾式。逻辑含义：假设原命题为真且结论为假，必然导出逻辑矛盾。这构成了归谬法（反证法）的理论基石。性质07·逆向思维基础若A⇒B，则¬B⇒¬A。逻辑含义：原命题与逆否命题是逻辑等价的。这一性质为解决问题提供了“从反面切入”的逆向思维路径。本章总结01/核心概念•蕴含公式：逻辑式G⇒H成立，当且仅当命题公式G→H是重言式。•符号辨析：“⇒”描述的是逻辑关系，“→”是命题公式中的联结词。02/证明方法