2022年《离散数学》复习提纲2.pdf

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

1、学习资料收集于网络，仅供参考学习资料离散数学期末复习大纲一、数理逻辑复习知识点 1、命题与联结词（否定、析取、合取、蕴涵、等价? ） ，复合命题2、命题公式与赋值（成真、成假） ，真值表，公式类型（重言、矛盾、可满足） ，公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论6、谓词、量词、个体词（一阶逻辑3 要素） 、个体域、变元（约束出现与自由出现）7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）8、谓词公式的等值式（代换实例、消去量词、量词否定和量词

2、辖域收与扩、量词分配）和置换规则（置换规则、换名规则）9、一阶逻辑前束范式（定义、求法）本章重点内容： 命题与联结词、公式与解释、 （主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与解释、求前束范式。复习要求 1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、掌握利用真值表、等

3、值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料联结词描述一个简单命题；掌握命题的符号化。7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。8、掌握求一阶逻辑前束范式的方法。二、 集 合复习知识

4、点 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用本章重点内容： 集合的概念、集合的运算性质、集合恒等式的证明。复习要求 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。三、二元关系复习知识点 1、序偶、迪卡儿积，迪卡儿积的性质及运算。2、二元关系（定义、空关系、全域关

5、系、恒等关系） 、关系表达式、关系矩阵与关系图3、关系的定义域、值域、限制、像、复合关系（右复合）与逆关系4、关系的性质（自反性、反自反性、对称性、反对称性、传递性）5、关系的闭包（自反闭包、对称闭包、传递闭包）6、等价关系与等价类、商集、划分7、偏序关系与哈斯图、极大/小元、最大 /小元精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料本章重点内容： 二元关系的概念、关系的性质、关系的闭包、等价关系及划分、偏

6、序关系和哈斯图复习要求 1、了解序偶与迪卡儿积的概念，掌握迪卡儿积的运算。2、理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。3、掌握求复合关系与逆关系的方法。4、理解关系的性质（自反性、反自反性、对称性、反对称性、传递性），掌握其判别方法（定义、图） 。5、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。6、理解等价关系和划分、掌握等价类和划分的求法7、理解偏序关系的概念，掌握画哈斯图的方法，极大/小元、最大 /小元的求法。四、函数复习知识点 1、理解函数概念：函数、函数相等、A 到 B 的函数。2、理解单射、满射、双射等概念，

7、掌握其判别方法。3、函数的复合与反函数本章重点内容：函数的定义及判别方法、 函数的三大性质、 函数的复合与反函数。复习要求 1、掌握函数及从 A 到 B 的函数的判别方法。2、理解函数的像与原像。3、掌握函数的单射、满射、双射的判别方法。4、掌握求函数的复合与反函数的方法。五、 图论复习知识点 1、 图的基本概念：无向图与有向图、顶点与边的关联关系、顶点（边）与顶点精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习

8、资料（边）之间邻接关系、 简单图与多重图、 顶点度数（度）与握手定理、 图的同构、完全图、子（补）图。2、 通路与回路、简单通（回）路与初级通（回）路；连通图与非连通图、连通分支、点割集、边割集、点（边）连通度；强连通图、单向连通图与弱连通图；二部图。3、 图的矩阵表示：关联矩阵、邻接矩阵、可达矩阵。4、 欧拉通（回）路、（半）欧拉图；哈密尔顿通（回）路、 （半）哈密尔顿图；5、 无向树、生成树、带权树、最小生成树。6、 有向树、树根、有序树、二叉树、最优二叉树、前缀码、最佳前缀码、霍夫曼（Huffman）算法、二叉树的周游及应用。本章重点内容：握手定理、点（边）割集、通路与回路、特殊图（欧拉

9、图与哈密顿图、无（有）向树） 、最优二叉树、最佳前缀码、霍夫曼（Huffman）算法。复习要求 1、理解图的有关概念：图、完全图、简单图、子图、母图、生成子图等。2、深刻理解握手定理及其推论的内容，并能熟练地应用它们。3、能判断两个图是否同构。4、理解连通度、点割集、边割集、割边和割点。5、能判断图是否为强连通图、单向连通图与弱连通图。6、理解图的矩阵表示（关联矩阵、相邻矩阵）和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。4、理解欧拉图、哈密顿图的定义及判别定理。在无向图中找出一条欧拉通路或欧拉回路、哈密顿通路或哈密顿回路。5、理解无向树的定义，熟练掌握无向树的主要性质

10、，并能灵活应用它们。6、理解生成树的有关概念与性质。7、理解有向树、根树、二叉树和前缀码的有关概念；掌握用霍夫曼（Huffman）算法求带权图的最优二分树， 掌握求最佳前缀码方法， 二叉树的中序和前序行遍法。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料考试说明一、考核方式1）期末笔试为 100 分钟的闭卷考试，占总评成绩的70。2）平时成绩来自作业、考勤和课堂考核，占总评成绩30。二、各部分比例（大概为讲

11、授学时*2.5 ）1）数理逻辑： 35 分2）集合论： 40 分3）图论：25 分三、考题类型1）单选题： 20 题，每题 1 分，共 20 分2）判断题： 20 题，每题 1 分，共 20 分3）填空题： 10 题，每题 2 分，共 20 分4）综合题： 5 题，每题 8 分，共 40 分四、常见综合题1.用等值演算法证明等值式。2.在自然推理系统 P 中构造证明推理（多种方法）3.用等值演算法求解主析取范式或主合取范式，计算分析4.集合恒等式的证明或化简 (1-2 例题或练习 ) 5.集合的运算，有穷集的计数（文氏图、包含排斥原理）6.求二元关系导出的划分 (1-2 例题或作业 ) 7.给

12、定一个偏序集，画出哈斯图并求极大、极小元素、求最大、最小元素、上界、最小上界、下界、最大下界、上确界和下确界。8.图的集合表示、图形表示、矩阵表示，以及相互之间的转换。9.利用握手定理，无向树中的顶点数、边数、度数、叶子数，知道其中部分数据，求其余部分数据。10. 用 Huffman 算法求 最优二叉树产生的最佳前缀码（根树的应用）。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料离散数学试卷结构及样题一、单

13、选题（20小题，每题 1分，共 20分）1.设xxM：)(是人，xxP：)(犯错误，命题 “没有不犯错误的人” 符号化为（）A.)()(xPxMxB.)()(xPxMxC.)()(xPxMxD.)()(xPxMx2.设 A= x, y , B= y, z 则 AB 为（） A. ( x, y),( x, z) ,( y, y),( y, z) B. ( y, x),( x, z) ,( y, y),( y, z) C. ( x, y),( z, x) ,( y, y),( y, z) D. (x, y),( x, z) ,( y, y),( z, y) 3.设集合 A=1,2,3 ,A 上的关

14、系 R(1,1),(2,2),(2,3),(3,3),(3,1), 则 R 具有( ) A.反自反性B.传递性C.对称性D.以上答案都不对4.关于整数集 Z 上的“”关系 R，以下描述不正确的是（）A.R 的自反闭包是“”关系B.R 的对称闭包是“”关系C.R 的传递闭包是它本身D.R 的反自反闭包是“”5.下列图中（）是欧拉图二、判断题（20 小题，每题 1 分，共 20 分）1.公式( xF(x)yG(y)yG(y)是可满足式。（）2.C)(AC)(BB)(A这个定律叫做假言三段论。（）3.设 A=a， b， c， d ， R 是 A 上的一个二元关系， R = ,是自反的，是反对称的，是

15、传递的。（）4.在每个图中，所有顶点的度数之和等于边数的两倍。（）5.树是不包含回路的连通图，在（n，m）树中必有 m=n+1（）。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料三、填空题（10 小题，每题 2 分，共 20 分）1.已知命题公式RQPG)(，则G 的析取范式为。2.设A=2,3,4,5，若 A上的关系为 R=|(x-y)/2是整数 ，则R= 。3.R是集合 X上的一个关系，如果 R 是自反

16、的，对称的，传递的，则R 称为。4.无向完全图 Kn的边数为。5.在一个图中，不与任何一个顶点相邻接的点叫做。四、综合题（5 小题，每题 8 分，共 40 分）1 用等值演算法证明等值式(pq)(p r)(p(q r) 。2 对偏序集（ 3，5，6，15，24，30，| ）上的整除关系，画出哈斯图并回答下列问题：1）求极大、极小元素；2）求最大、最小元素；3）找出 3，5的所有上界，如果存在的话求出最小上界；4）找出 15，30的所有下界，如果存在的话求出最大下界。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - -

17、 -第 7 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料离散数学复习题一、选择题1.下述句子中哪一个不是命题（）A. 5是有理数B. 2020年元旦下大雪C. 我正在说假话D. ln1是整数2.在自然推理系统 P中，推理规则通常不包括（）A.直接证明法B.前提引入规则C.置换规则D.结论引入规则3.命题22(1)x y xy的意义是（）A.对任何 x 均存在 y使得 x2+y2=1 B.对任何 y均存在 x 使得 x2+y2=1 C.存在 y 对任何 x 均使得 x2+y2=1 D.存在 x 对任何 y均使得 x2+y2=1 4.下述句子中哪一

18、个是命题（）A.海南岛的天气好热啊！B.我知道我什么都不知道C.开会时请关闭手机D.明天天气晴朗5.判断推理是否正确的方法通常不包括（）A.真值表法B.归纳法C.等值演算法D.主析取范式法6.在自然推理系统 P中,联结词符号不包括（）A. B. C. D. 7.在自然推理系统 P中，构造证明的方法通常不包括（）A.直接证明法B.附加前提证明法C.归纳法D.归谬法8.对于集合的表示法，下列表示错误的是（）A. x | x 是实数? x21=0 B. x | x21=0，其中x 是自然数 C.-1, 1 D. x 是实数并且 x21=0 9.下列命题中错误的是（）A. 1 1, 1 B. 1 1,

19、 1 C. 1 1, 1 D. 1 1 10. 下列集合的基数互不相等的是（）A. , 和1, 2 B. 和 C. , 和1,1, 2 D. 1，1,1,2,3和1, 1, 2 11. 设 M(x):x 是人，P(x):x 犯错误， 命题“没有不犯错误的人” 符号化为（）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料A.)()(xPxMxB.)()(xPxMxC.)()(xPxMxD.)()(xPxMx12

20、. 设 G、 H 是谓词公式，P 是谓词，G)(xxP, H)(xxP,则谓词公式HG是( ) A.永真的B.永假的C.可满足的D.矛盾的13. 对于集合的表示法，下列表示正确的是（）A.(-1 , 0 , 1) B. x | x21=0 ? x 是自然数 C.-1 , 0 , 1 D. x 是实数并且 x21=0 14. 设 a、b、c 各不相同，对于下列选项中的两个集合，相等的是（）A. a, b, c和c, a, b B. a, b, c和a, b,c C. a, b, c和a, b, c D. a, b和a, b 15. 设 A、B、C 为集合，下列命题中错误的是（）A. (AB) B

21、 B B. A-B = A B = C. A-B = A B D. AB = B AB = A 16. 设 A=1,2,3,B =1,2, 那么下列不是从A 到 B 的二元关系的是（）A. , B. AB C.D. , 17. 设 R = , , , , 则 domR 和 ranR 分别 是（）A. 1, 2, 4和2, 3, 4 B. 1, 2, 4和1, 2, 3, 4 C. 1, 2, 3, 4和1, 2, 3 D. 1, 2, 3和1, 2, 3, 4 18. 设 R = , , , , S = , , , , ，则 R S 是（）A. B. , C. , , D. , , 19. 设

22、 R = , , , , , ，则 R2是（）A. , , B. , C. 1, 2, 3 D. 2, 4 20. 列集合的基数互为相等的是（）A. , 和1, ，1, 2 B. 和 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料C. , 和1, 1, 2, 3 D. 1, 1,1,2,3和1, 1, 2, 3 21. 设 X=，Y= P(, )， 下列命题为假的是（）A. X Y B. X = Y C.

23、X Y D. X Y 22. 设 A=1,2,3,B =1,2, 那么下列不是从A 到 B 的二元关系的是（）A. , B. AB C.D. , 23. 设 R = , , , , 则 domR 和 ranR 分别 是（）A. a, b, c和b, c, d B. a, b, d和b, c, d C. a, b, c和b, c D. a, b, d和b, c 24. 下列关系中哪个能构成函数？（）A. |x,yN,x+y10 B. |x,yN,x+y=20 C. |x,yR,|x|=y D. |x,yZ,x=|y| 25. 设无向图如图所示，则（）是一条哈密顿回路Agabcdefg Babcd

24、efg Ccfabcdeg Defgabcd 26. 设 G 为 n 阶 m 条边的无向连通图，则下列( )是不可能的。A mn-1 B m=n-1 C m=n D m=n+1 27. 设 A=1, 2, 3, 4， 定义在A 上的关系 R=, , , ,则关系R 具有性质（）A. 自反的B. 对称的C. 传递的D. 以上均不对28. 设 A=1, 2, 3，定义在 A 上的关系 R=,，则 R 的对称闭包是（）A. , B. , C. , D. 以上均不对精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第

25、10 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料29. 下列（）是满 2 元树30. 下列给出的符号串集合（）不是前缀码。 A. 1,11,101,001,0011 B.1,01,001,000 C.0,10,110,1111 D.b,c,dd,dc,aba,abb,abc 二、判断题1.设 R 是集合 A 上的关系，若21, RR是对称的，则21RR也是对称的。 （）2.设 A=a， b， c， d ， R 是 A 上的一个二元关系， R = ,是自反的，是反对称的，是传递的。（）3.自然数集 N 上的关系“”（小于等于）是偏序关系，也是全

26、序关系，同时也是良序关系。（）4.设 R 是整数集 Z 上的一个关系，如果R 是拟序，则 R 是反对称的。（）5.在每个图中，所有顶点的度数等于边数的两倍。（）6.树是不包含回路的连通图，在（n，m）树中必有 m=n+1（）。7.公式 p?q 为重言式。（）8.如果推理正确，则结论一定正确。（）9.若明天有超强台风，则明天放假。明天不放假，所以明天没有超强台风。( ）10. 在公式z)G(x,y)x(F(x,中， x 为指导变元，z)G(x,y)F(x,为x 的辖域。（）11. 公式( xF(x)yG(y)yG(y)是可满足式。（）12. 设 a、b 各不相同， a,b=a,b 。（）13.

27、空集是所有集合的子集。（）14. 设 R 为二元关系，则 R 既可能不是对称的，也可能不是反对称的。（）15. 函数 f:NN,f(x)=(x)mod 3,x 除以 3 的余数 ,是满射，不是单射（）16. 设 T 是 n 阶非平凡的无向树，则T 中至少有两片树叶。（）17. 如果函数 f:XY 是满射函数，而且是一对一函数， 那么 f:XY 一定存在逆函数。（）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习

28、资料18. 如果函数 f:XY 是一一对应函数，那么f:XY 一定存在逆函数。（）19. 设 R 是整数集 Z 上的一个关系， R = |x - y 是偶数 ，则 R 是等价关系。（）20. 自然数集 N 上的关系“”（小于等于）是偏序关系，也是全序关系，同时也是良序关系。（）21. 自然数集 N 上的关系“ ”（小于）是偏序关系，也是全序关系，同时也是良序关系。（）22. 自然数集 N 上的关系“整除”是偏序关系，也是全序关系，同时也是良序关系。（）23. 设 R 是整数集 Z 上的一个关系，如果R 是拟序，则 R 是反对称的。（）24. 在每个图中，所有顶点的度数等于边数的两倍。（）25.

29、 在任何有向图中，所以顶点的入度之和等于所有顶点出度之和。（）三、填空题1.公式（ qp）p的主合取范式为。2.根据假言推理定律，（AB)A。3.设M(x):x 是男生 , F(y):y女生, H(x,y):x比y力气大，则命题“不是所有的男生都比所有的女生力气大”符合号形式为。4.在一阶逻辑中将命题符号化时，若没有指明个体域，则使用。5.公式x(M(x)F(x) 的前束范式是。6.量词辖域收缩与扩张等值式x(A(x)B) 。7.设A=，1, a, b ，B=2, a, b ，则 AB= 。8.无向图 G 有生成树当且仅当 _ 。9.对于2叉有序正则树， 访问次序为： _ 的行遍法为中序行遍法

30、。10. 一个无向树的顶点是 27，则它的边数有个。11. 公式qp的成真赋值是。12. （AB) (BC）为假言三段论。13. 设F(x): x是人， G(x): x喜欢共享单车，则“有人不喜欢共享单车”符号化形式为。14. 在一阶逻辑中将命题符号化时，若没有指明个体域，则使用。15. 公式x(M(x)F(x) 的前束范式是。16. 设A=1,3,5,7,9，B=2,3,5,7,10，C=2,5,6 ，则 B-AC = 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 15 页 - - -

31、 - - - - - - - 学习资料收集于网络，仅供参考学习资料17. 设A = 0, 1, 2，则A上不同关系的个数为。18. 设f:R R, f=|xR, 该逆函数为：。19. 连通无回路的无向图称为_。20. 一个无向树的边数是 27，则它的顶点有个。四、综合题1 设命题公式 G =（QR）（ P（QR） ）, 求 G的主析取范式。（各种方法都要求掌握）2用真值表判断下列公式的类型：(pr) (pq) 3 用等值演算法证明等值式(pq)(pq)(pq) (pq)。4 在自然推理系统 P中用附加前提法证明下面推理：前提： sp,p(qr),q 结论： sr 5 在自然推理系统 P中构造下

32、面推理的证明：若明天是星期一或星期三，我明天就有课。若我明天有课，今天必备课。我今天没备课。所以，明天不是星期一，也不是星期三。6 某班有 30 个学生，其中 18 人会打篮球， 10 人会打排球， 8 人会打篮球和排球，7 人会打篮球和网球， 还有 3 人会打这三种球。 已知 7 个会打网球的人都会打篮球或排球。求不会打球的人数。7 设 A=1,2,3,4,5,6,8,10,12,16,18， “ ”为 A上的整除关系，试完成：1）画出偏序集 的哈斯图；2）设 B= x | x A x 5 ，求出 B的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。89 设 A=1,2,3,4，

33、在 A A上定义二元关系 R： ,R x + y = 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 15 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料u + v ，求 R导出的划分。1011无向图 G有 18条边， 3 个 4 度顶点， 4 个 5 度顶点，其余顶点度数均小于 3，问 G的阶数 n 为至少是多少？10. 在通信中，八进制数字出现的频率如下： 0：35% 1：25% 2：20% 3：15% 4：10% 5：10% 6：5% 7：5% 求传输

34、它们的最佳前缀码，并求传输10n（n=2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为 3）的码字传输需要多少个二进制数字？精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 15 页 - - - - - - - - - - 文档编码：KDHSIBDSUFVBSUDHSIDHSIBF-SDSD587FCDCVDCJUH 欢迎下载 精美文档欢迎下载 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 15 页 - - - - - - - - - -