離散數(shù)學(xué)(修訂版)課后習(xí)題答案

第一章部分課后習(xí)題參考答案

16設(shè)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.判斷下面一段論述是否為真：“乃是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則行也是無(wú)

理數(shù)。另外6能被2整除，6才能被4整除。”

答：p：乃是無(wú)理數(shù)1

q：3是無(wú)理數(shù)0

r:四是無(wú)理數(shù)1

s:6能被2整除1

t:6能被4整除0

命題符號(hào)化為：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)公式類型為永真式(方法如上例)

第二章部分課后習(xí)題參考答案

3.用等值演算法判斷下列公式的類型，對(duì)不是重言式的可滿足式，再用真值表法求出

成真賦值.

⑴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)

第三章部分課后習(xí)題參考答案

14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：

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

結(jié)論：—?p

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

結(jié)論：pAq

證明：(2)

①「(q/xr)前提引入

②一iqv—ir①置換

③②蘊(yùn)含等值式

④r前提引入

⑤「q③④拒取式

⑥Pfq前提引入

⑦[P(3)⑤⑥拒取式

證明(4)：

①t/\r前提引入

②t①化簡(jiǎn)律

③q―"S前提引入

④set前提引入

⑤q-t③④等價(jià)三段論

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

⑦(q-t)⑥化簡(jiǎn)

⑧q②⑥假言推理

⑨q->P前提引入

⑩P⑧⑨假言推理

(ll)pAq⑧⑩合取

15在自然推理系統(tǒng)P中用附加前提法證明下面各推理:

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

結(jié)論：sfr

證明

①s附加前提引入

②srp前提引入

③P①②假言推理

④pf(qfr)前提引入

⑤q-?r③④假言推理

⑥q前提引入

⑦r⑤⑥假言推理

16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：

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

結(jié)論：—1P

證明：

①P結(jié)論的否定引入

②pr-q前提引入

③①②假言推理

④「rvq前提引入

⑤「r④化簡(jiǎn)律

⑥r(nóng)Ars前提引入

⑦r⑥化簡(jiǎn)律

⑧rA—>r⑤⑦合取

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

第四章部分課后習(xí)題參考答案

3.在一階邏輯中將下面將下面命題符號(hào)化，并分別討論個(gè)體域限制為(a),(b)條件時(shí)命

題的真值：

(1)對(duì)于任意x,均有錯(cuò)誤！未找到引用源。2=(x+錯(cuò)誤！未找到引用源。)(x錯(cuò)誤！

未找到引用源。).

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

其中(a)個(gè)體域?yàn)樽匀粩?shù)集合.

(b)個(gè)體域?yàn)閷?shí)數(shù)集合.

解：

F(x):錯(cuò)誤！未找到引用源。2=(x+錯(cuò)誤！未找到引用源。)(x錯(cuò)誤！未找到引用

源。).

G(x):x+5=9.

(1)在兩個(gè)個(gè)體域中都解釋為VxF(x),在(a)中為假命題，在(b)中為真命題。

(2)在兩個(gè)個(gè)體域中都解釋為王G(x),在(a)(b)中均為真命題。

4.在一?階邏輯中將下列命題符號(hào)化：

(1)沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù).

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

解：

(l)F(x):x能表示成分?jǐn)?shù)

H(x):x是有理數(shù)

命題符號(hào)化為："X(「F(X)A"(X))

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

H(x):x是外地人

命題符號(hào)化為：尸(x)->〃(x))

5.在一階邏輯將下列命題符號(hào)化：

(1)火車都比輪船快.

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

解：

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

命題符號(hào)化為：WxWy((F(x)AG(y))fH(x,y))

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

命題符號(hào)化為：「力(G(y)AVx(F(x)-H(x,y)))

9.給定解釋I如下：

(a)個(gè)體域D為實(shí)數(shù)集合R.

(b)D中特定元素錯(cuò)誤！未找到引用源。=0.

(c)特定函數(shù)錯(cuò)誤！未找到引用源。(x,y)=x錯(cuò)誤！未找到引用源。y,x,yw￡>錯(cuò)誤!

未找到引用源。.

(d)特定謂詞錯(cuò)誤！未找到引用源。(x,y):x=y,錯(cuò)誤！未找到引用源。

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

說(shuō)明下列公式在I下的含義,并指出各公式的真值：

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

(2)G(x,y))

答：(D對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x〈y,那么xwy.真值1.

(2)對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x-y=0,那么x〈y.真值0.

10.給定解釋I如下：

(a)個(gè)體域D=N(N為自然數(shù)集合).

(b)D中特定元素錯(cuò)誤！未找到引用源。=2.

(c)D上函數(shù)錯(cuò)誤！未找到引用源。=x+y,錯(cuò)誤！未找到引用源。(x,y)=xy.

(d)D上謂詞錯(cuò)誤！未找到引用源。(x,y):x=y.

說(shuō)明下列各式在I下的含義，并討論其真值.

(1)錯(cuò)誤！未找到引用源。xF(g(x,a),x)

(2)錯(cuò)誤!未找到引用源。x錯(cuò)誤!未找到引用源。y(F(f(x,a),y)-F(f(y,a),x)

答：(D對(duì)于任意自然數(shù)x,都有2x=x,真值0.

(2)對(duì)于任意兩個(gè)自然數(shù)x,y,使得如果x+2=y,那么y+2=x.真值0.

11.判斷下列各式的類型：

(1)錯(cuò)誤！未找到引用源。

(3)錯(cuò)誤！未找到引用源。yF(x.y).

解：(1)因?yàn)閜f(q->p)o-ipv(->qvp)ol為永真式；

所以錯(cuò)誤！未找到引用源。為永真式；

(3)取解釋I個(gè)體域?yàn)槿w實(shí)數(shù)

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

所以，前件為任意實(shí)數(shù)x存在實(shí)數(shù)y使x+y=5,前件真；

后件為存在實(shí)數(shù)x對(duì)任意實(shí)數(shù)y都有x+y=5,后件假，］

此時(shí)為假命題

再取解釋I個(gè)體域?yàn)樽匀粩?shù)N,

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

所以，前件為任意自然數(shù)x存在自然數(shù)y使x+y=5,前件假。此時(shí)為假命題。

此公式為非永真式的可滿足式。

13.給定下列各公式一個(gè)成真的解釋，一個(gè)成假的解釋。

(1)錯(cuò)誤！未找到引用源。(F(x)錯(cuò)誤！未找到引用源。

(2)錯(cuò)誤！未找到引用源。x(F(x)錯(cuò)誤！未找到引用源。G(x)錯(cuò)誤！未找到引用源。

H(x))

解：(1)個(gè)體域:本班同學(xué)

F(x)：x會(huì)吃飯，G(x)：x會(huì)睡覺(jué).成真解釋

F(x)：x是泰安人,G(x)：x是濟(jì)南人.(2)成假解釋

(2)個(gè)體域:泰山學(xué)院的學(xué)生

F(x)：x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.

F(x)：x會(huì)吃飯,G(x)：x會(huì)睡覺(jué),H(x)：x會(huì)呼吸.成真解釋.

第五章部分課后習(xí)題參考答案

5.給定解釋I如下：

(a)個(gè)體域D=⑶4};

(b)](x)錯(cuò)誤！未找到引用源。為7(3)=4,7(4)=3錯(cuò)誤！未找到引用源。

(c)7(x,y)為7(3,3)=萬(wàn)(4,4)=0,萬(wàn)(3,4)=7(4,3)=1錯(cuò)誤！未找到引用源。.

試求下列公式在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))(本題課本上有錯(cuò)誤)

解：⑴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.在自然數(shù)推理系統(tǒng)F中，構(gòu)造下面推理的證明：

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

結(jié)論：3xR(x)

(2)前提:Vx(F(x)—(G(a)AR(x))),錯(cuò)誤！未找到引用源。xF(x)

結(jié)論:錯(cuò)誤！未找到引用源。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)⑤化簡(jiǎn)

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

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

第六章部分課后習(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.設(shè)a,b,c各不相同，判斷下述等式中哪個(gè)等式為真:

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

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

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

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

8.求下列集合的暴集：

⑴{a,b,c}P(A)={0,{a},,{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.化簡(jiǎn)下列集合表達(dá)式：

(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個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5

人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。

求不會(huì)打球的人數(shù)。

解：阿八={會(huì)打籃球的人},B={會(huì)打排球的人},C={會(huì)打|EI網(wǎng)球

的人}"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

不會(huì)打球的人共5人

21.設(shè)集合人={{1,2},{2,3},{1,3},{0}},計(jì)算下列表達(dá)式:

(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、設(shè)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)得證。

第七章部分課后習(xí)題參考答案

7.列出集合A={2,3,4}上的恒等關(guān)系1A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系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.設(shè)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.設(shè)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.設(shè)A={a,b,c,d},號(hào),R2為A上的關(guān)系，其中

與={{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.設(shè)人={1,2,3,4),在AxA上定義二元關(guān)系R,

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

(1)證明R是AxA上的等價(jià)關(guān)系.

(2)確定由R引起的對(duì)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是對(duì)稱的

任意的<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上的等價(jià)關(guān)系

(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.設(shè)A={1,2,3,4},R為AxA上的二元關(guān)系，V(a,b),<c,d)eAxA,

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

(1)證明R為等價(jià)關(guān)系.

(2)求R導(dǎo)出的劃分.

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

a+b=a+b

<a,b>R<a,b>

，R是自反的

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

設(shè)<a,b>R<c,d>,則a+b=c+d

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

，R是對(duì)稱的

任意的<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上的等價(jià)關(guān)系

(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.對(duì)于下列集合與整除關(guān)系畫(huà)出哈斯圖:

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

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

解：

⑵

45.下圖是兩個(gè)偏序集＜A,Ry＞的哈斯圖.分別寫(xiě)出集合A和偏序關(guān)系Ry的集合表達(dá)式.

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.分別畫(huà)出下列各偏序集<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)

項(xiàng)目(1)(2)

極大元：ea,b,d,e

極小元：aa,b,c,e

最大元：e無(wú)

最小元：a無(wú)

第八章部分課后習(xí)題參考答案

1.設(shè)f:NfN,且

1,若X為奇數(shù)

f(x)=土若X為偶數(shù)

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.判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的？

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

(2)f:N->N,f(x)=(x)mod3,x除以3的余數(shù)不是滿射，不是單射

1,若x為奇數(shù)

(3)f:N-N,Rx)=<不是滿射，不是單射

0,若x為偶數(shù)

0,若x為奇數(shù)

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

1，若x為偶數(shù)

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

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

5.設(shè)*=｛小娘｝,丫=｛1,2,3｝戶｛累,1>,<1),2>,?,3>,｝判斷以下命題的真假：

(l)f是從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的函數(shù)；對(duì)

(2)f是從X到Y(jié)的函數(shù)，但不是滿射，也不是單射的；錯(cuò)

(3)f是從X到Y(jié)的滿射，但不是單射；錯(cuò)

(4)f是從X到Y(jié)的雙射.錯(cuò)

第十章部分課后習(xí)題參考答案

4.判斷下列集合對(duì)所給的二元運(yùn)算是否封閉：

(1)整數(shù)集合Z和普通的減法運(yùn)算。

封閉，不滿足交換律和結(jié)合律，無(wú)零元和單位元

(2)非零整數(shù)集合錯(cuò)誤！未找到引用源。普通的除法運(yùn)算。不封閉

(3)全體〃x〃實(shí)矩陣集合錯(cuò)誤！未找到引用源。(R)和矩陣加法及乘法運(yùn)算，其中

n錯(cuò)誤！未找到引用源。2o

封閉均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律；

加法單位元是零矩陣，無(wú)零元；

乘法單位元是單位矩陣，零元是零矩陣；

(4)全體〃X〃實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n錯(cuò)誤！未找到引用源。

2o不封閉

(5)正實(shí)數(shù)集合錯(cuò)誤！未找到引用源。和錯(cuò)誤！未找到引用源。運(yùn)算，其中錯(cuò)誤！未

找到引用源。運(yùn)算定義為：

錯(cuò)誤！未找到引用源。

不封閉因?yàn)閘°l=lxl-l-l=-U/?+

(6)〃錯(cuò)誤！未找到引用源。關(guān)于普通的加法和乘法運(yùn)算。

封閉，均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律

加法單位元是0,無(wú)零元；

乘法無(wú)單位元零元是0;〃=1單位元是1

(7)A=｛%,?,…,4｝錯(cuò)誤！未找到引用源。n錯(cuò)誤！未找到引用源。運(yùn)算定義如下:

錯(cuò)誤！未找到引用源。

封閉不滿足交換律，滿足結(jié)合律,

(8)S=錯(cuò)誤！未找到引用源。關(guān)于普通的加法和乘法運(yùn)算。

封閉均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律

(9)S={0,1},S是關(guān)于普通的加法和乘法運(yùn)算。

加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律

(10)S=錯(cuò)誤！未找到引用源。與關(guān)于普通的加法和乘法運(yùn)算。

加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律

5.對(duì)于上題中封閉的二元運(yùn)算判斷是否適合交換律，結(jié)合律，分配律。

見(jiàn)上題

7.設(shè)*為Z+錯(cuò)誤！未找到引用源。上的二元運(yùn)算Vx,ywZ，，

X*Y=min(x,y),即x和y之中較小的數(shù).

⑴求4*6,7*30

4,3

(2)*在Z+上是否適合交換律，結(jié)合律，和累等律？

滿足交換律，結(jié)合律，和幕等律

(3)求*運(yùn)算的單位元，零元及Z+中所有可逆元素的逆元。

單位元無(wú)，零元1,所有元素?zé)o逆元

8.S=QxQ。為有理數(shù)集，*為$上的二元運(yùn)算，錯(cuò)誤！未找到引用源。<a,b〉,〈x,y〉

錯(cuò)誤！未找到引用源。S有

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

(1)*運(yùn)算在S上是否可交換，可結(jié)合？是否為累等的？

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

可結(jié)合：(<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)*運(yùn)算是否有單位元，零元？如果有請(qǐng)指出，并求S中所有可逆元素的逆元。

設(shè)va,b>是單位元，錯(cuò)誤！未找到引用源。vx,y>錯(cuò)誤！未找到引用源。S,va,b

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

貝(jvax,ay+b>=vxa,xb+y>=vx,y>，解的<a,b>=<l,0>，即為單位。

設(shè)va,b>是零元，錯(cuò)誤！未找到引用源。vx,y>錯(cuò)誤！未找到引用源。S，<a,b

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

貝(Jvax,ay+b>=vxa,xb+y>=va,b>,無(wú)解。即無(wú)零元。

錯(cuò)誤！未找到引用源。vx,y>錯(cuò)誤！未找到引用源。S,設(shè)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

所以當(dāng)xwO時(shí)，<x,y>T1_y

X，X

10.々S={a,b},S上有四個(gè)運(yùn)算：*,錯(cuò)誤！未找到引用源。分別有表10.8確定。

*aboab*ab□ab

aaaaababaaab

baabbabaabab

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

(1)這4個(gè)運(yùn)算中哪些運(yùn)算滿足交換律，結(jié)合律，幕等律？

(a)交換律，結(jié)合律，嘉等律都滿足，零元為a,沒(méi)有單位元；

(b)滿足交換律和結(jié)合律，不滿足嘉等律，單位元為a,沒(méi)有零元

a'-a,bi-h

⑹滿足交換律，不滿足嘉等律,不滿足結(jié)合律

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

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

沒(méi)有單位元，沒(méi)有零元

(d)不滿足交換律，滿足結(jié)合律和幕等律

沒(méi)有單位元，沒(méi)有零元

⑵求每個(gè)運(yùn)算的單位元，零元以及每一個(gè)可逆元素的逆元。

見(jiàn)上

16.設(shè)V=〈N,+,錯(cuò)誤！未找到引用源。〉，其中+,錯(cuò)誤！未找到引用源。分別代

表普通加法與乘法，對(duì)下面給定的每個(gè)集合確定它是否構(gòu)成V的子代數(shù)，為什么？

(1)S尸錯(cuò)誤！未找到引用源。是

(2)S產(chǎn)錯(cuò)誤！未找到引用源。不是加法不封閉

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

第十一章部分課后習(xí)題參考答案

8.設(shè)S={0,1,2,3},?為模4乘法，即

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

問(wèn)〈S,8〉是否構(gòu)成群？為什么？

解：(1)VX,yes,xay=(xy)mod4eS,?是S上的代數(shù)運(yùn)算。

(2)Vx,y,zWS,設(shè)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),結(jié)合律成立。

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

(4)r'=1,3T=3,0和2沒(méi)有逆元

所以，〈S,不構(gòu)成群

9.設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算。如下：

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

問(wèn)z關(guān)于。運(yùn)算能否構(gòu)成群？為什么？

解：⑴Vx,yGZ,xoy=x+y-2eZ,o是Z上的代數(shù)運(yùn)算。

(2)Vx,y,zGZ,

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

同理(xoy)oz=xo(yoz),結(jié)合律成立。

⑶設(shè)e是單位元，VxGZ,xoe=eox=x,x+e-2=e+x-2=x,e=2

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

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

所以〈Z,o）構(gòu)成群

1L設(shè)G=M°1P°1f；1，[仁1°j],證明G關(guān)于矩陣乘法構(gòu)成-個(gè)群.

llo1Jlo-1Jlo1Jlo-1JJ

解：(1)Vx.yGG,易知xyWG,乘法是Z上的代數(shù)運(yùn)算。

(2)矩陣乘法滿足結(jié)合律

(3)設(shè)|是單位兀，

10V

(4)每個(gè)矩陣的逆元都是自己。

所以G關(guān)于矩陣乘法構(gòu)成一個(gè)群.

14.設(shè)G為群，且存在a￡G,使得

G={akIkez}

證明：G是交換群。

證明：Vx,yCG,設(shè)x=y=a',貝U

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

所以，G是交換群

17.設(shè)G為群，證明e為G中唯一的幕等元。

證明：設(shè)e°eG也是幕等元，則e；=e°,即e：=e°e,由消去律知e°=e

18.設(shè)G為群，a,b,c￡G,證明

Iabc|=Ibca|=Icab|

證明：先證設(shè)(abc)，=eo(bca)*=e

設(shè)(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

反過(guò)來(lái)，設(shè)(bac)k=e,則(abc?=e.

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

19.證明：偶數(shù)階群G必含2階元。

證明：設(shè)群G不含2階元，VaeG,當(dāng)a=e時(shí)，。是一階元，當(dāng)a/e時(shí)，。至少是3

階元,因?yàn)槿篏時(shí)有限階的，所以a是有限階的，設(shè)。是k階的，則qT也是k階的，所以

高于3階的元成對(duì)出現(xiàn)的，G不含2階元，G含唯一的1階元e,這與群G是偶數(shù)階的矛

盾。所以，偶數(shù)階群G必含2階元

20.設(shè)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含至少含一個(gè)3階元，設(shè)為a,則OHM,且小。=”/。

令方=。2的證。

21.設(shè)G是M.(R)上的加法群，n22,判斷下述子集是否構(gòu)成子群。

(1)全體對(duì)稱矩陣是子群

(2)全體對(duì)角矩陣是子群

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

(4)全體上(下)三角矩陣。是子群

22.設(shè)G為群，a是G中給定元素，a的正規(guī)化子N(a)表示G中與a可交換的元素構(gòu)成

的集合，即

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

證明N(a)構(gòu)成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òu)成G的子群

31.設(shè)外是群&到Gz的同態(tài)，夕2是邑到G：,的同態(tài)，證明外。夕2是&到G：,的同態(tài)。

證明：有已知夕1是G1到G2的函數(shù)，82是G2到G3的函數(shù)，則01?夕2是G1到G3的函數(shù)。

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

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

所以：8?小是1到G3的同態(tài)。

33.證明循環(huán)群一定是阿貝爾群，說(shuō)明阿貝爾群是否一定為循環(huán)群，并證明你的結(jié)論。

證明：設(shè)G是循環(huán)群,令G=<a>,Vx,yeG,令x==/,那么

k1kilhk1k

xy=aa=a-a=aa=yxtG是阿貝爾群

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

Oeabc

abc

aaecb

bb

chae

是交換群,但不是循環(huán)群,因?yàn)閑是一階元，a,b,c是二階元。

36.設(shè)。/是5元置換，且

（12345）（12345、

O'==，T=

（21453）（34512）

⑴計(jì)算or,T(y,T~',；

（2）將.er,尸，b-，cr表成不交的輪換之積。

(3)將(2)中的置換表示成對(duì)換之積，并說(shuō)明哪些為奇置換，哪些為偶置換。

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)奇置換

第十四章部分課后習(xí)題參考答案

5、設(shè)無(wú)向圖G有10條邊，3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于3,問(wèn)G至

少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫(xiě)出度數(shù)列、A(G)、b(G)。

解：由握手定理圖G的度數(shù)之和為：2x10=20

3度與4度頂點(diǎn)各2個(gè)，這4個(gè)頂點(diǎn)的度數(shù)之和為14度。

其余頂點(diǎn)的度數(shù)共有6度。

其余頂點(diǎn)的度數(shù)均小于3,欲使G的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取2,

所以,G至少有7個(gè)頂點(diǎn)，出度數(shù)列為3,3,4,4,2,2,2,A(G)=4,3(G)=2.

7、設(shè)有向圖D的度數(shù)列為2,3,2,3,出度列為1,2,1,1,求D的入度列，并求A(D),b(。)，

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

解：D的度數(shù)列為2,3,2,3,出度列為1,2,1,1,D的入度列為1,1,1,2.

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

8、設(shè)無(wú)向圖中有6條邊，3度與5度頂點(diǎn)各1個(gè)，其余頂點(diǎn)都是2度點(diǎn)，問(wèn)該圖有多少

個(gè)頂點(diǎn)？

解：由握手定理圖G的度數(shù)之和為：2x6=12

設(shè)2度點(diǎn)x個(gè)，則3xl+5xl+2x=12,x=2,該圖有4個(gè)頂點(diǎn).

14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對(duì)可圖化的數(shù)列，試給出3種非同

構(gòu)的無(wú)向圖，其中至少有兩個(gè)時(shí)簡(jiǎn)單圖。

(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是奇數(shù)，不可圖化；

(2)2+2+2+2+3+3+4+4=16,是偶數(shù)，可圖化；

18、設(shè)有3個(gè)4階4條邊的無(wú)向簡(jiǎn)單圖Gi、G2、G3,證明它們至少有兩個(gè)是同構(gòu)的。

證明：4階4條邊的無(wú)向簡(jiǎn)單圖的頂點(diǎn)的最大度數(shù)為3,度數(shù)之和為8,因而度數(shù)列

為2,2,2,2；3,2,2,1；3,3,1,1。但3,3,1,1對(duì)應(yīng)的圖不是簡(jiǎn)單圖。所以

從同構(gòu)的觀點(diǎn)看，4階4條邊的無(wú)向簡(jiǎn)單圖只有兩個(gè)：

所以，G］、G2,G3至少有兩個(gè)是同構(gòu)的。

20、已知n階無(wú)向簡(jiǎn)單圖G有m條邊，試求G的補(bǔ)圖3的邊數(shù)〃。

AX,,n(n-1)

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

2

21、無(wú)向圖G如下圖

(1)求G的全部點(diǎn)割集與邊割集，指出其中的割點(diǎn)和橋；

(2)求G的點(diǎn)連通度k(G)與邊連通度2(G)。

解：點(diǎn)割集：{a,b},(d)

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

%(G)=4(G)=1

23、求G的點(diǎn)連通度MG)、邊連通度4(G)與最小度數(shù)仇G)。

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

28、設(shè)n階無(wú)向簡(jiǎn)單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問(wèn)這樣的無(wú)向圖有幾種

非同構(gòu)的情況？

I3〃=2m/口

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

2n-3=m

31、設(shè)圖G和它的部圖。的邊數(shù)分別為加和帚，試確定G的階數(shù)。

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

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

22

45、有向圖D如圖

(1)求叱到匕長(zhǎng)度為1，2,3,4的通路數(shù)；

(2)求看到匕長(zhǎng)度為1，2,3,4的回路數(shù);

(3)求D中長(zhǎng)度為4的通路數(shù)；

(4)求D中長(zhǎng)度小于或等于4的回路數(shù)；

(5)寫(xiě)出D的可達(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)匕到匕長(zhǎng)度為1，2,3,4的通路數(shù)為0,2,0,0；

(2)%到以長(zhǎng)度為1，2,3,4的回路數(shù)為0,0,4,0；

(3