离散数学考前综合复习资料

1、离散数学综合复习资料一、判断题1 A、B、C是任意命题公式，如果AÙCÛBÙC，一定有AÛB。（ ）2设<A，*>是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元q，则e¹q。（ ）3 A、B、C为任意集合，已知AÈB=AÈC，必须有B=C。（ ）4 自然数集是可数的。（ ）5 命题联结词Ø，Ù，Ú是最小联结词组。（ ）6 有理数集是可数的。（ ）7 交换群必是循环群。（ ）8 图G的邻接矩阵A，Al中的i行j列表示结点vi到vj长度为l路的数目。（ ）二

2、、解答题1 求命题公式Ø(P®Q)的主析取范式。2 举出A=a,b,c上的二元关系R和S满足： （1）R既不是自反的又不是反自反的，既是对称的又是反对称的；（2）S既不是对称的又不是反对称的，是传递的。3 以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。（1） f: N®Q, f(x) = 1/x（2） f: R´R®R´R, f(x,y)=<y+1,x+1>4 判断下列代数系统是否是群，并说明理由：(1) <R，->：实数集关于减法； (2) <I，+>：整数集关于加法；

3、5.构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。d ° b°°e°c°a6.画一个有欧拉回路，但没有汉密尔顿回路的图。7.将下列命题符号化（1）如果张三和李四都不去，她就去。（ØPÙØQ）®R）（2）今天要么是晴天，要么是雨天。（P"Q）v4V5v1v2v30 1 0 0 01 0 1 0 00 1 0 0 00 0 0 0 10 0 0 1 0A(G)=8.设G=<V,E>，V=V1,V2,V3,V4的邻接矩阵：（1）试画出该图。（

4、2）V2的入度d-(V2)和出度d+(V2)是多少？（3）利用邻接矩阵的性质求从V1到V2长度为3的路有几条？9.将下列命题符号化（1）除非你走否则我留下。（2）我们不能边看电视边看报。10.设集合A有m个元素，B有n个元素，则A到B的关系有多少个？A到B的函数有多少个？11.设有一组权3、4、13、5、6、12，（1）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。（2）设上述权值分别对应英文字母b、d、e、g、o、y，试根据求得的最优树构造前缀码，并对二进制序列译码。三、证明题1 设R,S是A上的等价关系，证明RÇS也是A上的等价关系。2 设f和g都是群

5、<A，*>到<B，>的同态，令H=x|xÎA，f(x)=g(x)，试证：<H，*>是<A，*>的子群。3 当且仅当连通图的每条边均为割边时，该连通图才是一棵树。4 f是群<G,°>到群<G,*>的同态映射，e是G中的幺元则，f的同态核K=x|xÎG且f(x)=e构成的代数系统<K,°>是<G,°>的子群。5 证明当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。6 设f是从A到B的一个函数，定义A上的关系R：aRb当且仅当f(a)=f(b)，

6、证明：R是A上的等价关系。7 代数系统<I,+>是一个群，设B=x|x=5n,nÎI，证明：<B,+>是<I,+>的子群。8 连通图至少有一棵生成树离散数学综合复习资料答案一、判断题题号12345678答案二、解答题1、求命题公式Ø(P®Q)的主析取范式。解：Ø(P®Q)ÛØ(ØPÚQ)ÛPÙØQ2、 解：（1）R = <a,a>,<b,b>（2） S=<a,a>,<b,b><a,b&g

7、t;,<b,a><a,c>3、以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。（1） f: N®Q, f(x) = 1/x（2） f: R´R®R´R, f(x,y)=<y+1,x+1>解：（1）不是函数，在x=0时无定义。（2） 函数，双射，f-1(x,y)=<y-1,x-1>4、判断下列代数系统是否是群，并说明理由：(1) <R，->：实数集关于减法； (2) <I，+>：整数集关于加法；解：（1）+在R上是封闭的，不可结合所以<R，->不是

8、群；（2）+在I上是封闭的，可结合的，幺元是0，I中任意元素x的逆元为-x，所以<I，+>是群；5、构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。解：右图所示哈斯图表示一个偏序集，其中：子集B=b，c有上界d，e但没有最小上界，同时子集B=b，c有最大下界a，但没有最小元。 6、画一个有欧拉回路，但没有汉密尔顿回路的图。解：7、将下列命题符号化（1）如果张三和李四都不去，她就去。（ØPÙØQ）®R）（2）今天要么是晴天，要么是雨天。（P"Q）v4V5v1v2v30 1 0 0 01 0

9、 1 0 00 1 0 0 00 0 0 0 10 0 0 1 0A(G)=8、解：（1）如右上图（2）d-(V2)=2，d+(V2)=2（3）因为a(3)12=2，所以V1到V2长度为3的路有2条。9将下列命题符号化（1）除非你走否则我留下。（ØP®Q）（2）我们不能边看电视边看报。（Ø（PÙQ)）10设集合A有m个元素，B有n个元素，则A到B的关系有多少个？A到B的函数有多少个？解：1）A到B的关系有2mn个。2）A到B的函数有nm个。 11设有一组权3、4、13、5、6、12，（1）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子

10、的权）。（2）设上述权值分别对应英文字母b、d、e、g、o、y，试根据求得的最优树构造前缀码，并对二进制序列译码。解：（1）见下页（2）将上面的最优树的每个分枝点引出的两条边，左侧边标0，右侧边标1，得到一个b、d、e、g、o、y对应的前缀码000，001，11，010，011，10。对二进制序列译码为goodbye。34567111912132544 0 1 0 1 0 10 1 0 1 y eb d g o三、证明题1.设R,S是A上的等价关系，证明RÇS也是A上的等价关系。证明：a)自反性：对任意aÎA，因为<a,a>ÎA,<a,a>

11、ÎS，所以<a,a>ÎRÇS，即RÇS具有自反性。b)对称性：对任意a,bÎA，如果有<a,b>ÎRÇS，则<a,b>ÎR且<a,b>ÎS。因为R,S是等价关系，所以具有对称性，所以<b,a>ÎR且<b,a>ÎS。所以<b,a>ÎRÇS，即RÇS具有对称性。c)传递性：对任意a,b,cÎA，若有<a,b>,<b,c>ÎRÇ

12、;S则<a,b>,<b,c>ÎR且<a,b>,<b,c>ÎS则因为R,S是等价关系，所以具有传递性，所以<a,c>ÎR且<a,c>ÎS所以<a, c>ÎRÇS，即RÇS具有传递性。所以RÇS是A上的等价关系。2.设f和g都是群<A，*>到<B，>的同态，令H=x|xÎA，f(x)=g(x)，试证：<H，*>是<A，*>的子群。证明 由定义知HÍA （1）设e是<

13、;A,*>的幺元，e是<B,>的幺元， 因为f,g都是<A，*>到<B，>的同态，则f(e)=g(e)=e，所以eÎH，所以H¹Æ； （2）"a,bÎH，有f(a)=g(a)，f(b)=g(b)， 因为f,g都是同态映射，所以f(b)-1=f(b-1)且g(b)-1=g(b-1) 所以f(a* b-1)=f(a)f(b-1)=f(a)f(b)-1= g(a)g(b)-1=g(a)g(b-1)=g(a* b-1) 所以a* b-1ÎH，所以<H,*>是<A,*>的子群。3

14、 当且仅当连通图的每条边均为割边时，该连通图才是一棵树。证明：必要性：如果图G是树，则删去任一边后就不连通，故任一边均为G的割边。充分性：任取两个结点u,v，图G连通，则u,v之间有路存在。若u,v间有两条路，则可组成一个回路，则删除回路上任一条边后不改变图的连通性，这样该回路上的边都不是割边，与前提矛盾，因此任意两个结点间恰有一条路，图G是树。4 f是群<G,°>到群<G,*>的同态映射，e是G中的幺元则，f的同态核K=x|xÎG且f(x)=e构成的代数系统<K,°>是<G,°>的子群。证明：由定义可知K

15、ÍG，设G中的幺元为e，则有f(e)=e，所以eÎA，即A为非空集合。对于任意的a,bÎK，有f(a)=e，f(b)=e则f(a°b-1)=f(a)*f(b-1)=f(a)*f(b)-1=e*e=e则a°b-1ÎK，因此<K,°>是<G,°>的子群。5 证明当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。证明：必要性：设e是图G的割边，e关联的两个结点是a,b。如果e包含在G的一个回路中，那么除了边e=(a,b)外，a到b还有一条路存在，所以删去e后，a,b之间仍然连通，与e是割边

16、矛盾。充分性：如果边e不包含在G的回路中，则连接a,b只有边e。所以删除边e后，a,b不再连通，所以e是G的割边。6 设f是从A到B的一个函数，定义A上的关系R：aRb当且仅当f(a)=f(b)，证明：R是A上的等价关系。证明：a)自反性：对任意aÎA，f(a)=f(a)，所以aRa，即R是自反的。b)对称性：对任意a，bÎA，若aRb，即f(a)=f(b)，即f(b)=f(a)，故bRa，即R是对称的。c)传递性：对任意a，b，cÎA，若aRb，bRc，即f(a)=f(b)，f(b)=f(c)即f(a)=f(b) =f(c)，故aRc，即R是传递的。所以R是A上的等价关系。7 代数系统<I,+>是一个群，设B=x|x=5n,nÎI，证明：<B,+>是<I,+>的子群。证明：由题意知BÍI并且B非空，设"x,yÎB则有x,yÎI，且x=5n1, y=5n2(n1,n2