《离散数学》复习提纲(2018)

离散数学期末复习大纲一、数理逻辑复习知识点1、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论6、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量词分配）和置换规则（置换规则、换名规则）9、一阶逻辑前束范式（定义、求法）本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与解释、求前束范式。 复习要求1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；掌握命题的符号化。7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。8、掌握求一阶逻辑前束范式的方法。二、 集 合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。复习要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。三、 二元关系复习知识点1、序偶、迪卡儿积，迪卡儿积的性质及运算。2、二元关系（定义、空关系、全域关系、恒等关系）、关系表达式、关系矩阵与关系图3、关系的定义域、值域、限制、像、复合关系（右复合）与逆关系 4、关系的性质（自反性、反自反性、对称性、反对称性、传递性） 5、关系的闭包（自反闭包、对称闭包、传递闭包）6、等价关系与等价类、商集、划分7、偏序关系与哈斯图、极大/小元、最大/小元本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系及划分、偏序关系和哈斯图复习要求1、了解序偶与迪卡儿积的概念，掌握迪卡儿积的运算。2、理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。3、掌握求复合关系与逆关系的方法。4、理解关系的性质（自反性、反自反性、对称性、反对称性、传递性），掌握其判别方法（定义、图）。5、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。6、理解等价关系和划分、掌握等价类和划分的求法7、理解偏序关系的概念，掌握画哈斯图的方法，极大/小元、最大/小元的求法。四、函数复习知识点1、理解函数概念：函数、函数相等、A到B的函数。2、理解单射、满射、双射等概念，掌握其判别方法。3、函数的复合与反函数本章重点内容：函数的定义及判别方法、函数的三大性质、函数的复合与反函数。复习要求1、掌握函数及从A到B的函数的判别方法。2、理解函数的像与原像。3、掌握函数的单射、满射、双射的判别方法。4、掌握求函数的复合与反函数的方法。五、 图论复习知识点1、 图的基本概念：无向图与有向图、顶点与边的关联关系、顶点（边）与顶点（边）之间邻接关系、简单图与多重图、顶点度数（度）与握手定理、图的同构、完全图、子（补）图。2、 通路与回路、简单通（回）路与初级通（回）路；连通图与非连通图、连通分支、点割集、边割集、点（边）连通度；强连通图、单向连通图与弱连通图；二部图。3、 图的矩阵表示：关联矩阵、邻接矩阵、可达矩阵。4、 欧拉通（回）路、（半）欧拉图；哈密尔顿通（回）路、（半）哈密尔顿图；5、 无向树、生成树、带权树、最小生成树。6、 有向树、树根、有序树、二叉树、最优二叉树、前缀码、最佳前缀码、霍夫曼（Huffman）算法、二叉树的周游及应用。本章重点内容： 握手定理、点（边）割集、通路与回路、特殊图（欧拉图与哈密顿图、无（有）向树）、最优二叉树、最佳前缀码、霍夫曼（Huffman）算法。复习要求1、理解图的有关概念：图、完全图、简单图、子图、母图、生成子图等。2、深刻理解握手定理及其推论的内容，并能熟练地应用它们。3、能判断两个图是否同构。4、理解连通度、点割集、边割集、割边和割点。5、能判断图是否为强连通图、单向连通图与弱连通图。6、理解图的矩阵表示（关联矩阵、相邻矩阵）和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。4、理解欧拉图、哈密顿图的定义及判别定理。在无向图中找出一条欧拉通路或欧拉回路、哈密顿通路或哈密顿回路。5、理解无向树的定义，熟练掌握无向树的主要性质，并能灵活应用它们。6、理解生成树的有关概念与性质。7、理解有向树、根树、二叉树和前缀码的有关概念；掌握用霍夫曼（Huffman）算法求带权图的最优二分树，掌握求最佳前缀码方法，二叉树的中序和前序行遍法。考试说明一、考核方式1）期末笔试为100分钟的闭卷考试，占总评成绩的70。2）平时成绩来自作业、考勤和课堂考核，占总评成绩30。二、各部分比例（大概为讲授学时*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. 给定一个偏序集，画出哈斯图并求极大、极小元素、求最大、最小元素、上界、最小上界、下界、最大下界、上确界和下确界。8. 图的集合表示、图形表示、矩阵表示，以及相互之间的转换。9. 利用握手定理，无向树中的顶点数、边数、度数、叶子数，知道其中部分数据，求其余部分数据。10. 用Huffman算法求最优二叉树产生的最佳前缀码（根树的应用）。离散数学试卷结构及样题一、单选题 （20小题，每题1分，共20分）1. 设是人，犯错误，命题“没有不犯错误的人”符号化为（ ）A. B.C. D.2. 设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上的关系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. 这个定律叫做假言三段论。 （ ）3. 设A=a，b，c，d，R是A上的一个二元关系，R = ,是自反的，是反对称的，是传递的。（ ）4. 在每个图中，所有顶点的度数之和等于边数的两倍。（ ）5. 树是不包含回路的连通图，在（n，m）树中必有m=n+1（ ）。三、填空题 （10小题，每题2分，共20分）1. 已知命题公式，则G的析取范式为 。2. 设A=2,3,4,5，若A上的关系为R=|(x-y)/2是整数，则R= 。3. R是集合X上的一个关系，如果R是自反的，对称的，传递的，则R称为 。4. 无向完全图Kn的边数为 。5. 在一个图中，不与任何一个顶点相邻接的点叫做 。四、综合题 （5小题，每题8分，共40分）1 用等值演算法证明等值式(pq)(pr)(p(qr)。2 对偏序集（3，5，6，15，24，30，|）上的整除关系，画出哈斯图并回答下列问题： 1）求极大、极小元素；2）求最大、最小元素；3）找出3，5的所有上界，如果存在的话求出最小上界；4）找出15，30的所有下界，如果存在的话求出最大下界。离散数学复习题一、选择题 1. 下述句子中哪一个不是命题（ ）A. 是有理数 B. 2020年元旦下大雪 C. 我正在说假话 D. ln1是整数2. 在自然推理系统P中，推理规则通常不包括（ ）A.直接证明法 B.前提引入规则C.置换规则 D.结论引入规则3. 命题的意义是（ ）A.对任何x均存在y使得x2+y2=1 B.对任何y均存在x使得x2+y2=1C.存在y对任何x均使得x2+y2=1 D.存在x对任何y均使得x2+y2=14. 下述句子中哪一个是命题（ ）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是实数 x2-1=0 B. x | x2-1=0，其中 x是自然数 C.-1, 1 D. x是实数并且x2-1=0 9. 下列命题中错误的是（ ）A. 1 1, 1 B. 1 1, 1 C. 1 1, 1 D. 1 110. 下列集合的基数互不相等的是（ ）A. , 和1, 2B. 和C. , 和1,1, 2D. 1，1,1,2,3和1, 1, 211. 设M(x):x是人，P(x):x犯错误，命题“没有不犯错误的人”符号化为（ ）A. B.C. D.12. 设G、H是谓词公式，P是谓词，G, H,则谓词公式是( )A.永真的 B.永假的 C.可满足的 D.矛盾的13. 对于集合的表示法，下列表示正确的是（ ）A.(-1 , 0 , 1) B. x | x2-1=0 x是自然数 C.-1 , 0 , 1 D. x是实数并且x2-1=0 14. 设a、b、c各不相同，对于下列选项中的两个集合，相等的是（ ）A. a, b, c和c, a, bB. a, b, c和a, b,cC. a, b, c和a, b, cD. a, b和a, b15. 设A、B、C为集合，下列命题中错误的是（ ）A. (AB) B BB. A-B = A B = C. A-B = ABD. AB = B AB = A16. 设A=1,2,3,B =1,2, 那么下列不是从 A 到 B 的二元关系的是（ ）A. ,B. ABC. D. ,17. 设R = , , , , 则domR 和ranR分别 是（ ）A. 1, 2, 4和2, 3, 4 B. 1, 2, 4和1, 2, 3, 4C. 1, 2, 3, 4和1, 2, 3D. 1, 2, 3和1, 2, 3, 418. 设R = , , , , S = , , , , ，则RS 是（ ）A. B. , C. , , D. , , 19. 设R = , , , , , ，则R2是（ ）A. , , B. , C. 1, 2, 3D. 2, 420. 列集合的基数互为相等的是（ ）A. , 和1, ，1, 2B. 和C. , 和1, 1, 2, 3D. 1, 1,1,2,3和1, 1, 2, 321. 设X=，Y= P(, )， 下列命题为假的是（ ）A. X YB. X = YC. X YD. X Y22. 设A=1,2,3,B =1,2, 那么下列不是从 A 到 B 的二元关系的是（ ）A. ,B. ABC. D. ,23. 设R = , , , , 则domR 和ranR分别 是（ ）A. a, b, c和b, c, d B. a, b, d和b, c, dC. a, b, c和b, cD. a, b, d和b, c24. 下列关系中哪个能构成函数？（ ）A. |x,yN,x+y10 B. |x,yN,x+y=20C. |x,yR,|x|=y D. |x,yZ,x=|y|25. 设无向图如图所示，则（ ）是一条哈密顿回路Agabcdefg Babcdefg Ccfabcdeg Defgabcd26. 设G为n阶m条边的无向连通图，则下列( )是不可能的。 A mn-1 B m=n-1 C m=n D m=n+127. 设A=1, 2, 3, 4，定义在 A上的关系R=, , , ,则关系R具有性质（ ）A. 自反的 B. 对称的C. 传递的D. 以上均不对28. 设A=1, 2, 3，定义在A上的关系R=,，则R的对称闭包是（ ）A. ,B. ,C. ,D. 以上均不对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上的关系，若是对称的，则也是对称的。（ ）2. 设A=a，b，c，d，R是A上的一个二元关系，R = ,是自反的，是反对称的，是传递的。（ ）3. 自然数集N上的关系“”（小于等于）是偏序关系，也是全序关系，同时也是良序关系。（ ）4. 设R是整数集Z上的一个关系，如果R是拟序，则R是反对称的。（ ）5. 在每个图中，所有顶点的度数等于边数的两倍。（ ）6. 树是不包含回路的连通图，在（n，m）树中必有m=n+1（ ）。7. 公式pq 为重言式。（ ）8. 如果推理正确，则结论一定正确。 （ ）9. 若明天有超强台风，则明天放假。明天不放假， 所以明天没有超强台风。( ） 10. 在公式中，x为指导变元，为的辖域。（ ）11. 公式(xF(x)$yG(y)$yG(y)是可满足式。 （ ）12. 设a、b各不相同，a,b=a,b。 （ ）13. 空集是所有集合的子集。 （ ） 14. 设R为二元关系，则R既可能不是对称的，也可能不是反对称的。（ ）15. 函数f:NN,f(x)=(x)mod 3,x除以3的余数 ,是满射，不是单射 （ ）16. 设T是n阶非平凡的无向树，则T中至少有两片树叶。 （ ）17. 如果函数f:XY是满射函数，而且是一对一函数，那么f:XY一定存在逆函数。（ ）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. 在任何有向图中，所以顶点的入度之和等于所有顶点出度之和。（ ）三、填空题 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叉有序正则树，访问次序为：_的行遍法为中序行遍法。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