离散数学(第五版)清华大学出版社第6章习题解答6.1 A:⑨; B:⑨; C:④; D:⑥; E:③分析对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对给定运算的封闭性,具体方法已在 5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法.1°给定集合S和二元运算°,判定<S, °>是否构成关群、独导点和群.根据定义,判别时要涉及到以下条件的验证:条件1 S关于°运算封闭:条件2 °运算满足结合集条件3 °运算有幺元,条件4 °?x∈S,x-1∈S.其中关群判定只涉及条件1和2;独导点判定涉及条件1、2、和3;而群的判定则涉及到所有的四个条件。
, *>是否构成环,交换环,含幺环,整环, 2 °给定集合S和二元运算°和*,判定<S, °域.根据有关定义需要检验的条件有:条件1 <S, °>S构成交换群,条件2 <S, *> 构成关群,条件 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°判定偏序集<S,≤>或代数系统<S,o,*>是否构成格、分本配格、有补格和布尔格.73若<S,≤>为偏序集,首先验证?x,y∧y和x∨y是否属于S.若满足条件则S为格,且<S,∨,∧>构成代数系统.若<S,o,*>是代数系统且°和*运算满足交换律、结合律和吸收律,则<S,o,*>构成格。
在此基础上作为分配格的充分必要条件是不含有与图 6.3所示的格同构的子格。
而有补格和布尔格的判定只要根据定义进行即可。
注意对于有限格,只要元素个数不是2的幂,则一定不是布尔格。
但元素个数恰为2n的有限格中只有唯一的布尔格。
以本题为例具体的判定过程如下:(1)由n+n=2n?S1可知S1对+运算不封闭,根本不构成代数系统。
(2)由2*2=4?S2可知S2对*运算不封闭,也不构成代数系统。
(3)S3关于o,*运算封闭,构成代数系统。
且S3关于模n加法o满足交换群的定义,关于模n乘法*满足关群的定义,且*对o有分配律。
因而<S3,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没乘法逆元。
<G,⊕>是循环群。
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=| 36.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运算的零元。
由于在布尔代数的表示<L,∧,∨,',0,1>中,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关于°运算的逆元。
综合上述,<Z,°>构成群。
6.5 根据矩阵乘法可以得到G的运算表如下:· a b c da abc db b a d cc cd b ad 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=<x>。
因此G是4阶循环群。
G的子群有{a},{a,b},G三个。
令S={{a},{a,b},G},则<S,?>的哈斯图如图 6.4所示。
分析这里对怎样求一个循环群的生成元和子群做一点说明。
1 °若G=<a>是无限循环群,那么G只有两个生成元,即a和a-1。
G的子群有元数多个,它们分别由ak生成。
这里的k可以是0,1…。
将ak生成子群的元素列出来就是<ak >={e,ak,a-k,a2k,a-2k,L},该子群也是一个无限循环群。
不难证明当k≠l时,子群{ak}≠<al >。
例如,G=<a>是n阶循环群,那么G={e,a,L,an-1}。
G的生成元有φ(n)个,这里的φ(n)是欧拉图函数,即小于等于n且与n互素的正整数个数。
求生成元的方法是:先找到所有有小于等于n且与n互素的正整数.对于每个这样的正整数r,ar 就是G的d阶子群.以本题为例.|D|=4,与 4 互素的数是 1 和 3.因此G=<c>的生成元是76c1=c,c3=d.再考虑子群.4的正因子是1,2,4所以,G的子群有3个,即414<c >=<c >=<a>={a}. 1阶子群422<c >=<c >={b,a}. 2阶子群4<c1 >=<c>=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 关于⊕是封闭的,构成代数系统<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>={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=?,因而有77n ?B n为奇数B =???n为偶数尽管<B>中包含了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, 其中的元素满足)=ik,σ(ik)=1.这就是从σ中中解出来的第一个轮换σ(1)=i1,σ(i1)=i2,L,σ(ik-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,就是第二个轮换(365).所有的元素都出现在轮换之中,分解结束,并且σ=(124)(365).在求置换σ 的轮换表示时可将表示式中的 1 轮换省略.例如,σ=(13)(2)(46)(5)中的(2)和(5)都是1-轮换,可将σ简记为(13)(46).此外要说明的是表示式中的轮换是不相交的,即同一个元素不能出现在两个轮换之中.如果交换了轮换的次序,或者选择了轮换中不同的元素作为首元素而保持顺序不变,那么所得的轮换表示是相同的.例如, σ=(124)(365)也可以写作σ=(365)(124)或σ=(124)(365)等.怎样求στ或σ-1,τ-1呢?根据复合函数的定义,只需求给定n 元置换σ和τ,78στ(n)就可以得到στ的置换表示或轮换表示.以本题为出στ(1), στ(2),…,类似地有στ(2)=3,στ(3)=1,στ(4)=2,στ(5)=4,例,στ(1)=σ(τ(1))=σ(6)=5.逆的计算比乘法简单.设σ=ττ 化简为στ=(15423).从而得到στ=(15423)(6),στ(6)=6,其中的τ 若为Lτ 为σ的轮换表示式,那么σ-1=τ-1,Lτ-1τ-1,则1 2kk2 1j轮换(i,i Li) ,则有τ-1=(iLii),j=1,2,L,k. 例如, σ=(124)(365) ,1 2 lj1 2lσ-1=(563)(421).从而στσ-1=(στ)σ-1=(15423)(563)(421).而στσ-1(1)=στ(4)=2,,στσ-1(2)=στ(1)=5,στσ-1(3)=στ(5)=4,στσ-1(4)=στ(2)=3,στσ-1(5)=στ(6)=6,στσ-1(6)=στ(3)=1,的计算中有στ(6)出现.观察到στ的表示在στσ-1=(5)因此,得到στσ-1=(1256)(34).式(15423)中不含有6,这就意味着στ(6)=(6).6.11 (1) 是同态映射. 当G={e}时为单同态,满同态和同构.而当G不是平凡群时,?既不是单同态,也不是满同态.(2) 是同态映射,且为单同态,不是满同态.(3) 是同态映射,也是单同态和满同态.6.12 (1) 哈斯图如图 6.5 所示.(2) 可以构成布尔代数.?x,y∈A,x∨y是x与y的最小公倍数,x∧y是x与y的最大公约数.而A关于∨和∧运算是封闭的.容易验证∨和∧运算满足交换律,结合律,吸收律,且是互相可分配的,因此,该偏序集构成分配格. ?x,y∈A,x∨y是x与y的最小公倍数, x∧y是x与y的最大公约数.而A关于∨和∧运算是封闭的.容易验证∨和∧运算满足交换律,结合律,79吸收律,且是互相可分配的,因引,该偏序集构成分配格. ?x∈A,110是x的补元,x这就证明了该偏序集构成分配格.即布尔代数.6.13 (1) 图 6.1中的(3),(4),(5),(8)图不是格.(3)图中的{f,g}没有最小上界;(4)图中的{a,e}没有最大下界;(5)图中的{d,e}没有最大下界;(8)图中的{d,e}没有最小上界.(2) 图 6.1 中的(1),(2)图为分配格,但不是有补格和布尔格;(6)图不是分配格和布尔格,但是有补格;(7)图不是分配格,也不是有补格和布尔格.分析图 6.1中格(1)和(2)的所有五元子格都不与图 6.3中的格同构,因而它们都是分配格.但对于图 6.1(6)和(7)中的格都能找到与图 6.3(2)中的格同构的子路.例如,图 6.1(6)中的{a,b,c,d,f}和(7)中的{a,b,c,f,g},因此,它们都不是分配格.再考虑补元.(1)图中格的b,c,d元素都没补元;(2)图中格的b,c,d,e元素都没补元;(7)图中格的d元素没有补元.它们不是有补格.而(6)图中格的每个元素都有补元,是有补格.6.14 (1)图中0与1互为补元; a,b,c,d都没有补元.(2)图中0与1互为补元;a的补元是b和d; c的补元是b和d的补元为a和c;d的补元为a和c.(3)图中0与1互为补元;b与c互为补元;a和d都没有补元.。