《离散数学考前综合复习资料大学》由会员分享，可在线阅读，更多相关《离散数学考前综合复习资料大学（8页珍藏版）》请在金锄头文库上搜索。
1、如果e包含在G的一个回路中，那么除了边e=(a,b)外，a到b还有一条路存在，所以删去e后，a,b之所以不是群；（2）+在I上是封闭的，可结合的，幺元是0，I中任意元素x的逆元为-x，所以试根据求得的最优树构造前缀码，并对二进制序列0100110110010001011译码。解：（1）见b)-1=e*e=e则ab-1K，因此是的子群。5证明当且仅当G的一条i j离散数学综合复习资料一、判断题1 A、B、 C是任意命题公式，如果 A C B C，一定有 A B。（ ）2设是一个代数系统，且集合 A 中元素的个数大于 1。如果该代数系统中存在幺元 e 和零元 ，则 e 。（ ）3 A、B、 C为任
2、意集合，已知 A B=A C，必须有 B=C。（ ）4 自然数集是可数的。（ ）5 命题联结词 ， ， 是最小联结词组。（ ）6 有理数集是可数的。（ ）7 交换群必是循环群。（ ）8 图 G的邻接矩阵 A， Al 中的 i 行 j 列表示结点 v 到 v 长度为 l 路的数目。（ ）二、解答题1求命题公式 (P Q)的主析取范式。2举出 A=a,b,c 上的二元关系 R和 S 满足：（ 1）R既不是自反的又不是反自反的，既是对称的又是反对称的；（2）S 既不是对称的又不是反对称的，是传递的。3以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。（ 1）f: N Q, f
3、(x) = 1/x（2）f: R R R R, f(x,y)=4判断下列代数系统是否是群，并说明理由：(1) ：实数集关于减法； (2) ： 整数集关于加法；5. 构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大 下界但没有最小元。d eb ca6. 画一个有欧拉回路， 但没有汉密尔顿回路的图。7. 将下列命题符号化c上的二元关系R和S满足：（1）R既不是自反的又不是反自反的，既是对称的又是反对称的；（2）S既不解：（1）R=,（2）S=,a不连通，故任一边均为G的割边。充分性：任取两个结点u,v，图G连通，则u,v之间有路存在。若u,v间9将下列命题符号化（1）除
4、非你走否则我留下。（PQ）（2）我们不能边看电视边看报。（PQ)）10000010100101001000001v1v2（ 1 ）如果张三和李四都不去，她就去。（ P（2 ）今天要么是晴天，要么是雨天。（P Q）8. 设 G=， V=V1,V2,V3,V4 的邻接矩阵：000A(G)=0（ 1 ）试画出该图。Q） R）v3v4V5（2）V2的入度 d-(V2) 和出度 d+(V2) 是多少？（3 ）利用邻接矩阵的性质求从 V1到 V2长度为 3 的路有几条？9. 将下列命题符号化（ 1 ）除非你走否则我留下。（2 ）我们不能边看电视边看报。10. 设集合 A有 m个元素， B有 n 个元素，则
5、 A到 B 的关系有多少个？ A到 B 的函数有多少 个？11. 设有一组权 3、4、13、5、6、12，（ 1 ）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。（2 ）设上述权值分别对应英文字母 b、d、e、g、o、y ，试根据求得的最优树构造前缀码， 并对二进制序列 0100110110010001011 译码。三、证明题1设 R,S 是 A上的等价关系， 证明 R S 也是 A上的等价关系。2设 f 和 g 都是群到的同态，令 H=x|x A， f(x)=g(x) ，义。（2）函数，双射，f-1(x,y)=判断下列代数系统是否是群，并说明理由：(1、y对应的前
6、缀码000，001，11，010，011，10。对二进制序列译码为goodbye。三和出度d+(V2)是多少？（3）利用邻接矩阵的性质求从V1到V2长度为3的路有几条？9.将下列命题符下页（2）将上面的最优树的每个分枝点引出的两条边，左侧边标0，右侧边标1，得到一个b、d、e、g、o试证： 是的子群。3当且仅当连通图的每条边均为割边时，该连通图才是一棵树。4f 是群到群的同态映射， e是 G中的幺元则， f 的同态核 K=x|x G且 f(x)=e构成的代数系统 是的子群。5证明当且仅当 G的一条边 e 不包含在 G的回路中时， e 才是 G的割边。6设 f 是从 A到 B 的一个函数，定义
7、A上的关系 R： aRb 当且仅当 f(a)=f(b) ，证明： R是 A上的等价关系。7代数系统 是一个群，设 B=x|x=5n,n I ，证明： 是 的子群。8连通图至少有一棵生成树、y，试根据求得的最优树构造前缀码，并对二进制序列0100110110010001011译码。三、证所以不是群；（2）+在I上是封闭的，可结合的，幺元是0，I中任意元素x的逆元为-x，所以都不去，她就去。（P（2）今天要么是晴天，要么是雨天。（PQ）8.设G=，V=V1,V加法；5.构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小离散数学综合复习资料答案一、判断题题号答
8、案1 2 3 4 5 6 7 8 二、解答题1、求命题公式 (P Q)的主析取范式。 解： (P Q) ( P Q) P Q2、 解：（ 1）R = ,（2）S=,3、以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。（ 1）f: N Q, f(x) = 1/x（2）f: R R R R, f(x,y)=解：（ 1 ）不是函数，在 x=0 时无定义。（2） 函数，双射， f-1(x,y)=4、判断下列代数系统是否是群，并说明理由：(1) ：实数集关于减法； (2) ：整数集关于加法；解：（ 1）+在 R上是封闭的，不可结合所以不是群；（2）+在 I 上是封闭的，可结合的
9、，幺元是0，I 中任意元素 x 的逆元为-x， 所以是群；5、构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大 下界但没有最小元。解：右图所示哈斯图表示一个偏序集，其中：子集 B=b ，c 有上界 d，e 但没有最小上界，同时子集 B=b ，c 有最大下界 a ，但没有最小元。6、画一个有欧拉回路，但没有汉密尔顿回路的图。)-1=g(a)g(b-1)=g(a*b-1)所以a*b-1H，所以是的子群。3RS，则R且S。因为R,S是等价关系，所以具有对称性，所以R(a)=f(b)，证明：R是A上的等价关系。证明：a)自反性：对任意aA，f(a)=f(a)，所以a明题1设
10、R,S是A上的等价关系，证明RS也是A上的等价关系。2设f和g都是群到解： 7、将下列命题符号化（ 1 ）如果张三和李四都不去，她就去。（ P（2 ）今天要么是晴天，要么是雨天。（P Q）8、A(G)=解：（ 1 ）如右上图0100010100010000000100010v1v2Q） R）v3v4V5（2）d-(V2)=2 ，d+(V2)=2（3 ）因为 a(3) =2，所以 V1到 V2长度为 3 的路有 2 条。 129将下列命题符号化（ 1 ）除非你走否则我留下。（ P Q）（2 ）我们不能边看电视边看报。（ （P Q) ）10设集合 A有 m个元素， B有 n 个元素，则 A到 B
11、的关系有多少个？ A到 B 的函数有多少 个？解： 1）A到 B 的关系有 2mn个。 2）A到 B 的函数有 nm个。11设有一组权 3、4、13、5、6、12，（ 1 ）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权） 。提矛盾，因此任意两个结点间恰有一条路，图G是树。4f是群到群的同态映射，e，y-1=-y，所以x+y-1=x+(-y)=5n1-5n2=5(n1-n2)B所以是代数系统是一个群，设B=x|x=5n,nI，证明：是的子群。证明：(x)=1/x（2）f:RRRR,f(x,y)=解：（1）不是函数，在x=0时无定（2 ）设上述权值分别对应英文字母 b、d
12、、e、g、o、y ，试根据求得的最优树构造前缀码， 并对二进制序列 0100110110010001011 译码。解：（ 1 ）见下页（2 ）将上面的最优树的每个分枝点引出的两条边，左侧边标 0，右侧边标 1，得到一个 b、 d、e、g、o、y 对应的前缀码000 ，001，11，010，011，10。对二进制序列译码为 goodbye 。440 125011121 y6ob d3 413e0 119g001157三、证明题1. 设 R,S 是 A上的等价关系，证明 R S 也是 A上的等价关系。 证明： a) 自反性：对任意 a A，因为 A, S，所以 R S，即 R S 具有自反性。b) 对称性：对任意 a,b A，如果有 R S，则 R且 S。因为 R,S 是等价关系，所以具有对称性，所以 R且
