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

* 计算机学院 * 12、P24 2（2） 解：根据给定的条件有下述命题： P：现场无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者 则根据案情有如下命题公式： {P，Q∨R，S→ ～ P，Q→ T，～ S→ ～ R，R→ M} P P S→～P P ～S T①②I ～S→～R P ～R T③④I Q∨R P Q T⑤⑥I Q→T P T T⑦⑧I 即 金刚是偷窃者 * 计算机学院 * 13、若n是偶数，并且n大于5，则m是奇数。只有n是偶数，m才大于6。n是大于5，所以，若m大于6，则m是奇数。 解：设p：n是偶数，q: n大于5, r: m是奇数, s: m大于6. 前提: (p∧q) →r,s→p,q 结论：s→r 证明: q P ～s∨q ①扩充法则 （关键） * 计算机学院 * s→q ②蕴涵式 s→p P (s→p)∧(s→q) ③④合取 s→(p∧q) ⑤蕴涵式 (p∧q)→r P s→r ⑥⑦ 假言三段论 计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * * 计算机学院 * 消解法（原理）(归结推理法) 利用规则推理有很大的随意性，不易机械执行，归结推理法是仅有一条推理规则的机械推理法,容易以程序实现，是定理机器证明的重要方法。是反证法的特殊情况。 根据基本蕴涵式I8（析取三段论） 即 P，～P∨Q ? Q 和基本蕴涵式I13（归结原理） （P∨Q ）∧（～P∨R）? Q∨R * 计算机学院 * 消解规则（归结式定义） 设C1=L∨C1′, C2=～L∨C2′是两个子句，有互补对L和～L，则新子句 R（C1,C2)=C1′∨C2′ 称作C1和C2的消解式（归结式)。 为了证明 A1,A2,…,An ? B 根据反证法，即需证明 A1,A2,…,An,～B ? R∧～R 利用消解规则进行推理，其过程为： 1）从{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 (□) 消解方法的机械性是很明显的，其复杂性就是怎样寻找包含互反句节的子句。不同的寻找方式就产生了各种方式的消解算法。 * 计算机学院 * 例1-7．5 如果公司的利润高，那么公司有个好经理或它是一个好企业及大体上是个好的经营年份。现在的情况是：公司的利润高,不是一个好的经营年份。要证明，公司有个好经理。 解：设A：公司的利润高 B：公司有个好经理 C：公司是个好企业 D：大体上是个好的经营年份 则原题可符号化为： （A?(B∨（C∧D））∧A∧～D? B * 计算机学院 * P1:A?(B∨（C∧D）