《离散数学》第九章习题参考答案

第九章群

习题9解答

1分析(D运算显然是封闭的.下面验证结合律.V%,y,z€S,

(%*y)*Z=X*Z=X,%*(y*z)=%*y=x

(2)任取eCS,定义T=Su{e},VxGS,x*e=e*x=xfe*e=e.那么<

7>>构成独异点.

2分析(a*b)*(a*b)=a*b*a*b=a*a*Z?*b=a*b

3分析能构成群.运算封闭.Vx,y,z£Z,

(xoy)oz=(x+y-2)+z-2=x+y+z-4

%o(yoz)=xo(y+z-2)=x+(y+z-2)-2=x+y+z—4

结合律成立，单位元是2,x的逆元是4-工

4分析设矩阵A=("),B=(；?,C=[：)，D=(二二)

那么运算表如表10T所示.运算封闭，矩阵乘法满足结合律，单位元为4每

个矩阵的逆元都是它自己.因此G关于矩阵乘法构成群.

表10-1

•ABCD

AABCD

BBADC

CCDAB

DDCBA

5分析1WT,Vx,yGT,(x,n)=1,(y,n)=1,因此存在整数Q,b,c,d>

使得

xa+nb=1,yc+nd=1

从而得到=1-nb,yc=1-nd

(xa)(yc)=1-nb-nd+n2bd=(QC)+n(b+d—nbd)=1

设xy=tn+i,其中£,i为非负整数，且04i<九,那么=i.根据上式得到

(tn+i)(ac)+n(b+d-nbd)=1=t(ac)+n{tac+b+d-nbd)=1

由于ac,tac+b+d—nbd都是整数，因此。,几)=1.这就证明了无⑥yE7.

1为7中单位元，VxGT,由于(％九)=1,存在整数a,b使得XQ+nb=1.

如果1<a<n,,那么论a=1,a就是x的逆元.下面证明存在a满足0<a<n,

根据除法存在整数k和出使得a=nk+a\其中0<Q'V儿于是有+优)+

nb=1,即工优+n(b+xk)=1,优满足要求

显然⑥满足结合律和交换律，综合上述证明了T关于模n乘法构成Abel群.

6分析设a为九阶元素，所以

an=e

(an)-1=e

曾证明(〃)T=(a-1)%因而可得

(a-1)71=e

再证明"是满足上述等式的最小止整数，用反证法.设且有

=e

(a*)T=e

ak=((小)-1)-1=e

这和a为几阶元素矛盾，所以a一1也为阶元素.

当a为无限阶元素时，。一1也为无限阶元素，否则，若QT为九阶元素时，由于

(a-1)-1=a,也为阶元素，这和a为无限阶元素矛盾.

综上所述，a和a一1有相同的阶数.证毕.

7.分析设。=<a>是循环群，Val\a7G<a>,

alai==a7+l=ajal

因此G是Abel群，但Abel群不一定是循环群.例如Klein四元群是Abel群，但不是循

环群.

7.分析由于a是VG,*>的生成元，所以

其中a。=8.在(N]5,㊉15)中，若令

4={0,5,10}

A5={0,3.6.9.12}

易知(43,㊉15)是(必5,㊉15)的3阶了群，(包,㊉15)是(N15,㊉15)的5阶了群，由此可

知，若令

510510

B3=[a0,a,a}={e,a,a]

03691236912

B5={a,a,a,a,a}={e,a,a,a,a)

则(殳产)是(G,*)的3阶子群，(坛，*)是3*)的5阶子群.

8分析只需找出4次对称群(S4,*)中的4阶元素a,则令G={Q,Q2,Q3,Q4},(。,*)即

为4阶循环群.令

a=(l?34)

则有

@2=（；234\

341/

/I234\

V3412/

@3=（；234\

4127

/I234、

一（4123）

3XI234、

a

1237

=GA\：）

由此可知，Q为4阶元素，令6=5,。2,03,04},则是4次置换群也是4阶循环群.

提升习题

1分析如图9-1所示.

对面的置换根据立力体旋转或翻转的对称轴不同分类.围绕过一对面中心的时称

轴（3个）旋转90度、180度、270度，产生的置换结构如下：

90度、270度：（•）（・）（•・・•）6个

180度：（・•）（・•）（・）（・）3个

围绕过一棱中点的对称轴（6个）翻转180度，产生的置换结构如下

180度：（・•）（••）（••）6个

围绕过一对顶点的对称轴（4个）旋转120度、240度，产生的置换结构如下

120度、240度：（•一）（••・）8个

还有恒等置换，其结构是

0度：（•）（•）（•）（•）（•）（•）1个

总计24个置换.代入Polya定理得

^■(n6+8n2+12n3+3n4)

2分析围绕中心旋转60度、120度、180度、240度、300度的置换结构如

下：

60度、300度：（...............）2个

120度、240度：（•••）（•一）2个

180度：（一）（…）（一）1个

围绕过一对弦中点的对称轴（3个）翻转180度，产生的置换结构如下

180度：（一）（一）（一）3个

围绕过一对顶点的对存在（3个）翻转180度，产生的置换结构如下

180度：（…）（・•）（•）（・）3个

还有恒等置换，其结构是

0度：（•）（•）（•）（•）（•）（•）1个

代入Polya定理得

M(36+3-344-4•33+2•32+2-3)=92

3分析

（1）设计思路

输入：指定的置换。

输出：该置换的类型。

实现语言：可自选，C/C++、Java、Python均可。

基本思路：首先将置换转换为轮换，确定每一种轮换的个数，得到置换的类

型。

(2)核心代码

这里用Python代码表示如下：

defgetRotationstperm):

#得到置换的轮换表达式，输入形式类似pennl=[l,4,3,6,2,5]

rots=[]

a=set(range(1,len(perm)+1))

whilea:

start=min(a)

nt=perm[start-l]

r=[start]

whilestart!=nt:

r.append(nt)

nt=perm[nt-l]

rots,append(r)

a=a-set(r)

returnrots

definegetPermutationT)rpe(rotations):

#得到置换的类型，输入为gctRotations输出的轮换结果

ptype={}

foriinrotations:

key=str(len(i))

Ifkeynotintype:

ptype[key]=O

ptype[key]=ptype[key]+1

returndiet(sorted(ptype.iterns0,key=lambdax:x[0]))

perml=[l,4,3,6,2,5]

rot=getRotations(permsl)

print(rot)

rtype=getPermutationType(rot)

print(rtype)

4分析

(1)设计思路

输入：代数系统的运算表

输出：该代数系统是否是半群，是否是独异点，是否是群或循环群。如果是群，

求出每个元素的阶。

实现语言：可自选，C/C++、Java>Pylhon均可。

基本思路：判定方面以运算是否满足结合律、有单位元，每个元素有逆元为标

准。求出元素的阶之后，如果有元素的阶等于群的阶，则为循环群。

(2)这里用Python代码表示如下：

Importnumpyasnp

Importitertools

defIsAssociative(A,n):

#判断运算是否满足结合律，A为用二维数组表示的运算表，n为阶数

Isassociative=True:

Fornuminitertools.product(rang(0,n),repeat=3):

IfA[A[num[0]][num[l]]][num[2]!=A[num[0]][A[num[l]]

[num[2]]]:

Isassociative=False;

Break;

Return(isassociative)

DeffindIdentity(A,n):

#判断元素是否有单位元，A为用二维数组表示，n为阶数

Identity=None:

Nums=rangef0,n)

Fornuminnums:

If(A[num]==nums).all():

Idcntuty=num;

ReturnIdentity

Deffindinverse(A,n,uid):

#判断运算是否有逆元，A为用二维数组表示的运算表，，n为阶数，uid为单

位元

Rev=np.empty([n],dtype=type(A[Oj[0]))

Fornuminrange(0,n):

Ind=np.argwhere(A[num]==uid)

Ifind.size>0:

IfA[ind[0][0],num]==uid:

Rev[num]=ind[0]0[0]

Else:

Rev[num]=-1

Else:

Rev[num]

Returnrev

DefinefindOrder(A,n,uid):

#求出群中每个元素的阶，A为用二维数组表示的运算表，，n为群的阶数，uid

为单位元

Orders=np.empty([n],dtype(A[O][0]))

Fornuminrange(0,n):

A二num

Fornumjinranged,n+1):

Ifa==uid:

Orders[num]=numj