离散数学试卷（十四） 一、 填空10%（每小题2分） 1、<P(S,U,n,~>:2、B,Y:3、+书0[山2☒是： 4、5n-:5.9 [1[)[2)o 220四 二、选择10%（每小题2分） 题目12345 答案C B D B D 三、判断10%（每小题2分） 愿目12345 答案NYY NY 四、证明46% 1、(10分)证明： (1)Va,b,c∈A,若a*b=a*c则b=c 事实上：a*b=a*c.a使à*(a*b)=a*(a*c) (a*a)+b=(a*a)*c.e*b=e*c 即：b=c (2)e是<A,>之么元。 事实上：由于e是左么元，现证e是右么元。 reA,x*e∈A,3歌使r*(x*e)=(住*x)*e=e*e=e=*x 由(1)即x*e=x,.e为右幺元 (3)xeA,则x∈A 事实上：x∈A(x*)*x=x*(代*x)=x*e=x=e*x x*文=e故有歌*x=x*元=ex有逆元 由(2)，(3)知：<A,>为群。 2、(10分)证明：
离散数学试卷（十四） 92 一、 填空 10%（每小题 2 分） 1、<P (S), ,, ~ >；2、β，γ；3、 是； 4、 ( 1) 2 1 n n − ；5、9 二、 选择 10%（每小题 2 分） 题目 1 2 3 4 5 答案 C B D B D 三、 判断 10%（每小题 2 分） 题目 1 2 3 4 5 答案 N Y Y N Y 四、 证明 46% 1、（10 分）证明： （1） a,b,c A,若a*b = a*c 则b = c b c a a b a a c e b e c a b a c a a a b a a c = = = = = : ( ˆ * ) * ( ˆ * ) * , * * : * * ˆ ˆ *( * ) ˆ *( * ) 即 事实上 使 (2) e 是<A，*>之幺元。 事实上：由于 e 是左幺元，现证 e 是右幺元。 由 即 为右幺元 使 x e x e x A x e A x x x e x x e e e e x x = = = = = (1) * , , * , ˆ ˆ *( * ) (ˆ * ) * * ˆ * （3） x A x A −1 ,则 x x e x x x x e x x x A x x x x x x x e x e x * ˆ ˆ * * ˆ ˆ : ( * ˆ) * *(ˆ * ) * * 故有 有逆元 事实上 = = = = = = = 由（2），（3）知：<A,*>为群。 2、（10 分）证明： +3 [0] [1] [2] [0] [0] [1] [2] [1] [1] [2] [0] [2] [2] [0] [1]
离散数学试卷（十四） 设<G,>是循环群，G-(a,设<S,是<G,>的子群。且S≠{，S≠G,则存在最小正整数m,使 得：a"∈S,对任意a∈S,必有1=m+上0≤r<m,t>0, 故：d=d-tm=d*am=d*(a")'∈S即：d=ad*(a"yeS 所以a∈S但m是使a"∈S的最小正整数，且0≤r<m,所以r-0即：ad=(a")y 这说明S中任意元素是a"的乘幂。所以<G,>是以a为生成元的循环群。 3、(8分)证明： 对集合aH和bH,只有下列两种情况： (1)aHbH≠Φ：(2)aH∩bH=Φ 对于aHOb≠中，则至少存在h,h,∈H,使得ah=bh,即有a=bM,h,这时任意 ah∈aH,有ah=bh,hh∈bH,故有aH bH 同理可证：bH aH所以aH=bH 4、(8分)证明： 反证法：如果<A,+,·>,是整环，且有三个以上元素，则存在a∈A,a≠0，a≠1且a·a=a 即有：a≠0，a-l≠0但a-(a-)=a~a-a=a-a=0这与整环中无零因子条件矛盾。因 此<A,+,·>不可能是整环。 5、(10分)证明： 因为G=<V,ED不连通，设其连通分支是G),.,GW)(k≥2)，u,veV,则有两种情 况： (1)u,V,分别属于两个不同结点子集V.V,由于GV),GV)是两连通分支，故(u,)在不 G中，故u,v在G中连通。 (2)u,y,属于同一个结点子集V,可在另一结点子集V,中任取一点w,故(u,w(w,v)均 在G中，故邻接边(u,w)(w,v)组成的路连接结点u和v,即u,v在G中也是连通的。 五、布尔表达式8% 函数表为： 93
离散数学试卷（十四） 93 设<G,*>是循环群,G=(a)，设<S,*>是<G,*>的子群。且 S {e},S G ，则存在最小正整数 m，使 得： a S m ，对任意 a S l ，必有 l = tm + r, 0 r m, t 0 ， 故： a a a a a a S r l tm l tm l m t = = = − − − * *( ) 即： a a a S l r m t = *( ) 所以 a S r 但 m 是使 a S m 的最小正整数，且 0 r m ，所以 r=0 即： l m t a = (a ) 这说明 S 中任意元素是 m a 的乘幂。 所以<G,*>是以 m a 为生成元的循环群。 3、（8 分）证明： 对集合 aH 和bH ，只有下列两种情况： （1） aH bH ； （2） aH bH = 对于 aH bH ，则至少存在 h1 ,h2 H ，使得 ah1 = bh2 ，即有 1 2 1 − a = bh h ，这时任意 ahaH ，有 ah = bh h h bH −1 2 1 ，故有 aH bH 同理可证： bH aH 所以 aH = bH 4、（8 分）证明： 反证法：如果<A，+，·>，是整环，且有三个以上元素，则存在 a A,a ,a 1且 a a = a 即有： a ,a −1 但a (a −1) = a a − a = a − a = 这与整环中无零因子条件矛盾。因 此<A，+，·>不可能是整环。 5、（10 分）证明： 因为 G=< V，E>不连通，设其连通分支是 ( ), , ( ) ( 2) G V1 G Vk k ，u,v V ，则有两种情 况： （1） u , v，分别属于两个不同结点子集 Vi，Vj，由于 G(Vi) , G(Vj)是两连通分支，故(u , v)在不 G 中，故 u , v 在 G 中连通。 （2） u ,v ，属于同一个结点子集 Vi，可在另一结点子集 Vj 中任取一点 w，故(u , w),(w , v )均 在 G 中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点 u 和 v，即 u , v 在 G 中也是连通的。 五、布尔表达式 8% 函数表为：
离散数学试卷（十四） X2 E(x,x2,x3) 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 、0 1 0 1 1 1 1 0 1 1 1 析取范式：E(,名，)=（人A,V()V(任人） V(xx3)V(Xx) 合取范式：E(x,x2,x)=(VxV2x)A(xVx2Vx)A(XIVX2 Vx) 六、树的应用16% 1、(6分)解： X 绩高整数数每所 以它是欧拉图。 2、(10分)解 13 根据权数构造最优二叉树：
离散数学试卷（十四） 94 1 x 2 x 3 x ( , , ) 1 2 3 E x x x 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 析取范式： ( ) ( ) ( , , ) ( ) ( ) ( ) 1 2 3 3 1 2 3 2 2 3 1 1 3 1 2 1 2 3 x x x x x x E x x x x x x x x x x x x = 合取范式： ( , , ) ( ) ( ) ( ) 2 3 1 3 2 1 2 3 1 2 3 1 E x x x = x x x x x x x x x 六、 树的应用 16% 1、（6 分）解： 2、（10 分）解： 根据权数构造最优二叉树：
离散数学试卷（十四） 传输它们的最佳前缀码如上图所示，happy new year的编码信息为： 10011010101010011101110100001111011000 附：最优二叉树求解过程如下： 5 67 8 10 10 12 15 11 7 10 10 12 15 11 15 10 10 12 6 11 15 20 12 15 15 20 23 15 20 23 30 43 30 73 95
离散数学试卷（十四） 95 传输它们的最佳前缀码如上图所示，happy new year 的编码信息为： 10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下：