《离散数学》总复习.

1adfadffd《离散数学》总复习2adfadffd第一部分数理逻辑。包括命题逻辑和谓词逻辑。一、离散数学的主要内容有哪些？离散数学的主要内容可以分为四个部分：第二部分集合论。包括集合、关系和函数。第三部分代数系统。包括代数系统的一般概念，几类典型的代数系统。第四部分图论。包括图的基本概念，几种特殊的图。3adfadffd二、考试1、题型考试试题的题型有：单项选择题，10道题，占10分。填空题，共10个空，占10分。计算题，共4小题，占20分。证明题，共5题，占30分。2、难易程度考试题的难度不会超过教材、参考书和模拟试题的难度。以简单题占60%，较难题占30%，难题占10%。3、考试范围考试试题覆盖《离散数学》的全部内容。4adfadffd第一部分数理逻辑一、内容提要1、命题及其联结词（非、与、或、单条件、双条件）。2、命题公式的析取范式和合取范式（主范式）。3、命题公式间的等价关系和蕴含关系。4、命题演算的推理理论。5、谓词公式的有关概念（量词、谓词、变元、真值指派等）6、谓词公式间的等价关系和蕴含关系。7、谓词演算的推理理论。5adfadffd二、重点和难点1、命题公式间的等价关系和蕴含关系。2、命题演算的推理理论(包括命题符号化)。3、谓词公式间的等价关系和蕴含关系。4、谓词演算的推理理论(包括命题符号化)。6adfadffd三、例题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,⑦7adfadffd2、证明推理：(PQ)(RS),(QP)R,RPQ证：①RP②(QP)RP③(QP)T,①,②,I④RST,①,I⑤(PQ)(RS)P⑥PQT,④,⑤,I⑦PQT,③,⑥,I8adfadffd第二部分集合论集合论包括集合、二元关系和函数，它们之间的关系是：二元关系是一种特殊的集合，集合中的元素都是序偶；函数是一种特殊的二元关系。一、内容提要1、集合的两种表示方法：列举法和描述法。2、特殊的集合：空集、全集、子集和幂集。3、集合的运算：并、交、差和对称差，各种运算的性质。4、集合运算的基本定律：交换律，结合律，分配律，吸收律，德.摩根律等。5、有序n元组、n维笛卡尔积。6、关系的定义：笛卡尔积的子集。9adfadffd7、关系的表示方法：集合、矩阵和关系图。8、关系的性质：自反性、反自反性、对称性、反对称性和传递性。9、关系的运算：复合运算、逆运算和闭包运算。10、特殊的二元关系及其相关特性：等价关系（自反性、对称性、传递性）、偏序关系（自反性、反对称性、传递性）、等价类、偏序关系中的特殊元素（极大元、上界等）。11、函数的定义、函数的定义域和值域。12、函数的性质：单射、满射和双射。13、函数的运算：复合函数、逆函数。14、集合的基数。10adfadffd二、重点和难点1、掌握元素与集合之间的关系，集合与集合之间的关系。2、运用集合运算的基本定律去化简集合表达式或证明集合等式。3、掌握二元关系的五个性质和二元关系的运算。4、等价关系的证明、等价类的求解，偏序关系的特定元素的求解。5、函数的性质，求复合函数和逆函数。11adfadffd三、例题1、这两个关系是否正确？答：正确。在中表示元素；在中表示空集。2、求R={1,2,2,3,3,4}的传递闭包。解：R的传递闭包={1,2,2,3,3,4,1,3,2,4,1,4}。注意：求传递闭包是一个不断重复合并有序对的过程。有序对1,4往往被漏掉。3、化简集合表达式：((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B))解：((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B))(吸收律和零律)=A⊕⊕A⊕U(同一律)=A⊕A⊕U(零律)=⊕U=U12adfadffd4、设集合A＝{a,b,c,d,e}，偏序关系R的哈斯图如图所示，若A的子集B={c,d,e}，求：（1）用列举法写出偏序关系R的集合表达式；（2）写出集合B的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。解：（1）R=IA{d,b,d,c,d,a,b,a,c,a,e,c,e,a}（2）集合B的极大元：c，极小元：d、e，最大元：c，最小元：无，上界：c、a，上确界：c，下界：无，下确界：无。13adfadffd5、已知f：RR且f(x)=(x+4)3-2，已知g：RR且g(x)=3x+5，求:f与g的合成函数，并求3在f与g的合成函数下的函数值。解:(1)f∘g:RR，且(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=102814adfadffd第三部分代数系统一、内容提要1、代数系统的定义（封闭性）、特殊元素（幺元，零元、逆元、幂等元）。2、代数系统之间的关系：子代数，同态（单同态、满同态、同构）。3、同余关系的定义和商代数。4、半群、独异点和群的定义及其相互间的关系。5、群的基本性质：消去律、元素的阶。6、循环群的性质及生成元。7、子群的定义及判定方法、正规子群的定义及判定方法、子群的陪集。(拉格朗日定理)15adfadffd8、环和域的定义。9、子环的定义及其判定方法。10、格的定义及其性质。11、特殊的格：分配格、有界格、有补格、有补分配格。12、布尔代数及其性质。二、重点和难点1、代数系统的定义及特异元素，如何证明两个代数系统同态与同构。2、循环群的定义及其性质。3、子群的定义及其判定方法。4、格的定义及其性质。16adfadffd三、例题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+2xe=x，由x的任意性,得e=0R,幺元为0。17adfadffd2.给定代数系统U=X,∘,V=Y,*,W=Z,⊗,设f:X→Y是从U到V的同态，g:Y→Z是从V到W的同态，则g∘f:X→Z必是从U到W的同态。证：对任意的a,bX，证明：g∘f(a∘b)=g∘f(a)⊗g∘f(b)g∘f(a∘b)=g(f(a∘b))=g(f(a)*f(b))(f是同态映射)=g(f(a))⊗g(f(b))(g是同态映射)=g∘f(a)⊗g∘f(b)18adfadffd3、设G,*是群，a,b∈G，且(a*b)2=a2*b2，证明a*b=b*a。证：因为群满足消去律，所以(a*b)2=a2*b2(a*b)*(a*b)=(a*a)*(b*b)(因*可结合)a*(b*a)*b=a*(a*b)*b(群满足左右消去律)b*a=a*b19adfadffd4、设*运算是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=x20adfadffd5、设A,*是个代数系统，使得对任意的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)=右式21adfadffd6、设Ｘ为集合，证明＜ρ(X),∩＞与＜ρ(X),∪＞是同构的。证：对任意的Sρ(X),设f(S)=～S（1）来证f是个同态映射，即证：f(S1∩S2)=f(S1)∪f(S2)）f(S1∩S2)＝~(S1∩S2)＝~S1∪~S2＝f(S1)∪f(S2)（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为双射。22adfadffd7、设A,*是半群，对于A中的每一个元素a和b，若a≠b，则a*b≠b*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=a23adfadffd（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＝a24adfadffd（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*c25adfadffd8、设G,∘是一个群，bG，定义函数f:G→G且给定成：对任意的xG，f(x)=b∘x∘b-1。证明：f是从G,∘到G,∘的一个同构映射。证：（1）显然G,∘与G,∘同类型；（2）单射：对任意的x,yG,证明：f(x)=f(y)x=yf(x)=f(y)b∘x∘b-1=b∘y∘b-1（消去律）x∘b-1=y∘b-1（消去律）x=y26adfadffd（3）满射【f:G→G，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∘(b∘b-1)=e∘y∘e=y27adfadffd（4）证明f是个同态映射（即：运算的像=像的运算）对任意的x,yGf(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-1f(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-128adfadffd第四部分图论一、内容提要1、图的基本概念：无向图、有向图、简单图、结点的度数、子图、补图、图的同构。2、握手定理：所有结点的度数之和等于边数的2倍。3、图的连通性：割边、割点、边割集、点割集。通路、回路、连通分支。4、图的矩阵表示：邻接矩阵、关联矩阵。5、欧拉图和哈密尔顿图的定义和判定条件。6、树的定义、性质、判定条件和遍历。7、二