2022年离散数学复习资料.docx

《2022年离散数学复习资料.docx》由会员分享，可在线阅读，更多相关《2022年离散数学复习资料.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 读书之法 ,在循序而渐进 ,熟读而精思考纲：第一章 数理规律 1 命题及其真值 命题概念,命题联结词,命题真值表,命题符号化 2 重言式 命题公式的性质,规律等价公式,永真包蕴公式,命题公式推倒（化简与证明） 3 范式 指派,析取范式,合取范式,微小项,极大项,主范式的求法,与真值表之间的关系 4 联结词的扩充与归约 功能完备集,与非,或非 5 推理规章和证明方法 CP规章,直接证明法、条件证明法、反证法,命题公式证明 6 谓词和量词 全称量词,存在量词,基于谓词的命题符号化,公式的说明 7 谓词演算的永真公式 谓词公式的等价公式和永真包蕴公式

2、,前束范式 8 谓词演算的推理规章基于谓词的推理,ES、EG、US、UG规章集合其次章 1 集合论的基本概念 集合的定义,表示方法 2 集合的运算 交,并,补,差,环和,环积,定义和谓词表示方法,幂集 3 自然数 定义（明白） 4 集合的笛卡儿乘积 笛卡尔成果的运算第三章 二元关系 1 关系的基本概念 二元关系的定义、性质判定及证明（自反,反对称,对称,反对称,传递）、关系图、关系矩阵 2 关系的运算 二元关系的合成运算、逆运算、矩阵表示, 3 关系上的闭包运算 自反闭包,对称闭包,传递闭包,求法和性质证明 4 次序关系 篇序关系的定义,哈斯图,8 种特别元素 5 等价关系和划分 等价关系的定

3、义,等价划分,等价关系的证明；名师归纳总结 第四章函数第 1 页,共 8 页- - - - - - -精选学习资料 - - - - - - - - - 读书之法 ,在循序而渐进 ,熟读而精思 1 函数的基本概念 定义、合成运算 2 特别函数类 单射,满射,双射的判定 3 逆函数 定义第八章 图论 1 图的基本概念 图、点、边的相关概念 2 路径和回路 基本路径,简洁路径,基本回路,简洁回路 3 图的矩阵表示 关联矩阵,邻接矩阵,可达性矩阵,权矩阵,最短路径（迪克斯特拉算法） 4 欧拉图和哈密尔顿图欧拉图的定义、判定方法；哈密尔顿图的应用- 最小哈密尔顿回路（TSP）问题（最邻近算法） 5* 二

4、部图和平面图 定义,应用 6 树 树的定义,性质,生成树,最小生成树（克鲁斯克儿算法） 7 有向树 二元树的定义,遍历,二元树与一般树的转换,表达式的运算等试卷类型： 闭卷题型： 填空题、命题符号化、作图、证明、运算离散数学练习题 一、填空题1. 仅用和 写出以下表达式的等价形式A0 1 7 M M M ,就a P Q R b AD E 2. 仅用和 写出以下表达式的等价形式a P Q R b Q P Q ；3. 构造公式 P P Q Q 的真值表；4. 公式A 有三个命题变元P、Q、R 组成,其主合取范式为其主析取范式为：A0 2 5 6 m m m m ,5. 公式A 有三个命题变元P、Q

5、、R 组成,其主析取范式为就其主合取范式为：名师归纳总结 - - - - - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - 读书之法 ,在循序而渐进 ,熟读而精思6. 设 A a , b , c , d , A 上的二元关系：R a, a ,a,b ,b, d ,c, a ,c,c ,sR R S S a,c ,b,b ,c,b ,c,c ,d,d 就 S 1 R rR tS 7. 给定如下列图的二元树：按先根次序遍历拜访结点的次序为：按中根次序遍历拜访结点的次序为：按后根次序遍历拜访结点的次序为：8. A 1,2, B a,b, AB2 = P2,1P2,29

6、. 设说明I 如下：D=1 ,2P1, 1P1,20110确定以下各式的真值：xPx,2 _ _; yP1, y _ _; x yPx, y _ _；x yPx, 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= , ,就 R；BA=R 能产生划分 a,b,c,d12. A 1,2,

7、B a,b, AB = 13. 给定集合S=a,b,c,d ,S 上的等价关系14. 指出以下映射是单射、满射、双射仍是既非单射也非满射：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.

9、全部猫都是动物,但有些动物不是猫；三、作图：26. 用二元有序树表示命题公式：（见课后习题 P320 2）27. 将下图所示的一般的树转换为等价的二叉树；28. 将下图所示的二叉树 T 转换为等价的一般树或树林；P309 11）29. 用克鲁斯克尔算法求出左图的最小生成树；（见课后习题 四、证明题：30. A B C D,D E G AG31. 证明以下论证：假如甲参与球赛,就乙或丙也将参与球赛；假如乙参与球赛,就甲不参与球赛；假如丁参与球赛,就丙不参与球赛；所以,假如甲参与球赛,就丁不参与球赛；32. 设 R 为二元关系, S a,b | c,a,c Rc,b R ,证明,如 R 是等价关系

10、,就S 也是等价关系；33. 试证明：在任何一棵树Tn,m 中均有 m=n-1；五、运算题：34. 设集合 A 2,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 QR第 5

11、页,共 8 页 B: A DE2.a:PQ- - - - - - -精选学习资料 - - - - - - - - - 读书之法 ,在循序而渐进 ,熟读而精思 B:Q Q P Q P P Q P P QQ 3.P 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 14.AM2 M3 M4 M5 M65. AM2 M3 M4 M76., , , ,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：

12、反自反,对称,反对称,传递 b: 自反,反对称,传递 c: 自反,反对称传递 d ：自反,对称传递 16.5 17.4 二名师归纳总结 18. 设 A 是“ 李明”B是“ 王平”F（x,y）：“x 与 y 是高校同学” , F（A,B）第 6 页,共 8 页19. 设 Px 为“ x 是哺乳动物”Qx 为“ x 是胎生的”. x（PxQx ）20 设 px 为“x 是一个公式” , Qx 为“ x 是一个主析取范式”,Mx,y 为“ x与 y 等价”xPxyQyMx,y21. 设 Px 为“ x 是人”Qx 为“ x 是药品”Sx,y 为“x 对 y 过敏”x yPx Qy Sx,y22. 设

13、 Px 为“ 参与考试的人”Qx 为“x 取得好成果”x（Px.Qx ）23 设 px 为“x 发光”Qx 为“x 是金子”. xPx Qx- - - - - - -精选学习资料 - - - - - - - - - 读书之法 ,在循序而渐进 ,熟读而精思24 设 Px 为“x 是兔子”Qx 为“ x 是乌龟”Hx,y 为“x 比 y 跑的快”xPx yQy Hx,y25 设 PX为“x 是猫” , Qx 为“ x 是动物”x（Px Qx ）想（ Qx . Px ）三：略四30 设 A成立就推出 A B与 A BC D就推出 C D即 D即 D E又 D EG故 G就 AG31 设甲乙丙丁参与球

14、赛为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 最大下界 235名师归纳总结 node P/T pro lt 10 10 10 第 7 页,共 8 页a 1b 2 a c 6 h 10 d 4 e 6 6 11 11 e 3 a 3 11 f 7 c 11 - - - - - - -精选学习资料 - - - - - - - - - 读书之法 ,在循序而渐进 ,熟读而精思g 9 f 13 13 12 h 15 5 d 9 11 11 11 15 I 8 e/h 11 Z 15 g 16 16 14 故 aedhcfgz名师归纳总结 - - - - - - -第 8 页,共 8 页