离散数学(修订版)课后习题答案

第一章部分课后习题参考答案

16设p、q的真值为0；r、s的真值为1,求下列各命题公式的真值。

(1)pV(qAr)oOV(OAl)QO

(2)(p-r)A(-qVs)o(0-1)A(1V1)。0八loO.

(3)(-ipA^qAr)—(pAq八—>r)<=>(1AlAD-(0A0AO)o0

(4)(TAs)—(PAF)<=>(0A1)(1AO)<=>0^0<=>1

17.判断下面一段论述是否为真：“乃是无理数。并且，如果3是无理数，则行也是无

理数。另外6能被2整除，6才能被4整除。”

答：p：乃是无理数1

q：3是无理数0

r:四是无理数1

s:6能被2整除1

t:6能被4整除0

命题符号化为：p八(qfr)/\(t—s)的真值为1,所以这一段的论述为真。

19.用真值表判断下列公式的类型：

(4)(p-q)―(」q-「p)

(5)(pAr)3(->p/\1q)

(6)((pfq)八(qfr))-*(p-r)

答：(4)

Pqp—q“「P(pfq)f(「qf「p)

00iii11

01i0i11

100i001

11i0011

所以公式类型为永真式

(5)公式类型为可满足式(方法如上例)

(6)公式类型为永真式(方法如上例)

第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出

成真赋值.

⑴Fp八qfq)

(2)(pf(pVq))V(pfr)

(3)(pVq)f(pAr)

答：(2)(p-(p\/q))V(p-*r)<=>(-]pV(pVq))V(-1pVr)«>_|pVpVqVro1

所以公式类型为永真式

⑶pqrPVqpAr(pVq)-*(pAr)

000001

001001

0i0100

0i1100

100100

101111

1i0100

1i1111

所以公式类型为可满足式

4.用等值演算法证明下面等值式：

(2)(p-*q)A(p--r)=(pf(qAr))

(4)(pA-'q)V(~ipAq)<=>(pVq)八(p/\q)

证明(2)(p->q)A(p~*r)

=(-ipVq)A(--pVr)

o->pV(qAr))

0p-*(qAr)

(4)(pA-'q)V(~>pAq)<=>(pV(-ipAq))△(「qV(「pAq)

u>(pV->p)A(pVq)A(「qV「p)A(~>qVq)

<=>1A(pVq)A->(pAq)Al

=(pVq)A(pAq)

5.求下列公式的主析取范式与主合取范式，并求成真赋值

(1)(「pfq)f(「qVp)

(2)->(pfq)AqAr

(3)(pV(qAr))-*(pVqVr)

解：

(1)主析取范式

(「p—q)—(->qvp)

=->(pvq)v(「qVp)

O(-'pA-'q)v(-iqvp)

=(->?A->q)v(^qAP)v(->qA->p)v(pAq)v(pArq)

=(->p人rq)v(pA-1q)v(p人q)

m0vm2vm3

0E(0,2,3)

主合取范式：

(-ip-*q)—(->qvp)

0->(pvq)v(rqvp)

=(-'pA->q)v(-'qvp)

=(->pv(->qvp))A(->qv(->qvp))

O1八(pv-Iq)

o(pv-iq)OM]

on⑴

(2)主合取范式为：

-1(p-q)AqAr=~।(->pvq)AqAr

=(PA->q)AQAT^O

所以该式为矛盾式.

主合取范式为n(0,1,2,3,4,5,6,7)

矛盾式的主析取范式为0

(3)主合取范式为：

(pv(qAr))-*(pvqvr)

o-'(pv(qAT))-*(pvqvr)

=(—>pA(~'qv-ir))v(pvqvr)

=(->pv(pvqvr))A((-^qv->r))v(pvqvr))

O1A1

Q1

所以该式为永真式.

永真式的主合取范式为1

主析取范式为E(0,1,2,3,4,5,6,7)

第三章部分课后习题参考答案

14.在自然推理系统P中构造下面推理的证明：

(2)前提：p->q,(qAr),r

结论：—।p

⑷前提：q—>p,q<->s,s<->t,tAr

结论：pAq

证明：(2)

①「(q/xr)前提引入

②一iqv—ir①置换

③②蕴含等值式

④r前提引入

⑤「q③④拒取式

⑥Pfq前提引入

⑦[P(3)⑤⑥拒取式

证明(4)：

①t/\r前提引入

②t①化简律

③q―"S前提引入

④set前提引入

⑤q-t③④等价三段论

⑥(Q—>t)A(t—>q)⑤置换

⑦(q-t)⑥化简

⑧q②⑥假言推理

⑨q->P前提引入

⑩P⑧⑨假言推理

(ll)pAq⑧⑩合取

15在自然推理系统P中用附加前提法证明下面各推理:

(1)前提：p->(q->r),s->p,q

结论：sfr

证明

①s附加前提引入

②srp前提引入

③P①②假言推理

④pf(qfr)前提引入

⑤q-»r③④假言推理

⑥q前提引入

⑦r⑤⑥假言推理

16在自然推理系统P中用归谬法证明下面各推理：

⑴前提：->rvq,rA->s

结论：—1P

证明：

①P结论的否定引入

②pr-q前提引入

③①②假言推理

④「rvq前提引入

⑤「r④化简律

⑥rArs前提引入

⑦r⑥化简律

⑧rA—>r⑤⑦合取

由于最后一步r/x「r是矛盾式，所以推理正确.

第四章部分课后习题参考答案

3.在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为(a),(b)条件时命

题的真值：

(1)对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x错误！

未找到引用源。).

(2)存在x,使得x+5=9.

其中(a)个体域为自然数集合.

(b)个体域为实数集合.

解：

F(x):错误！未找到引用源。2=(x+错误！未找到引用源。)(x错误！未找到引用

源。).

G(x):x+5=9.

(1)在两个个体域中都解释为VxF(x),在(a)中为假命题，在(b)中为真命题。

(2)在两个个体域中都解释为王G(x),在(a)(b)中均为真命题。

4.在一•阶逻辑中将下列命题符号化：

(1)没有不能表示成分数的有理数.

(2)在北京卖菜的人不全是外地人.

解：

(l)F(x):x能表示成分数

H(x):x是有理数

命题符号化为："X(「F(X)A"(X))

(2)F(x):x是北京卖菜的人

H(x):x是外地人

命题符号化为：尸(x)->〃(x))

5.在一阶逻辑将下列命题符号化：

(1)火车都比轮船快.

(3)不存在比所有火车都快的汽车.

解：

(l)F(x):x是火车；G(x):x是轮船；H(x,y):x比y快

命题符号化为：WxWy((F(x)AG(y))fH(x,y))

(2)(l)F(x):x是火车；G(x):x是汽车;H(x,y):x比y快

命题符号化为：「力(G(y)AVx(F(x)-H(x,y)))

9.给定解释I如下：

(a)个体域D为实数集合R.

(b)D中特定元素错误！未找到引用源。=0.

(c)特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,yw£>错误!

未找到引用源。.

(d)特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。

(x,y):x<y,x,ye£>.

说明下列公式在I下的含义,并指出各公式的真值：

(1)VxWy(G(x,y)f「F(x,y))

(2)G(x,y))

答：(D对于任意两个实数x,y,如果x〈y,那么xwy.真值1.

(2)对于任意两个实数x,y,如果x-y=0,那么x〈y.真值0.

10.给定解释I如下：

(a)个体域D=N(N为自然数集合).

(b)D中特定元素错误！未找到引用源。=2.

(c)D上函数错误！未找到引用源。=x+y,错误！未找到引用源。(x,y)=xy.

(d)D上谓词错误！未找到引用源。(x,y):x=y.

说明下列各式在I下的含义，并讨论其真值.

(1)错误！未找到引用源。xF(g(x,a),x)

(2)错误!未找到引用源。x错误!未找到引用源。y(F(f(x,a),y)-F(f(y,a),x)

答：(D对于任意自然数x,都有2x=x,真值0.

(2)对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.

11.判断下列各式的类型：

(1)错误！未找到引用源。

(3)错误！未找到引用源。yF(x.y).

解：(1)因为pf(q->p)o-ipv(->qvp)ol为永真式；

所以错误！未找到引用源。为永真式；

(3)取解释I个体域为全体实数

F(x,y)：x+y=5

所以，前件为任意实数x存在实数y使x+y=5,前件真；

后件为存在实数x对任意实数y都有x+y=5,后件假，］

此时为假命题

再取解释I个体域为自然数N,

F(x,y)：:x+y=5

所以，前件为任意自然数x存在自然数y使x+y=5,前件假。此时为假命题。

此公式为非永真式的可满足式。

13.给定下列各公式一个成真的解释，一个成假的解释。

(1)错误！未找到引用源。(F(x)错误！未找到引用源。

(2)错误！未找到引用源。x(F(x)错误！未找到引用源。G(x)错误！未找到引用源。

H(x))

解：(1)个体域:本班同学

F(x)：x会吃饭，G(x)：x会睡觉.成真解释

F(x)：x是泰安人,G(x)：x是济南人.(2)成假解释

(2)个体域:泰山学院的学生

F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.

F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.

第五章部分课后习题参考答案

5.给定解释I如下：

(a)个体域D=⑶4};

(b)](x)错误！未找到引用源。为7(3)=4,7(4)=3错误！未找到引用源。

(c)7(x,y)为7(3,3)=万(4,4)=0,万(3,4)=7(4,3)=1错误！未找到引用源。.

试求下列公式在I下的真值.

(1)Vx3yF(x,y)

⑶⑥Vy(F(x,y)f尸(f(x)J(y)))

解：(1)Vx3yF(x,y)oVx(F(x,3)vF(x,4))

o(F(3,3)v-(3,4))A(尸(4,3)v-(4,4))

<=>(0V1)A(1V0)<=>1

(2)VxWy(尸(x,y)fb(/(x)J(y)))

oVx((F(x,3)-»F(/(X),/(3)))A(F(X,4)TF(/(X),/(4))))

oVx((F(x,3)fF(/(x),4))A(F(x,4)-F(/(x),3)))

o((/(3,3)tF(/(3),4))A(F(3,4)tF(/(3),3)))

A((/(4,3)TF(/(4),4))A(F(4,4)t2/(4),3)))

o((0->F(4,4))A(尸(3,4)t尸(4,3)))A((1T尸(3,4))A(0->尸(3,3)))

0(0-0)人(1-1)△(1-1)△(0-0)01

12.求下列各式的前束范式。

(1)VxF(x)—>WyG(x,y)

(5)BX]F(x.,x2)->(77(x,)->-yBx2G(x},x2))(本题课本上有错误)

解：⑴VxF(x)TVyG(x,y)。WxF(x)TVyG(f,y)o3xVy(F(x)tG(t,y))

(5)3X1F(X1,X2)—>(H(xt)—>-dx2Ga，/))

O3XIF(X1,X2)-»(//(X3)Vx2—>G(X3,X2))

O3X1F(X1,X4)—>VX2(H(X3)—>—IG(X3,X2))

O\/X,VX2(F(X„X4)T(HU)->[G®")

15.在自然数推理系统F中，构造下面推理的证明：

(1)前提：*F(x)-»Vy((F(y)vG(y))fR(y)),*F(x)

结论：3xR(x)

(2)前提:Vx(F(x)—(G(a)AR(x))),错误！未找到引用源。xF(x)

结论:错误！未找到引用源。x(F(x)AR(x))

证明⑴

①入户*)前提引入

②F(c)①EI

③★尸(x)fVy((F(y)vG(y))->R(y))前提引入

④Vy((F(y)vG(y))-R(y))①③假言推理

⑤(F(c)VG(c))-R(c))④UI

@F(c)VG(c)②附加

⑦R(c)⑤⑥假言推理

⑧mxR(x)⑦EG

⑵

①mxF(x)前提引入

②F(c)①EI

③Wx(F(x)f(G(a)AR(x)))前提引入

④F(c)f(G(a)AR(c))③UI

@G(a)AR(c)②④假言推理

⑥R(c)⑤化简

⑦F(c)/\R(c)②⑥合取引入

@3x(F(x)AR(x))

第六章部分课后习题参考答案

5.确定下列命题是否为真：

(1)0C0真

(2)0e0假

(3)0c{0}真

(4)0e{0}真

(5){a,b}c{a,b,c,{a,b,c}}真

(6){a,b}e{a,b,c,{a,b})真

(7){a,b}={a,b,{{a,b}}}真

(8){a,b}w{a,b,{{a,b}}}假

6.设a,b,c各不相同，判断下述等式中哪个等式为真:

(l){{a,b},c,0}={{a,b},c}假

(2){a,b,a}={a,b}真

⑶{{a},{b}}={{a,b}}假

(4){0,{0},a.b}={{0,{0}},a,b)假

8.求下列集合的暴集：

⑴{a,b,c}P(A)={0,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

(2){1,{2,3}}P(A)={0,{1},{{2,3}},{1,{2,3}}}

(3){0}P(A)={0,{0})

(4){0,{0}}P(A)={0,⑴，{{2,3}},{1,⑵3}}}

14.化简下列集合表达式：

(1)(AUB)OB)-(AUB)

(2)((AUBUO-(BUO)UA

解：

(1)(AUB)AB)-(AUB)=(AUB)PB)「〜(AUB)

=(AUB)n-(AUB))nB=0AB=0

(2)((AUBUO-(BUO)UA=((AUBUOD〜(BUO)UA

=(An〜(BUO)u((BUC)n〜(BUO)UA

=(An〜(BUC))U0UA=(An〜(BUC))UA=A

18.某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5

人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。

求不会打球的人数。

解：阿八={会打篮球的人},B={会打排球的人},C={会打|EI网球

的人}"OS/

|A|=14,|B|=12,|AnB|=6,|AQC=5,|AnBnc|=2,

|C|=6,CcAUBI_________________I

如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5

不会打球的人共5人

21.设集合人={{1,2},{2,3},{1,3},{0}},计算下列表达式:

(1)UA

(2)nA

(3)nuA

(4)unA

解：(1)UA={1,2}U{2,3}U{1,3}U{0}={1,2,3,0)

(2)nA={I,2}n⑵3}n{i,3}n{0)=0

(3)nuA=in2n3n0=0

(4)unA=0

27、设A,B,C是任意集合，证明

(1)(A-B)-C=A-Buc

(2)(A-B)-C=(A-C)-(B-C)

证明

(1)(A-B)-C=(AD~B)Pl~C=Afi(〜BD〜C)=AD〜(B℃)=A-BuC

(2)(A-C)-(B-C)=(AA-C)n~(BPI〜C)=(AA〜C)Cl(〜BUC)

=sn〜cn〜B)u(An~cno=(An~cn~B)u0

=An〜(BuC)=A-BuC由(1)得证。

第七章部分课后习题参考答案

7.列出集合A={2,3,4}上的恒等关系1A,全域关系EA,小于或等于关系LA,整除关系DA.

解：L={<2,2>,<3,3>,<4,4>}

EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}

LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}

DA={<2,4>}

13.设A={<1,2>,<2,4>,<3,3>}

B={<1,3>,<2,4>,<4,2>}

求AUB,ACB,domA,domB,dom(AuB),ranA,ranB,ran(AcB),fld(A-B).

解：A^B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}

ACB={<2,4»

domA={l,2,3}

domB={l,2,4}

dom(AVB)={l,2,3,4)

ranA={2,3,4}

ranB={2,3,4}

ran(A^B)={4}

A-B={<1,2>,<3,3>},fld(A-B)={l,2,3)

14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}

求RoR,R-1,Rt{0,l,},R[{1,2}]

解：RoR={<0,2>,<0,3>,<1,3>}

R",={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2»

Rt{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}

R[{l,2}]=ran(R|{1,2])={2,3}

16.设A={a,b,c,d},号,R2为A上的关系，其中

与={{a,a),(a,b),(b,d)}

R2={[a,d),(b,c),(b,d),(c,b)}

求均。为,/?2。"2,与3。

解：RioR2={<a,d>,<a,c>,<a,d>}

R2OR1={<C,d>}

Ri2=Ri°Ri={<a,a>,<a,b>,<a,d>}

2

R2=R2oR2={<b,b>,<c,c>,<c,d>}

32

R2=R2oR2={<b,c>,<c,b>,<b,d>}

36.设人={1,2,3,4),在AxA上定义二元关系R,

V<u,v>,<x,y>€AxA,<u,v>R<x,y>ou+y=x+v.

(1)证明R是AxA上的等价关系.

(2)确定由R引起的对AxA的划分.

(1)证明：<u,v>R<x,y>=u+y=x-y

<u,v>R<x,y>u>u-v=x-y

V<u,v>Q\xA

*.*u-v=u-v

/.<u,v>R<u,v>

是自反的

任意的<u,v>,<x,y>EAXA

如果<u,v>R<x,y>,那么u-v=x-y

x-y=u-v・'・<x,y>R<u,v>

・・・R是对称的

任意的<u,v>,<x,y>,<a,b>WAXA

若<u,v>R<x,y>,<x,y>R<a,b>

则u-v=x-y,x-y=a-b

u-v=a-b<u,v>R<a,b>

•••R是传递的

••.R是AXA上的等价关系

(2)n={{<1,1>,<2,2>,<3,3>,<4,4>},{<2,1>,<3,2>,<4,3>},{<3,1>,<4,2>},

{<4,1>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>}}

41.设A={1,2,3,4},R为AxA上的二元关系，V(a,b),<c,d)eAxA,

〈a,b)R〈c,d〉oa+b=c+d

(1)证明R为等价关系.

(2)求R导出的划分.

(1)证明：V<a,b)€AxA

a+b=a+b

<a,b>R<a,b>

，R是自反的

任意的<a,b>,<c,d>GAXA

设<a,b>R<c,d>,则a+b=c+d

c+d=a+b<c,d>R<a,b>

，R是对称的

任意的<a,b>,<c,d>,<x,y>eAXA

若<a,b>R<c,d>,<c,d>R<x,y>

则a+b=c+d,c+d=x+y

a+b=x+y.,.<8,b>R<x,y>

，R是传递的

...R是AXA上的等价关系

(2)n={{<l,1>}>{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<4,1>,<2,3>,<3,2>},

{<2,4>,<4,2>,<3,3>},{<3,4>,<4,3>},{<4,4>}}

43.对于下列集合与整除关系画出哈斯图:

(1){1,2,3,4,6,8,12,24}

(2){1,2,3,4,5,6,7,8,9,10,11,12}

解：

⑵

45.下图是两个偏序集＜A,Ry＞的哈斯图.分别写出集合A和偏序关系Ry的集合表达式.

g

Ry={〈a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>}uIA

(b)A={a,b,c,d,e,f,g}

Ry={〈a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}uIA

46.分别画出下列各偏序集<A,RY>的哈斯图，并找出A的极大元'极小元'最大元和

最小元.

(l)A={a,b,c,d,e}

Ry={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}。I

(2)A={a,b,c,d,e},R-<={<c,d>}IA.

解:

(1)(2)

项目(1)(2)

极大元：ea,b,d,e

极小元：aa,b,c,e

最大元：e无

最小元：a无

第八章部分课后习题参考答案

1.设f:NfN,且

1,若X为奇数

f(x)=土若X为偶数

2,

求f(0),f({0})f(l),f({l}),f({0,2,4,6,“・}),f({4,6,8}),f“({3,5,7}).

解:f(0)=0,f({0})={0},f({1})={1。

f({0,2,4,6,-})=N,f({4,6,8})={2,3,4},f1({3,5,7})={6,10,14).

4.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的？

(l)f:N.N,f(x尸x?+2不是满射，不是单射

(2)f:N->N,f(x)=(x)mod3,x除以3的余数不是满射，不是单射

1,若x为奇数

(3)f:N-N,Rx)=<不是满射，不是单射

0,若x为偶数

0,若x为奇数

(4)f:N->{0,l},f(x)=是满射，不是单射

1，若x为偶数

(5)f:N-{0}->R,f(x)=lgx不是满射，是单射

(6)f:R^R,f(x)=x2-2x-15不是满射，不是单射

5.设*=｛小娘｝,丫=｛1,2,3｝户｛累,1>,<1),2>,«,3>,｝判断以下命题的真假：

(l)f是从X到Y的二元关系，但不是从X到Y的函数；对

(2)f是从X到Y的函数，但不是满射，也不是单射的；错

(3)f是从X到Y的满射，但不是单射；错

(4)f是从X到Y的双射.错

第十章部分课后习题参考答案

4.判断下列集合对所给的二元运算是否封闭：

(1)整数集合Z和普通的减法运算。

封闭，不满足交换律和结合律，无零元和单位元

(2)非零整数集合错误！未找到引用源。普通的除法运算。不封闭

(3)全体〃x〃实矩阵集合错误！未找到引用源。(R)和矩阵加法及乘法运算，其中

n错误！未找到引用源。2o

封闭均满足交换律，结合律，乘法对加法满足分配律；

加法单位元是零矩阵，无零元；

乘法单位元是单位矩阵，零元是零矩阵；

(4)全体〃X〃实可逆矩阵集合关于矩阵加法及乘法运算，其中n错误！未找到引用源。

2o不封闭

(5)正实数集合错误！未找到引用源。和错误！未找到引用源。运算，其中错误！未

找到引用源。运算定义为：

错误！未找到引用源。

不封闭因为l°l=lxl-l-l=-U/?+

(6)〃错误！未找到引用源。关于普通的加法和乘法运算。

封闭，均满足交换律，结合律，乘法对加法满足分配律

加法单位元是0,无零元；

乘法无单位元零元是0;〃=1单位元是1

(7)A=｛%,?,…,4｝错误！未找到引用源。n错误！未找到引用源。运算定义如下:

错误！未找到引用源。

封闭不满足交换律，满足结合律,

(8)S=错误！未找到引用源。关于普通的加法和乘法运算。

封闭均满足交换律，结合律，乘法对加法满足分配律

(9)S={0,1},S是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满足交换律，结合律

(10)S=错误！未找到引用源。与关于普通的加法和乘法运算。

加法不封闭，乘法封闭，乘法满足交换律，结合律

5.对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。

见上题

7.设*为Z+错误！未找到引用源。上的二元运算Vx,ywZ，，

X*Y=min(x,y),即x和y之中较小的数.

⑴求4*6,7*30

4,3

(2)*在Z+上是否适合交换律，结合律，和累等律？

满足交换律，结合律，和幕等律

(3)求*运算的单位元，零元及Z+中所有可逆元素的逆元。

单位元无，零元1,所有元素无逆元

8.S=QxQ。为有理数集，*为$上的二元运算，错误！未找到引用源。<a,b〉,〈x,y〉

错误！未找到引用源。S有

<a,b>*<x,y>=<ax,ay+b>

(1)*运算在S上是否可交换，可结合？是否为累等的？

不可交换：vx,y>*va,b>=vxa,xb+y><a,b>*<x,y>

可结合：(<a,b>*<x,y>)*<c,d>=<ax,ay+b>*<c,d>=<3xc,axd+(ay+b)>

<a,b>*(<x,y>*<c,d>)=<a,b>*<xc,xd+y>=<axc,a(xd+y)+b>

(<a,b>*vx,y>)*<c,d>=va,b>*(vx,y>*vc,d>)

不是幕等的

(2)*运算是否有单位元，零元？如果有请指出，并求S中所有可逆元素的逆元。

设va,b>是单位元，错误！未找到引用源。vx,y>错误！未找到引用源。S,va,b

>*<x,y>=<x,y>*<a,b>=<x,y>

贝(jvax,ay+b>=vxa,xb+y>=vx,y>，解的<a,b>=<l,0>，即为单位。

设va,b>是零元，错误！未找到引用源。vx,y>错误！未找到引用源。S，<a,b

>*<x,y>=<x,y>*<a,b>=<a,b>

贝(Jvax,ay+b>=vxa,xb+y>=va,b>,无解。即无零元。

错误！未找到引用源。vx,y>错误！未找到引用源。S,设va,b>是它的逆元va,b

>*<x,y>=<x,y>*<a,b>=<1,0>

<ax,ay+b>=<xa,xb+y>=<1,0>

a=l/x,b="y/x

所以当xwO时，<x,y>T1_y

X，X

10.々S={a,b},S上有四个运算：*,错误！未找到引用源。分别有表10.8确定。

*aboab*ab□ab

aaaaababaaab

baabbabaabab

(a)(b)(c)(d)

(1)这4个运算中哪些运算满足交换律，结合律，幕等律？

(a)交换律，结合律，嘉等律都满足，零元为a,没有单位元；

(b)满足交换律和结合律，不满足嘉等律，单位元为a,没有零元

a'-a,bi-h

⑹满足交换律，不满足嘉等律,不满足结合律

ao(b。b)=a。a=b,(a。b)。b=a。b=a

a°(b°b)手(a0b)°b

没有单位元，没有零元

(d)不满足交换律，满足结合律和幕等律

没有单位元，没有零元

⑵求每个运算的单位元，零元以及每一个可逆元素的逆元。

见上

16.设V=〈N,+,错误！未找到引用源。〉，其中+,错误！未找到引用源。分别代

表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？

(1)S尸错误！未找到引用源。是

(2)S产错误！未找到引用源。不是加法不封闭

(3)S3={-1,0,1}不是，加法不封闭

第十一章部分课后习题参考答案

8.设S={0,1,2,3},®为模4乘法，即

〃Vx,y£S,x0y=(xy)mod4

问〈S,8〉是否构成群？为什么？

解：(1)VX,yes,xay=(xy)mod4eS,®是S上的代数运算。

(2)Vx,y,zWS,设xy=4k+r0<r<3

(x0y)0z=((xy)mod4)®z=r®z=(rz)mod4

=(4kz+rz)mod4=((4k+r)z)mod4=(xyz)mod4

同理x®(y®z)=(xyz)mod4

所以，(x@y)=x®(y@z),结合律成立。

(3)VxGS,(x&l)=(l®x)=x,,所以1是单位元。

(4)r'=1,3T=3,0和2没有逆元

所以，〈S,不构成群

9.设Z为整数集合，在Z上定义二元运算。如下：

〃Vx,y^Z,xoy=x+y-2

问z关于。运算能否构成群？为什么？

解：⑴Vx,yGZ,xoy=x+y-2eZ,o是Z上的代数运算。

(2)Vx,y,zGZ,

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

同理(xoy)oz=xo(yoz),结合律成立。

⑶设e是单位元，VxGZ,xoe=eox=x,x+e-2=e+x-2=x,e=2

(4)VxeZ,设x的逆元是y,xoy=yox=e,即x+y-2=y+x-2=2,

所以，x-1-y-4-x

所以〈Z,o）构成群

1L设G=M°1P°1f；1，[仁1°j],证明G关于矩阵乘法构成-个群.

llo1Jlo-1Jlo1Jlo-1JJ

解：(1)Vx.yGG,易知xyWG,乘法是Z上的代数运算。

(2)矩阵乘法满足结合律

(3)设|是单位兀，

10V

(4)每个矩阵的逆元都是自己。

所以G关于矩阵乘法构成一个群.

14.设G为群，且存在a£G,使得

G={akIkez}

证明：G是交换群。

证明：Vx,yCG,设x=y=a',贝U

xy=aka'=ak+l==a'+k=a'ak=yx

所以，G是交换群

17.设G为群，证明e为G中唯一的幕等元。

证明：设e°eG也是幕等元，则e；=e°,即e：=e°e,由消去律知e°=e

18.设G为群，a,b,c£G,证明

Iabc|=Ibca|=Icab|

证明：先证设(abc)，=eo(bca)*=e

设(abcY-e,则(abc)("c)(abc)…(abc)=e,

即a(bca}(bca)(bca)••■(bca)a1=e

左边同乘a一,右边同乘a得

(bcd)(bcd)(bcd)---(bed)=(bac)k=a''ea=e

反过来，设(bac)k=e,则(abc?=e.

由元素阶的定义知，Iabc|=Ibca|,同理|bca|=Icab|

19.证明：偶数阶群G必含2阶元。

证明：设群G不含2阶元，VaeG,当a=e时，。是一阶元，当a/e时，。至少是3

阶元,因为群G时有限阶的，所以a是有限阶的，设。是k阶的，则qT也是k阶的，所以

高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛

盾。所以，偶数阶群G必含2阶元

20.设G为非Abel群，证明G中存在非单位元a和b,aWb,且ab=ba.

证明：先证明G含至少含3阶元。

若G只含1阶元,则G={e},G为Abel群矛盾；

若G除了1阶元e外,其余元。均为2阶元，则/=e,=«

Va,beG,a"'=a,b"l=b,(aby'=ab,所以ab=a'b~x=-ba,

与G为Abel群矛盾；

所以，G含至少含一个3阶元，设为a,则OHM,且小。=”/。

令方=。2的证。

21.设G是M.(R)上的加法群，n22,判断下述子集是否构成子群。

(1)全体对称矩阵是子群

(2)全体对角矩阵是子群

(3)全体行列式大于等于0的矩阵.不是子群

(4)全体上(下)三角矩阵。是子群

22.设G为群，a是G中给定元素，a的正规化子N(a)表示G中与a可交换的元素构成

的集合，即

N(a)={x|xGGAxa=ax}

证明N(a)构成G的子群。

证明：ea=ae,eeN(a)丰(/)

Vx,yeN(a\则ax=xa,ay=ya

a(xy)=(ax)y=(xa)y=x(ay)=x(yd)=(盯)a，所以xywN(a)

由ax=xa,Wx~'axx'-x~'xax^{,x^ae=eax{,HPx~'a-ax^',所以x”eN(a)

所以N(a)构成G的子群

31.设外是群&到Gz的同态，夕2是邑到G：,的同态，证明外。夕2是&到G：,的同态。

证明：有已知夕1是G1到G2的函数，82是G2到G3的函数，则01♦夕2是G1到G3的函数。

V。力eG1,(例0(p2)(")=(p2M(孙=仍Q(a)(p\V))

=33（a）））®2S（♦）））=（%°%）3）@°仍）（。）

所以：8•小是1到G3的同态。

33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。

证明：设G是循环群,令G=<a>,Vx,yeG,令x==/,那么

k1kilhk1k

xy=aa=a-a=aa=yxtG是阿贝尔群

克莱因四元群，G={e,a,b,c}

Oeabc

abc

aaecb

bb

chae

是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。

36.设。/是5元置换，且

（12345）（12345、

O'==，T=

（21453）（34512）

⑴计算or,T(y,T~',；

（2）将.er,尸，b-，cr表成不交的轮换之积。

(3)将(2)中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。

5,、(12345、(12345、.fl234

解：1r<7=\ar=/=

(45321J(43125)(4512?

,fl2345>.(12345、

<7-1=(J''T(7=\

(21534)(54132)

(2)9=(1425)「1=(14253)cy-'ra=(143)(25)

(3)R=(14)(12)(15)奇置换，

r-1=(14)(12)(15)(13)偶置换

尸丝=(14)(13)(25)奇置换

第十四章部分课后习题参考答案

5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3,问G至

少有多少个顶点？在最少顶点的情况下，写出度数列、A(G)、b(G)。

解：由握手定理图G的度数之和为：2x10=20

3度与4度顶点各2个，这4个顶点的度数之和为14度。

其余顶点的度数共有6度。

其余顶点的度数均小于3,欲使G的顶点最少，其余顶点的度数应都取2,

所以,G至少有7个顶点，出度数列为3,3,4,4,2,2,2,A(G)=4,3(G)=2.

7、设有向图D的度数列为2,3,2,3,出度列为1,2,1,1,求D的入度列，并求A(D),b(。)，

△+(£>)/+(£>),△-(£>)/-(£)).

解：D的度数列为2,3,2,3,出度列为1,2,1,1,D的入度列为1,1,1,2.

△(D)=3/(。)=2,△+(£))=20+(。)=1,"(D)=2,(0)=1

8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少

个顶点？

解：由握手定理图G的度数之和为：2x6=12

设2度点x个，则3xl+5xl+2x=12,x=2,该图有4个顶点.

14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同

构的无向图，其中至少有两个时简单图。

(1)2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4

解：(1)2+2+3+3+4+4+5=23是奇数，不可图化；

(2)2+2+2+2+3+3+4+4=16,是偶数，可图化；

18、设有3个4阶4条边的无向简单图Gi、G2、G3,证明它们至少有两个是同构的。

证明：4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列

为2,2,2,2；3,2,2,1；3,3,1,1。但3,3,1,1对应的图不是简单图。所以

从同构的观点看，4阶4条边的无向简单图只有两个：

所以，G］、G2,G3至少有两个是同构的。

20、已知n阶无向简单图G有m条边，试求G的补图3的边数〃。

AX,,n(n-1)

解：in-------------m

2

21、无向图G如下图

(1)求G的全部点割集与边割集，指出其中的割点和桥；

(2)求G的点连通度k(G)与边连通度2(G)。

解：点割集：{a,b},(d)

边割集{e2,e3},{e3,e4},{el,e2},{el,e4}{el,e3},{e2,e4},{e5}

%(G)=4(G)=1

23、求G的点连通度MG)、边连通度4(G)与最小度数仇G)。

解：A(G)=2、2(G)=3、3(G)=4

28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种

非同构的情况？

I3〃=2m/口

解：\得n=6,m=9.

2n-3=m

31、设图G和它的部图。的边数分别为加和帚，试确定G的阶数。

AS­”(〃+l)ZH-1+Jl+8(-+M

解：m+m=------侍〃=---------------

22

45、有向图D如图

(1)求叱到匕长度为1，2,3,4的通路数；

(2)求看到匕长度为1，2,3,4的回路数;

(3)求D中长度为4的通路数；

(4)求D中长度小于或等于4的回路数；

(5)写出D的可达矩阵。

解：有向图D的邻接矩阵为:

‘00001、'01010、’20200、

101000000202020

A=00001,A2=01010A-'=20200

101000000202020

、01010,、20200,、00004/

’00004、’01215、

4040052522

T=00004A+A2+A3+A4=21215

4040042522

、04040,、25254,

(1)匕到匕长度为1，2,3,4的通路数为0,2,0,0；

(2)%到以长度为1，2,3,4的回路数为0,0,4,0；

(3