离散数学（第五版）清华大学出版社第6章习题解答

离散数学（第五版）清华大学出版社第6章习题解答

6.1 A:⑨; B:⑨; C:④; D:⑥; E:③

分析 对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对给定运算的封闭性,具体方法已在5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法.

1°给定集合S和二元运算°,判定是否构成关群、独导点和群. 根据定义，判别时要涉及到以下条件的验证： 条件1 S关于 °运算封闭： 条件2 °运算满足结合集 条件3 °运算有幺元， 条件4 °?x∈S,x?1∈S.

其中关群判定只涉及条件1和2；独导点判定涉及条件1、2、和3；而群的判定则涉及到所有的四个条件。

2 ° 给定集合S和二元运算 °和 *，判定是否构成环,交换环,含幺环,整环,域.根据有关定义需要检验的条件有: 条件1 S构成交换群, 条件2 构成关群, 条件 3 * 对 °运算的分配律, 条件4 * 对运算满足交换律, 条件5 * 运算有幺元,

条件6 * 运算不含零因子——消去律， 条件7 |S|≥2,?x∈S,x≠0,有x?1∈S（对*运算）.

其中环的判定涉及条件1,2和3;交换环的判定涉及条件1,2,3和4;含幺环的判定涉及条件1,2,3和5;整环的判定涉及条件1-6;而域的判定则涉及全部7个条件. 3° 判定偏序集或代数系统是否构成格、分本配格、有补格和布尔格. 73

若为偏序集,首先验证?x,y∧y和x∨y是否属于 S.若满足条件则 S为格,且构成代数系统.若是代数系统且°和*运算满足交换律、结合律和吸收律，则构成格。

在此基础上作为分配格的充分必要条件是不含有与图6.3所示的格同构的子格。而有补格和布尔格的判定只要根据定义进行即可。 注意对于有限格，只要元素个数不是2的幂，则一定 不是布尔格。但元素个数恰为2n的有限格中只有唯一 的布尔格。

以本题为例具体的判定过程如下：

（1） 由n+n=2n?S1可知S1对+运算不封闭，根本不构成代数系统。 （2）由2*2=4?S2可知S2对*运算不封闭，也不构成代数系统。

（3）S3关于o,*运算封闭，构成代数系统。且S3关于模n加法o满足交换群的定义，关于模n乘法*满足关群的定义，且*对o有分配律。因而构成环。但当n=6时，有2*3=3*2=0.S6中含有零因子2和3，不是整环，也不是域。类似地分析可知，当n为合数时，Sn不是域，但n为素数时Sn构成域。 （4）S4是偏序集。对于小于等于关系≤,x∧y=min{x,y},x∨y=max{x,y}，显然有x∧y,x∨y∈S4，构成格。但S4不是有补格，2和3没有补元，也不是布尔代数。 （5）容易验证S5关于矩阵加法构成群。 6．2 A:②; B:③; C:⑦; D:⑩; E:⑨

分析 此处的G实际上是Z4.Zn关于模n加法构成群，但关于模n乘法只构成独导点，而不构成群，因为0没乘法逆元。是循环群。2是2阶元 ，1和3是4阶元。

如何求群G中元素的阶？如果|G|=n，则?x∈G,|x|是n的正因子。首先找 74

到n的正因子，并从小到大列出来，然后依次检查每相正因子r。使得xr =e的最小的正因子r就是x的阶。本题的|G|=44的正因子是1，2，4。由于 21=2≠0. 22=2⊕2=0.

所以，|2|=2。类似地有

31=,32=3⊕3=2,33=3⊕3=1,34=3⊕3⊕3⊕3=0, 而|3=| 3

6.3 2 A:②; B:④; C:⑤; D:⑦; E:⑧

分析 （1）根据布尔代数定义可知U和I运算适合交换律、结合律、幂等律、分配律、D·M律等，适合消去律。?x∈L,0VX=X,xV0=x,xV1=1,1Vx=1，所以，0是V运算的幺元，1是V运算的零元。由于在布尔代数的表示中，0和1是作为代数常数列出来的，所以，最小的子布尔代数应包含所有的代数常数。经验证{0,1}恰构成子布尔代数，因而是最小的子布尔代数。

（2）表达式的等价式与对偶式是两个要领,应加以区别.容易看出,由吸收律、交换律、分配律有

(a∧b)∨(a∧b∧c)∨(b∧c) =(a∧b)∨(b∧c) 吸收集 =(b∧a)∨(b∧c) 交换集 =b∧(a∧c) 分配律

这说明该表达式与b∧(a∨c)是等价的，而其他两个表达式都不满足要求。 6.4 易证Z对 °运算是封闭的，且对任意x,y,z∈Z有 (xoy)oz=(x+y?2)+z?2=x+y+x?4,

xo(yoz)=xo(y+z?2)=x+(y+z?2)?2=x+y+z?4, 75

结合律成立。2是 °运算的幺元。?x∈Z,4?x是x关于 °运算的逆元。综合上述，构成群。

6.5 根据矩阵乘法可以得到G的运算表如下： · a b c d a a b c d b b a d c c c d b a d d c a b

由运算表可以看出a是幺元。又由 b2=a,c4=cc2 2=b2=a。d4 =d2d2=b2=a.

知道|b|=2,|c|=|d|=4.当|G|与G中元素x的阶相等时，有G=。因此G是4阶循环群。

G的子群有{a},{a,b},G三个。令S={{a},{a,b},G}，则的哈斯图如图6.4所

示。

分析 这里对怎样求一个循环群的生成元和子群做一点说明。

1 °若G=是无限循环群，那么G只有两个生成元，即a和a?1。G的子群有元数多个，它们分别由ak生成。这里的k可以是0，1…。将ak生成子群的元素列出来就是

={e,ak,a?k,a2k,a?2k,L},

该子群也是一个无限循环群。不难证明当k≠l时，子群{ak}≠。

例如，G=是n阶循环群，那么G={e,a,L,an?1}。G的生成元有φ(n)个，这里的φ(n)是欧拉图函数，即小于等于n且与n互素的正整数个数。求生成元的方法是：先找到所有有小于等于n且与n互素的正整数.对于每个这样的正整数r,ar就是G的d阶子群.

以本题为例.|D|=4,与 4 互素的数是 1 和 3.因此G=的生成元是 76

c1=c,c3=d.再考虑子群.4的正因子是1,2,4所以,G的子群有3个,即 4 14

==={a}. 1阶子群 4 22

=={b,a}. 2阶子群 4

==G. 4阶子群

根据包含关系不难得到图6.4所示的哈斯图.

6.6 Z[i]对普通加法和乘法是封闭的,且加法满足交换律,结合律,乘法满足结合律,第六法对加法满足分配律.又知道加法的幺元是 0,?a+bi∈Z[i],?a?bi是a+bi的负元.从而Z[i]关于加法和乘法构成环.容易看出这是一个整环,但不是域. 6.7 (1) 不是格,(2),(3)和(4)都是格. 6.8 任取x,y∈S,由S的性质有 x⊕y=(x∧y)∨(x''∧y)∈S,

S 关于⊕是封闭的,构成代数系统.容易验证⊕运算满足结合律. 幺元是0,因为?x∈S有

x⊕0=(x∧0)∨(x''∧0)=(x∧1)∨(x'∧0)=x∨0=x. 同理有0⊕x=x.且?x∈S有 x⊕x=(x∧x)∨(x''∧x)=0∨0=0. 6.9 (1) X ={1,4,5}

(2) ={B,B2}={1,4,5},?}.

分析 设G为群,a,b∈G.群方程ax=b在G中有唯一解x=a?1b.类似地,群方程ya=b在G中也有唯一解y=ba?1.代入本题有 X ={1,3}?1⊕{3,4,5}={1,3}⊕{3,4,5}={1,4,5} 由于对任何B∈P(A)有B⊕B=?,因而有 77

n ?B n为奇数 B =? ?? n为偶数

尽管中包含了B的所有幂,但只有两个结果,即B和?. 6.10 (1) σ =(124)(356),τ=(1634)(25). (2) στ=(15423)(356),τσ=(15462), στσ?1=(15423)(563)(421)=(1256)(34).

分析 为了求出σ的轮换表示,先任选一个元素,比如说 1,从上述表示式中找到σ(1).如果σ(1)=1,则第一个轮换就找到了,是(1).如果σ(1)=i1,i1≠1,接下去找σ(i1)=i2.继续这一过程,直到某个ik满足σ(ik)=1为止.通过这样的挑选,从{1,2,L,n} 中 选 出 了 一 个 序 列 : 1,i1,i2,L,ik, 其 中 的 元 素 满 足σ(1)=i1,σ(i1)=i2,L,σ(ik )=ik,σ(ik)=1.这就是从σ中中解出来的第一个轮换 ?1

(1,i1,i2Lik).如果该轮换包含了{1,2,L,n}中的所有元素,那么分解结否,并且有σ=(1,i1,i2Lik);否则任取{1,2,L,n}中没有剩下的元素为止.

以本题的σ为例.由σ的置换表示知道.σ(1)=2,σ(2)=4,σ(4)=4,σ(4)=1,从而得到第一个轮换(124).接着从{3,5,6}中选取 3,继续这一过程,得到σ(3)=6,σ(6)=5,σ(5)=3,这