第一章部分課后習題參考答案

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