《2022年离散数学复习资料 .pdf》由会员分享，可在线阅读，更多相关《2022年离散数学复习资料 .pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、读书之法 ,在循序而渐进 ,熟读而精思考纲：第一章数理逻辑1 命题及其真值命题概念，命题联结词，命题真值表，命题符号化2 重言式命题公式的性质，逻辑等价公式，永真蕴含公式，命题公式推倒（化简与证明）3 范式指派，析取范式，合取范式，极小项，极大项，主范式的求法，与真值表之间的关系4 联结词的扩充与归约功能完备集，与非，或非5 推理规则和证明方法CP规则，直接证明法、条件证明法、反证法，命题公式证明6 谓词和量词全称量词，存在量词，基于谓词的命题符号化，公式的解释7 谓词演算的永真公式谓词公式的等价公式和永真蕴含公式，前束范式8 谓词演算的推理规则基于谓词的推理，ES 、EG 、US、UG规则第
2、二章集合1 集合论的基本概念集合的定义，表示方法2 集合的运算交，并，补，差，环和，环积，定义和谓词表示方法，幂集3 自然数定义（了解）4 集合的笛卡儿乘积笛卡尔成绩的计算第三章二元关系1 关系的基本概念二元关系的定义、性质判断及证明（自反，反对称，对称，反对称，传递）、关系图、关系矩阵2 关系的运算二元关系的合成运算、逆运算、矩阵表示，3 关系上的闭包运算自反闭包，对称闭包，传递闭包，求法和性质证明4 次序关系篇序关系的定义，哈斯图，8 种特殊元素5 等价关系和划分等价关系的定义，等价划分，等价关系的证明。第四章函数精选学习资料 - - - - - - - - - 名师归纳总结 - - -
3、- - - -第 1 页，共 8 页读书之法 ,在循序而渐进 ,熟读而精思1 函数的基本概念定义、合成运算2 特殊函数类单射，满射，双射的判断3 逆函数定义第八章图论1 图的基本概念图、点、边的相关概念2 路径和回路基本路径，简单路径，基本回路，简单回路3 图的矩阵表示关联矩阵，邻接矩阵，可达性矩阵，权矩阵，最短路径（迪克斯特拉算法）4 欧拉图和哈密尔顿图欧拉图的定义、判断方法；哈密尔顿图的应用- 最小哈密尔顿回路（TSP ）问题（最邻近算法）5* 二部图和平面图定义，应用6 树树的定义，性质，生成树，最小生成树（克鲁斯克儿算法）7 有向树二元树的定义，遍历，二元树与普通树的转换，表达式的计算
4、等试卷类型： 闭卷题型： 填空题、命题符号化、作图、证明、计算离散数学练习题一、填空题1. 仅用和写出下列表达式的等价形式a) (P Q) R b) A(D E) 2. 仅用和写出下列表达式的等价形式a) (P Q) R b) Q (P Q) ；3. 构造公式P (P Q) Q的真值表。4. 公式A 有三个命题变元P、Q、R 组成，其主合取范式为A0 1 7 M M M ，则其主析取范式为：5. 公式A 有三个命题变元P、Q、R 组成，其主析取范式为A0 2 5 6 m m m m ，则其主合取范式为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第
5、 2 页，共 8 页读书之法 ,在循序而渐进 ,熟读而精思6. 设 A a , b , c , d , A 上的二元关系：R a, a ,a,b ,b, d ,c, a ,c,c ，S a,c ,b,b ,c,b ,c,c ,d,d 则S 1 R R S r(R) s(R) t(S ) 7. 给定如图所示的二元树：按先根次序遍历访问结点的顺序为：按中根次序遍历访问结点的顺序为：按后根次序遍历访问结点的顺序为：8. A 1,2, B a,b, AB2 = 9. 设解释I 如下：D=1 ，2P(1，1)P(1，2)P(2，1)P(2，2)0110确定下列各式的真值：xP(x,2) _ _; yP(
6、1, y) _ _; x yP(x, y) ) _ _。x yP(x, y) _;10. 集合A , 2,2 的幂集( A) 。11. 设全集U=1,2,3,4,5,6,7,8,9,10, A=1,2,4,5,6, B=2,4,6,8,10,精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页读书之法 ,在循序而渐进 ,熟读而精思则： (A B)-B = , B A= , BA= , BA=12. A 1,2, B a,b, AB = 。13. 给定集合S=a,b,c,d ，S 上的等价关系R 能产生划分 a,b,c,d，则 R14.
7、 指出下列映射是单射、满射、双射还是既非单射也非满射：a) f : Z R, f (x) ln x； (Z+: 表示正整数集)。b) f : R R ，f (x) x2 1 （R 表示不小于0 的实数）。c) f : R R ，f (x) x2 （R 表示不小于0 的实数）。d) f : AB, g : BC, g f 是双射，则f 是e) f : R R ，15. 请说出以下二元关系是否满足自反性、反自反性、对称性、反对称性和传递性。(a)：(b)：(c)：(d)：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页读书之法 ,在循
8、序而渐进 ,熟读而精思16. 某单位装配了30 辆汽车，其中15 辆有录音机，8 辆有空调， 6 辆有座位调节，三种设备都有的有2 辆，问这三种设备都不具备的汽车至少有辆？17. 设无向图中有6 条边，有一个3 度结点和一个5 度结点，其余结点的度数为2，则该图的结点数为：。二、命题符号化：18. 李明和王平是大学同学。19. 不是所有的哺乳动物都是胎生的。20. 任何一个公式总存在一个与之等价的主析取范式。21. 有些人对某些药品过敏。22. 参加考试的人不一定取得好成绩。23. 发光的不都是金子。24. 有的兔子比所有的乌龟跑的快。25. 所有猫都是动物，但有些动物不是猫。三、作图：26.
9、 用二元有序树表示命题公式：（见课后习题P320 2）27. 将下图所示的普通的树转换为等价的二叉树。28. 将下图所示的二叉树T 转换为等价的普通树或树林。29. 用克鲁斯克尔算法求出左图的最小生成树。（见课后习题P309 11）四、证明题：30. A B C D,D E G AG31. 证明下列论证：如果甲参加球赛，则乙或丙也将参加球赛；如果乙参加球赛，则甲不参加球赛；如果丁参加球赛，则丙不参加球赛；所以，如果甲参加球赛，则丁不参加球赛。32. 设 R 为二元关系，S a,b | c,a,c Rc,b R，证明，若 R 是等价关系，则S也是等价关系。33. 试证明：在任何一棵树T(n,m)
10、中均有 m=n-1。五、计算题：34. 设集合A2,3,4,5,6,8,12,18,36 ，R 是 A 上的整除关系，(1) 画出偏序集 (A, R) 的哈斯图；(2) 写出集合A 的最大元，最小元，极大元，极小元。(3) 写出A 的子集 2, 3, 6 的上界，下界，最小上界，最大下界；(4) 写出A 的子集 2, 4, 6 的上界，下界，最小上界，最大下界；35. 在下图中用迪克斯特拉算法求从a到 z 最经济道路的长度以及该道路所经过的结点，并给出求解过程。（见课后习题P278 18）_答案：一.1.a：(P Q B: ADE2.a:PQR精选学习资料 - - - - - - - - -
11、名师归纳总结 - - - - - - -第 5 页，共 8 页读书之法 ,在循序而渐进 ,熟读而精思 B:Q3.P Q P Q P (P Q) P (P QQ 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 14.AM2M3M4M5M65. AM2M3M4M76., , , ,7.ABDGHCEFI BGDHAECIF GHDBEIFCA8.,9. 1 0 0 110.1,5 2,4,6 1,5,8,10 2,3,4,6,7,912.,13.,14. 单射既非单射也非满射满射单射双射15. a：反自反，对称，反对称，传递 b: 自反，反对称，传递 c: 自反，反对称
12、传递 d ：自反，对称传递16.517.4二18. 设 A是“李明” B是“王平” F（x，y）：“x 与 y 是大学同学”， F（A,B）19. 设 P(x) 为“x 是哺乳动物” Q(x) 为“x 是胎生的” ? x（P(x)Q(x) ）20 设 p(x) 为“x 是一个公式”， Q(x) 为“x 是一个主析取范式” ,M(x,y) 为“x与 y 等价”x(P(x)y(Q(y)M(x,y)21. 设 P(x) 为“x 是人” Q(x) 为“x 是药品” S(x,y) 为“x 对 y 过敏”x y(P(x) Q(y) S(x,y)22. 设 P(x) 为“参加考试的人” Q(x) 为“x 取
13、得好成绩”x（P(x)?Q(x)）23 设 p(x) 为“x 发光” Q(x)为“x 是金子” ? x(P(x) Q(x)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页读书之法 ,在循序而渐进 ,熟读而精思24 设 P(x) 为“x 是兔子” Q(x) 为“x 是乌龟” H(x,y) 为“x 比 y 跑的快”x(P(x)y(Q(y)H(x,y)25 设 P(X)为“x 是猫”， Q(x) 为“x 是动物”x（P(x) Q(x) ）想（Q(x)? P(x) ）三：略四30设 A成立则推出 A B与 A BC D则推出 C D即 D
14、即 D E又 D EG故 G则 AG31 设甲乙丙丁参加球赛为ABCDAB CB?A A?D D?C又?A B C与?B ?A推出 C且?D ?C故 D联立 A?D得 A?D32. 自反性x R 自反R Q S对称性x,y 若S c 使R R R 对称R R S传递性x,y,z若S,S C1使 R R, C2使 R R R是传递R R S34. 如图A的最大元 36 最小元无极大元 36 极小元 2，3，52，3，6 上界 6，12，18，36 下界无最小上界 6 最大下界无2，4，6 上界 12，16 下界 2 最小上界 12 最大下界 235node P/T pro l(t)a 1b 2 a c 6 h 10 10 10 10 d 4 e 6 6 e 3 a 3 f 7 c 11 11 11 11 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页读书之法 ,在循序而渐进 ,熟读而精思g 9 f 13 13 12 h 5 d 9 I 8 e/h 11 11 11 11 Z g 16 16 15 15 15 14 故 aedhcfgz精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页