離散數(shù)學(xué)及其應(yīng)用(課后習(xí)題)

習(xí)題1.1

2.指出下列命題是原子命題還是復(fù)合命題。

（3）大雁北回，春天來了。

（4）不是東風(fēng)壓倒西風(fēng)，就是西風(fēng)壓倒東風(fēng)。

（5）張三和李四在吵架。

解：（3）和（4）是復(fù)合命題，（5）是原子命題。

習(xí)題1.2

1.指出下列命題的真值：

（1）若2+2>4,則太陽從西方升起。

解：該命題真值為T（因為命題的前件為假）。

（3）胎生動物當(dāng)且僅當(dāng)是哺乳動物。

解：該命題真值為F（如鴨嘴獸雖是哺乳動物，但不是胎生動物）。

2.令P：天氣好。Q：我去公園。請將下列命題符號化。

（2）只要天氣好，我就去公園。

（3）只有天氣好，我才去公園。

（6）天氣好，我去公園。

解：（2）P―>Q。

（3）Q—?P。

（6）PC。。

習(xí)題1.3

2.將下列命題符號化（句中括號內(nèi)提示的是相應(yīng)的原子命題的符號表示）:

（1）我去新華書店（P）,僅當(dāng)我有時間（。）。

（3）只要努力學(xué)習(xí)（P）,成績就會好的（。）。

（6）我今天進(jìn)城（尸），除非下雨（。）。

（10）人不犯我（P）,我不犯人（。）；人若犯我，我必犯人。

解：（1）P-?Q。

（3）PTQ。

（6）—\Q—>Po

（10）（—\P—>―iQ）A（P-■

習(xí)題1.4

1.寫出下列公式的真值表:

(2)PvfR)。

解：該公式的真值表如下表:

pQRQfRPv(QfR)

00011

00111

01000

01111

10011

10111

11001

11111

2.證明下列等價公式：

(2)(PvQ)人「(PAQ)。一^^―。)。

證明：

」(PC。)=->((PA。)VA[0))

=「(PA。)人一?(-1P人]。))

U>「(PAQ)A(PV。)

=(PV。)人」(PA0)

(4)(PfO)A(PfR)oPf(QAR)。

證明：

(PfQ)A(PfBOJPVSAJPVR)

0->PV(QAR)

=Pf(。人R)

3.甲、乙、丙、丁4人參加考試后，有人問他們誰的成績最好，甲說，不是我。乙說：是

丁?丙說：是乙。丁說：不是我。已知4個人的回答只有一個人符合實際，問成績最好的是

誰？

解：設(shè)A：甲成績最好。乙成績最好。C：丙成績最好。O：丁成績最好。

四個人所說的命題分別用尸、Q、RS表示，則

P—iA；Q<=>—iAA―\BA—\CAD；R<=>—\AABA―\CA-\D；S<=>―iD。

則只有一人符合實際的命題K符號化為

K<=>(PA—iQA—i/?A—iS)V(—iPA0A—i/?A—iS)V(—iPA—1。A/?A-iS)V(—iPA—1。A—i/?AS)

PA―\QA—\RA—\S-IAA-i(-IAA-IJBA"—\CAD)A—1(—IAAA-iCA―i￡))A￡)

<=>-iAA(4vBvCv-i￡>)A(Av「BvCVD)AD

今(-iAAZ))A(AvBvCv-J))A(Av-iBvCvD)

0(-v4ABACAZ))V(-V4ABAD)V(-IAA-IBACAD)V(-IAACAD)

oO;

同理，

—IJPA<2A—I/?A-ISAA—I/4A—iBA—iCAA)A—1(—iAABA—iCA—J9)AO0;

—iPA—1。A/?A—iS<=>AA_1(—iAA—iBA—iCA。)A—iAABA—iCA—iDAZ)<=>0；

―\PA―I。A—iRASA,A-1(—iAA—\BA-iCAD)A—1(—iAABA—iCA-iD)A—J)

<=>AA(AvBvCv-J))A(Av-iBVCVZ))A-IZ)

AA-\D,

所以，當(dāng)K為真時，4人「。為真，即甲的成績最好。

習(xí)題1.5

2.證明下列各蘊(yùn)含式：

(3)Pf(QfR)=(PfQ)f(PfK)。

證明：

方法一：真值表法(列出命題公式(尸f(Qf/?))->((Pf。)f(Pf/?))的真值表)。

PQRPT。PTR0TKPT(QTR)(PTQ)T(PTR)

000111111

001111111

010110111

011111111

100001111

101011111

110100001

111111111

方法二：等值演算法

(P->(QfR))f((P->?)-?(PfR))

oTP->(QfR))v((P—Q)f(P->R))

Ov(—iQvR))v—1(—iPvQ)v(—iPvR)

=(PA<2A-iZ?)v(PA-I0)V(—>/>v/f)

=(PAQA-17?)v((Pv—iPvZ?)A(—1。v—iPvR))

=(PAQA-1/?)V(-10V-iPVR)

0(Pv—iQv—iPvR)v(Qv—iQv—iPv7?)v(—>Rv-iQv-iPvR)

o1.

方法三：分析法

(1)直接分析法：若前件Pf(QfR)為真，分兩種情況：

(I)尸為假，則尸一>。為真，P—R為真，(PfQ)-?(PfR)為真。

(II)尸為真，則QfR為真，此時若。為真，則R為真，則Pf。為真，PTR為

真，(PfQ)f(PfR)演；若。搬，則PfR為假，(PfQ)f(PfR)

為真。

綜上，若前件為真，后件必為真，故該蘊(yùn)含式成立。

(2)間接分析法：若后件(Pf。)-?(PfR)為假，則尸一。為真，PfR為假。由

PfR為假可知，P為真,R為假。再由尸一>?？芍?。為真。此時0fR為假，

Pf(QfR)為假，即前件為假。故蘊(yùn)含式成立。

5.敘述下列各個命題的逆換式和逆反式，并以符號寫出。

(1)如果下雨，我不去。

解：設(shè)P：天下雨。Q：我去。

逆換式：如果我不去，天就下雨。符號表示為-?p。

逆反式：如果我去，天就不下雨。符號表示為0T「尸。

(2)僅當(dāng)你走我將留下。

解：設(shè)P：我留下。Q：你走。

逆換式：如果你走，我就留下。符號表示為：2f尸。

逆反式：如果你不走，我就不留下。符號表示為：「。一>->尸。

習(xí)題1.6

2.將下列命題公式用只含V和「的等價式表達(dá)，并要求盡可能簡單。

(1)(P/\Q)A-\P?

解：(尸人。)人一!尸=(尸八一1尸)人。=0人。=0.

(2)(P->(Qv-i/?))A-\PAQ,

解：(Pf(Qv-iK))人「尸八2=

。(-|PV(2V—iR)A-1PAQ=(-|PA-|PA0)V(-1PA0A0)V(-iPA0A-i/?)

=(「PA2)V(-IP/\2)V(-IPAQA「K)=(「PA2)V(「P/\2A「K)

=(一|尸A0)V(一1尸A0A—iR)=-1尸AQ

=TPv「O).

(3)―\PA-\QA(―\R―?P).

解：一iPA「2/\(「RfP)=」PA-i0A(/?vP)

。(-|PA-iQA/f)V(-|PA-10八P)。(-|PA-iQA/?)V0

=-tPA-iQ人R=-i(Pv0V

習(xí)題1.7

6.求下列命題公式的主析取范式和主合取范式：

(1)((Pv。)-R)f尸,

解：((Pv。)-R)fP=TTPv?)vR)vP

=((PvQ)/\T?)vP=(PvQvP)/\(PvM)=(Pv2)/\(PvT?)

=(PV0V(7?A-iUJ))A(PV(2A-I0)v-J?)

=(PV0V7?)A(PV0V-IJR)A(PV2V-d?)A(PV-10v-d?)

=(尸v。vK)八(Pv。v-uR)A(Pv-i。v—iR)

0Mo人加1人知3(主合取范式)

m2vvm5v/w6vm7.(主析取范式)

習(xí)題1.8

1.證明（」Pv「。）人（「尸一＞R）A（Rf-1s）=Sf[0.

證明：(1)sp（附加前提）

(2)R―>—iSp

(3)S—>―JiT(2)E

(4)T(1)(3)I

(5)-uPfRP

(6)PT(5)E

(7)PT(4)(6)I

(8)—iPv—iQP

(9)-'QT(7)(8)I

(10)CP

2.用間接證法證明Pf（[0-?R）,Q--iP，S—>―iR，P=―\S.

證明：(1)sp(附加前提)

(2)Sp

(3)-)/?T(1)(2)I

(4)PP

(5)P—>(-iQ—>R)P

(6)—iQ—>RT(4)((5)I

⑺。T(3)(6)I

(8)QfMP

⑼「pT(7)(8)I

(10)PA-1P(矛盾式)T(4)(9)I

由（10）得出了矛盾，根據(jù)歸謬法說明原推理正確。

5.“如果下雨，春游就會改期：如果沒有球賽，春游就不會改期。結(jié)果沒有球賽，所以沒有

下雨?！弊C明上述論斷正確。

解設(shè)P：下雨。0：有球賽。R：春游改期。則上述論斷轉(zhuǎn)化為要證明PTR,

—iQ=—iP.

證：⑴一p

(2)P

(3)-iRT(1)(2)I

(4)PTRP

(5)—\PT(3)(4)I

因此，上述推理正確。

7.證明RvS是前提Cv0,CTR,OfS的有效結(jié)論。

證明：(1)CvDP

(2)T(1)E

(3)DTSP

(4)-.C-?ST(2)(3)I

(5)CTRP

(6)—\R―>—\CT(5)E

(7)—\R―>ST(4)(6)I

(8)R7sT(7)E

習(xí)題2.1

用謂詞表達(dá)式寫出下列命題：

(5)每個有理數(shù)是實數(shù)。

解：Vx(Q(x)fR(x)),其中Q(x)：x是有理數(shù)。R(x)：x是實數(shù)。

(6)有的函數(shù)連續(xù)。

解：3X(F(X)AC(X)),其中尸(x)：x是函數(shù)。C(x)：x連續(xù)。

習(xí)題2.2

2.將下列命題符號化：

(3)沒有人登上過木星。

解：設(shè)M(x)：x是人。A(x)：x登上過木星。則命題可表示為T3O(M(x)人A(x)).

3.符號化下列命題：

(2)盡管有人聰明，但未必一切人都聰明。

解：設(shè)M(x)：x是人。C(x)：x聰明。則命題可表示為

3x(M(x)AC(X))A-nVx(M(x)->C(x)).

習(xí)題2.3

2.對下列謂詞公式中約束變元進(jìn)行換名：

(1)Vx3j(P(x,z)->0(j))oS(x,j)

(2)(Vx(P(x)f(R(X)VQ(X)))ANAx))f土S(X,Z)

解(1)Vw3v(P(w,z)0(v))<4-5(x,j)

(2)(Vw(P(w)—>(!?(?)v<2(?)))A3vl?(v))-?3zS(x,z)

3.對下列謂詞公式中自由變元進(jìn)行代入：

(1)Vx^tr,z))A3xVzC(x,y,z)

(2)(VJP(X,J)A3Z0(X,Z))VVXgy)

解(1)(3jA(s,j)->Vxfi(x,w))A3XVZC(X,/,Z)

⑵(VyP(s,y)人士。(s,z))vVxR(x,f)

習(xí)題2.4

3.證明下列等價式：

(1)-i3r(P(X)A0(x))=Vx(p(x)f-i(2(x)).

證明:-3X(P(X)AQ(X))

0Vx「(P(x)人。(x))

oVx(「P(x)v[Q(x))

oVx(P(x)f[0(x))

(2)-iVx(P(X)->2(x))O3x(p(x)A-I0(x)).

證明：-1Vx(P(X)TQ(X))

o3x「(P(x)f0(x))

o3x->(-iP(x)vo(x))

o女(P(X)A「Q(X))

習(xí)題2.5

求下列謂詞公式的前束析取范式和前束合取范式：

(1)(Vx)P(x)->(3x)g(x).

解：(Vx)P(x)f0x)0(x)

O-i(Vr)P(X)V(3x)(2(x)

o(3x)-iP(x)v(3x)(2(x)

00X)(-1P(x)vQ(x))(前束析取范式、前束合取范式)

(2)(Vx)(Vj)((3Z)(P(x,z)AP(j,z))v(3M)e(x,y,u)).

證明：(Vx)Wy)((土)(P(x,z)AP(y,z))v0〃)Q(x,yM)

o(Vx)(Vy)0z)((P(x,z)AP(y,z))v0“)2(x,y,w))(轄域擴(kuò)張)

="x)(Vy)(女)0w)((P(x,z)AP(y,z))vQ(x,y,“))(轄域擴(kuò)張)(前束析取范式)

=(Vx)(Vj)(3z)(3w)((P(x,z)vg(x,J,H))A(P(j,z)v0(x,j,?)))(前束合取范式)

習(xí)題2.6

1.證明下列各式。

(2)Vx(A(x)vJB(x)),x6(x)VxA(x).

證明：(1)VxC(x)p

(2)C(?)US(1)

(3)Vx(8(x)->-1c(x))p

(4)B(a)―>―\C(a)US(3)

(5)^B(a)T(2)(4)I

(6)Vx(A(x)vB(x))P

(7)A(a)vS(a)US(6)

(8)A(?)T(5)(7)I

(9)VxA(x)UG(8)

2.符號化下列命題并推證其結(jié)論。

(3)所有有理數(shù)是實數(shù)，某些有理數(shù)是整數(shù)，因此，某些實數(shù)是整數(shù)。

解：設(shè)0(x)：x是有理數(shù)。/?(x)：x是實數(shù)。Z(x)：x是整數(shù)。則命題可符號化為:

Vx(0(x)-?/?(x)),3X(0(X)AZ(X))=>3X(/?(X)AZ(X))Q

證明如下：

(1)3X(0(X)AZ(X))p

(2)2(C)AZ(c)ES(1)

(3)Vx(Q(x)fR(x))P

(4)2(C)fR(c)US(3)

(5)2(c)T(2)I

(6)R(c)T(4)(5)I

(7)Z(c)T(2)I

(8)R(C)AZ(C)T(6)(7)I

(9)3X(7?(X)AZ(X))EG(8)

(4)每個大學(xué)生不是文科生就是理科生，有的大學(xué)生是優(yōu)等生，小張不是理科生，但他是

優(yōu)等生，因此如果小張是大學(xué)生，他就是文科生。

解：設(shè)S(x)：x是大學(xué)生。A(x)：X是文科生。B(x)：x是理科生。C(x)：x是優(yōu)等

生。，2：小張。該命題可符號化為：

Vx(S(x)A(x)vB(x)),3x(S(x)AC(X)),-JS(a),C(a)=>S(a)—>4(。)。

證明如下：

(1)Vx(S(x)->A(x)vB(x))p

(2)S(a)->A(?)vB(?)US(3)

(3)S(?)附加前提

(6)T(4)(5)I

(7)「B(a)P

(8)A(?)T(6)(7)I

(9)S(?)->A(a)CP

習(xí)題3.1

3.確定下列命題是真還是假，并簡要說明為什么。

(1)0C0(2)0e0(3)0e{0}(4)0c{0}

解(1)該命題為真，因為0是任何集合的子集。

(2)該命題為假，因為。不包含任何元素。

(3)該命題為真，因為。屬于集合{0}。

(4)該命題為真，因為0是任何集合的子集。

6.求下列集合的募集：

⑵{1,0}(3){0,{0}}

解(2)該集合的募集為{0,{1},{0},{1,0}}。

(3)該集合的塞集為{0,{0},{{0}},{0,{0}}}

習(xí)題3.2

6.證明下列等式：

(4)A-(B-C)=(A-B)u(AryC).

證明：A-(B-C)=A-(BnC)=An(BnC)

=An(BuC)=(AnB)o(AnC)=(A-B)o(AnC)

因此，A—(B—C)=(A-B)kJ(AoC)o

(5)A-(BnC)=(A-B)u(A-C)o

證明：A-(BnC)^An(BnC)=An(BuC)

=(AnB)u(AnC)=(A-fi)u(A-C)o

因此，A-(BnC)=(A-B)u(A-C)o

(8)(AuB)n(AuC)=(AnC)u(AnB)o

證明：(AuB)c(ZuC)

=((AuB)nA)o((AoB)nC)

=(AnA)u(AnB)u(AnC)o(BnC)

=(AnB)u(AnC)u(BnC)

=(AnC)u(AnB)o[(BnC)n(AoA)]

=(AnC)u(AnB)o(BnCnA)o(BnCr>A)

=[(AnC)o(AnBnC)]u[(AnB)u(AnBnC)]

=(AnC)u(AnB)

因此，(Au3)c(ZuC)=(AcC)u(Zc3)。

習(xí)題3.4

3.下列等式能否成立？

(3)(BnC)xA=(BxA)n(CxA)o

解：該等式成立。證明如下：

設(shè)<*,9>€(30。)、4<^>xeBnCAyeA

<^>xeB/\xeC/\yeA

<=>(xe^AjeA)A(xeCAjeA)

=<x,y>eBxAA<x,y>eCxA

=<x,y>e(BxA)n(CxA)

因此，(8cC)xA=(3xA)c(CxA)。

(4)(BuC)xA=(BxA)u(CxA)o

解：該等式成立。證明如下：

設(shè)<*,9>€(3。。)、4<^>xeBuCAyeA

<^>(xeB\/xeC)/\yeA

<=>(xe^AjeA)v(xeCAjeA)

=<x,y>efixAv<x,y>eCxA

O<x,y>e(BxA)u(CxA)

因此，(8uC)xA=(BxA)u(CxA)。

習(xí)題3.5

1.對于下列各種情況，用列舉法求出X到￥的關(guān)系S、domS、ranS,觸S的關(guān)系圖,

寫出S的關(guān)系矩陣。

(1)X={0,1,2},?={0,2,4},S={<x,y>\x,jeXnK).

解：S={<0,0>,<0,2>,<2,0>,<2,2>},

domS={0,2},ranS={0,2}0

關(guān)系圖如下：

習(xí)題3.6

5.設(shè)X={a,b,c,d},X上的關(guān)系R的關(guān)系矩陣如下，試問R是不是自反的、反自反的、

對稱的、反對稱的和傳遞的？

’0101、Toil、

00000101

(1)(4)

10011011

、0100,Jill;

解（1）R是反自反的、反對稱的、非傳遞的。因為％=1,。=1,但％=。。

（2）R是自反的、對稱的、非傳遞的。因為勺=1,2=1，但「32=°。

習(xí)題3.7

5.(1)設(shè)X={a,A,c},X上關(guān)系R的關(guān)系矩陣是

‘101、

MR=110

J11,

試求出MR°R°R。

習(xí)題3.9

4.設(shè)X={1,2,3,4,5},試根據(jù)以下X的劃分求X上相應(yīng)的等價關(guān)系，并畫出關(guān)系圖。

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

解：⑴X{1}={<1,1>}

&={2}x{2}={<2,2>}

R3={3,4,5}x{3,4,5}={<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,

<5,3>,<54,>,<55,>}

R=4uR?D&={<1」>，<2,2>,<3,3>,<3,4>,<3,5>,<4,3>,

<4,4>,<4,5>,<53,>,<54,>,<55,>}

關(guān)系圖如下：

3

習(xí)題3.10

1.對于下列集合上的“整除”關(guān)系，畫出其哈斯圖。

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

解：該整除關(guān)系的哈斯圖如下：

習(xí)題4.1

1.指出下列各關(guān)系是否為x到y(tǒng)的函數(shù)：

(1)X=Y=N,Z?={<x,j>1(xeX)A(j€￥)A(x+j<100)}.

(3)X={1,2,3,4}'y=XxX,Rx={<1,<2,3?,<2,<3,4?,<3,<1,4?,<4,<2,3?},

R2={<1,<2,3?,<2,<3,4?,<3,<2,3?).

解(1)R不是從x到y(tǒng)的函數(shù)；

(2)段是從x到y(tǒng)的函數(shù)，&不是從x到丫的函數(shù)。

習(xí)題4.2

1.設(shè)Z+，Z,R,C分別表示正整數(shù)集、整數(shù)集、實數(shù)集、復(fù)數(shù)集，試指出下列映射中

哪些是單射、滿射、雙射，并寫出定義域和值域。

(1)/:2-2+為/(*)=|2*|+1。

(2)于：RfR為/(x)=cosxo

冗

(4)f:為/(x)=cosxo

2

解(1)為一般映射，定義域為Z,值域為{yly=2A+l,AGN}。

(2)為一般映射，定義域為R,值域為

(4)為單射，定義域為值域為［0,1］。

2

習(xí)題4.3

4.設(shè)〉={1,2,3,4}。

(3)能否找到另一gH/x的單射g：XfX,有g(shù)og=/x?

解:能。例如g={<l,2>,<2,l>,<3,4>,<4,3>}。

(4)試定義一個映射X使/2=/且/。/、。

解：例如/={<1,2>,<22,>,<33,>,<44,>}。

習(xí)題7.1

1.設(shè)無向圖G=<V,E,/>,V={v1,v2,--,v6},E={e1,e2,—,e6},(p(el)=(vl,v2),

(p(e2)=(v2,v2),<P(e3)=(v2,v4),夕(64)=(〃,%),(p(e5)=(v3,v4),夕(0。=(匕，匕)。

(1)畫出G的圖形。

(2)求G的各節(jié)點的度數(shù)，并驗證握手定理。

(3)G是否是簡單圖？

(2)deg(v,)=2,deg(v2)=4,deg(v3)=2,deg(v4)=3deg(v5)=l,deg(v6)=0?

6

?deg（匕）=12,2\E\=U,握手定理成立。

i=l

（3）圖G中存在環(huán)，故G不是簡單圖。

4.下面各圖有幾個節(jié)點？

（2）21條邊，3個度為4的節(jié)點，其余都是度為3的節(jié)點。

解：設(shè)度數(shù)為3的節(jié)點個數(shù)為x,

由握手定理，2x21=3x4+3》

解得x=10

故該圖有13個節(jié)點。

習(xí)題7.2

4.分別指出圖7-32中的3個圖分別屬于哪種類型（強(qiáng)連通，單側(cè)連通，弱連通）。

（a）（b）

解（a）是強(qiáng)連通的，（b）是單側(cè)連通的，（c）是弱連通的。

習(xí)題7.3

1.圖7-39給出了一個有向圖，試求

（1）鄰接矩陣。

（2）A4,并找出從！到。長度

為1、2、3、4的路各有幾條？

（3）可達(dá)性矩陣。

’0111、「0101、'0212、

020100110122

A3=?—

011101010212

、0011,k0100?即20"

’0212、’0101、’0323、

012200110413

A4=?=

021201010323

、0201,100,<0122,

從鄰接矩陣及其幕可知，從匕到0長度為1的路有1條，從匕到,長度為2的路有1條，

從%到匕長度為3的路有2條，從匕到0長度為4的路有3條。

(3)令5=4+屋+工+工,

’0747、‘0111、

07470111

則8=,可達(dá)性矩陣尸=

07470111

、0434,、0111>

習(xí)題7.4

2.確定〃取怎樣的值，完全圖有一條歐拉回路。

解：完全圖K,,有一條歐拉回路的充要條件是每個節(jié)點的度數(shù)都是偶數(shù)。而在爪“中，每個

節(jié)點的度數(shù)都是〃-1。故當(dāng)〃為奇數(shù)時，完全圖叫，有一條歐拉回路。

習(xí)題7.6

5.設(shè)G是一個連通平面圖，它有〃個節(jié)點，機(jī)條邊，且每個面山欠條邊圍成。試證

k(n-2)

tn-o

k-2

證明：設(shè)圖G有，個面，由平面圖的面的次數(shù)的定理，

r

2m=y^deg(7?;)=Arr.(1)

i=l

再由歐拉定理，

〃-m+r=2.