離散數(shù)學(xué)及算法課后習(xí)題作業(yè)答案

離散數(shù)學(xué)及算法(曹曉東，原旭版)

課后作業(yè)題答案

第一章命題邏輯

1.第7頁(yè)第3題

(1)解：逆命題：如果我去公園，則天不下雨；

反命題：如果天下雨，則我不去公園；

逆反命題：如果我不去公園，則天下雨了。

(2)解：(此題注意：P僅當(dāng)Q翻譯成P-Q)

逆命題：如果你去，那么我逗留。

反命題：如果我不逗留，那么你沒(méi)去。

逆反命題：如果你沒(méi)去，那么我不逗留。

(3)解：逆命題：如果方程％"+y"=Z"無(wú)整數(shù)解，那么n是大于2的正整數(shù)。

反命題：如果n不是大于2的正整數(shù)，那么方程X"+y"=Z"有整數(shù)解。

逆反命題：如果方程％"+y"=Z"有整數(shù)解，那么n不是大于2的正整數(shù)。

(4)解：逆命題：如果我不完成任務(wù)，那么我不獲得更多的幫助。

反命題：如果我獲得了更多的幫助，那么我能完成任務(wù)。

逆反命題：如果我能完成任務(wù)，那么我獲得了更多的幫助。

2.第15頁(yè)第1題

(4)解：TTPv。)f—'(「Pv」。)

(-,pv-，e)(-,pv->2)(重言式)

(9)解：P/\7PtQoFTQ0T(重言式)

(10)W：Pv-nQ—QoT-。=。(可滿足式)

3.第16頁(yè)第5題

(2)證明：」(TPv0)f「P)

=T(PVQ)V「P)

O「(PVQ)AP

=-nFA-nQAP

=—1PAp八「Q

=F人-i。

OF

因此，TTPv。)—「尸)3尸，得證。

(4)證明：(P->「尸)△(「尸-P)

=(「Pv「P)/\(PvP)

<=>->FAF

OF

因此，(P-「尸)人(「2一尸)3尸，得證。

4.第16頁(yè)第6題

(1)P人Q=PTQ

證明：設(shè)尸△。為真，那么P為真，并且Q為真，因此P-。為真。所以PAQnP-。。

(2)Pf(Q>/?)=>(尸—。)—(尸-R)

證明：設(shè)(P—Q)f(尸-R)為假，于是Pf。為真，PfR為假。得P為真，Q為真,

R為假。于是得QfR為假，由P為真可得，P->(0fR)為假。因此，

P-?(0->A)n(P->0)->(PfR)。得證。

(5)(Pv「P—Q)f(Pv[0=#?)-6/?

證明：(Pv「P—Q)f(Pv「PfR)

Q(TTQ)T(TTR)

OQTR

因此，(Pv「PfQ)f(Pv「四印)-eR,得證。

5.補(bǔ)充:試證明((Q△A)-C)△(A-(尸vC))o(A△(P-。))fC

證明：((QAA)-C)/\(A-(PvC))

0(TQAA)VC)A(-U4V(PVO)

0(—>AvCv—iQ)A(—u4vCvP)

u>(—AvC)v(PA—>Q)

(AA(P—Q))fC

o-I(AA(-iPvQ))vC

(―iAv-i(―\PvQ))vC

o「Av(PA—>Q)vC

o(-v4vC)v(PA->Q)

因此，((Q△A)-C)△(A-(PvC))o(A△(P—Q))-C,得證。

6.第21頁(yè)第1題

(2)解：(PA2)V(^/,A2)V(FA^2)

=((PV[P)AQ)V(PMQ)

=°V(PM0)

=(PvQ)人(Qv-iQ)

oPV。

<=>n(o)

7.第21頁(yè)第2題(只求主析取范式)

(4)W：(PA—iQAS)V(—iPA(2A7?)

=(尸△—i(2ASA/?)v(PA-iQASA-iR)v(-1PAgA5A/?)v(—iP△Q△—?5AR)

0^(5,7,10,11)

8.第25頁(yè)第3題

證明：(1)Bp規(guī)貝Ij

(2)B(―u4v―iC)p規(guī)則

(3)-iAv-iCT規(guī)則,(1)(2)

(4)A—(8->C)P規(guī)則

(5)A^CT規(guī)則，⑴(4)

(6)(AAC)v(—iAA-iC)T規(guī)則(5)

(7)—i(AAC)T規(guī)則(3)

(8)-LAA-iC,T規(guī)則⑹⑺

(9)」(AvC)T規(guī)則⑻

因此，」(AvC)是題目的有效結(jié)論，AvC不是。

9.第26頁(yè)第7題

（a）火，的「尸

證明：（1）―iRP規(guī)則

（2）「QvRP規(guī)則

(3)T規(guī)則(1)(2)

(4)TP—。）P規(guī)則

(5)T規(guī)則（4）

(6)「PT規(guī)則(3)(5)

(b)(PAQ)—>/?,—\R-iS^S-1八Q

證明：（1）SP規(guī)則

(2)-、Rv-\SP規(guī)則

(3)「RT規(guī)則(1)(2)

(4)(P八Q)TRP規(guī)則

(5)T尸人。）T規(guī)則(3)(4)

(6)—>Pv—iQT規(guī)則（5）

（c）（PTQ）T/R,R1。分尸

證明：（題目有問(wèn)題）

10.第26頁(yè)第8題

（a）—iPvQ,—iQ玲R+—FS

證明:(1)pp規(guī)則（假設(shè)前提）

(2)「PvQp規(guī)則

(3)QT規(guī)則(1)(2)

(4)「QvRP規(guī)則

(5)RT規(guī)貝I(3)(4)

(6)RTSP規(guī)則

(7)ST規(guī)則(5)(6)

(8)PTSCP規(guī)則(1)(7)

(b)PTQnPf(PdQ)

證明:(1)pP規(guī)則（假設(shè)前提）

(2)PTQP規(guī)則

(3)QT規(guī)則(1)(2)

(4)P/\QT規(guī)則(1)(3)

(5)P->(FAQ)CP規(guī)貝ij⑴(4)

（c）（Pv。）＞R=（尸人。）―/?

證明：(1)PMQP規(guī)則（假設(shè)前提）

(2)PT規(guī)則（1）

(3)QT規(guī)則（1）

(4)P'QT規(guī)則(2)(3)

(5)(PvQ)->RP規(guī)則

(6)RT規(guī)則(4)(5)

(7)(PAQ)TRCP規(guī)則(1)(6)

11.:第26頁(yè)第9題

(a)(R->->Q),/?vS,S—?Q^P*「P

證明：(1)P規(guī)則（假設(shè)前提）

(2)PT規(guī)則（1）

(3)PTQP規(guī)則

(4)QT規(guī)則(2)(3)

(5)S—>—\QP規(guī)則

(6)—iST規(guī)則(4)(5)

(7)R7sP規(guī)貝IJ

(8)RT規(guī)則(6)(7)

(9)RT「QP規(guī)則

(10)-'QT規(guī)則(8)(9)

(11)QLQT規(guī)則(4)(10)

(12)F規(guī)則(1)(11)

(b)S—》―\Q^RV-JS,我P-1P

證明：(1)P規(guī)則（假設(shè)前提）

(2)pT規(guī)則（1）

(3)尸3。P規(guī)則

(4)QT規(guī)則（2）(3)

(5)ST—1。P規(guī)則

(6)\ST規(guī)則（4）(5)

(7)RvSP規(guī)則

(8)RT規(guī)則（6）(7)

(9)「RP規(guī)則

(10)R八「RT規(guī)則（8）(9)

(11)F規(guī)則（1）(10)

(c)TP-。)-?TRvS),((。")-R^RnQ

證明:(1)RP規(guī)則

(2)(QfP)v「RP規(guī)則

(3)QTPT規(guī)則(1)(2)

(4)R7sT規(guī)則(1)

(5)TPfQ)->TRvS)P規(guī)則

(6)IPtQ)T規(guī)則(4)(5)

(7)PTQT規(guī)則(6)

(8)(2->。)人(。-P)T規(guī)則(3)(7)

(9)尸3。T規(guī)則（8）

第二章謂詞邏輯

1.第39頁(yè)第1題

(b)(3x)A(x)T(Vx)B(x)0(Vx)(A(x)TB(x))

(3x)A(x)T(Vx)B(x)

=>-,(3x)A(x)v(Vx)B(x)

證明：=>(Vx)Y(x)v(Vx)B(x)

=>(Vx)(—u4(x)vB(x))

=>(Vx)(A(x)tB(x))

(還可以用推理的方法證明)

證明：⑴「(Vx)(A(x)-6(x))P(假設(shè)前提)

(2)0x)(「(A(x)f5(切)T

(3)(3x)(A(x)A—iB(x))T

(4)(3x)A(x)A(3x)—iB(x)T

(5)(3x)A(x)T

(6)T

(7)(3x)A(x)—>(Vx)B(x)P

(8)(Vx)B(x)T(5)(7)

(9)「B(a)ES(6)

(10)B(a)US(8)

(11)-13(。)A3(a)T(9)(10)

(12)W)(A(x)fB(x))F(1)(11)

(d)(Vx)(A(x)vB(x)),(Vx)(B(x)-「G(x)),(.冰(x)Vx)A(x)

證明：（1）(Vx)C(x)P

(2)C(x)US(1)

(3)(Vx)(B(x)T->C(x))P

(4)B(x)—-iC(x)US(3)

(5)[8(x)T(2)(4)

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

(7)A(x)vB(x)US(6)

(8)A(x)T(5)(7)

(9)(Vx)A(x)UG(8)

2.第39頁(yè)2

(a)(Vx)(P(x)TQ(x))n(Vx)P(x)->(Vx)Q(x)

證明：（1）(Vx)P(x)p（假設(shè)前提）

(2)P(x)US(1)

(3)"V(P(x)f。。))p

(4)P(x)f。(尤)US(3)

(5)Q(X)T(2)(4)

(6)(Tx)Q(x)UG(5)

(7)(Vx)P(x)T(Vx)Q(x)CP(1)(6)

(b)(Vx)(P(x)vQ(x))n(Vx)P(x)v0x)Q(x)

(Vx)P(x)v(士)Q(x)o」(Vx)(「Q(x))v(Wx)P(x)

證明：由于

o(Vx)(「Q(x))f(Vx)P(x)

因此，原題等價(jià)于證明(Vx)(P(x)vQ(x))n(Vx)(「Q(x))T(Wx)P(x)

(1)(Vx)(「Q(x))p（假設(shè)前提）

(2)「Q(x)US(1)

(3)(Vx)(P(x)vQ(x))p

(4)尸(x)vQ(x)US(3)

(5)尸(x)T(2)(4)

(6)(Vx)P(x)UG(5)

(7)(Vx)(「Q(x))f(Vx)P(x)CP(1)(6)

3.第39頁(yè)第3題

（a）所有的有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。

解：首先定義如下謂詞：

尸（X）：%是有理數(shù)

R（%）：X是實(shí)數(shù)

/（X）：%是整數(shù)

于是問(wèn)題符號(hào)化為：

(Vx)(P(x)->7?(x)),(3x)(P(x)A/(x))=>(訓(xùn)(R(x)/(%))

推理如下：

(1)(土)(尸(%)A[(%))p

(2)P(a)A1(a)ES(1)

(3)(Vx)(p(x)T/?(%))P

(4)P(a)fR(a)US(3)

(5)P(a)T(2)

(6)/⑷T(2)

(7)R(a)T(4)(5)

(8)R(a)A1(a)T(6)(7)

(9)(3x)(/?(x)A/(%))EG(8)

(b)任何人如果他喜歡步行，他就不喜歡乘汽車，每一個(gè)人或者喜歡乘汽車或者喜歡騎自

行車，有的人不愛(ài)騎自行車，因而有的人不愛(ài)步行。

解：首先定義如下謂詞：

P(x):x是人

產(chǎn)(%):%喜歡步行

C(x):x喜歡乘汽車

B(x)：x喜歡騎自行車

于是問(wèn)題符號(hào)化為：

(Vx)(P(x)A/(x)--1c(x)),(Vx)(P(x)-C(x)V8(%)),

(lx)(P(x)△［盤(pán)%))3(木)(尸(x)iF(x))

推理如下：

(1)(土)(尸(x)人p

(2)P(a)八一18(a)ES(1)

(3)q(a)T(2)

(4)T(2)

(5)(Vx)(P(x)->C(x)vB(x))P

(6)P(a)—>C(a)vB(a)US(5)

(7)C(a)vB(a)T(3)(6)

(8)C(?)T(4)(7)

(9)(V%)(P(x)AF(x)-「C(x))P

(10)P(a)AF(a)--iC(a)US(9)

(11)「(尸3)八%。))T(8)(10)

(12)—1尸(Q)V—iF(iZ)T(11)

(13)T(3)(12)

(14)P(a)A—iF(iz)T(3)(13)

(15)(3X)(P(X)A-IF(X))EG(14)

(c)每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而且聰明的科學(xué)工作者在他的事業(yè)中

都將獲得成功。華為是科學(xué)工作者并且他是聰明的，所以，華為在他的事業(yè)中將獲得成功。

解：首先定義如下謂詞：

尸(X)：%是科學(xué)工作者

Q(x):x是刻苦鉆研的

/?(光)：％是聰明的

S(x):%在他的事業(yè)中將獲得成功

定義個(gè)體a：華為

于是命題符號(hào)化為：

(Vx)(P(x)TQ(x)),(Vx)(P(x)AQ(x)AR(x)->5(x)),

P(a)AR(a)=>S(a)

推理如下：

(i)(VX)(P(x)fQ(x))P

(2)尸(a)-Q(q)us(1)

(3)P(a)AR(a)p

(4)T(3)

(5)R(a)T(3)

(6)Q(a)T(2)(4)

(7)(Vx)(尸(x)AQ(x)AR(x)->S(x))P

(8)P(a)AQ(a)AR(a)TS(a)US(7)

(9)尸(a)AQ(a)AR(a)T(3)(6)

(10)S(a)T(8)(9)

(d)每位資深名士或是中科院院士或是國(guó)務(wù)院參事，所有的資深名士都是政協(xié)委員。張偉

是資深名士，但他不是中科院院士。因此，有的政協(xié)委員是國(guó)務(wù)院參事。

解：首先定義如下謂詞：

P(%):%是資深名士

Q(x):x是中科院院士

R(x):%是國(guó)務(wù)院參事

S(x):%是政協(xié)委員

定義個(gè)體a：張偉

于是命題符號(hào)化為：

(Vx)(P(x)tQ(x)V7?(x)),(Vx)(P(x)->S(%)),

P(a)A」Q(a)n(3x)(5(x)A/?(%))

推理如下：

(1)尸(Q)八-iQ(Q)p

(2)T(1)

(3)—iQ(a)T(1)

(4)(Vx)(尸⑴fS(x))P

(5)P(a)fS(a)US(4)

(6)S(a)T(2)(5)

(7)(Vx)(P(x)fQ(x)vR(x))p

(8)P(a)—>0(a)vR(a)US(7)

(9)Q(a)vR(a)T(2)(8)

(10)R(a)T(3)(9)

(11)S(a)AR(a)T(6)(10)

(12)0尤)(5(%)AR(x))EG(11)

(e)每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù)，自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被2整除。并不是所有

的自然數(shù)都能被2所整除。因此，有的自然數(shù)是奇數(shù)。

解：首先定義如下謂詞：

N(X)：X是自然數(shù)

。(無(wú))：%是奇數(shù)

0(%)：X是偶數(shù)

P(%)：X能被2整除

于是命題符號(hào)化為：

(Vx)(N(x)-?(2(x)VO(x))),(Vx)(7V(x)-?(0(X)-P(x))),

i(Vx)(7V(x)-P(%))n(*)(N(x)AQ(X))

推理如下：

(1)」(Dx)(N(x)->P(%))P

(2)(Hx)(N(x)八-TP(X))T(1)

(3)ES(2)

N(G)A-1P(a)

(4)N(a)T(3)

(5)T(3)

-1P(a)

(6)(V%)(N(x)-?(0(x)3P(x)))P

(7)N(a)f(0(a)—P(a))us(6)

(8)0(a)0尸(a)T(4)(7)

(9)—iO(￡l)T(5)(8)

(10)(Vx)(7V(x)T(C(x)VO(x)))P

(11)N(a)->(Q(a)VO(a))US(10)

(12)Q(a)▽。⑷T(4)(11)

(13)Q(。)T(9)(12)

(14)N(a)AQ(a)T(4)(13)

(15)(3x)(2V(x)A2(x))EG(14)

(f)如果一個(gè)人怕困難，那麼他就不會(huì)獲得成功。每個(gè)人或者獲得成功或者失敗過(guò)。有些

人未曾失敗過(guò)，所以，有些人不怕困難。

解：首先定義如下謂詞：

尸(X)：%是人

Q(x):尤怕困難

/?(%):%曾獲得成功

S(x)：%曾獲得失敗

于是命題符號(hào)化為：

(Vx)(P(x)AQ(x)T」R(x)),(Vx)(P(x)T(/?(%)VS(x))),

0%)(P(X)A「MX))3(^)(P(x)[Q(x))

推理如下：

(1)0X)(P(X)A-1S(X))P

(2)P(a)A-)S(a)ES(1)

(3)P(a)T(2)

(4)-,S(a)T(2)

(5)(V%)(P(x)->(R(x)vS(x)))P

(6)尸(a)f(E(a)vS(a))us(5)

(7)R(a)vS(a)T(3)(6)

(8)R(a)T(4)(7)

(9)(Vx)(P(x)AQ(x)t-J?(x))P

(10)P(a)AQ(a)—>—ijR(a)US(9)

(11)」(P(a)AQ(a))T(8)(10)

(12)-iP(a)v-iQ(a)T(11)

(13)「。⑷T(3)(12)

(14)P(a)A-iQ(a)T(3)(13)

(15)(3X)(P(X)A^Q(X))EG(14)

4.第40頁(yè)第5題

解：錯(cuò)誤，第2行的y是泛指，第4行的y是特制

更改如下：

(1)0x)P(x)P

(2)尸(y)ES(1)

(3)(Wx)(P(x)fQ(x))P

(4)P(y)-Q(y)US(3)

(5)Q(y)T(2)(4)

(6)(3x)Q(x)EG(5)

5.第40頁(yè)第6題

(a)(Bx)P(x)->(Vx)((P(x)vQ(x))->R(x)),

0x)P(x),(川匆x)n(川0y)(R(x)AR(y))

證明:

(1)(3x)P(x)P

⑵P(a)￡5,(1)

⑶(3x)2(x)P

(4)Q(b)ES,⑶

(5)(玉)P(x)f(Vx)((P(x)vQ(x))->R(x))P

(6)(Vx)((P(x)vQ(x))fR(x))(1),(5)

⑺(P(a)vQ(a))-R(a)US,(6)

(8)P(a)vQ(a)T,(2)

⑼R⑷T,⑺，⑻

(10XP(b)vQS))-RS)US,(6)

(11)PS)vQ(b)T,(4)

(12)R(b)T,(10),(U)

(13)R(a)八R(b)T,⑼，（⑵

(14)(寺)(R(a)AR(y))EG,(13)

(15)0x)0y)(R(x)AR(y))EG,(14)

(b)(3x)P(x)->(Vx)Q(x)n(Vx)(P(x)->0(x))

證明：(1)0x)P(x)-?(Vx)Q(x)P

(2)->0x)P(x)v(Vx)Q(x)T(1)

(3)(Vx)「P(x)v(Vx)Q(x)T(2)

(4)(Wx)(「P(x)vQ(x))T(3)

(5)(V尤)(P(x)->Q(x))T(4)

6.第42頁(yè)第1題

(a)"x)(P(x)f(十)。(田)

解:(Vx)(P(x)r(寺)。(y))

o(V元)(「P(x)v(寺)Q(y))

o(V%)0y)(「P(x)vQ(y))

(b)(Vx)(Vy)((3z)(P(x,y)AP(y,z))->(3u)Q(x,y,?))

解：

(Wx)(W)，)(0z)(P(x,y)AP(y,z))f0”)Q(x,)，,〃))

o(Vx)(Vy)(「(切(P(x,y)AP(y,z))v(A)Q(x,y,〃))

o(Vx)(Vj)((Vz)(->P(x,y)v-iP(y,z))v(Bu)Q(x,y,w))

o(Vx)(Vy)(Vz)(3w)(->P(x,y)v->P(y,z)vQ(x,y,u))

(c)](Vx)6y)A(x,y)T(3x)(Vy)(B(x,y)△(Vy)(A(y,x)TB(x,y)))

解：

TVx)(h)A(x,y)T(3x)(Vy)(B(x,y)A(Vy)(A(y,x)-?B(x,y)))

O(Vx)(寺)A(x,y)v(3x)(Vy)(B(x,y)A(Vy)(A(y,x)TB(x,y)))

o(Vx)(3y)A(x,y)v(3x)(Vy)(B(x,y)△(Vy)(「A(y,x)vB(x,y)))

o(Vx)(3y)A(x,y)v(3w)(Vv)(B(u,v)A(VZ)(-V4(Z,W)VB(U,Z)))

O(VX)(3>9(3M)(VV)(VZ)(A(X,y)v(B(u,v)A(T1(Z,W)VB(U,Z))))

7.第42頁(yè)第2題

(b)(Vx)(P(x)T(Vy)((Vz)2(x,z)TTVz)R(x,y)))

解：前束析取范式

(Vx)(P(x)T(Vy)((Vz)2(x,z)t[”y)R(x,y)))

o(Vx)(「P(x)v(Vy)((Vz)Q(x,z)->["y)R(x,)，)))

o(Vx)(「P(x)v(Vy)(「(Vz)Q(x,z)v「(Vy)R(x,y)))

o(Vx)(「P(x)v(Vy)(「(Wz)Q(x,z)v「(VM)R(XM))

o(Vx)(「P(x)v(Vy)((土)「Q(x,z)v(Bu)^R(x,?)))

O(Vx)(Ty)(&)0M)(「P(X)v(~,Q(x,z)v「R(x,〃)))

o(Vx)(Vy)(七)G”)(「P(x)v」Q(x,z)vT?(x,〃))

由于」P(x)v[0(x,z)v是基本和，因此前束合取范式與前束析取范式一樣:

(Vx)(P(x)->(Vy)((Vz)Q(x,z)->[”z)R(x,y)))

o(Vx)(Vy)0z)0〃)(「P(x)v「Q(x,z)vT?(龍,〃))

(d)(Vx)(P(x)tQ(x,y))t((中)P(y)A0z)Q(y,z))

解：前束析取范式：

(Vx)(P(x)tQ(x,y))->((寺)尸(y)A0z)Q(y,z))

oTVx)(P(x)->Q{x,y))v((中)尸(y)A(出)。(%z))

o「(Vx)(「P(x)vQ(x,)，))v(0y)P(y)A(Bz)g(y,z))

o(3x)(P(x)AQ(x,y))v((十)P(y)A(玉)Q(y,z))

o0x)(P(x)A2(X,M))v(0y)P(y)A0Z)Q(〃,Z))

o(3x)(3y)(2z)((P(x)AQ(X,U))V(P(y)AQ(U,Z)))

前束合取范式：

(Vx)(P(x)-?Q(x,y))->((h)P(y)A0z)Q(y,z))

o(土)(力)0z)((P(x)A0(xM)v(P(y)A03,z)))

o(3x)(3y)(3z)((P(x)v(P(y)AQ(U,Z)))A(Q(X,〃)V(P(y)AQ(U,Z))))

<=>(3x)(3y)(3z)((P(x)vP(y))A(P(X)VQ(M,Z))A(Q(X,M)VP(y))A(Q(X,“)VQ(U,Z)))

第三章集合論

1.第46頁(yè)第3題

給出集合A、B和C的例子，使得AeB,BeC而

解：

A={a}

B={{a},b}

C={{{a},b},c}

2.第46頁(yè)第6題

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

解：設(shè)4={{1,{2,3}}}

則p(A)={0,{{l,{2,3}}}}

⑸p(p(0))

解：

夕(0)={0}

p(p(0))={0,{0})

3.第46頁(yè)第9題

(1)解：子集個(gè)數(shù)2刈

2ioi

(2)解：元素的奇數(shù)的子集個(gè)數(shù)為—=210°

2

(3)解：不會(huì)有102個(gè)元素的子集。

4.第46頁(yè)第10題

解：把17化為二進(jìn)制，是00010001,Bl7={a4,a8}；

把31化為二進(jìn)制，是00011111,&]={。4，。5，46，07，“8}

{4,4，%}，編碼為01000110，為B[0

{q,如}，編碼為10000001,為Ba

5.第53頁(yè)第5題

(1)(A-6)-C=A-(6UC)

證明：

(A-B)-C

=(AH~B)-C

=(4n~8)n~c

=API(~BH-c)

=An~(6UC)

=A-(B\JC)

上面是一種簡(jiǎn)單的方法，還可以利用文字?jǐn)⑹觯稳屬于(A-6)-C,。。。。。證明。

還有一種方法，就是利用第五章的特征函數(shù)證明，下面給出過(guò)程

匕A-B)-C

=匕4-8)一匕

=(〃AA*%)一A*%)*%

〃A-(8UC)

”A7A*WBUC

HA*WB+WC，B*WC)

=〃A(1-(/+〃L〃B*〃C))

=WAQTB)Q-"C)

所以，力(A-B)-C="4-(BUC)

從而可得，(A-B)—C=A-(BUC)。

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

證明：

(A-B)-C

=(柏~6)-C

=an~BPI~c

=an~cn~8

=(A-C)n~B

=(A—C)—8

(3)(A-B)-C=(A-C)-(B-C)

證明：

(A-C)-(B-C)

=(An~c)-(3n~c)

=(An~c)n~(8n~c)

=(An~c)n(~8uc)

=(An~cn~B)u(An~cnc)

=an~Bn~c

=(A-B)n~C

=(A-B)-C

因止匕，(A-5)-C=(A-C)-(5-C)

6.第53頁(yè)第9題

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

解：由于(A—B)n(A—C)=A,因此必有A—8=A且A—C=A。也就是40|8=0

并且AP|C=。。

(2)(A-8)U(A-C)=0

解：由于(A—B)U(A—C)=0，因此必有A—6=0且A—C=0。也就是AqB并且

A^Co

(3)(A-5)n(A-C)=0

解：

(A-5)n(A-C)

=(an~B)n(An~c)

=an~~c

=an~(BUc)

因此，(A-B)n(A—C)=0意味著4q(8UC)

(4)(A—6)十(A—C)=0

解:

（A-5）?（A-C）

=（An~B）十（An~c）

=（An~6n~sn~o）u（an-cn~（ACI~助

=（an~Bn（~AUc））u（An~cn（~AU8））

=（An~8nc）u（An8n~c）

=an。十o

兩種可能，第一種8十C=0,即B=C；

第二種，4=80。或者4=~（80。）

因此，此題答案為3=C或者?御DCA=~（8UC）。

7.第53頁(yè)第11題

（1）An（8十。）=（4門(mén)6）十sno

證明：

（ADB）十（API。）

=（AnBn~（Ano）u缶ncn~缶n⑶）

=（4rw（~AU~c））u（Ancn（~AU~B））

=5詢~A）u（an6n~c）u（Ancn~A）u（Ancn~8）

=（4nBn~c）u（Ancn~B）

=An（（6n~c）u（cn~8））

=AD（B十o

因此，An（B十C）=（AAB）十（Ano。

（2）AU（6十C）=（AU6）十（AUC）

注意:這個(gè)題目本身不正確，舉例如下：全集為{1,2,3},A="},B={2},C={3}

則AU（8十C）={1,2,3},（AU8）十（AUC）={2,3},不相等。

8.第57頁(yè)第3題

解：設(shè)A,B,C分別表示騎木馬、坐滑行軌道和乘宇宙飛船的兒童集合。

由公園的總收入知,IAI+1BI+1C1=70/0.5=140

l/in5nCh20

iAnBn~ci+Mn?Bnci+i?AnBnci+iAn8nci=5

lAn5i+iAnci+ifinci

=3"80。1+140始?CI+IACI?BCICI+I?ACIBOCI

因此，=55+2IAnBnCI

=55+40

=95

沒(méi)有坐過(guò)任何一種的兒童總數(shù)為

|~An-5n-ci

=75-IAUBUCI

=7^(lAI+IBI+ICI-IAnBI-IAnCI-IBnCI+IAnBClCI)

=75-(140-95+20)

=10

答：一共10個(gè)兒童沒(méi)有坐過(guò)其中任何一種游樂(lè)設(shè)備。

9.第57頁(yè)第5題

解：設(shè)A,B,C分別是學(xué)習(xí)數(shù)學(xué)、物理、生物的大一學(xué)生集合。

由題意可知，

141=67,181=47,1Cl=95,

IACl81=28,1AClC1=26,13rle1=27,

I?An?BPI?ci=50

l~Af-]~BQ~CI

=200-IAUBUCI

二2(HDAI+IBI+ICI-IAClBI-IAnCI-IBClCI+IAnBClCI)

=200-(67+47+95-26-27-28+1AQfiClCI)

=50

解方程，得

iAn5nci=22

因此，一共有22人三門(mén)功課都學(xué)。

10.第59頁(yè)第1題

(1)AX{1}XJB

解：AX{1}X5={<0,1,1>,<0,1,2>,<1,1,1>,<1,1,2>}

(2)A2XB

解

A2X5={<0,0,1>,<0,1,1>,<1,0,1>,<1,1,1>,<0,0,2>,<0,1,2>,<1,0,2>,<1,1,2>}

(3)(BxA)2

解：BxA={<1,0>,<1,1>,<2,0>,<2,1>}

(BxA)2={?1,0>,<1,0?,?l,0>,<1,1?,?1,0>,<2,0?,?l,0>,<2,1?,

??,?1,1>,<1,1?,?1,1>,<2,0?,?1,1>,<2,1?,

?2,0>,<l,0?,?2,0>,<1,1?,?2,0>,<2,0?,?2,0>,<2,1?,

?2,1>,<l,0?,??,?2,l>,<2,0?,?2,1>,<2,1?}

11.第60頁(yè)第2題

解：Xxy表示在在笛卡爾坐標(biāo)系中，-3Wx<2且-24y40的矩形區(qū)域內(nèi)的點(diǎn)集。

12.第60頁(yè)第3題

(1)(An6)x(CnO)=(AxC)n(8xO)

證明：任取<X,y〉6(408)*(?？?。)，有

<x,y>e(AnB)x(CnD)

=xe(AD8)△yw(CCl￡))

<^>(xeAAyeC)A(xeBAyG￡))

=<x,y>eAxCA<x,y>EBXD

u><x,y>G(AxC)A(BxD)

由<%,y〉取值的任意性知，(An8)X(Cn。)=(AXC)n(8X。)。

(2)當(dāng)且僅當(dāng)才，才有(AnB)UC=An(6UC)

證明：當(dāng)C=A時(shí)，AUC=A,于是(AnB)UC=(AUC)n(BUC)=An(BUC)。

當(dāng)(Ans)uc=An(Buc)時(shí)，

任取xeC,可知xe(An5)UC，由(AnB)UC=ACKBUC)知xeAn(8U。)，

于是得到xeA。所以，CqA。

13.第60頁(yè)第5題(這種題目也可以不推理，只要舉出反例即可)

(1)(AU8)x(CUO)=(AxC)U(5xO)

解：任取<九,丁〉e(AU8)x(CU0M

<x,y>e(AUB)x(CUD)

oxe(AUB)△ye(CU。)

<=>(xGAvxeB)A(yeCvyeD)

o(xeAA(yeCvye￡>))v(xeBA(yeCvye￡)))

<=>(xeAAyeC)v(xeAAyeD)v(xeBAyeC)v(xeBAye￡>)

0<%,y〉e(4xC)U(Ax0U(8xC)U(BxO)

選擇A={1},B={2},C={a},D=

則(AU8)x(CU0={<l,a>,<1力>,<2,a>,<2,b>}

(AxC)U(8xO)={<l,a〉,<2,b〉}

因此該等式不成立。

(2)(A-8)x(C-O)=(AxC)-(8x￡))

解：任取<龍,y〉c(A-8)x(C?—。)，有

<x,y>e(A-B)x(C-D)

=<x,y>e(Afi?8)x(CQ?D)

o%e(Ad?B)Aye(CH?D)

o(xcA/\xeB)/\(yeC/\ye￡>)

<=>(xeAAyeC)A(x^BAy^Z))

<=>(xeAAyeC)A(x^jBAy^D)

0(%eAAyeC)A-i(xeBvyeD)

選擇A={1,2},B=⑴,C={a,b},D={a}

(A-B)x(C-D)={<2,/>>)

(AxC)-(6xO)={<l,b>,<2,a>,<2/>}

因此，該等式不成立.

(3)(A十5)x(C十O)=(AxC)十(BxO)

解:設(shè)人={1,2},B=⑵,C={3,4},D={4}

則(4十B)x(C十￡>)={<1,3>}

(AxC)十3。)={<1,3〉,<1,4>,<2,3>}

因此，該等式不成立。

(4)(A-8)xC=(AxC)-(8xC)

解：取<x,y〉e(A-3)xC,有

<x,y>e(A-B)xC

=<x,y>e(AH~B)xC

oxe(Ad~S)AyGC

o(xeAA)?eC)A(x^Bvy^C)

o(xeAAyeC)A—i(xGBAyeC)

O(<X,y〉eAxC)△(<〉￡BxC)

o<x,y>e(AxC-BxC)

因此，該等式成立。

(5)(A十8)xC=(AxC)十(BxC)

解：任取取<x,y〉G(AXC)十(8xC),有

<%,y〉c(AxC)十(8xC)

<=>((xeAAyeC)A—i(xc8AycC))v((xeBAyeC)A—I(XeAAyeC))

o((xeAAyeC)A(xeBvy￡C))v((xeBAyeC)A(xg/lvy^C))

0(%eA/\yeC/\%e8)v(xeA/\xeB/\yeC)

=((XGAAX￡JB)V(XWAAXGB))AyEC

=尤e((AC?8)U(?An5))△ycC

oxeA十B/\yeC

0<%,y〉e(A十B)xC

因此，該等式成立。

第四章二元關(guān)系

1.第63頁(yè)第2題

解：&U&2={〈1，2〉,〈2,4〉,〈3,3〉,〈1,3〉,〈4,2〉}

鳥(niǎo)(?&={〈2,4〉}

0(7?,)={1,2,3)

。(")={1,2,4}

R(RJ={2,3,4}

R(")={2,3,4}

。(鳥(niǎo)U%)={1,2,3,4}

7?(-0&2)={4}

2.第63頁(yè)第3題

解：

L={<1,1〉,<1,2〉,<1,3>,<1,6>,<2,2>,<2,3>,<2,6>,

<3,3〉,<3,6〉,<6,6〉}

。={<1,1>,<1,2>,<1,3>,<1,6>,<2,2〉,〈2,6〉,<3,3>,<3,6>,<6,6>}

L0。={<1]>,<1,2>,<1,3>,<1,6>,<2,2>,<2,6>,<3,3>,<3,6>,<6,6>}

3.第63頁(yè)第4題

證明：設(shè)D(R)=A,D(S)=B。

(1)任取xeAUB，則分為兩種情況，164或%63。當(dāng)％cA時(shí)，由R是自反的，

知<〉e/?,于是<x,%〉eRUS；當(dāng)?reB時(shí)，由S是自反的，知<九,x〉eS,

于是<x,x〉eRUS。因此不管任何情況，(VX)XGAUB，<x,x>eR\JS,

RUS是自反的。

(2)任取光eAClB,則為eA且xeB。由R和s都是自反的，知<x,x〉eR并且

<>GS,于是<x,x〉eRnS。因此RC|S是自反的。

4.第63頁(yè)第5題

證明:設(shè)D(R)=A,D(S)=B。

(1)任取xeAnB,則XGA且尤由R和S都是自反的，知＜%,X〉GR并且

＜x,x＞eS,于是＜%,x〉eRnS。因此RCIS是自反的。

(2)任?。紉,yACRCIS,則＜%,y〉cR并且＜x,y〉eS。由R和s是對(duì)稱的，

知＜〉eR并且＜〉eS,于是＜丁,光〉6R「|5。因此，APIS是對(duì)稱的。

(3)任?。肌礶RdS,＜y,z＞eClS,可得＜%,y〉eR,＜y,z〉eR并

且＜x,y〉eS,＜y,z〉eS。由R是可傳遞的，知＜%,z〉e/?；由s是可傳遞的，

知＜x,z〉eS。于是＜x,z〉eRnS。因此，Rp|S是可傳遞的。

5.第63頁(yè)第7題

解：任取XGS,除5外，＜〉￡E,但＜5,5〉eR,因此R是不自反的；若

<x,y>^R,即％+y=10,可得y+x=10,<〉eR,知R是對(duì)稱的;

＜3,7〉eR,＜7,3〉eR,但＜3,3〉任火，可得R是不可傳遞的。

綜上，R是不自反的、對(duì)稱的、不可傳遞的。

6.第63頁(yè)第8題

解：(1)R是集合A上的二元關(guān)系，A為空集。

(2)R是集合A上的二元關(guān)系，A={1,2},R={＜1,1〉}。

(3)R是集合A上的二元關(guān)系，A為空集。

(4)R是集合A上的二元關(guān)系,A={1,2,3},/?={<!,1>,<1,2>,<2,1>,

,＜1,3＞}

7.第69頁(yè)第1題

解：

0123

01001

肛=10000

21101

30010

8.第69頁(yè)第2題

解：設(shè)乂={1,2,3,},X中的二元關(guān)系有2寸=512個(gè)。

9.第69頁(yè)第3題

證明：集合X中的每個(gè)二元關(guān)系都是XxX的子集，X有〃個(gè)元素，XxX有〃2個(gè)元素,

夕(XxX)有2/個(gè)元素，每一個(gè)元素都是XxX的一個(gè)子集，也是一種二元關(guān)系，