《离散数学》总复习.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,adfadffd,*,*,adfadffd,离散数学,总复习,adfadffd,第一部分 数理逻辑。包括命题逻辑和谓词逻辑。,一、离散数学的主要内容有哪些？,离散数学的主要内容可以分为四个部分：,第二部分 集合论。包括集合、关系和函数。,第三部分 代数系统。包括代数系统的一般概念，几类典型的代数系统。,第四部分 图论。包括图的基本概念，几种特殊的图。,adfadffd,二、考试,1,、题型,考试试题的题型有：单项选择题，,10,道题，占,10,分。填空题，共,10,个空，占,10,分。计算题，共,4,小题，占,20,分。证明题，共,5,题，占,30,分。,2,、难易程度,考试题的难度不会超过教材、参考书和模拟试题的难度。以简单题占,60%,，较难题占,30%,，难题占,10%,。,3,、考试范围,考试试题覆盖,离散数学,的全部内容。,adfadffd,第一部分 数理逻辑,一、内容提要,1,、命题及其联结词（非、与、或、单条件、双条件）。,2,、命题公式的析取范式和合取范式（主范式）。,3,、命题公式间的等价关系和蕴含关系。,4,、命题演算的推理理论。,5,、谓词公式的有关概念（量词、谓词、变元、真值指派等）,6,、谓词公式间的等价关系和蕴含关系。,7,、谓词演算的推理理论。,adfadffd,二、重点和难点,1,、命题公式间的等价关系和蕴含关系。,2,、命题演算的推理理论,(,包括命题符号化,),。,3,、谓词公式间的等价关系和蕴含关系。,4,、谓词演算的推理理论,(,包括命题符号化,),。,adfadffd,三、例题,1,、,证明推理：,(,x)(P(x),(Q(x),R(x),(,x)P(x),(,x)(P(x),R(x),证：,(,x)P(x)P,P(c)ES,(,x)(P(x),(Q(x),R(x)P,P(c),(Q(c),R(c)US,Q(c),R(c)T,I,R(c)T,I,P(c),R(c)T,I,(,x)(P(x),R(x)EG,adfadffd,2,、,证明推理：,(P,Q),(R,S),(Q,P),R,R,P,Q,证：,R P,(Q,P),R P,(Q,P)T,I,R,S T,I,(P,Q),(R,S)P,P,Q T,I,P,Q T,I,adfadffd,第二部分 集合论,集合论包括集合、二元关系和函数，它们之间的关系是：二元关系是一种特殊的集合，集合中的元素都是序偶；函数是一种特殊的二元关系。,一、内容提要,1,、集合的两种表示方法：列举法和描述法。,2,、特殊的集合：空集、全集、子集和幂集。,3,、集合的运算：并、交、差和对称差，各种运算的性质。,4,、集合运算的基本定律：交换律，结合律，分配律，吸收律，德,.,摩根律等。,5,、有序,n,元组、,n,维笛卡尔积。,6,、关系的定义：笛卡尔积的子集。,adfadffd,7,、关系的表示方法：集合、矩阵和关系图。,8,、关系的性质：自反性、反自反性、对称性、反对称性和传递性。,9,、关系的运算：复合运算、逆运算和闭包运算。,10,、特殊的二元关系及其相关特性：等价关系（自反性、对称性、传递性）、偏序关系（自反性、反对称性、传递性）、等价类、偏序关系中的特殊元素（极大元、上界等）。,11,、函数的定义、函数的定义域和值域。,12,、函数的性质：单射、满射和双射。,13,、函数的运算：复合函数、逆函数。,14,、集合的基数。,adfadffd,二、重点和难点,1,、掌握元素与集合之间的关系，集合与集合之间的关系。,2,、运用集合运算的基本定律去化简集合表达式或证明集合等式。,3,、掌握二元关系的五个性质和二元关系的运算。,4,、等价关系的证明、等价类的求解，偏序关系的特定元素的求解。,5,、函数的性质，求复合函数和逆函数。,adfadffd,三、例题,1,、,这两个关系是否正确？,答：正确。在,中,表示元素；在,中,表示空集。,2,、求,R=,的传递闭包。,解：,R,的传递闭包,=,。,注意：求传递闭包是一个不断,重复,合并有序对的过程。有序对,往往被漏掉。,3,、,化简集合表达式：,(A,B),A),(B,B),A,(B,B),解：,(,(A,B),A),(B,B),A,(B,B),)(,吸收律和零律,),=,A,AU(,同一律,),=,AA,U(,零律,),=U=U,adfadffd,4,、,设集合,A,a,b,c,d,e,，偏序关系,R,的哈斯图如图所示，若,A,的子集,B=c,d,e,，求：（,1,）用列举法写出偏序关系,R,的集合表达式；（,2,）写出集合,B,的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。,解：（,1,）,R=I,A,（,2,）集合,B,的极大元：,c,，极小元：,d,、,e,，最大元：,c,，最小元：无，上界：,c,、,a,，上,确,界：,c,，下界：无，下,确,界：无。,adfadffd,5,、已知,f,：,RR,且,f(x)=(x+4),3,-2,，已知,g,：,RR,且,g(x)=3x+5,，,求,:,f,与,g,的合成函数，并求,3,在,f,与,g,的合成函数下的函数值。,解,:(1)f,g:RR,，且,(f,g)(x)=g(f(x)=g(x+4),3,-2)=3(x+4),3,-2)+5=3(x+4),3,-1,(f,g)(3)=3*(3+4),3,-1=1028,adfadffd,第三部分 代数系统,一、内容提要,1,、代数系统的定义（封闭性）、特殊元素（幺元，零元、逆元、幂等元）。,2,、代数系统之间的关系：子代数，同态（单同态、满同态、同构）。,3,、同余关系的定义和商代数。,4,、半群、独异点和群的定义及其相互间的关系。,5,、群的基本性质：消去律、元素的阶。,6,、循环群的性质及生成元。,7,、子群的定义及判定方法、正规子群的定义及判定方法、子群的陪集。,(,拉格朗日定理,),adfadffd,8,、环和域的定义。,9,、子环的定义及其判定方法。,10,、格的定义及其性质。,11,、特殊的格：分配格、有界格、有补格、有补分配格。,12,、布尔代数及其性质。,二、重点和难点,1,、代数系统的定义及特异元素，如何证明两个代数系统同态与同构。,2,、循环群的定义及其性质。,3,、子群的定义及其判定方法。,4,、格的定义及其性质。,adfadffd,三、例题,1,、设,R,是实数集，在,R,上定义二元运算,*,，,x,y,R,，定义,x*y=x+y+2xy,。,试说明,*,是否满足结合律、交换律？是否存在幺元？若存在请求出幺元,。,解：,x,y,z,R,，,(x*y)*z=(x+y+2xy)*z=(x+y+2xy)+z+2(x+y+2xy)z,=x+(y+z+2yz)+2x(y+z+2yz)=x*(y+z+2yz)=x*(y*z),*,运算可结合。,x*y=x+y+2xy=y*x,*,运算可交换。,设幺元为,e,，,x,R,e,*,x,=,x,*,e,=,x,+,e,+2,xe,=,x,，由,x,的任意性,得,e,=0,R,幺元为,0,。,adfadffd,2.,给定代数系统,U=,V=,W=,设,f:XY,是从,U,到,V,的同态，,g:YZ,是从,V,到,W,的同态，则,gf:XZ,必是从,U,到,W,的同态。,证：对任意的,a,b,X,，证明：,gf(ab)=gf(a)gf(b),gf(ab)=g(f(ab),=g(f(a)*f(b),(f,是同态映射,),=g(f(a)g(f(b),(g,是同态映射,),=gf(a)gf(b),adfadffd,3,、设,是群，,a,bG,，且,(a*b),2,=a,2,*b,2,，证明,a*b=b*a,。,证：因为群满足消去律，所以,(a*b),2,=a,2,*b,2,(,a*b)*(a*b)=(a*a)*(b*b)(,因,*,可结合,),a*(b*a)*b=a*(a*b)*b (,群满足左右消去律,),b*a=a*b,adfadffd,4,、设,*,运算是,X,中的可结合的二元运算，并且对任意的,x,y,X,若,x*y=y*x,，则,x=y,。证明：,X,中的每个元素都是等幂的。,证：,对任意的,x,X,要证明,x,是等幂的，即证明：,x*x=x,因为：,*,运算是,X,中的可结合的二元运算,所以：,x*(x*x)=(x*x)*x,由已知：,x*y=y*x,x=y,得：,x*x=x,adfadffd,5,、设,是个代数系统，使得对任意的,a,b,c,d,A,有：,a*a=a,(a*b)*(c*d)=(a*c)*(b*d),证明：,a*(b*c)=(a*b)*(a*c),证：,左式,a*(b*c),（因为,a*a=a,）,=(a*a)*(b*c),（因为,(a*b)*(c*d)=(a*c)*(b*d),）,=(a*b)*(a*c)=,右式,adfadffd,6,、设为集合，证明,(X),与,(X),是同构的。,证：对任意的,S,(X),设,f(S)=,S,（,1,）来证,f,是个同态映射，即证：,f(S,1,S,2,)=f(S,1,)f(S,2,),）,f(S,1,S,2,),(S,1,S,2,),S,1,S,2,f(S,1,)f(S,2,),（,2,）来证,f,是个双射函数,任取,S1,S2,(X),且,S1 S2,f(S1)=,S1,f(S2)=,S2,因为,S1 S2,，所以，,S1,S2,，即,f(S1)f(S2),。故,f,是单射的；又因为,f,是,(X),到,(X),的自身的映射，故,f,是满射的。即,f,为双射。,adfadffd,7,、设,是半群，对于,A,中的每一个元素,a,和,b,，若,ab,，则,a*bb*a,（,a*b=b*a,a=b,）,（,1,）证明对于,A,中的一切,a,，有,a*a=a,。,（,2,）对于,A,中任意的,a,和,b,，证明,a*b*a=a,。,（,3,）对于,A,中任意的,a,b,和,c,，证明,a*b*c=a*c,。,证：,（,1,）,a*a=a,因为,是半群，,*,运算可结合，所以：,(a*a)*a=a*(a*a),a*a=a,adfadffd,（,2,）证明：对于,A,中任意的,a,和,b,，证明,a*b*a=a,。,证：能推出,(a*b*a)*a=a*,(a*b*a),即可。,(a*b*a)*a,（,*,运算可结合）,a*b*(a*a),a*b*a,（由（,1,）知）,(a*a)*b*a,（由（,1,）知）,a*(a*b*a),（由提示）,即：,(a*b*a)*a,a*(a*b*a),故有,a*b*a,a,adfadffd,（,3,）对于,A,中任意的,a,b,和,c,，证明,a*b*c=a*c,。,证：能推出,(a*b*c)*(a*c)=(a*c)*(a*b*c),即可。,(a*b*c)*(a*c),（,*,运算可结合）,=a*b*(c*a*c),（由（,2,）,=a*b*c,（由（,2,）,=(a*c*a)*b*c,（,*,运算可结合）,=(a*c)*(a*b*c),（由提示）,即：,(a*b*c)*(a*c)=(a*c)*(a*b*c),故：,a*b*c=a*c,adfadffd,8,、设,是一个群，,b,G,，定义函数,f:GG,且给定成：对任意的,x,G,，,f(x)=b,x,b,-1,。,证明：,f,是从,到,的一个同构映射。,证：,（,1,）显然,与,同类型；,（,2,）单射：,对任意的,x,y,G,证明：,f(x)=f(y)x=y,f(x)=f(y),b,x,b,-1,=,b,y,b,-1,（消去律）,x,b,-1,=,y,b,-1,（消去律）,x,=,y,adfadffd,（,3,）满射 【,f:GG,，,f(x)=b,x,b,-1,】,对任意的,y,G,证明：在,G,中至少存在一个原像,b,-1,y,b,，使得：,f(b,-1,y,b,),=b,(b,-1,y,b,),b,-1,=(b,b,-1,),y,(bb,-1,),=e,y,e,=,y,adfadffd,（,4,）证明,f,是个同态映射（即：运算的像,=,像的运算）,对任意的,x,y,G,f(x,y),=b,(x,y),b,-1,(,由,f,的定义,),=b,(x,e,y),b,-1,(,群中存在幺元,e),=b,(x,b,-1,b,y),b,-1,=(b,x,b,-1,),(,b,y,b,-1,),(,结合律,),=f(x),f(y),(,由,f,的定义,),或：,f(x,y)=b,(x,y),b,-1,f(x),f(y)=(,b,x,b,-1,),(b,y,b,-1,),（因,可结合）、,=b,x,(,b,-1,b),y,b,-1,=b,x,e,y,b,-1,=b,(,x,y),b,-1,adfadffd,第四部分 图论,一、内容提要,1,、图的基本概念：无向图、有向图、简单图、结点的度数、子图、补图、图的同构。,2,、握手定理：所有结点的度数之和等于边数的,2,倍。,3,、图的连通性：割边、割点、边割集、点割集。通路、回路、连通分支。,4,、图的矩阵表示：邻接矩阵、关联矩阵。,5,、欧拉图和哈密尔顿图的定义和判定条件。,6,、树的定义、性质、判定条件和遍历。,7,、二部图和平面图的定义、性质和判定条件,adfadffd,二、重点和难点,1,、掌握图的基本概念。,2,、运用握手定理解题。,3,、利用图的矩阵求两个结点间的通路条数。,4,、欧拉图和哈密尔顿图的判定。,5,、树的遍历方法。,adfadffd,三、例题,1,、设,T,是完全,2,杈树，有,t,片树叶，,i,个分支点，证明,:i=t-1,(,即：在完全,2,杈中，分支结点数比树叶数少,1),证：由握手定理知：,2+t+(i+t-1-t)3=2m=2(t+i-1),即：,t+3i-1=2t+2i-2,解得：,i=t-1,2,、设,T,是完全,2,杈树，有,t,片树叶，,i,个分支点，证明,T,的边数,m=2t-2,。,证：设,T,有,m,条边，根据握手定理可得：,2+t+(i+t-1-t),3=2m,即：,3i+t-1=2m,i=t-1,3(t-1)+t-1=2m,4t+4=2m,解得：,m=2t-2,。故结论成立。,adfadffd,3,、在,n,阶简单有向图中，完全有向图的边数为,n(n-1),。,证：完全有向图中任意两个结点间都有方向相反的两条边，所以：,m=2C,n,2,=2*n(n-1)/2=n(n-1),4,、对于（,n,n+1,）的图,G,，则,G,中至少有一个点的度大于等于,3,。,证：,现假设图,G,中所有结点的度均小于,3,即,2,，由握手定理知：,=2(n+1),矛盾,2n,又因为,则：,即得：,2(n+1),2n,adfadffd,5,、设,n,阶无向图,G,有,m,条边，其中，,n,k,个结点的度为,k,其余结点的度为,k+1,，证明：,n,k,=n(k+1)-2m,证：由握手定理知：,n,k,k+(n-n,k,),(k+1)=2m,整理得：,n,k,=n(k+1)-2m,。,6,、一棵树有,2,个点的度为,2,，,1,个点的度为,3,，,3,个点的度为,4,，其余结点的度为,1,，问该树有多少度为,1,的点？,解：,设有,x,个结点的度为,1,；则：,2,2+1,3+3,4+x,1=2,(2+1+3+x-1),19+x=10+2x,解得：,x=9,adfadffd,7,、证明在完全,2,杈树中，边的总数,m=2(n,t,-1),证：,设完全,2,杈树有,m,条边，则有,m+1,个结点,根结点的度为,2,，叶结点的度为,1,，其余结点的度为,3,，则：,2+n,t,+(m+1-1-n,t,)*3=2m,2+n,t,+3m-3n,t,=2m,解得：,m=2(n,t,-1),adfadffd,3,、每个自然数不是奇数就是偶数。如果自然数是偶数，当且仅当它能被,2,整除。并非每个自然数都能被,2,整除。因此，有的自然数是奇数。,【提示：,P(x,),：,x,是自然数，,Q(x,),：,x,是奇数，,R(x,),：,x,是偶数，,S(x),：,x,能被,2,整出,】,证,:,先符号化：,(,x,)(,P,(,x,)(,Q,(,x,),R,(,x,),，,(,x,)(,P,(,x,),R,(,x,),S,(,x,),，,(,x,)(,P,(,x,),S,(,x,),(,x,)(,P,(,x,),Q,(,x,),adfadffd,第二次测试题,1.,设,A=1,，,2,，,3,，,4,，,6,，,12,，,R,为,A,上的整除关系，则,R,为,A,上的偏序关系。,（,1,）试画出,R,的哈斯图,（,2,）并给出子集,2,，,3,，,6,的最大元和最小元、极大元和极小元、上界和下界、上确界和下确界。,2.,设,T,是一棵完全,k,元树，其中分枝结点数为,i,，叶结点数为,t,。试证明,k,与分枝结点数为,i,，叶结点数为,t,有如下关系式成立：（,k,1,）,i=t,1,3.,使用推论规则证明下列各题：,(1)P(QR),，,Q,P,，,S,R,，,P,S,（用,P,，,T,规则）,(2)(,X)(P(X)Q(X),(,)P(X)(,X)Q(X),。,