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

16設p、q的真值為0；r、s的真值為1,求以下各命題公式的真值。

⑴pV(qAr)<=>0V(0A1)<=>0

(2)(p-r)Z\(—<qVs)=(0-1)A(1VI)<^OA1<=>0.

(3)(->pA-nqAr)<->(pAqA—>r)<=>[1A1A1)—(0A0A0)<^>0

(4)LrAs)[0A1)-(1A0)O0f001

17.判斷下面一段論述是否為真：“乃是無理數。并且，如果3是無理數，則艱也是無理數。另外

6能被2整除，6才能被4整除。"

答：p：萬是無理數1

q:3是無理數0

r:正是無理數1

s:6能被2整除1

t:6能被4整除0

命題符號化為：pA(q-r)八(t~s)的真值為1,所以這一段的論述為真。

19.用真值表判斷以下公式的類型：

(4)(p-q)-(-iq-*-'p)

⑸(pAr)0(-'pA-1q)

⑹((pfq)A(q^r))—(p^r)

答：⑷

pqp—q「qf「p(pfq)f(「qf「p)

00iii11

01i0i11

1001001

iii0011

所以公式類型為永真式

(5)公式類型為可滿足式(方法如上例)

(6)公式類型為永真式(方法如上例)

第二章局部課后習題參考答案

3.用等值演算法判斷以下公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.

⑴「(p/Xq—q)

(2)(p-(pVq))V(p-r)

(3)(pVq)-*(pAr)

答：(2)(pf(pVq))lpV(pVq))V(-'pVr)<=>-'pVpVqVr<=>1

所以公式類型為永真式

(3)PqrpVqpAr(pVq)--(pAr)

00000I

001001

010100

011100

100100

101111

110100

111111

所以公式類型為可滿足式

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

(2)(pfq)A(p-*r)<=>(p-(qAr))

(4)(pA-'q)V(->pAq)<=>(pVq)AfpAq)

證明(2)(pfq)A(p-r)

。([pVq)ALpVr)

。「pV(qAr))

Opf(qAr)

(4)(pA^q)V(-'pAq)<=>(pV(-'pAq))A(「qV(「p/\q)

oSV^p)A(pVq)ACqV』)A(-'qVq)

O1A(pVq)A-1(pAq)A1

O(pVq)A(pAq)

5.求以下公式的主析取范式與主合取范式，并求成真賦值

(1)(-ip^-q)—(->qVp)

(2)(p-q)AqAr

⑶(pV(qAr))—(pVqVr)

解：

(1)主析取范式

(->pfq)f(->qvp)

O(pvq)V(->qvp)

=(』人一'q)v(-iqvp)

O(-1pA-?q)V(-iqAp)V(-'qA-ip)v(pAq)V(pA-1q)

O(-?p人-iq)V(pAiq)V(pAq)

OE(0,2,3)

主合取范式：

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

O「(pvq)V(->qvp)

O(~|pA-iq)v(-'qVp)

O(-|pv(->qvp))A(-iqv(-iqvp))

o1A(pV-iq)

(pV-1q)U*Mi

0ri⑴

(2)主合取范式為：

—1(p—q)AqArO—?(一)pvq)Aq/\r

01(pA-1q)AqAr='0

所以該式為矛盾式.

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

矛盾式的主析取范式為0

(3)主合取范式為：

(pv(qAr))—(pvqvr)

O-1(pv(qAr))~*(pvqvr)

<=>(-'PAC-'qv-'r))v(pvqvr)

<=>(-'pv(pvqvr))A((-'qv-'r))v(pvqvr))

<=>1A1

01

所以該式為永真式.

永真式的主合取范式為1

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

第三章局部課后習題參考答案

14.在自然推理系統P中構造下面推理的證明：

(2)前提：pfq,-I(qAr),r

結論：—1p

(4)前提：q-?p,q—s,sCt,tAr

結論：pAq

證明：（2）

①—i(qAr)前提引入

(2)-iqv-ir①置換

③qf-ir②蘊含等值式

④r前提引入

⑤-iq③④拒取式

@p->q前提引入

⑦「P(3)⑤⑥拒取式

證明(4)：

①t/\r前提引入

②t①化簡律

③q—s前提引入

④s—t前提引入

⑤q—t③④等價三段論

⑥(qft)人(tfq)⑤置換

⑦(qft)⑥化簡

⑧q②⑥假言推理

⑨qfp前提引入

⑩P⑧⑨假言推理

(ll)pAq⑧⑩合取

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

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

結論：s—>r

證明

①s附加前提引入

②sfp前提引入

③P①②假言推理

④pf(qfr)前提引入

⑤qfr③④假言推理

⑥q前提引入

⑦r⑤⑥假言推理

16在自然推理系統P中用歸謬法證明下面各推理:

(1)前提：->rvq,rA-iS

結論：—ip

證明：

①p結論的否認引入

②p->「q前提引入

③「q①②假言推理

④「rvq前提引入

⑤「r④化簡律

@rA^s前提引入

⑦r⑥化簡律

⑧rA—>r⑤⑦合取

由于最后一步rA「r是矛盾式,所以推理正確.

第四章局部課后習題參考答案

3.在一階邏輯中將下面將下面命題符號化，并分別討論個體域限制為(a),(b)條件時命題的真值:

(1)對于任意x,均有”-2=(X+V2)(X-V2).

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

其中(a)個體域為自然數集合.

(b)個體域為實數集合.

解：

F(x)：x：-2=(x+\7)(x-vT).

G(x):x+5=9.

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

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

4.在一階邏輯中將以下命題符號化：

(1)沒有不能表示成分數的有理數.

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

解：

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

H(x):x是有理數

命題符號化為：「3x(「尸(x)A”(幻)

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

H(x):x是外地人

命題符號化為：「也(尸(x)f〃(x))

5.在一階邏輯將以下命題符號化：

(1)火車都比輪船快.

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

解：

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

命題符號化為：VxVy((F(x)AG(y))fH(x,y))

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

命題符號化為：「寺(G(y)AV%(F(x)->H(x,y)))

9.給定解釋I如下：

(a)個體域D為實數集合R.

(b)D中特定元素3=0.

(c)特定函數i(x,y)=x—y,x,yeD.

(d)特定謂詞寺定,y):x=y,G(x,y):x<y,x,ye￡).

說明以下公式在I下的含義,并指出各公式的真值：

答：(1)對于任意兩個實數x,y,如果x<y,那么xHy.真值1.

(2)對于任意兩個實數x,y,如果x-y=0,那么x〈y.真值0.

10.給定解釋I如下：

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

(b)D中特定元素3=2.

(c)D上函數=x+y,g(x,y)=xy.

(d)D上謂詞f(x,y):x=y.

說明以下各式在I下的含義，并討論其真值.

(1)VxF(g(x,a),x)

(2)VxVy(F(f(x,a),y)-F(f(y,a),x)

答：(1)對于任意自然數x,都有2x=x,真值0.

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

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

⑴P(xy)-*(G(xy)-?F(xy)).

(3)rxE'F-x.v)-?BxiyF(x,y).

解：⑴因為>(q->p)vp)o1為永真式；

所以F?;???C--.：??1?"I為永真式；

(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.給定以下各公式一個成真的解釋，一個成假的解釋。

⑴W(F(x)vG(X)]

(2)3X(F(X)AG(X)AH(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.確定以下命題是否為真：

(1)0C0真

(2)假

(3)0c{0}真

(4)0e{0}真

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

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

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

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

6.設a,b,c各不一樣，判斷下述等式中哪個等式為真:

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

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

(3){{a},{b}}={{a,b}}假

⑷{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}}

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

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

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

14.化簡以下集合表達式：

(1)(AUB)AB)-(AUB)

⑵KAUBUC-(BUC))UA

解：

(i)(AUB)HB)-(AUB)=(AUB)HB)八?(AUB)

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

(2)((AUBUO-(BUO)UA=((AUBUOn?(BUO)UA

=sn?(BUC))U((BUC)n?(BUC))UA

=(AH~(BlJc))U0UA=(AQ~(BlJc))UA=A

18.某班有25個學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球

和網球，還有2人會打這三種球。6個會打網球的人都會打籃球或排球。

求不會打球的人數。|￡一

解：阿人={會打籃球的人},B={會打排球的人},C={會打網球的人}A(sV

A|=14,B|=12,|A0B|=6,|AC|=5,|ADBDC|=2,

|CH6,CCAUBI'|

如以以下圖。

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

不會打球的人共5人

21.設集合人={{1,2},⑵3},{1,3},{0}),計算以下表達式：

(1)UA

(2)nA

(3)nuA

⑷unA

解:⑴uA={1,2}U{2,3}U{1,3}U{0}={1,2,3,0}

(2)nA={I,2)n{2,3)nu,3)n{。}=。

(3)nuA=in2n3n0=0

⑷unA=0

27、設A,B,C是任意集合，證明

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

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

證明

(1)(A-B)-C=(AQ-B)A-C=Ap(-BA-C)=AQ~(B^C)=A-BOC

(2)(A-c)-(B-c)=(An-c)n-(Bn-c)=sn?on(?BUC)

=(An~cn~B)u(Ap~cn0=(An~cn?B)U0

=Afi~(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>}

D*={<2,4>}

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

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

求AUB,AcB,domA,domB,dom(A。B),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(ACB)={4}

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

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

求R°R,R1,RT{0,1,},R[{1,2}]

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

R',={<1(0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}

RT{0,l}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}

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

16.設A={a,b,c,d},&&為A上的關系，其中

R]={人a,好,卜4}

求一火21&。

解：Ri°R2={<a,d>,<a,c>,<a,d>}

R2ORF{<C>d>}

RI2=RI°Ri={<a,a>,<a,b>,<a,d>}

2

R2=R2。R={<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>EAxA,<u,v>R<x,y><=>u+y=x+v.

(1)證明R是AxA上的等價關系.

(2)確定由R引起的對AxA的劃分.

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

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

V<u,v>￡AxA

U-V=U-V

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

???R是自反的

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

如果<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>

貝lju-v=x-y,x-y=a-b

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

???R是傳遞的

???R是AXA上的等價關系

(2)n={{<l,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)WAxA,

〈a,b〉R(c,d)Oa+b=c+d

(1)證明R為等價關系.

(2)求R導出的劃分.

(1)證明：V<a,b)GAXA

a+b=a+b

A<a,b>R<a,b>

???R是自反的

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

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

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

JR是對稱的

任意的b>,<c,d>,<x,y>@AXA

假設<a,b>R<c,d>,<c,d>R<x,y>

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

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

???R是傳遞的

，R是AXA上的等價關系

(2)n={{<1,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}

解：

(1)(2)

45.以以以下圖是兩個偏序集＜A,R.＞的哈斯圖.分別寫出集合A和偏序關系R.的集合表達式.

(a)(b)

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

R.；={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>)D1A

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

R.(={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}1A

46.分別畫出以下各偏序集<A,R->的哈斯圖,并找出A的極大元'極小元'最大元和最小元.

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

R.(={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}□L.

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

解：

(1)(2)

工程(1)(2)

極大元：ea,b,d,e

極小元：aa,b,c,e

最大元：e無

最小元：a無

第八章局部課后習題參考答案

1.設f:NfN,且

L若x為奇數

f⑻=一若%為偶數

求￡(0),“{0})」(1),“{1})」({0,2,4,6「?})，￡({468}),f'({3,5,7)).

解:f(0)=0,f({0})={Q),f(1)=1,f({l})={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:NTN,f(x)=(x)mod3,x除以3的余數不是滿射，不是單射

1若x為奇數

⑶f:NfN,f(x)=，2“…不是滿射，不是單射

[0,若x為偶數

[0,若X為奇數日….7VA上

(4)f:Nf{0,l},f(x)={H/田期是滿射，不是131單射

1,右X為偶數

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

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

5.設X={a,b,c,d},Y={l,2,3},f={<a,l>,<b,2>,<c,3>,}判斷以下命題的真假:

(l)f是從X到Y的二元關系，但不是從X到Y的函數；對

(2)f是從X到Y的函數，但不是滿射，也不是單射的；錯

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

(4)f是從X到Y的雙射.錯

第十四章局部課后習題參考答案

5、設無向圖G有10條邊，3度與4度頂點各2個，其余頂點的度數均小于3,問G至少有多少個頂

點在最少頂點的情況下，寫出度數列、A(G)、3(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,5(G)=2.

7、設有向圖D的度數列為2,3,2,3,出度列為1,2,1,1,求D的入度列，并求△(￡>),5(。)，

A+(D),△(￡>),A-(D),S-(D).

解：D的度數列為2,3,2,3,出度列為1,2,1,1,D的入度列為1,1,1,2.

△(。)=3?(。)=2,4+(。)=2@+(。)=1,△-(/))=2,<T(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的邊數根'。

版,n(n-1)

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

2

21、無向圖G如以以以下圖

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

(2)求G的點連通度A(G)與邊連通度/1(G)。

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

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

左(G)=4(G)=1

23、求G的點連通度％(G)、邊連通度4(G)與最小度數演G)。

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

28、設n階無向簡單圖為3-正則圖，且邊數m與n滿足2n-3=m問這樣的無向圖有幾種非同構的情

況

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

2n-3=m

31、設圖G和它的部圖3的邊數分別為加和加，試確定G的階數。

5—n{n+1)?—1+-v1+8(m+m)

解：m+m=------得z,=-------------------

22

45、有向圖D如圖

⑴求叱到七長度為1，2,3,4的通路數；

(2)求看到為長度為1，2,3,4的回路數；

(3)求D中長度為4的通路數；

(4)求D中長度小于或等于4的回路數；

(5)寫出D的可達矩陣。

解：有向圖D的鄰接矩陣為：

"0000r'01010、’20200、

101000000202020

A=00001,A2=01010屋=20200

101000000202020

、01010,、20200,、00004,

(1)匕到也長度為1，2,3,4的通路數為0,2,0,0；

⑵%到為長度為1，2,3,4的回路數為0,0,4,0；

(3)D中長度為4的通路數為32；

(4)D中長度小于或等于4的回路數10；

'11111、

11111

(4)出D的可達矩陣P=11111

11111

J-1b

第十六章局部課后習題參考答案

1＞畫出所有5階和7階非同構的無向樹.

2、一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，問T有幾個頂點?

解：設3度分支點X個，則

5xl+3x2+3x=2x(5+3+x-l),解得x=3

T有11個頂點

3、無向樹T有8個樹葉，2個3度分支點，其余的分支點都是4度頂點，問T有幾個4度分支

點根據T的度數列，請至少畫出4棵非同構的無向樹。

解：設4度分支點X個，則

8xl+2x3+4x=2x(8+2+x—1),解得x=2

度數列111111113344

4、棵無向樹T有%(i=2,3,k)個i度分支點，其余頂點都是樹葉，問T應該有幾片樹葉?

解：設樹葉x片，則

n,.xz+xx1=2x(n.+%-1),解得x=(i-2)%+2

評論：2,3,4題都是用了兩個結論，一是握手定理，二是加=〃一1

5、n(n》3)階無向樹T的最大度A(T)至少為幾最多為幾

解：2,n-1

6、假設n(n23)階無向樹T的最大度A(T)=2,問T中最長的路徑長度為幾

解：n-1

7、證明：n(n22)階無向樹不是歐拉圖.

證明：無向樹沒有回路，因而不是歐拉