您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 薪酬管理 > 离散数学复习资料和试题
离散数学复习资料和试题集合论1.集合与集合之间的关系,元素与集合之间的关系1.判别下列各题是否正确:(1){1,2}{1,2,3,{1,2,3}}正确(2){p,q,r}{p,q,r,{p,q,r}}正确2.设有集合A={a,b,c},为空集,则{a}A3.设S1=,S2={},S3=ρ({}),S3=ρ(),则:S2∈S4为假命题2.幂集:ρ(A)就是集合A中子集所组成的集合求下列集合的幂集:(1){a,{a}}={,{a},{{a}},{a,{a}}}(2){,a,{a}}={,{},{a},{{a}},{,a},{,{a}},{a,{a}},{,a,{a}}}3.集合的运算:10组集合恒等式:1)交换率:A∪B=B∪A;A∩B=B∩A2)结合律:A∪(B∪C)=(A∪B)∪C;A∩(B∩C)=(A∩B)∩C3)分配律:A∪(B∩C)=(A∪B)∩(A∪C);A∩(B∪C)=(A∩B)∪(A∩C)4)同一律:A∪=A;A∩E=A5)零一律:A∩=;A∪E=E6)互补率:A∪~A=E;A∩~A=;~E=;~=E7)双重否定率:~~A=A8)幂等率:A∪A=A;A∩A=A9)吸收率:A∪(A∩B)=A;A∩(A∪B)=A10)德摩根率:~(A∪B)=~A∩~B;~(A∩B)=~A∪~B交:A∩B;并:A∪B;差运算:A—B(属于A不属于B);补运算:~A;对称差运算:AB;笛卡儿乘积:A×B={a,b|a∈A,b∈B}设A={a,b,c},B={b,d,e}则A—B={a,c},AB={a,c,d,e}4.集合的计数问题:|A|=2n(n是集合A的元素的个数)|A∪B|=|A|+|B|—|A∩B|;|A∪B∪C|=|A|+|B|+|C|—|A∩B|—|A∩C|—|B∩C|+|A∩B∩C|5.关系的性质:①由图写出性质②有性质画图③由关系集合写性质(自反性,反自反性,对称性,反对称性,传递性:)P34##2.6用图表示出来的在集合X={1,2,3}上的关系的6个图形,从图中可以清楚的看出:(1)R1是自反的、对称的、又是传递的(它是一个全关系);(2)R2是反自反的、反对称的(3)R3不是反自反的、反对称的(4)R4是自反的、反对称的(5)R5是反自反的、对称的、反对称的、传递的(它是一个空关系)6.映射与关系6.设集合A={a1,a2,a3,a4},B={b1,b2,b3},σ={〈a1,b2〉,〈a2,b2〉,〈a3,b1〉,〈a4,b3〉}则σ是满射但不是单射7.关系的闭包:r(R)=R∪IA┎;s(R)=R∪~R;t(R)=R∪R1∪R2∪R3……∪Rn1.设A={a,b,c},R1、R2是A上的二元关系:R1={〈a,a〉,〈b,b〉,〈b,c〉,〈d,d〉}R2={〈a,a〉,〈b,b〉,〈b,c〉,〈c,b〉,〈d,d〉}试证明R1是R2的何种闭包解:R1∪~R1={〈a,a〉,〈b,b〉,〈b,c〉,〈d,d},〈c,b〉}即有R1∪~R1=R2根据对成闭包的定义及求解方法只R2是R1的对称闭包2.设集合A={a,b,c,d},定义R={〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉}求r(R),s(R),t(R)解:r(R)={〈a,a〉,〈b,b〉,〈c,c〉,〈d,d〉,〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉}s(R)={〈a,b〉,〈b,a〉,〈b,c〉,〈c,b〉,〈c,d〉,〈d,c〉}t(R)={〈a,a〉,〈b,b〉,〈a,b〉,〈a,c〉,〈a,d〉,〈b,a〉,〈b,c〉,〈b,d〉,〈c,d〉}3.由关系集合写性质设A={a,b,c},R={〈a,a〉,〈b,b〉},具有反对称性8.关系的运算(复合运算)R1R21.设X={0,1,2,3},X上有两个关系:R1={〈i,j〉|j=i+1或j=i/2};R2={〈i,j〉|i=j+2}求复合关系:R1R2R1={〈0,1〉,〈1,2〉,〈2,3〉,〈0,0〉,〈2,1〉},R2={〈2,0〉,〈3,1〉}则有:R1R2={〈1,0〉,〈2,1〉}2.设R1,R2是集合A={1,2,3,4}上的二元关系,其中R1={〈1,1〉,〈1,2〉,〈2,4〉},R2={〈1,4〉,〈2,3〉,〈2,4〉,〈3,2〉},试求:R1R2解:R1R2=〈1,4〉,〈1,3〉}9.特殊关系等价关系:1.A={0,1,2,4,5,8,9},R为A上模为4的同余关系,求(1)R的所有等价类(2)画出R的关系图解:R={〈0,0〉,〈1,1〉,〈2,2〉,……,〈9,9〉,〈0,4〉,〈4,0〉,〈1,5〉,〈5,1〉,〈4,8〉,〈8,4〉,〈5,9〉,〈9,5〉,〈0,8〉,〈8,0〉,〈1,9〉,〈9,1〉}(1)[0]R={0,4,8}=[4]R=[8]R;[1]R={1,5,9}=[5]R=[9]R;[2]R={2}(2)2.A={a,b,c,d}A的等价关系R={〈a,a〉,〈b,b〉,〈c,c〉,〈d,d〉,〈a,b〉,〈b,a〉,〈8,4〉,〈c,d〉,〈d,c〉}求(1)图(2)A的等价类(3)A/R(商集)解:(1)(2)[a]R=[b]R={a,b}[c]R=[d]R={c,d}(3)A/R={{a,b},{c,d}}3.A={,1,2,4,……,24}上定义R={x,y|x,y∈A,且(x—y)能被12整除}(1)写出R(2)画图(3)证明R是等价关系解:(1)R={1,1,2,2,……24,24,1,13,2,14,……12,24,24,12}(2)(3)(定义法)若证明R为等价关系,只需证明R具有自反性,对称性,传递性①自反性:x∈A,则x,x∈R所以R具有自反性②对称性:若x,y∈R,则12|(x—y),y—x=(—x+y)所以12|(y—x),故y,x∈R,所以R具有对称性③传递性:如果x,y∈R,且y,z∈R,则12|(x—y)且12|(y—z)则x—z=(x—y)+(y—z)能被12整除,故12|(x—z),x,z∈R所以R具有传递性综上所述,R为等价关系偏序关系1.集合X={2,3,6,8},上的整除关系R={〈2,2〉,〈3,3〉,〈6,6〉,〈8,8〉,〈2,6〉,〈2,8〉,〈3,6〉}是偏序的,求其哈斯图2.集合A={2,3,6,12,24,36}上的整除关系R是偏序的,它可用哈斯图表示R={〈2,2〉,〈3,3〉,〈6,6〉,〈12,12〉,〈24,24〉,〈36,36〉,〈2,6〉,〈3,6〉,〈6,12〉,〈12,24〉,〈2,12〉,〈3,12〉,〈6,24〉,〈12,36〉〈2,24〉,〈3,24〉,〈6,36〉,〈2,36〉,〈3,36〉}求特殊关系1.设A={a,b,c}的幂集ρ(A)={,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}上的“”是偏序关系,则(1)B={{a,b},{b,c},{b},{c},}(2)B={{a},{c}},求8种特殊关系解:(1)不y∈B,y’y,故无罪最大元,最小元是;极大元为{a,b},{b,c};极小元为;上界和上确界均{a,b,c};下界下确界均为(2)无最大最小元;极大元和极小元均为{a},{c};上界为,{a,c},{a,b,c};上确界为{a,c};下界和下确界均为;2.集合A={2,3,6,12,24,36},其中“≤”为A上的整除关系R1)画出一般的关系图和哈斯图2)设B1={6,12}B2={2,3}B3={24,36}B4={2,3,6,12}为A的子集试求出B1B2B3B48种元素3.A={a,b,c,d,e,f,g,h},对应的哈斯图如下;令B1={a,b},B2={c,d,e},求B1B28种元素解B1B2最大元无无最小元无c极大元a,bd,e极小元a,bc上界c,d,e,f,g,hh下界无a,b,c上确界ch下确界无c最大元最小元极大元极小元上界下界上确界下确界B112612612,24,362,3,6126B2无无2,32,36,12,24,36无6无B3无无24,3624,36无2,3,6,12无12B412无122,312,24,36无12无代数系统1.代数系统单位元逆元素零元素1.在实数集R上定义二元关系“*”:“”如下:x*y=x+y—xy,xy=1/2(x+y)(1)x*y是否满足结合律、交换率?是否有单位元及逆元?(2)xy是否满足结合律、交换率?是否有单位元及逆元?解:因为(1)(x*y)*z=(x+y—xy)*z=x+y—xy+z—xz—yz+xyzx*(y*z)=x*(y+z—yz)=x+y—xy+z—xz—yz+xyz满足结合率x*y=x+y—xy;y*x=y+x—xy满足交换率x*0=x+0—x0=0+x—0x=x所以单位元是0x*x—1=x+x—1—xx—1=0所以x—1=—x/(1—x)(x≠1)所以对于R—{1}的所有x均有逆元素—x/(1—x)(2)因为(xy)z=1/2(x+y)z=1/2(1/2(x+y)+z)=1/4x+1/4y+1/2zx(yz)=x1/2(y+z)=1/4y+1/4z+1/2x所以不满足结合律又因为xy=1/2(x+y),yx=1/2(x+y)所以满足交换率;不存在单位元素和逆元素2.在代数系统N,+中的单位元是:03.设A是非空集合ρ(A),∪,∩中,ρ(A)对运算∪的单位元是,ρ(A)对运算∩的单位元是A2.找子群证明交换群1.试证阶为偶数的循环群中周期为2的元素个数一定是奇数证明:设(G,*)是阶为n的循环群,即|G|=n(n是偶数)。任取a∈G,an=e(m2),a的阶为m,a的逆元素a—1∈G,故(a—1)m=(am)—1=e—1=e,由群的性质,知a—1的阶也是m,则必定有a≠a—1反证法,若a≠a—1,则a2=e,所以a的阶不大于2,这与m2矛盾,所以a≠a—1,即当a的阶数大于2时,a与它的逆元素总是成对出现的又因为群中唯一的单位元素e的阶为1,此时阶大于2的元素个数是偶数,加上单位元e,个数为奇数了,剩下的那些阶为2的元素个数必须是奇数,才能满足所给条件n是偶数,得证2.找出(Z12,12)的所有子群解:(1)1阶子群([0],12)(2)2阶子群({[0],[6]}12)(3)3阶子群({[0],[4],[8]},12)(4)4阶子群({[0],[3],[6],[9]},12)(5)6阶子群({[0],[2],[4],[6],[8],[10],}12)(6)12阶子群(Z1.2,1.2)3.设群中每个元素的逆元素是其自身的,则G是一个交换群证明:对于任意的a,b∈G由a*b∈G,因为一个元素的逆元素就是其自己,于是a*b=(a*b)—1=b—1*a—1=b*a,所以G是交换群3.计算置换设M={1,2,3},σ与Τ是M的置换:σ=123,Τ=123231321求σ—1,σΤ,Τσ,Τ—1σ—1=123σΤ=123123=123312231321213Τσ=123123=123321231132Τ—1=1233214.证明两代数系统同构1.证明R+,×和R,+同构证:设g:R+→R,g(x)=lnx显然g(x)=lnx为一一对应的函数ln(x1x2)=lnx1+lnx2得g(x1x2)=g(x1)+g(x2)(x1,x2∈x)所以证明R+,×和R,+同构2.证明两个代数系统之间的同构关系就是等价关系证:设X,Y,*和Z,+为任意的三个代数系统首先,X,≌X,,所以满足自反性其次,如果X,≌Y,*,即存在g:X→Y,使得,x1,x2∈X,有g(x1x2)=g(x1)*g(x2)由g为一一对应的函数,所以存在g—1:Y→X,y1y2∈Y1g—1(y1)=x1g—1(y2)=
本文标题:离散数学复习资料和试题
链接地址:https://www.777doc.com/doc-2234804 .html