《2022年离散数学考前综合复习资料 .pdf》由会员分享，可在线阅读，更多相关《2022年离散数学考前综合复习资料 .pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学综合复习资料一、判断题1 A、B、C是任意命题公式，如果A CB C，一定有 AB。 （ ）2设是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e 和零元 ，则 e。 （ ）3 A、B、C为任意集合，已知A B=A C，必须有 B=C 。 （ ）4 自然数集是可数的。（ ）5 命题联结词 ， ， 是最小联结词组。（ ）6 有理数集是可数的。（ ）7 交换群必是循环群。（ ）8 图 G的邻接矩阵 A，Al中的 i 行 j 列表示结点 vi到 vj长度为 l 路的数目。（ ）二、解答题1求命题公式(PQ)的主析取范式。2举出 A=a,b,c 上的二元关系 R和 S满足：
2、（1）R既不是自反的又不是反自反的，既是对称的又是反对称的；（2）S既不是对称的又不是反对称的，是传递的。3以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。（1） f: NQ, f(x) = 1/x （2） f: RRR R, f(x,y)= 4判断下列代数系统是否是群，并说明理由：(1) ：实数集关于减法； (2) ：整数集关于加法；5. 构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。6. 画一个有欧拉回路，但没有汉密尔顿回路的图。7. 将下列命题符号化d be c a 精选学习资料 - - - - - - - - -
3、 名师归纳总结 - - - - - - -第 1 页，共 8 页（1）如果张三和李四都不去，她就去。 （ （PQ ）R）（2）今天要么是晴天，要么是雨天。 （P Q ）8. 设 G= ，V=V1,V2,V3,V4 的邻接矩阵：（1）试画出该图。（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、1
4、2，（1）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。（2）设上述权值分别对应英文字母b、d、e、g、o、y，试根据求得的最优树构造前缀码，并对二进制序列0100110110010001011译码。三、证明题1设 R,S是 A上的等价关系，证明R S也是 A上的等价关系。2设 f 和 g都是群 到的同态，令 H=x|xA，f(x)=g(x)，0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 A(G)= v1 v2 v3 v4 V5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -
5、- -第 2 页，共 8 页试证： 是的子群。3当且仅当连通图的每条边均为割边时，该连通图才是一棵树。4f 是群到群 的同态映射， e是 G 中的幺元则， f 的同态核 K=x|xG且f(x)=e 构成的代数系统 是的子群。5证明当且仅当 G的一条边 e 不包含在 G的回路中时， e 才是 G的割边。6设 f 是从 A到 B的一个函数，定义 A上的关系 R ：aRb当且仅当 f(a)=f(b)，证明：R是A上的等价关系。7代数系统 是一个群，设 B=x|x=5n,nI ，证明： 是 的子群。8连通图至少有一棵生成树精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
6、- - -第 3 页，共 8 页离散数学综合复习资料答案一、判断题题号1 2 3 4 5 6 7 8 答案二、解答题1、求命题公式(PQ)的主析取范式。解：(PQ)(P Q)PQ 2、 解： （1）R = , （2） S=, 3、以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。（1） f: NQ, f(x) = 1/x （2） f: RRR R, f(x,y)= 解： （1）不是函数，在x=0时无定义。（2） 函数，双射， f-1(x,y)= 4、判断下列代数系统是否是群，并说明理由：(1) ：实数集关于减法； (2) ：整数集关于加法；解： （1）+在 R上是封闭的
7、，不可结合所以不是群；（2）+在 I 上是封闭的，可结合的，幺元是0，I 中任意元素 x 的逆元为 -x ，所以是群；5、构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。解：右图所示哈斯图表示一个偏序集，其中：子集 B=b，c 有上界 d，e 但没有最小上界，同时子集 B=b，c 有最大下界 a，但没有最小元。6、画一个有欧拉回路，但没有汉密尔顿回路的图。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页解：7、将下列命题符号化（1）如果张三和李四都不去，她就去。 （ （PQ ）R）（2
8、）今天要么是晴天，要么是雨天。 （P Q ）8、解： （1）如右上图（2）d-(V2)=2，d+(V2)=2 （3）因为 a(3)12=2，所以 V1到 V2长度为 3 的路有 2 条。9将下列命题符号化（1）除非你走否则我留下。 （PQ ）（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）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。0 1 0 0 0 1
9、0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 A(G)= v1 v2 v3 v4 V5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页（2）设上述权值分别对应英文字母b、d、e、g、o、y，试根据求得的最优树构造前缀码，并对二进制序列0100110110010001011译码。解： （1）见下页（2）将上面的最优树的每个分枝点引出的两条边，左侧边标0，右侧边标 1，得到一个 b、d、e、g、o、y 对应的前缀码 000，001，11，010，011，10。对二进制序列译码为goodbye。三、证明题
10、1. 设 R,S 是 A上的等价关系，证明R S也是 A上的等价关系。证明： a) 自反性：对任意 a A，因为 A,S，所以R S，即 R S具有自反性。b)对称性：对任意a,bA，如果有 R S，则R且S。因为 R,S 是等价关系，所以具有对称性，所以R且S。所以R S，即 R S具有对称性。c) 传递性：对任意a,b,cA，若有,R S 则,R且,S 则因为 R,S是等价关系，所以具有传递性，3 4 5 6 7 11 19 12 13 25 44 0 1 0 1 0 1 0 1 0 1 y e b d g o 精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
11、 - - -第 6 页，共 8 页所以R且S 所以R S，即 R S具有传递性。所以 R S是 A上的等价关系。2. 设 f 和 g 都是群 到的同态，令 H=x|xA，f(x)=g(x)，试证： 是的子群。证明 由定义知 H A （1）设 e 是 的幺元， e是的幺元，因为 f,g都是到的同态，则f(e)=g(e)=e，所以 e H，所以H；（2）a,bH，有 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
12、(a) *g(b-1)=g(a* b-1) 所以 a* b-1H，所以 是 的子群。3当且仅当连通图的每条边均为割边时，该连通图才是一棵树。证明：必要性：如果图G是树，则删去任一边后就不连通，故任一边均为G的割边。充分性：任取两个结点 u,v ，图 G连通，则 u,v 之间有路存在。 若 u,v 间有两条路，则可组成一个回路，则删除回路上任一条边后不改变图的连通性，这样该回路上的边都不是割边，与前提矛盾，因此任意两个结点间恰有一条路，图G是树。4f 是群到群 的同态映射， e是 G 中的幺元则， f 的同态核 K=x|xG且 f(x)=e 构成的代数系统 是的子群。证明：由定义可知K G ，设
13、 G中的幺元为 e，则有 f(e)=e ，所以 e A，即 A为非空集合。对于任意的 a,bK，有 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-1K，因此是的子群。5证明当且仅当 G的一条边 e 不包含在 G的回路中时， e 才是 G的割边。证明：必要性：设e 是图 G的割边， e 关联的两个结点是a,b 。如果 e 包含在 G的一个回路中，那么除了边e=(a,b) 外，a 到 b还有一条路存精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页在，所以删去
14、e 后，a,b 之间仍然连通，与 e 是割边矛盾。充分性：如果边 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，cA，若 aRb ，bRc，即 f(a)=f(b)，f(b
15、)=f(c) 即 f(a)=f(b) =f(c)，故 aRc，即 R是传递的。所以 R是 A上的等价关系。7代数系统 是一个群，设 B=x|x=5n,nI ，证明： 是 的子群。证明：由题意知B I 并且 B非空，设 x,yB则有 x,yI ，且 x=5n1, y=5n2(n1,n2I) ，在 ，y-1= -y ，所以 x+y-1=x+(-y)= 5n1-5n2=5(n1-n2) B 所以是 的子群。8连通图至少有一棵生成树证明：设连通图G没有回路，则 G本身就是一棵生成树。若 G至少有一个回路，删去G的回路上的一条边，得到图G1 ，它仍是连通的并与G有同样的结点集。若 G1没有回路，则 G1 就是生成树。若 G1仍有回路，再删去回路上的一条边，重复上述步骤，直到得到一个连通图H ，它没有回路，但与G有相同的结点集，因此H是 G的生成树。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页