离散数学 课件 1.5 等价公式

第一章·命题逻辑1.5等价公式逻辑世界的化简魔法本节内容概览01.等价公式的定义与基本性质•等价公式的定义与相关定理

•常用的基本等价关系（命题定律）02.等值演算的核心规则•代入规则：重言式中命题变元的统一替换

•置换规则：公式子公式的等价替换03.等价公式的应用场景•判断公式的类型（重言式/矛盾式/可满足式）

•证明两个公式的等价性与逻辑化简问题04.联结词的全功能集•冗余联结词与独立联结词的概念

•全功能集的定义与极小联结词组定义1.19：等价公式定义内容给定两个命题公式A和B，设P₁，P₂，…，Pₙ是所有出现于A和B中的原子变元，若给P₁，P₂，…，Pₙ任一组真值指派，A和B的真值都对应相同，则称A和B是等价的或逻辑相等(Equivalence)，记作A⇔B。定理1.1：充要条件对于任意两个公式G和H，G⇔H的充分必要条件是公式G↔H是永真公式(Tautology)。💡提示：判断两个公式是否等价，可转化为证明其双条件命题是重言式。关键区分⇔等价符号属于关系符号，用于描述两个公式之间的逻辑等价关系，不能用于构造公式。↔双条件联结词属于逻辑联结词，是一个运算符，用于连接两个原子公式以构造新的复合命题公式。常用基本等价关系（命题定律）E1.¬¬P⇔P——对合律E2.P∨P⇔P——幂等律E3.P∧P⇔P——幂等律E4.(P∨Q)∨R⇔P∨(Q∨R)——结合律E5.(P∧Q)∧R⇔P∧(Q∧R)——结合律E6.P∨Q⇔Q∨P——交换律E7.P∧Q⇔Q∧P——交换律E8.P∨(Q∧R)⇔(P∨Q)∧(P∨R)——分配律E9.P∧(Q∨R)⇔(P∧Q)∨(P∧R)——分配律E10.P∨(P∧Q)⇔P——吸收律E11.P∧(P∨Q)⇔P——吸收律E12.¬(P∨Q)⇔¬P∧¬Q(德摩根律)E13.¬(P∧Q)⇔¬P∨¬Q(德摩根律)常用基本等价关系（续）E14P∨F⇔P同一律E15P∧T⇔P同一律E16P∨T⇔T零律E17P∧F⇔F零律E18P∨¬P⇔T否定律(排中律)E19P∧¬P⇔F否定律(矛盾律)E20P→Q⇔¬P∨Q条件等价式E21P→Q⇔¬Q→¬P假言易位E22P↔Q⇔(P→Q)∧(Q→P)双条件等价式E23P↔Q⇔¬P↔¬Q等价否定式E24(P→Q)∧(P→¬Q)⇔¬P归谬论等值演算的核心规则定理1.2：代入规则(SubstitutionRule)在一个永真式A中，任何一个原子命题变元R出现的每一处用另一个公式代入，所得的公式B仍为永真式。💡示例：`R∨¬R`是经典的永真式。若将变元R全部用公式`P→Q`代入，得到新公式`(P→Q)∨¬(P→Q)`，该公式依然是永真式。定理1.3：置换定理(ReplacementTheorem)设X是命题公式A的一个子公式，且已知X⇔Y。如果将A中X的一处或多处出现替换为Y，所得到的新公式B与原公式A逻辑等价，即A⇔B。🔍示例：已知蕴含等值式`P→Q⇔¬P∨Q`。若将公式中的P置换为合取式`R∧S`，可直接推出：`(R∧S)→Q⇔¬(R∧S)∨Q`。代入规则vs置换规则01.代入规则(Substitution)对象：原子命题变元(AtomicPropositionalVariables)范围：必须处处代入，不可遗漏任何一处相同的变元目的：保持公式的逻辑永真性(Tautology)02.置换规则(Replacement)对象：子公式(Subformulas)，即复合命题中的任何部分范围：具有灵活性，可进行部分或全部替换目的：保持公式间的逻辑等价性(LogicalEquivalence)例题1.36：证明(P∧Q)∨(P∧¬Q)⇔P(P∧Q)∨

(P∧¬Q)逻辑原式P∧(Q∨¬Q)分配律(Dist./E9)P∧T否定律(Neg./E18)P同一律(Id./E15)结论：通过上述三步等值演算，我们成功地将一个包含两个变元和多个连接词的复杂合式公式，化简为了单一的命题变元P，直观且严谨地验证了二者的逻辑等价关系。这展示了逻辑代数在简化逻辑电路与推理中的核心价值。例题1.37：证明P→(Q→R)⇔Q→(P→R)证明过程P→(Q→R)⇔¬P∨(¬Q∨R)(蕴含式等价转换，参考E20)⇔¬Q∨(¬P∨R)(利用逻辑或的结合律E4与交换律E6调整顺序)⇔Q→(P→R)(还原为蕴含式，参考E20)结论通过上述等值演算，我们成功证明了两个逻辑公式是完全等价的。这揭示了一个重要的逻辑性质：在多重蕴含式的逻辑结构中，前提命题的出现顺序是可以交换的，而不会改变整个复合命题的逻辑含义。应用一：判断公式类型方法：等值演算法利用命题逻辑中的一系列等价公式，对目标公式进行逻辑化简，根据最终的最简形式判断其类型。化简结果=T(真)→重言式(永真式)无论命题变元取何值，公式真值恒为真化简结果=F(假)→矛盾式(永假式)无论命题变元取何值，公式真值恒为假例题1.40：证明(P→Q)∧P→Q是重言式(P→Q)∧P→Q⇔(¬P∨Q)∧P→Q(蕴含表达式E₂₀)⇔¬((¬P∨Q)∧P)∨Q(蕴含表达式E₂₀)⇔(¬(¬P∨Q)∨¬P)∨Q(德摩根律E₁₃)⇔((P∧¬Q)∨¬P)∨Q(德摩根律E₁₂)⇔((P∨¬P)∧(¬Q∨¬P))∨Q(分配律E₉)⇔(T∧(¬Q∨¬P))∨Q(排中律E₁₈)⇔(¬Q∨¬P)∨Q(同一律E₁₅)⇔(¬Q∨Q)∨¬P(结合律、交换律)⇔T∨¬P(排中律E₁₈)⇔T(零律E₁₆)，故该式为重言式。应用二：证明公式等价方法：等值演算法利用已知的基本等价公式（如蕴含表达式、结合律、德摩根律等），通过一系列的等值演算步骤，将一个逻辑公式变换为另一个逻辑公式，从而证明二者逻辑等价。该方法比真值表法更高效。例题1.41：证明公式等价——P→(Q→R)⇔(P∧Q)→RP→(Q→R)(原始公式)⇔¬P∨(¬Q∨R)(蕴含式E20，再次应用)⇔¬(P∧Q)∨R(德摩根律E13，反向应用)⇔¬P∨(Q→R)(蕴含式E20：A→B⇔¬A∨B)⇔(¬P∨¬Q)∨R(结合律E4：(A∨B)∨C⇔A∨(B∨C))⇔(P∧Q)→R(蕴含式E20，最终形式)应用三：化简自然语言语句01问题描述请化简如下自然语言语句，使其表达更清晰、简洁：“情况并非如此，如果他不来，那么我也不去。”02逻辑符号化首先定义原子命题：•P：他来。

•Q：我去。将语句转化为命题公式：¬(¬P→¬Q)03等值演算化简¬(¬P→¬Q)

⇔¬(¬¬P∨¬Q)(蕴含式E20)

⇔¬(P∨¬Q)(对合律E1)

⇔¬P∧Q(德摩根律E12)注：利用蕴含式、对合律、德摩根律逐步消去多余连接词与否定词。04最终结论将最终公式转换回自然语言：“我去了，但他没来。”应用四：化简程序逻辑原程序逻辑IfAthen

ifBthenXelseY

else

ifBthenXelseY执行X的条件推导(A∧B)∨(¬A∧B)⇔(A∨¬A)∧B(分配律E9)⇔T∧B(排中律E18)⇔B(同一律E15)结论：执行X仅取决于条件B最终化简结果IfBthenXelseY代码可读性与效率显著提升应用五：化简开关电路01/原电路逻辑表达式((P∧Q∧R)∨(P∧Q∧S))

∧((P∧R)∨(P∧S))02/等值演算化简过程⇔(P∧Q∧(R∨S))∧(P∧(R∨S))

(分配律DistributiveLaw)⇔P∧Q∧(R∨S)∧P∧(R∨S)

(结合律AssociativeLaw)⇔P∧Q∧(R∨S)

(幂等律IdempotentLaw)03/化简后逻辑表达式P∧Q∧(R∨S)核心价值：通过逻辑代数化简，可显著减少电路中逻辑门的数量和连线复杂度，在实现相同逻辑功能的前提下，有效降低硬件成本并提高系统运行的可靠性。应用六：化简逻辑电路🔧电路状态：复杂冗余包含多个逻辑门与分支，信号路径长，存在大量可合并的逻辑单元，增加了电路的物理面积与功耗。✨电路状态：极简高效逻辑结构被压缩，去除了所有冗余逻辑，仅保留实现功能的最小逻辑单元，显著提升运行效率。📝布尔代数化简推演原逻辑表达式：F=((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)①运用吸收律(E11):(P∧Q∧R)∨(P∨Q∨S)⇔(P∨Q∨S)②再次运用吸收律(E11):(P∨Q∨S)∧(P∧S∧T)⇔P∧S∧T结论：电路被极大简化，仅需三个逻辑门(与门)即可实现原有功能。应用七：解决智力问题例题1.47：侦探推理问题四位证人（男管家P,厨师Q,园丁R,杂役S）的证词存在逻辑冲突，侦探需要利用逻辑规则，找出所有可能的真相组合。已知证词逻辑关系：1.若管家(P)诚实，则厨师(Q)也诚实→P→Q2.厨师(Q)与园丁(R)不可能同时诚实→¬(Q∧R)3.园丁(R)与杂役(S)不可能同时说谎→¬(¬R∧¬S)4.若杂役(S)诚实，则厨师(Q)在说谎→S→¬Q求解：构建真值表，筛选有效解PQRSP→Q¬(Q∧R)¬(¬R∧¬S)S→¬QFFFTTTTTFFTFTTTTFFTTTTTT结论：真相只有一个（部分）在所有满足条件的逻辑解中：1.男管家(P)和厨师(Q)必然在说谎。2.园丁(R)与杂役(S)至少一人说真话，但无法确定具体是谁。联结词的全功能集定义1.21冗余联结词与独立联结词在一个联结词集合D中，如果一个联结词可以由集合中的其他联结词定义和表示，则称此联结词为冗余联结词；否则，若无法由其他联结词定义，则称为独立联结词。定义1.22全功能集与极小联结词组•全功能集：任意真值函数都能用该集合中的联结词公式表示。•极小联结词组：在满足“全功能集”的前提下，集合内不含任何冗余联结词。核心逻辑推导若联结词集合S是全功能集，且从中删去任意一个联结词后就不再是全功能集，则S必为极小联结词组。经典极小联结词组举例数理逻辑中最常见的极小联结词组：{¬,∧}与{¬,∨}。所有的逻辑运算都可由“非”与“且”或“非”与“或”实现。常见的全功能集与极小联结词组全功能集(FunctionalCompleteness)S₁={¬,∧,∨,→,↔}——逻辑演算中最常用的集合S₂={¬,∧,∨}——布尔代数的基础集合，足以表达所有命题公式S₇={¬,→}——仅包含否定和蕴含联结词极小联结词组(MinimalSets)•经典组合：S₃={¬,∧}，S₄={¬,∨}•单元素完备集：S₅={↑}(与非/NAND)，S₆={↓}(或非/NOR)注：极小联结词组是指本身是全功能集，但去掉其中任何一个联结词后，就不再是全功能集。逻辑联结词真值表参考通过真值表可以验证不同联结词组的表达能力与等价性。例题1.50：公式转换目标：将公式P∧¬Q转化为只含指定联结词集合的等值公式。(1)联结词集合{¬,∨}P∧¬Q⇔¬(¬P∨Q)(根据德摩根律)(2)联结词集合{¬,→}P∧¬Q⇔¬(¬P∨Q)⇔¬(P→Q)(根据蕴含等值式)(3)联结词集合{↑}(与非联结词)P∧¬Q⇔P∧(Q↑Q)⇔¬(P↑(Q↑Q))⇔(P↑(Q↑Q))↑(P↑(Q↑Q))(4)联结词集合{↓}(或非联结词)