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

1、精品文档离散数学综合复习资料一、判断题）B。（ B C，一定有A 1 A 、B、C是任意命题公式，如果 A C。如果该代数系统中存在幺元中元素的个数大于 1*>是一个代数系统， 且集合 A2设<A， ）。（ e 和零元 ，则 e）。（ B=A C，必须有 B=C、3 AB、 C为任意集合，已知 A）（ 4 自然数集是可数的。 ）（ ， 是最小联结词组。 5 命题联结词 ， ）（ 6 有理数集是可数的。） 交换群必是循环群。（7l l）（路的数目。 行 j 列表示结点 v到 v，8图 G的邻接矩阵 AA长度为中的 i ji二、解答题 的主析取范式。(P Q)1求命题公式满足：和 SA

2、=a,b,c2 举出上的二元关系 R 既不是自反的又不是反自反的，既是对称的又是反对称的； ）R（ 1 S）既不是对称的又不是反对称的，是传递的。（2 3以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。 Q, f(x) = 1/xf: N（1）R, f(x,y)=<y+1,x+1>R R （2） f: R判断下列代数系统是否是群，并说明理由： 4 ：整数集关于加法；，+>(1) <R，-> ：实数集关于减法； (2) <I 构造一非空偏序集， 它存在一子集有上界， 但没有最小上界。 它还有一子集，存在最大 5. 下界但没有最小元。

3、e dcba6. 画一个有欧拉回路， 但没有汉密尔顿回路的图。 7. 将下列命题符号化 精品文档精品文档 R ）Q） ）如果张三和李四都不去，她就去。 （1（ P Q）（P （2）今天要么是晴天， 要么是雨天。 V=V1,V2,V3,V4 的邻接矩阵： 设 G=<V,E>，8. 0 100010100 v1v400 100A(G)=100 00v201000V5v3）试画出该图。（ 1+- d2（） V2 的入度 d(V2) 和出度 (V2) 是多少？ 长度为 3 的路有几条？ V1（3）利用邻接矩阵的性质求从到 V2 9. 将下列命题符号化 1 ）我们不能边看电视边看报。）除非你

4、走否则我留下。 （2（的函数有多少有有设集合10.Am个元素，BnB到到个元素，则 AB的关系有多少个？ A 个？ 5134 、，、126设有一组权 11.3 ）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）（1。，试根据求得的最优树构造前缀码， db2（）设上述权值分别对应英文字母、o、yge、并对二进制序列译码。三、证明题1设 R,S 是 A 上的等价关系，证明R S 也是 A 上的等价关系。*> 的同态，令 H=x|xA，f(x)=g(x)， 2 设 f 和 g 都是群 <A，*> 到<B， 精品文档精品文档试证： <H，*>

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

6、;I,+> 是一个群，设 B=x|x=5n,nI ，证明：<B,+>是<I,+> 的子群。8连通图至少有一棵生成树精品文档精品文档离散数学综合复习资料答案一、判断题题 12345678答案二、解答题的主析取范式。1、求命题公式(PQ)Q PQ)PQ)解： (P(R =<a,a>,<b,b>1）（2、 解： S=<a,a>,<b,b><a,b>,<b,a><a,c>）（2 3、以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。 Q, f(x) = 1/x（ 1

7、） f: NR, f(x,y)=<y+1,x+1>R f: R ） R （2 1 ）不是函数，在x=0 时无定义。（解： -1 (x,y)=<y-1,x-1> f）（2 函数，双射，、判断下列代数系统是否是群，并说明理由： 4 (1) <R，-> ：整数集关于加法；，：实数集关于减法； (2) <I+> 上是封闭的，不可结合 R1 解：（） +在 <R 所以，不是群； -> 0I 在上是封闭的，可结合的，幺元是， I 中任意元素 -x 的逆元为， x+2（） <I 所以，是群；+>、构造一非空偏序集， 它存在一子集有上界，

8、 但没有最小上界。它还有一子集，存在最大 5 下界但没有最小元。 解：右图所示哈斯图表示一个偏序集，其中： edcB=b 子集，有上界，但没有最小上界，同时子集 B=b， c 有最大下界 a，但没有最小元。6、画一个有欧拉回路，但没有汉密尔顿回路的图。精品文档精品文档解： 7 、将下列命题符号化 ） R（ P Q（1）如果张三和李四都不去，她就去。 Q）2（）今天要么是晴天，要么是雨天。 （ P 8 、0010 0v40 v110100 0010A(G)=10 000v200010V5v3（解： 1）如右上图 +- (V2)=22（） d(V2)=2 ， d(3) 长度为到 a3（）因为，所以

9、 =2V1V23的路有 2 条。 129 将下列命题符号化 ）Q）除非你走否则我留下。（ P （1 ） （ P Q)（2）我们不能边看电视边看报。 （的函数有多少到 BB的关系有多少个？个元素，则 m 个元素， B 有 nA 到 A10设集合有 A 个？ mmn 个。到 B 的函数有 n2 到 1） AB 的关系有 2 个。 ）A 解： ， 6、125134311设有一组权、 。1（）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）精品文档精品文档（ 2）设上述权值分别对应英文字母 b、d、 e、 g、o、 y，试根据求得的最优树构造前缀码，并对二进制序列译码。解：（

10、1）见下页（ 2）将上面的最优树的每个分枝点引出的两条边，左侧边标 0，右侧边标 1，得到一个 b、 d、e、g、o、y 对应的前缀码 000 ，001，11，010，011， 10 。对二进制序列译码为 goodbye。44012519010111712130101ye43 56bdgo三、证明题 也是 上的等价关系，证明是设 1.R,SARSA上的等价关系。 ，因为 自反性：对任意 a)aA<a,a>A,<a,a>S ，证明： 所以 <a,a>R RS具有自反性。，即 Sb)对称性：对任意 a,b A ，如果有 <a,b> R S，则 <

11、;a,b> R 且<a,b> S。因为 R,S 是等价关系，所以具有对称性，所以 <b,a>R且<b,a>S。所以 <b,a>R S ，即 R S 具有对称性。c) 传递性：对任意 a,b,cA，若有 <a,b>,<b,c>R SS<a,b>,<b,c>则且 R<a,b>,<b,c>精品文档精品文档则因为 R,S 是等价关系，所以具有传递性，所以 <a,c> R且<a,c> S所以 <a, c>R S，即 R S 具有传递性。所以 R

12、S 是 A 上的等价关系。* ，到 <A， *><B 设 H=x|x> 的同态，令 A， f(x)=g(x)， 2.f 和 g 都是群 的子群。，*><A 试证： <H，*> 是 AH由定义知 证明* ' 是（ >的幺元， 1）设 e 是 <A,*> 的幺元， e<B,* ， >的同态，则 f(e)=g(e)=e*> 到<B 都是因为 f,g<A ，所以 ' ，所以 e H H ；，有 f(a)=g(a) ，f(b)=g(b) ，a,b （2 ） H-1-1-1-1 )因为 ) 且

13、g(b)f,g都是同态映射，所以 f(b)=f(b=g(b* -1-1-1-1-1 )=f(a)f(b)=f(a)所以 f(b)= g(a) g(b)f(a* b=g(a) g(b)=g(a*-1 )b-1 <H,*> 所以 a* b H，所以是 <A,*> 的子群。 3 当且仅当连通图的每条边均为割边时，该连通图才是一棵树。 4 是树，则删去任一边后就不连通，故任一边均为证明：必要性：如果图 GG的割边。间有两条路，则G任取两个结点充分性：u,v ，图连通， u,vu,v之间有路存在。若则可组成一个回路， 则删除回路上任一条边后不改变图的连通性，这样该回路上的边都不是

14、割边，与前提矛盾，因此任意两个结点间恰有一条路，图G是树。5 f 是群 <G,° >到群 <G',*> 的同态映射， e' 是 G'中的幺元则， f 的同态核 K=x|x G且 f(x)=e' 构成的代数系统 <K,° >是<G,°>的子群。精品文档精品文档证明：由定义可知K G，设 G中的幺元为 e，则有空集合。对于任意的 a,b K，有 f(a)=e'，f(b)=e'-1-1-1=e'*e')=f(a)*f(b)=e则 f(a ° b

15、9;)=f(a)*f(bf(e)=e'，所以 e A，即A 为非-1K，因此 <K,°>是 b<G,° >的子群。°则 a6 证明当且仅当 G的一条边 e不包含在 G的回路中时， e 才是 G的割边。证明：必要性：设e 是图 G的割边， e 关联的两个结点是a,b 。如果 e 包含在 G 的一个回路中，那么除了边e=(a,b) 外， a 到 b 还有一条路存在，所以删去 e 后， a,b 之间仍然连通，与e 是割边矛盾。充分性：如果边 e 不包含在 G的回路中，则连接 a,b 只有边 e。所以删除边 e 后，a,b 不再连通，所以e

16、 是 G的割边。7 设 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 上的等价关系。8 代数系统 <I,+> 是一个群，设 B=x|x=5n,nI ，证明：<B,+>是<I,+> 的子群。证明：由题意知B I 并且 B 非空，设 x,yB 则有 x,yI ，且 x=5n1, y=5n2(n1,n2I) ，-1-1 =x+(-y)= 5n1-5n