离散数学(第6讲习题课1).pptxVIP

冯伟森Email：27四月2025离散数学计算机学院

计算机学院01.习题课一01.

消解法（原理）(归结推理法)计算机学院利用规则推理有很大的随意性，不易机械执行，归结推理法是仅有一条推理规则的机械推理法,容易以程序实现，是定理机器证明的重要方法。是反证法的特殊情况。根据基本蕴涵式I8（析取三段论）即P，～P∨Q?Q和基本蕴涵式I13（归结原理）（P∨Q）∧（～P∨R）?Q∨R

消解规则（归结式定义）计算机学院称作C1和C2的消解式（归结式)。根据反证法，即需证明A1,A2,…,An,～B?R∧～R设C1=L∨C1′,C2=～L∨C2′是两个子句，有互补对L和～L，则新子句R（C1,C2)=C1′∨C2′为了证明A1,A2,…,An?B利用消解规则进行推理，其过程为：从{A1,A2,…,An,～B}出发。

计算机学院2）将A1∧A2∧…∧An∧～B转化成合取范式，如P∧（P∨R）∧（～P∨Q）∧（～P∨R）的形式3）将合取范式中的所有子句（析取式）构成子句集合S，如S={P，P∨R，～P∨Q，～P∨R}4）对S使用消解规则对S的子句作归结，即消除互补式（互反对），如子句P∨R与～P∨Q作归结，得归结式R∨Q并将这归结式仍放S中，重复这一过程。5）直至归结出矛盾式(称为空子句，记为□)

计算机学院因此，其消解过程就是对S的子句求消解式的过程。R（C1,C2)=C1′∨C2′仅三种情况:①C1=A∨B，C2=～A∨D，则（（A∨B），（～A∨D））?B∨D②C1=A，C2=～A∨B则（A,～A∨B)?B③C1=A，C2=～A则（A，～A）?F(□)消解方法的机械性是很明显的，其复杂性就是怎样寻找包含互反句节的子句。不同的寻找方式就产生了各种方式的消解算法。

计算机学院如果公司的利润高，那么公司有个好经理或它是一个好企业及大体上是个好的经营年份。现在的情况是：公司的利润高,不是一个好的经营年份。要证明，公司有个好经理。解：设A：公司的利润高B：公司有个好经理C：公司是个好企业D：大体上是个好的经营年份则原题可符号化为：（A?(B∨（C∧D））∧A∧～D?B

计算机学院P1:A?(B∨（C∧D））?～A∨（B∨（C∧D））?～A∨（（B∨C）∧（B∨D））?（～A∨B∨C）∧（～A∨B∨D）P2:AP3:～DS={～A∨B∨C，～A∨B∨D，A，～D，～B}归结过程（消解步骤）

计算机学院（1）～A∨B∨CP引用子句（2）～A∨B∨DP（3）AP（4）～DP（5）～BP（6）B∨D由（2),(3)归结（7）B由（4）,（6）归结（8）FLASE□由（5）,（7）归结导出空子句

计算机学院一、基本概念命题命题的解释原子命题、复合命题逻辑联结词（～、∨、∧、?、→、?）命题公式公式的解释永真式(重言式)永假式(矛盾式，不可满足公式)可满足式

计算机学院命题公式的等价替换定理对偶式对偶原理基本等价式——命题定律范式句节、子句、短语、析取范式、合取范式极小项---主析取范式极大项---主合取范式命题公式的蕴涵基本蕴含（关系）式

计算机学院推理规则P规则（称为前提引用规则）Ｔ规则（逻辑结果引用规则）ＣＰ规则（附加前提规则）

计算机学院二、基本方法1、应用基本等价式及置换规则进行等价演算2、求主析取（主合取）范式的方法1）公式转换法2）真值表技术法主合取范式----在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式。主析取范式----在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式。

计算机学院01推理的各种方法直接法利用CP规则反证法02消解法03

计算机学院证：P→(Q→R)?～P∨(Q→R)（蕴涵式）?～P∨(～Q∨R)（蕴涵式）?(～P∨～Q)∨R(结合律)?～(P∧Q)∨R(DeMorgan定律)?(P∧Q)→R（蕴涵式）

计算机学院2、试证明(P∧(Q∨R))∨(P∧～Q∧～R)?P证明：(P∧(Q∨R))∨(P∧～Q∧～R)?P∧((Q∨R)∨(～Q∧～R))（分配律）?P∧((Q∨R)∨