离散数学讲.ppt

离散数学 第6讲 回顾上节课重要知识点： 24个重要等值式 析取范式与合取范式及相关定理 极大项和极小项的概念 主合取范式、主析取范式，二者的关系（必考题，一般运算较繁，应力求熟练） 联结词的完备集 第三章 命题逻辑的推理理论 第三章 命题逻辑的推理理论 本讲基本知识点： 3.1推理的形式结构 基本概念 推理方法：真值表法；等价（值）演算法；主析取范式 九条重要的推理定律 第三章 命题逻辑的推理理论 第三章 命题逻辑的推理理论 3.1 推理的形式结构 定义3.1 ——推理的有效性 设A1，A2，…Ak，B都是命题公式，若对于A1，A2，…Ak，B 中出现的命题变项的任意一组赋值， 或者A1 ∧ A2 ∧ … ∧ Ak为假， 或者当A1 ∧ A2 ∧ … ∧ Ak为真时，B也为真， 则称由前提A1，A2，…Ak 推出B的推理是有效的或正确的，并称B是有效的结论。 第三章 命题逻辑的推理理论 说明： （1）由前提A1，A2，…Ak推B的推理记作{A1，A2，…Ak}|-B ,这称为推理的形式结构。如果推理是正确的，记作{A1，A2，…Ak}|=B ，否则记作{A1，A2，…Ak}|≠B。 （2）对于任一组赋值，前提和结论的取值有以下四种情况： ① A1 ∧ A2 ∧ … ∧ Ak为0，B为0。 √ ② A1 ∧ A2 ∧ … ∧ Ak为0，B为1。 √ ③ A1 ∧ A2 ∧ … ∧ Ak为1，B为0。 × ④ A1 ∧ A2 ∧ … ∧ Ak为1，B为1。 √ 第三章 命题逻辑的推理理论 例3.1:(1){p, p ? q}|-q (2) {p, q ? p}|-q 第三章 命题逻辑的推理理论 对于以上简单的推理，不用真值表也可以判断推理是否正确，在(1)中，前提为p ∧ (p ? q)，当q为假时，无论p取真取假，均为假。 在(2)中，前提为 p ∧ (q ? p)，当q为假时，如果p为真，则 p ∧ (q ? p)为真，出现了前提为真，结论为假的情况，故推理是不正确的。 第三章 命题逻辑的推理理论 推理的另一种形式： 定理3.1 命题公式A1，A2，…Ak推B的推理正确当且仅当 (A1 ∧ A2 ∧ … ∧ Ak) ?B 为重言式。（证明参见课本） 于是推理的一般形式可转化为蕴含式： (A1 ∧ A2 ∧ … ∧ Ak) ?B 推理正确转化为： A1 ∧ A2 ∧ … ∧ Ak = B 第三章 命题逻辑的推理理论 于是，以后推理的形式就写作： 前提：p , p ? q 结论：q 推理的形式结构： (p ∧(p ? q)) ?q 判断推理是否正确的方法就是判断重言蕴涵式的方法： 1、真值表法； 2、等值演算法； 3、主析取范式法。 第三章 命题逻辑的推理理论 由以下三种方法 1、真值表法； 2、等值演算法； 3、主析取范式法。 解决推理问题的步骤： （a）将命题符号化； （b）写出前提、结论和推理的形式结构； （c）进行判断 第三章 命题逻辑的推理理论 例：判断下列推理是否正确。 1、今天小李或去网吧或去教室。他没去教室，所以他去网吧了。 设 p：小李去网吧。q：小李去教室。则， 前提：p ∨ q , ?q 结论：p 推理的形式结构： ((p ∨ q) ∧ ?q) ?p 第三章 命题逻辑的推理理论 第三章 命题逻辑的推理理论 方法2：等值演算法： ((p ∨ q) ∧ ?q) ?p ?((p ∧ ?q )∨ (q ∧ ?q)) ?p ?(p ∧ ?q ) ?p ? ? (p ∧ ?q ) ∨ p ? ? p ∨ q ∨ p ? 1 所以，推理正确，即（(p ∨ q) ∧ ?q) = p 第三章 命题逻辑的推理理论 方法3：主析取范式法： ((p ∨ q) ∧ ?q) ?p ??((p ∨ q) ∧?q) ∨ p ??(p ∨ q) ∨ q ∨ p ? (? p ∧ ?q ) ∨ q ∨ p ? (? p ∧ ?q ) ∨ q ∧(p ∨ ?p ) ∨ p ∧(q ∨ ?q ) ? (?p ∧ ?q )∨(q ∧p)∨(q ∧?p)∨( p∧q)∨ ( p∧ ?q ) ? m0 ∨ m1 ∨ m2 ∨ m3 所以，推理正确，即（(p ∨ q) ∧ ?q) = p 第三章 命题逻辑的推理理论 例：判断下列推理是否正确。 2、若a能被4整除，则天下雨。现天下雨。所以a能被4整除。