离散数学 课件 1.8 推理理论

1.8推理理论InferenceTheoryMATHEMATICALLOGIC/CHAPTER01目录CONTENTS01引言与基本概念什么是推理？有效结论的定义。02论证方法：真值表法通过穷举所有真值组合来验证推理。03论证方法：直接证明法利用推理规则和已知公式直接推导。04论证方法：间接证明法归谬法（反证法）与附加前提证明法（CP规则）。05综合应用与总结自然语言推理示例与本章小结。什么是推理？▌定义(Definition)推理是从一组前提(Premises)合乎逻辑地推出结论(Conclusion)的思维过程，是连接已知与未知的桥梁。▌核心逻辑(CoreLogic)结论的正确性由两大支柱共同保证：一是前提的真实性，二是推理过程的逻辑严密性。缺一不可。▌学习意义(Importance)掌握科学的推理方法，是构建严密逻辑思维、高效解决复杂问题、以及在辩论和论证中明辨是非的关键能力。推理无处不在·生活中的逻辑形式日常推理"如果母鸡是飞鸟，那鸭子会跑；鸭子不会跑，所以羊不吃草。"符号推理¬P→(¬R→S)

¬P→Q,¬Q

⇒R∨S经典三段论所有人都会死

苏格拉底是人

所以，苏格拉底会死定义1.31：有效结论(ValidConclusion)核心定义与记法设A和C是两个命题公式，当且仅当A→C为一重言式（永真式）时，称C是A的有效结论。记法：A⇒C逻辑含义解读•C可由A逻辑地推出(LogicallyfollowsfromA)•A蕴含C(AimpliesC)•A是推理的前提(Premise)，C是推理的结论(Conclusion)扩展：多前提集合下的有效结论若前提集合为{H₁,H₂,...,Hₙ}，当且仅当H₁∧H₂∧...∧Hₙ⇒C成立时，C是这组前提的有效结论。逻辑等价于公式：(H₁∧H₂∧...∧Hₙ)→C是重言式论证方法概览真值表法(TruthTables)▍核心方法通过穷举命题变元所有可能的真值组合，逐一验证公式在各种情况下的逻辑值。▍主要特点•优点：原理直观，结论绝对可靠，是逻辑验证的基石。•缺点：计算量随变元数量指数级增长，变元多时效率极低。直接证明法(DirectProof)▍核心方法利用公认的推理规则（如前提引入规则P、结论引入规则T），结合已知的逻辑等值式(E)或蕴含式(I)，从前提条件出发，一步步推导直至得出结论。▍主要特点•逻辑严密：推导链条清晰可见。•适用性广：数学和逻辑证明中最基础、最常用的方法。间接证明法(IndirectProof)▍核心方法不直接证明原结论，而是通过证明与结论相关的其他命题来间接达到目的。通常在直接证明困难时使用。▍常见形式•归谬法(反证法)：假设结论不成立，推导出矛盾。•附加前提证明法(CP规则)：适用于结论为蕴含式的证明。方法一：真值表法核心思想：穷举与计算1.穷举：列出命题公式中所有变元的全部可能的真值组合(共2ⁿ种)。2.计算：依次算出前提(H₁...Hₙ)与结论(C)在每种组合下的真值。3.验证：根据真值分布判断推理是否有效（见右侧方法）。方法A：正向验证在真值表中，定位所有前提全为真(T)的行。若这些行中，对应的结论C恒为真(T)，则推理逻辑成立。这是最直接的判断逻辑。方法B：反向验证(假言易位)定位所有结论C为假(F)的行。若这些行中，前提中至少有一个为假(F)，则推理成立。原理：P→Q≡¬Q→¬P(若结论不成立，则前提也必然不成立)📊适用场景与局限性适用：命题变元数量较少（通常≤3个）的简单推理，过程直观可靠。局限：变元增加时，真值表行数(2ⁿ)呈指数级增长，导致计算繁琐、效率低下。例题1.66：登录失败原因分析问题描述登录系统失败的原因是密码错误或者验证码错误，这次登录失败不是密码错误造成的，所以原因是验证码错误。Step1.逻辑符号化●P：登录失败是因为密码错误●Q：登录失败是因为验证码错误Step2.提取前提与结论前提：(P∨Q),¬P结论：Q待证明逻辑等价式：(P∨Q)∧¬P⇒Q例题1.66：真值表分析PQP∨Q¬PTTTFTFTFFTTTFFFT关键分析1.逐行检查表格中两个前提P∨Q和¬P的真值情况。2.观察发现，仅第三行中两个前提的真值同时为T(真)。3.在这一行中，结论Q的真值也为T(真)。推理有效(Valid)结论：推理形式(P∨Q)∧¬P⇒Q成立，即“否定肯定式”是有效的逻辑推理规则。方法二：直接证明法核心思想由一组已知的前提条件出发，严格遵循逻辑系统中公认的推理规则，利用已经被证明的等值式(E)或蕴含式(I)，通过一系列连续的、合乎逻辑的推导步骤，最终得出有效结论的过程。推理规则•P规则(前提引入)

在推理过程中的任意步骤，都可以随时引入给定的前提条件作为论证的依据。•T规则(结论引入)

在推导过程中，由前面的公式推导出的中间结论，可以作为后续步骤的前提继续使用。证明格式采用“行式”列表结构，清晰展示每一步的推导过程，确保逻辑严密：

(行号)公式依据例1:T(1)(2)I

→由步骤(1)(2)根据蕴含式得出

例2:T(1)E

→由步骤(1)根据等值式变换得出例题1.67：直接证明法演示待证问题：设前提集合G={P∨Q,Q→R,P→S,¬S}，结论H=R∧(P∨Q)。试通过直接证明法，严谨推导以证明逻辑蕴含关系G⇒H。步骤断言(Assertion)依据(Reason)(1)P→SP(前提引入规则)(2)¬SP(前提引入规则)(3)¬PT(1)(2)I(拒取式/ModusTollens)(4)P∨QP(前提引入规则)(5)QT(3)(4)I(析取三段论/DisjunctiveSyllogism)(6)Q→RP(前提引入规则)(7)RT(5)(6)I(假言推理/ModusPonens)(8)R∧(P∨Q)T(4)(7)I(合取引入/ConjunctionIntroduction)例题1.69：直接证明法再演示待证命题：(¬P→(¬R→S))∧(P→Q)∧¬Q⇒R∨S步骤公式(Formula)理由(Reason)(1)¬QP(前提引入,Premise)(2)P→QP(前提引入,Premise)(3)¬PT(1)(2)I(拒取式,ModusTollens)(4)¬P→(¬R→S)P(前提引入,Premise)(5)¬R→ST(3)(4)I(假言推理,ModusPonens)(6)R∨ST(5)E(蕴含表达式转换,ImplicationEquivalence)方法三：间接证明法核心思想：不直接证明结论，而是通过证明与结论相关的其他命题来间接达到目的。这种策略在直接推导受阻时往往能发挥关键作用。归谬法(反证法)▌基本原理假设结论不成立(¬C)，然后以此为前提，结合已知条件进行逻辑推导，最终推导出矛盾(A∧¬A)，从而证明原结论成立。▌适用场景当结论本身为否定形式，或者直接证明条件与结论之间的逻辑关系比较困难时。附加前提证明法(CP规则)▌基本原理当待证结论是蕴含式(A→B)时，将前件A作为一个“附加的”已知前提引入证明过程，然后证明在新的前提下，后件B必然成立。▌适用场景结论是蕴含式，或者可以方便地转化为蕴含式形式（如逻辑析取式A∨B等价于¬A→B）的证明题。间接证明法(1)-归谬法(ReductioadAbsurdum)基本原理要证明逻辑蕴含关系H₁∧H₂∧...∧Hₘ⇒C，等价于证明将结论的否定加入前提后形成的合取式H₁∧H₂∧...∧Hₘ∧¬C是一个矛盾式（永假式）。证明步骤1.假设：将原结论的否定式¬C作为附加前提引入推理系统。2.推理：结合原有的全部前提H₁...Hₘ和¬C进行严格逻辑推理。3.导出矛盾：在推理过程中，必须推导出形如A∧¬A的逻辑矛盾。4.结论：由于假设导致了矛盾，故假设不成立，原结论C得证。逻辑矛盾符号(⊥)符号“⊥”常用来表示任意的逻辑矛盾或永假式，是归谬法成功的标志。例题1.71：归谬法演示【问题】证明逻辑式W∨S可由前提集合{S∨U,U→(Q∧R),Q→W}有效推出。(1)¬(W∨S)

P(否定结论作为附加前提引入)(2)¬W∧¬ST(1)E(德摩根定律)(3)¬W

T(2)I(简化式)(4)¬ST(2)I(简化式)(5)S∨UP(前提引入)(6)UT(4)(5)I(析取三段论)结论：推导步骤(12)出现矛盾W∧¬W，故原推理有效。即：W∨S可由给定前提集合有效推出。(7)U→(Q∧R)

P(前提引入)(8)Q∧R

T(6)(7)I(假言推理)(9)Q

T(8)I(简化式)(10)Q→W

P(前提引入)(11)W

T(9)(10)I(假言推理)(12)W∧¬W

T(3)(11)I(合取引入)间接证明法(2)-CP规则核心原理要证明复合命题公式：H₁∧...∧Hₘ⇒A→B等价于证明：H₁∧...∧Hₘ∧A⇒B适用场景当推理的结论本身是一个蕴含式(A→B)时。或，结论是一个析取式(A∨B)时，可以先利用蕴含等值式将其转化为¬A→B，再使用CP规则。操作步骤1.引入附加前提：把结论A→B的前件A作为附加前提引入证明序列。2.证明后件：结合原前提和附加前提A，利用推理规则推导出结论的后件B。3.应用CP规则：得出最终结论A→B。例题1.72：CP规则演示问题描述：设前提集合G={P→(Q→S),¬R∨P,Q}，结论H=R→S。请根据推理规则证明逻辑蕴含关系G⇒H。(1)R

P(附加前提引入)(2)¬R∨P

P(前提引入)(3)P

T(1)(2)I(选言三段论)(4)P→(Q→S)

P(前提引入)(5)Q→S

T(3)(4)I(假言推理)(6)Q

P(前提引入)(7)S

T(5)(6)I(假言推理)(8)R→S

CP(1)(7)(结论引入)综合举例(1)-自然语言推理例题1.73：实数分类推理问题描述若数a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数。结论：所以，a是无理数。符号化设定•P:a是实数•Q:a是有理数•R:a是无理数•S:a能表示成分数待证命题前提条件：P→(Q∨R)¬S→¬QP∧¬S结论：⇒R综合举例(1)-证明过程步骤公式推理依据(Reason)1P∧¬SP(前提引入,Premise)2PT(1)I(简化式,Simplification)3¬ST(1)I(简化式,Simplification)4P→(Q∨R)P(前提引入,Premise)5Q∨RT(2)(4)I(假言推理,ModusPonens)6¬S→¬QP(前提引入,Premise)7¬QT(3)(6)I(假言推理,ModusPonens)8RT(5)(7)I(析取三段论,DisjunctiveSyllogism)综合举例(2)-苏格拉底三段论的思考经