离散数学总复习资料带习题.ppt

离 散 数 学 期 末 总 复 习 复 习 时 注 意 准确掌握每个概念 灵活应用所学定理 注意解题思路清晰 证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程. 考试内容 1.命题符号化，谓词符号化 2.主范式 3.给定个体域，求表达式的真值情况 4.推理证明（命题证明，谓词证明） 5.各种算法的证明（用图表示） 6.偏序，哈斯图，特殊元素的求解 7.欧拉图，哈密顿图，树的性质，握手定理 8.最小生成树 9.最优2叉树，前缀码，遍历序列 10.等价关系的证明。 第一章 命题逻辑 1.联结词 定义了六个逻辑联结词，分别是： (1) 否定“?” (2) 合取“∧” (3) 析取“∨” (4) 异或“ ” (5) 蕴涵“?” (6) 等价“?” 要熟练掌握这五个联结词在自然语言中所表示的含义以 及它们的真值表的定义。 ? ：否定 表示“不” ∧：合取 表示“不但…,而且...”“并且” ∨：析取 表示“或者－可兼取的或” ：异或 表示“或者－不可兼取的或” ?：蕴涵 表示“如果…,则...” ?: 等价 表示“当且仅当”“充分且必要” 可以将这六个联结词看成六种“运算”。 联结词的定义(包括真值表和含义). 特别要注意： “或者”的二义性, 即要区分给定的“或”是“可兼取的或∨”还是“不可兼取的或 ”。 “?”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件. 2.会命题符号化. 例如 P:我有时间. Q:我上街. R:我在家. 表示P是Q的充分条件: 如果p,则Q. 只要P,就Q. P?Q 表示P是Q的必要条件: 仅当P,才Q. 只有P,才Q. Q?P 如果P,则Q;否则R. (P?Q)?(?P?R) 3.永真式的证明. 方法1.列真值表. (?R?(Q?R)??(P??Q))??P 方法2.用公式的等价变换,化简成T. 例如证明(?R?(Q?R)??(P??Q))??P是永真式. 证:上式??(?R?(?Q?R)??(P??Q))??P(P?Q??P?Q) ?(R?(Q??R)? (P??Q))??P (公式的否定公式) ?((R?(Q??R))? ((P??Q)??P) (结合律) ? ((R?Q)?(R??R))?((P??P)?(?Q??P) (分配律) ?(R?Q)?(?Q??P) ?R?Q??Q??P? T (互补,同一律) 4.永真蕴涵式的证明, 记住常用的公式. 永真蕴涵式: A?B是永真式,则称 A永真蕴涵B. (A?B) 方法1.列真值表. 方法2.假设前件真,推出后件真. (即直接推理) 方法3.假设后件假,推出前件假.(即反证法) 例证明(P?(Q?R))?((P?Q)?(P?R))是永真蕴涵式. 证:假设后件(P?Q)?(P?R)假, 则P?Q为T, P?R为F,于 是P为T,R为F, 进而又得Q为T. 所以Q?R为F, 所以前件 P?(Q?R)为F. 所以(P?(Q?R))?((P?Q)?(P?R))为 永真式. 对于给定一个题,究竟是用哪种方法,原则上哪种都可以. 但是哪个方法简单,要根据具体题而定. 5.等价公式的证明,记住常用的公式. 方法1.列真值表. 方法2.用公式的等价变换. 例如:证明 P?(Q?R)?(P∧Q)?R P?(Q?R)??P?(?Q?R) ? (?P??Q)?R ??(P?Q)∨R? (P∧Q)?R 注意:不论是证明永真蕴涵式,还是证明等价公式以及后边 的求公式的范式,命题逻辑推理,都应用43页的公式。 必须记忆一些常用的公式 如:P43表中的 永真蕴涵式: I1, I3, I9, I10, I11, I12, I13, 等 价 公 式: E1 ~ E16, E18, E19 , E20, E21, 6.命题公式的范式 1)析取范式:A1∨A2∨...∨An (n≥1) Ai (i=1,2..n)是合取式. 2)合取范式:A1∧A2∧...∧An (n≥1) Ai (i=1,2..n)是析取式. 3)析取范式与合取范式的写法. 4)小项及小项的性质. m3 m2 m1