离散数学(杨圣洪版)-第1章-复习总结讲解.pptVIP

离散数学第一章 复习总结 北华航天工业学院 计算机学院 王兴会 命题 对错确定的陈述语句称为命题 联结词 命题逻辑中的联结词归纳为以下5种。 合取?：C语言中 and 并且 析取?：C语言中 || or 或 否定?：C语言中 ! not 非,不是,否定 条件式?：C语言中 if () 如果…那么 如p则q 双条件式?： 如p则q且如q则p,当且仅当 等值式 (1)p?q??p?q??q??p 条件式的等值式 (2)p?q?(p?q)?(q?p)?(p?q)?(?p??q) 双条件 (3)p???p 双重否定律 (4)p?p?p?p?p 幂等律 (5)p?q? q?p，p?q? q?p 交换律 (6) p?(q?r) ?(p?q) ? r 结合律 p?(q?r) ? (p?q) ? r (7) p?(q?r) ?(p?q)?(p?r) 分配律 p?(q?r) ? (p?q)?(p?r) (8) p?(p?r) ?p 吸收律(多吃少) p?(p?r) ?p (9) ?(p?q) ??p??q 德摩律 ?(p?q) ??p??q 置换规则 置换规则：当将公式A中的子公式B换成C得到公式D后，若B?C，那么A?D。 当将一个公式的局部进行等值替换后，仍与原公式等值，这也是数学中最常见的方法，不断对局部进行等值替换的操作，称为“等值演算”。 利用该规则及前述的等值式，可进行等值演算，从而推导出新的公式。 等值演算的基本套路 等值演算的基本套路 (1)转换? ： A?B??A?B (2)恰当转换? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) 确保公式只保留? ? ?联结词 (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)恰当使用分配律、吸收律。 析取范式与合取范式 文字：命题变项(变元)及其否定称为文字. 如 : p, q, r, ?p, ?q, ?r 简单析取式:仅由有限个文字构成的析取式. 如 : p?q, ?p?q, p??q, ?p? ?q, p?q?r 简单合取式:仅由有限个文字构成的合取式. 如 : p?q, ?p?q, p??q, ?p??q, p?q?r 析取范式与合取范式 析取范式：由有限个简单合取式的析取构成的命题公式。 合取范式：由有限个简单析取式的合取构成的命题公式。 析取范式与合取范式 构造析取范式的一般步骤： (1)转换? ： A?B??A?B (2)恰当转换? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)适当使用分配律： A?(B?C), A?(B?C). 析取范式与合取范式 (p?q) ?r ?(?p?q) ?r ?((?p?q)?r)?(?(?p?q)??r) ?(?p ?r)?(q?r)?(p??q??r) 析取范式与合取范式 小项：在含有n个变元的简单合取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单合取式为(极)小项。 m010 ：?p?q??r 大项：在含有n个变元的简单析取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单析取式为(极)大项。 M010：p??q?r 析取范式与合取范式 主析取范式：一个析取范式中，如果所有简单合取式均为(极)小项，则称为主析取范式。 主合取范式：一个合取范式中，如果所有简单析取式均为(极)大项，则称为主合取范式。 析取范式与合取范式 (p?q) ?r ?(?p ?r)?(q?r)?(p??q??r) 不是 (?p?q?r)?(?p??q?r)?(p?q?r)?(p??q??r) 是主析取范式 方法：每一项合取(q??q) (p?q)?r ?(p?r)?(?q?r)?(?p?q??r) 不是 ?(p?q?r)? (p??q?r)?(?p??q?r) ?(?p?q??r) 是主合取范式 方法：每一项析取(q??q) 析取范式与合取范式 p1,q1,r1:表示王娟，刘强，金鑫是班长； p2,q2,r2:分别表示