离散数学(第7讲习题课1).pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * * 计算机学院 * 第一章小结 一、基本概念 命题 命题的解释 原子命题、复合命题 逻辑联结词（～、∨、∧、?、→、?） 命题公式 公式的解释 永真式(重言式) 永假式(矛盾式，不可满足公式) 可满足式 * 计算机学院 * 命题公式的等价 替换定理 对偶式 对偶原理 基本等价式——命题定律 范式 句节、子句、短语、析取范式、合取范式 极小项---主析取范式 极大项---主合取范式 命题公式的蕴涵 基本蕴含（关系）式 * 计算机学院 * 推理规则 ① P规则（称为前提引用规则） ② Ｔ规则（逻辑结果引用规则） ③ ＣＰ规则（附加前提规则） * 计算机学院 * 二、基本方法 1、应用基本等价式及置换规则进行等价演算 2、求主析取（主合取）范式的方法 1）公式转换法 2）真值表技术法 主合取范式----在命题公式的真值表中，使公式取值 0时的解释所对应的全部极大项的合取式。 主析取范式----在命题公式的真值表中，使公式取值 1时的解释所对应的全部极小项的析取式。 * 计算机学院 * 3、推理的各种方法 （1）直接法 （2）利用CP规则 （3）反证法 4、消解法 * 计算机学院 * 三、典型例题 1、证明P→(Q→R) ?(P∧Q)→R 证：P→(Q→R) ? ～P∨(Q→R)（蕴涵式） ? ～P∨(～Q∨R) （蕴涵式） ?(～P∨ ～Q)∨R (结合律) ? ～ (P∧Q)∨R (De Morgan定律) ?(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)∨～(Q∨R)) (De Morgan定律) ?P∧T（矛盾律） ?P (同一律) * 计算机学院 * 3、证明 ((P∨Q) ∧～(P∧Q)) ?～(P?Q) ((P∨Q)∧～(P∧Q)) ? ((P∨Q)∧(～P∨～Q)) (De Morgan定律) ?((P∨Q)∧～P)∨ ((P∨Q)∧～Q)) （分配律） ?((P∧～P)∨(Q∧～P))∨((P∧～Q)∨(Q∧～Q)) ? (Q∧～P)∨(P∧～Q) （矛盾律） ? ～(～Q∨P)∨～(～P∨Q) (De Morgan定律) ?～((Q→P)∧(P→Q)) （蕴涵式） ?～(P?Q) （等价式） * 计算机学院 * 4、 G=～(Ｐ→Ｑ)∨Ｒ，求主析取和主合取范式。 解：首先列出其真值表如下： P Q R P→Q ～（P→Q） ～(P→Q)∨R 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 极大项 极小项 P∨Q∨R P∨～Q∨R ～P∨～Q∨R ～P∧～Q∧R ～P∧Q∧R P∧～Q∧～R P∧～Q∧R P∧Q∧R 主析取范式=（～P∧～Q∧R）∨（～P∧Q∧R）∨ （P∧～Q∧～R）∨（P∧～Q∧R）∨（P∧Q∧R） 主合取范式=（ P∨Q∨R ）∧（ P∨～Q∨R ）∧（～P∨～Q∨R） * 计算机学院 * 5、用公式转换法求上题中的主析取和主合取范式 ～(Ｐ→Ｑ)∨Ｒ?～（～P∨Q）∨R ?（P∧～Q）∨R ?（P∨R）∧（～Q∨R） ?（P∨R∨（～Q∧Q））∧（～Q∨R∨（～P∧P）） ?（P∨R∨～Q）∧（P∨R∨Q）∧（～Q∨R∨～P）∧（～Q∨R∨P） ?（P∨R∨～Q）∧（P∨R∨Q）∧（～Q∨R∨～P） （主合取范式） ～(Ｐ→Ｑ)∨Ｒ?～（～P∨Q）∨R ?（P∧～Q）∨R ?（P∧～Q∧（R∨～R））∨（R∧（P∨～P）∧（Q∨～Q）） ?（P∧～Q∧R）∨（P∧～Q∧～R））∨（R∧P）∨（R∧～P） ?（P∧～Q∧R）∨（P∧～Q∧～R））∨（R∧P∧（Q∨～Q）） ∨（R∧～P∧（Q∨～Q）） ?（P∧～Q∧R）∨（P∧～Q∧～R）∨（R∧P∧Q） ∨ （R∧P∧～Q）∨（R∧～P∧Q）∨（R∧～P∧～Q） （主析取范式） * 计算机学院 * 6、将下面一段程序简化 If A∧B then If B∨C then X Else Y End Else If A∧C t