离散数学总复习幻灯片

《离散数学总复习幻灯片》由会员分享，可在线阅读，更多相关《离散数学总复习幻灯片（27页珍藏版）》请在金锄头文库上搜索。

1、,离散数学总复习,一、如何学好离散数学？,1、熟读教材。准确理解各个概念和定理的含义（结合多个例子来理解），必要的推理过程要看懂、理解（它可以帮助你熟悉和深刻理解定理的含义）。,2、独立思考，大量练习。仅靠熟读教材并不能将书本上的知识变成你自己的知识，在熟读教材的基础上，必须通过大量练习，独立思考来真正获取知识。,3、注重抽象思维能力的培养。数学与其他学科相比较具有 较高的抽象性，而离散数学的抽象性特点更为显著，它有着大量抽象的概念和抽象的推理，要学好这门课程必须具有较好的 抽象思维能力，才能深入地掌握课程内容。,“常思考，多做题”,第四部分 数理逻辑。包括命题逻辑和谓词逻辑。,二、离散数学的

2、主要内容有哪些？,离散数学的主要内容可以分为四个部分：,第一部分 集合、函数、函数。包括集合、关系和函数。,第二部分 代数系统。包括代数系统的一般概念，几类典型的代数系统。,第三部分 图论。包括图的基本概念，几种特殊的图。,三、考试,1、题型 考试试题的题型有：单项选择题，共10小题，占20分。填空题，共10个空，占20分。简答题，共2小题，占20分。计算题，共2小题，占20分。证明题，共2小题，占20分。 2、难易程度 考试题的难度不会超过教材的难度。以基础题为主。 3、考试范围 考试试题覆盖离散数学的全部内容。,第一部分 集合、函数、关系,集合论包括集合、二元关系和函数，它们之间的关系是：

3、二元关系是一种特殊的集合，集合中的元素都是有序对；函数是一种特殊的二元关系。,一、内容提要 1、集合的两种表示方法：列举法和描述法。 2、特殊的集合：空集、全集、子集和幂集。 3、集合的运算：并、交、差和对称差，各种运算的性质。 4、集合运算的基本定律：交换律，结合律，分配律，吸收律，德.摩根律等。 5、有序n元组、n维笛卡尔积。 6、关系的定义：笛卡尔积的子集。,7、关系的表示方法：集合、矩阵和关系图。 8、关系的性质：自反性、反自反性、对称性、反对称性和传递性。 9、关系的运算：复合运算、逆运算和闭包运算。 10、特殊的二元关系及其相关特性：等价关系（自反性、对称性、传递性）、偏序关系（自

4、反性、反对称性、传递性）、等价类、偏序关系中的特殊元素（极大元、上界等）。 11、函数的定义、函数的定义域和值域。 12、函数的性质：单射、满射和双射。 13、函数的运算：复合函数、逆函数。 14、集合的基数。,二、重点和难点 1、掌握元素与集合之间的关系，集合与集合之间的关系。 2、运用集合运算的基本定律去化简集合表达式或证明集合等式。 3、掌握二元关系的五个性质和二元关系的运算。 4、等价关系的证明、等价类的求解，偏序关系的特定元素的求解。 5、函数的性质，求复合函数和逆函数。,三、例题 1、 这两个关系是否正确？ 答：正确。在中表示元素；在中表示空集。 2、求R=, , 的传递闭包。 解

5、：R的传递闭包=, , , , ,。 注意：求传递闭包是一个不断重复合并有序对的过程。有序对往往被漏掉。 3、化简集合表达式：(AB)A)(BB)A(BB) 解： (AB)A)(BB)A(BB) (吸收律和零律) =AAU (同一律) = AAU (零律) = U = U,4、设集合Aa, b, c, d, e，偏序关系R的哈斯图如图所示，若A的子集B=c, d, e，求：（1）用列举法写出偏序关系R的集合表达式；（2）写出集合B的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。,解：（1）R=IA, , , , , , （2）集合B的极大元：c，极小元：d、e，最大元：c，最小元

6、：无，上界：c、a，上确界：c，下界：无，下确界：无。,5、已知f：RR且f(x)=(x+4)3-2，已知g：RR且g(x)=3*x+5，求:(1)f与g的合成函数，并求3在f与g的合成函数下的函数值。(2)g与f的合成函数是否存在逆函数？为什么？如果有，求它的逆函数。 解: (1)fg: RR，且fg(x)=g(f(x)=3*(x+4)3-2)+5=3*(x+4)3-1 fg(3)=3*(3+4)3-1=1028 (2)因为g与f都是双射函数；那么，g与f的合成函数也是双射函数。故g与f的合成函数存在逆函数。 gf: RR，且gf(x)=f(g(x)=3*(3*x+5)3-2 (gf)-1:

7、 RR，且(gf)-1(x)=(x+2)/3)(1/3)-5)/3,第二部分 图论,一、内容提要 1、图的基本概念：无向图、有向图、简单图、结点的度数、子图、补图、图的同构。 2、握手定理：所有结点的度数之和等于边数的2倍。 3、图的连通性：割边、割点、边割集、点割集。通路、回路、连通分支。 4、图的矩阵表示：邻接矩阵、关联矩阵。 5、欧拉图和哈密尔顿图的定义和判定条件。 6、树的定义、性质、判定条件和遍历。 7、二部图和平面图的定义、性质和判定条件,二、重点和难点 1、掌握图的基本概念。 2、运用握手定理解题。 3、利用图的矩阵求两个结点间的通路条数。 4、欧拉图和哈密尔顿图的判定。 5、树

8、的遍历方法。,三、例题 1、设T是2叉正则树，有t片树叶，i个分支点，证明T的边数m=2t-2 。 证：设T有m条边，根据握手定理可得： t+3i-1=2m(1) 因为T是2叉正则树，根据树的性质可得： m=t+i-1.(2) 解由(1)，(2)构成的方程组得：m=2t-2。故结论成立。 2、已知无向图G为n(n2)阶简单图，G有m条边，则G的补图有_个结点，有_条边。 答： G的补图的结点个数等于G的结点个数，等于n。 G的补图的边数等于n阶完全图的边数减去G的边数，等于n(n-1)/2-m。,3、下列命题正确的是（ ） （a）G为n阶无向连通图，如果G的边数mn-1，则G中必有圈 （b）二

9、部图的顶点个数一定是偶数 （c）若无向图G的任何两个不相同的顶点均相邻，则G为哈密尔顿图 （d）3-正则图的顶点个数可以是奇数，也可以是偶数 解：c正确，因为无向图G为完全图。 a不正确，当G是无向树时，m=n-1，但G中没有圈。 b不正确，二部图要求结点能够分成两部分，每部分中的任何两个结点无边，并没有要求二部图的顶点个数是偶数. d不正确，3-正则图的所有结点的度数均为3，根据握手定理可得，所有顶点的度数之和是偶数。所以3-正则图的顶点个数必为偶数。,4、已知有向图D的顶点集合V(D)=v1,v2,v3,v4，其邻接矩阵如右图所示。求从v1到v3长度小于等于3的通路个数。,从v1到v3长度

10、小于等于3的通路个数= =0+1+4=5,A2=,=,A3=,=,解：,5、设n阶无向树G=中有m条边，证明m=n-1。 证：用数学归纳法进行证明。 (1)初始化：当n=1时，无向树G是平凡树，即G为平凡图。则m=0=n-1。 (2)假设归纳：假设当nk时，结论成立，即m=n-1。 当n=k+1时，从无向树G中删除某个结点v，如果结点v的度数为i，则有i条边与结点v相关联，且每条边均为桥。因此，从无向树G中删除结点v后得到i颗无向树，分别为：G1、G2、Gi，且对于所有的j(1ji)，均有|Gj|k。根据假设可得：无向树Gj的边mj=nj-1。无向树G的结点个数n=n1+n2+ni+1，无向树

11、G的边数m=m1+m2+mi+i=(n1-1)+(n2-1)+(ni-1)+i= n1+n2+ni= n-1。因此，当n=k+1时，结论也成立。 综合(1)、(2)可得：若n阶无向树G=中有m条边，则m=n-1。,第三部分 代数系统,一、内容提要 1、代数系统的定义（封闭性）、特殊元素（幺元，零元、逆元、幂等元）。 2、代数系统之间的关系：子代数，同态（单同态、满同态、同构）。 3、同余关系的定义和商代数。 4、半群、独异点和群的定义及其相互间的关系。 5、群的基本性质：消去律、元素的阶。 6、循环群的性质及生成元。 7、子群的定义及判定方法、正规子群的定义及判定方法、子群的陪集。,8、环和域

12、的定义。 9、子环的定义及其判定方法。 10、格的定义及其性质。 11、特殊的格：分配格、有界格、有补格、有补分配格。 12、布尔代数及其性质。,二、重点和难点 1、代数系统的定义及特殊元素，如何证明两个代数系统同态。 2、循环群的定义及其性质。 3、子群的定义及其判定方法。 4、格的定义及其性质。,三、例题 1、设R是实数集，在R上定义二元运算*，x,yR，定义x*y=x+y+2xy。试说明*是否满足结合律、交换律？是否存在幺元？若存在请求出 。 解： x,y,zR， (x*y)*z=(x+y+2xy)*z=(x+y+2xy)+z+2(x+y+2xy)z =x+(y+z+2yz)+ 2x(y

13、+z+2yz)= x*(y+z+2yz)=x*(y*z) *运算可结合。 x*y=x+y+2xy=y*x *运算可交换。 设幺元为e，xR, e*x=x*e=x+e+2xe=x，由x的任意性,得e=0R,幺元为0。,2、已知(L，*，)是格，且二元运算*和满足分配律，a,b,cL，化简表达式(a*b)(a*c)* (a*b)(b*c)。 解：(a*b)(a*c)*(a*b)(b*c) (a*b) ( (a*c)* (b*c) (分配律) =(a*b) (a*b)*c) (幂等律) =a*b (吸收律) 3、设G=为模24整数加群。 (1)求G的所有生成元。 (2)求G的所有非平凡的子群。 解：

14、（1）G的生成元：1，5，7，11，13，17，19，23。 （2）G的所有非平凡的子群：，。,4、设G是群，a,bG，且(ab)2=a2b2，证明ab=ba。 证：因为群满足消去律，所以 (ab)2=a2b2abab=aabb bab=abb ba=ab 5、设G=是18阶循环群，试求出G的全部生成元和全部子群，并证明任何子群均为正规子群。 解：因为循环群都是Abel群，G是循环群，H是G的子群。 aG，hH，有aha-1=aa-1h=eh=hH。 所以，H是正规子群。 G的生成元分别为：b,b5,b7,b11,b13,b17。 G的子群分别为：,第四部分 数理逻辑,一、内容提要 1、命题及

15、其联结词（非、与、或、蕴含、等价）。 2、命题公式的析取范式和合取范式。 3、命题公式间的等价关系和蕴含关系。 4、命题演算的推理理论。 5、谓词公式的有关概念（量词、谓词、变元、指派等） 6、谓词公式间的等价关系和蕴含关系。 7、谓词演算的推理理论。,二、重点和难点 1、命题公式间的等价关系和蕴含关系。 2、命题演算的推理理论。 3、谓词公式间的等价关系和蕴含关系。 4、谓词演算的推理理论。,三、例题 1、下列语句为命题的是（ ） （a）看球赛去 （b）离散数学是计算机系的一门必修课 （c）计算机有空吗？ （d）今天天气多好啊！ 解：命题是可以判定真假的陈述句，故b正确。 2、对于公式(x)(P(x)(y)Q(x,y)，下列说法正确的是（ ） （a）x和y都是自由变元 （b）x和y都不是自由变元 （c）x是自由变元，y不是自由变元 （d）x不是自由变元，y是自由变元 解：b正确。,3、证明推理： (x)(P(x) (Q(x)R(x), (x)P(x)(x)(P(x)R(x) 证： (x)P(x) P(c) (x)(P(x) (Q(x)R(x) P(c) (Q(c)R(c) Q(c)R(c)