离散数学及算法课后习题作业答案.pdf

离散数学及算法(曹晓东，原旭版)课后作业题答案第一章命题逻辑1.第7页第3题(1)解：逆命题：如果我去公园，则天不下雨；反命题：如果天下雨，则我不去公园；逆反命题：如果我不去公园，则天下雨了。(2)解：(此题注意：P仅当Q翻译成P -Q)逆命题：如果你去，那么我逗留。反命题：如果我不逗留，那么你没去。逆反命题：如果你没去，那么我不逗留。(3)解：逆命题：如果方程+y =Z 无整数解，那么n是大于2的正整数。反命题：如果n不是大于2的正整数，那么方程X +y =Z 有整数解。逆反命题：如果方程+y =Z 有整数解，那么n不是大于2的正整数。(4)解：逆命题：如果我不完成任务，那么我不获得更多的帮助。反命题：如果我获得了更多的帮助，那么我能完成任务。逆反命题：如果我能完成任务，那么我获得了更多的帮助。2 .第1 5页 第1题(4)解：TTPv。)f(Pv。)(-,p v-，e)(-,p v-2)(重言式)(9)解：P/7P t Q o F TQ 0T(重言式)(1 0)W：P v-nQ Q o T-。=。(可满足式)3 .第1 6页第5题(2)证明：(TPv 0)fP)=T(PVQ)VP)O(PVQ)AP=-nF A-nQ A P=1PAp 八 Q=F 人-i。O F因此，T T P v。)尸)3尸，得证。(4)证明：(P-尸)(尸-P)=(P vP)/(PvP)-FAFO F因此，(P-尸)人(2一尸)3尸，得证。4.第16页第6题(1)P 人 Q=P TQ证明：设尸。为真，那么P为真，并且Q为真，因此P-。为真。所以P A Q n P -。(2)P f (Q /?)=(尸。)(尸-R)证明：设(P Q)f (尸-R)为假，于是P f。为真，P f R为假。得P为真，Q为真,R为 假。于 是 得Q f R为 假，由P为 真 可 得，P-(0 f R)为 假。因 此，P-(0-A)n (P-0)-(P f R)。得证。(5)(P vP Q)f (Pv 0=#?)-6 /?证明：(P vP Q)f(P vP fR)Q(TTQ)T(TTR)OQTR因此，(P vP f Q)f(P v四 印)-e R,得证。5.补充:试证明(Q A)-C)(A-(尸 v C)o (A (P-。)f C证明：(QAA)-C)/(A -(P v C)0(T Q AA)VC)A(-U4V(PV O)0(A v C v iQ)A(u4 v C v P)u (A v C)v (P A Q)(AA(P Q)f Co-I(A A(-iP v Q)v C(iA v -i(P v Q)v CoA v(P A Q)v Co(-v4 v C)v(P A-Q)因此，(Q A)-C)(A -(P v C)o (A (P Q)-C,得证。6 .第2 1页 第1题(2)解：(PA2)V(/,A2)V(FA2)=(PVP)AQ)V(PMQ)=V(PM0)=(P v Q)人(Q v-iQ)o P V。n(o)7 .第2 1页第2题(只求主析取范式)(4)W：(P A iQ A S)V(iP A(2 A 7?)=(尸 i(2 AS A/?)v(P A-iQ A S A-iR)v (-1 P A g A5 A/?)v (iP Q 5 A R)0 (5,7,1 0,1 1)8.第2 5页第3题证明：(1)Bp规贝Ij(2)B(u4 v iC)p规则(3)-iA v-iCT 规 则,(1)(2)(4)A (8-C)P规则(5)A CT规则，(4)(6)(A A C)v (iA A-iC)T规则(5)(7)i(A A C)T规则(3)(8)-LA A-iC,T规则(9)(Av C)T规则因此，(A v C)是题目的有效结论，A v C不是。9.第2 6页第7题（a）火，的 尸证明：（1）（2）iRQ v RP规则P规则(3)T 规 则(1)(2)(4)TP。）P规则(5)T规 则（4）(6)PT 规 则(3)(5)(b)(P A Q)/?,R-iSS-1 八 Q证明：（1）SP规则(2)-、R v-SP规则(3)RT 规 则(1)(2)(4)(P 八 Q)TRP规则(5)T 尸人。）T 规 则(3)(4)(6)P v iQT规 则（5）（c）（PTQ）T/R,R 1。分 尸证明：（题目有问题）1 0.第2 6页第8题（a）iP vQ,iQ 玲 R+F S证明:(1)pp规 则（假设前提）(2)Pv Qp规则(3)QT 规 则(1)(2)(4)QvRP规则(5)RT 规贝I (3)(4)(6)RTSP规则(7)ST 规 则(5)(6)(8)PTSC P规 则(1)(7)(b)P T Q n P f(P d Q)证明:(1)pP规 则（假设前提）(2)PTQP规则(3)QT 规 则(1)(2)(4)P /QT 规 则(1)(3)(5)P-(FAQ)C P 规贝ij(4)（c）（Pv。）R =（尸人。）/?证明：(1)P MQP规 则（假设前提）(2)PT规 则（1）(3)QT规 则（1）(4)P QT 规 则(2)(3)(5)(P v Q)-RP规则(6)RT 规 则(4)(5)(7)(PAQ)TRC P 规 则(1)(6)1 1.:第2 6 页第9题(a)(R-Q),/?v S,S QP*P证明：(1)P规 则（假设前提）(2)PT规 则（1）(3)PTQP规则(4)QT 规 则(2)(3)(5)S QP规则(6)iST 规 则(4)(5)(7)R 7 sP规贝IJ(8)RT 规 则(6)(7)(9)RTQP规则(1 0)-QT 规 则(8)(9)(1 1)QLQT 规 则(4)(1 0)(1 2)F 规 则(1)(1 1)(b)S QR V-JS,我P-1P证明：(1)P规 则（假设前提）(2)pT规 则（1）(3)尸3。P规则(4)QT规 则（2）(3)(5)S T 1。P规则(6)ST规 则（4）(5)(7)R v SP规则(8)RT规 则（6）(7)(9)RP规则(1 0)R八 RT规 则（8）(9)(1 1)F规 则（1）(1 0)(c)TP-。)-TR v S),(。)-RRn Q证明:(1)RP规则(2)(Q f P)vRP规则(3)QTPT规则(1)(2)(4)R 7 sT规则(1)(5)TPf Q)-T R v S)P规则(6)I P t Q)T规则(4)(5)(7)PTQT规则(6)(8)(2-。)人(。-P)T规则(3)(7)(9)尸3。T规 则（8）第二章 谓词逻辑1 .第3 9页 第1题(b)(3 x)A(x)T(V x)B(x)0(V x)(A(x)T B(x)(3 x)A(x)T(V x)B(x)=-,(3 x)A(x)v(V x)B(x)证明：=(V x)Y(x)v(V x)B(x)=(V x)(u4(x)v B(x)=(V x)(A(x)t B(x)(还可以用推理的方法证明)证明：(V x)(A(x)-6(x)P (假设前提)(a)(Vx)(P(x)T Q(x)n (Vx)P(x)-(Vx)Q(x)(2)0 x)(A(x)f 5(切)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)E S (6)(1 0)B(a)U S (8)(1 1)-13(。)A 3(a)T (9)(1 0)(1 2)W)(A(x)f B(x)F (1)(1 1)(d)(Vx)(A(x)vB(x),(Vx)(B(x)-G(x),(.冰(x)V证明：（1）(Vx)C(x)P(2)C(x)U S (1)(3)(Vx)(B(x)T -C(x)P(4)B(x)-iC(x)U S (3)(5)8(x)T (2)(4)(6)(Vx)(A(x)vB(x)P(7)A(x)v B(x)U S (6)(8)A(x)T (5)(7)(9)2.第 3 9 页 2(Vx)A(x)U G (8)x)A(x)证明：（1）(Vx)P(x)p （假设前提）(2)P(x)U S (1)(3)V(P(x)f。)p(4)P(x)f。(尤)U S (3)(5)Q(X)T (2)(4)(6)(Tx)Q(x)U G (5)(7)(Vx)P(x)T (Vx)Q(x)C P (1)(6)(b)(Vx)(P(x)v Q(x)n (Vx)P(x)v 0 x)Q(x)(Vx)P(x)v(士)Q(x)o(Vx)(Q(x)v(Wx)P(x)证明：由于o(Vx)(Q(x)f(Vx)P(x)因此，原题等价于证明(Vx)(P(x)v Q(x)n (Vx)(Q(x)T (Wx)P(x)3.第 3 9 页第3题（a）所有的有理数是实数，某些有理数是整数，因此某些实数是整数。解：首先定义如下谓词：(1)(Vx)(Q(x)p （假设前提）(2)Q(x)U S (1)(3)(Vx)(P(x)vQ(x)p(4)尸(x)vQ(x)U S (3)(5)尸(x)T (2)(4)(6)(Vx)P(x)U G (5)(7)(Vx)(Q(x)f(Vx)P(x)C P (1)(6)尸（X）：%是有理数R（%）：X是实数/（X）：%是整数于是问题符号化为：(Vx)(P(x)-7?(x),(3x)(P(x)A/(x)=(训(R(x)/(%)推理如下：(1)(土)(尸(%)A(%)p(2)P(a)A 1(a)ES(1)(3)(Vx)(p(x)T /?(%)P(4)P(a)f R(a)US(3)(5)P(a)T(2)(6)/T(2)(7)R(a)T(4)(5)(8)R(a)A 1(a)T(6)(7)(9)(3x)(/?(x)A/(%)EG(8)(b)任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。解：首先定义如下谓词：P(x):x是人产(%):%喜欢步行C(x):x喜欢乘汽车B(x)：x喜欢骑自行车于是问题符号化为：(Vx)(P(x)A/(x)-1c(x),(Vx)(P(x)-C(x)V 8(%),(lx)(P(x)盘%)3(木)(尸(x)i F(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)v B(x)P(6)P(a)C(a)v B(a)US(5)(7)C(a)v B(a)T(3)(6)(8)C()T(4)(7)(9)(V%)(P(x)A F(x)-C(x)P(10)P(a)A F(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)每个科学工作者都是刻苦钻研的，每个刻苦钻研而且聪明的科学工作者在他的事业中都将获得成功。华为是科学工作者并且他是聪明的，所以，华为在他的事业中将获得成功。解：首先定义如下谓词：尸(X)：%是科学工作者Q(x):x是刻苦钻研的/?(光)：是聪明的S(x):%在他的事业中将获得成功定义个体a：华为于是命题符号化为：(Vx)(P(x)T Q(x),(Vx)(P(x)A Q(x)A R(x)-5(x),P(a)A R(a)=S(a)推理如下：(i)(VX)(P(x)f Q(x)P(2)尸(a)-Q(q)u s(1)(3)P(a)A R(a)p(4)T(3)(5)R(a)T(3)(6)Q(a)T(2)(4)(7)(Vx)(尸(x)A Q(x)A R(x)-S(x)P(8)P(a)A Q(a)A R(a)T S(a)US(7)(9)尸(a)A Q(a)A R(a)T(3)(6)(10)S(a)T(8)(9)(d)每位资深名士或是中科院院士或是国务院参事，所有的资深名士都是政协委员。张伟是资深名士，但他不是中科院院士。因此，有的政协委员是国务院参事。解：首先定义如下谓词：P(%):%是资深名士Q(x):x是中科院院士R(x):%是国务院参事S(x):%是政协委员定义个体a：张伟于是命题符号化为：(Vx)(P(x)t Q(x)V 7?(x),(Vx)(P(x)-S(%),P(a)AQ(a)n (3x)(5(x)A/?(%)推理如下：(1)尸(Q)八-iQ(Q)p(2)T(1)(3)iQ(a)T(1)(4)(Vx)(尸 f S(x)P(5)P(a)f S(a)US(4)(6)S(a)T(2)(5)(e)每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除。并不是所有的自然数都能被2所整除。因此，有的自然数是奇数。解：首先定义如下谓词：(7)(Vx)(P(x)f Q(x)v R(x)p(8)P(a)0(a)v R(a)US (7)(9)Q(a)v R(a)T (2)(8)(1 0)R(a)T (3)(9)(1 1)S(a)A R(a)T (6)(1 0)(1 2)0 尤)(5(%)A R(x)E G (1 1)N(X)：X是自然数。(无)：%是奇数0(%)：X是偶数P(%)：X能被2整除于是命题符号化为：(Vx)(N(x)-(2(x)VO(x),(Vx)(7V(x)-(0(X)-P(x),i(Vx)(7V(x)-P(%)n (*)(N(x)A Q(X)推理如下：(1)(Dx)(N(x)-P(%)P(2)(Hx)(N(x)八-TP(X)T(1)(3)N(G)A-1P(a)E S (2)(4)N(a)T (3)(5)-1P(a)T (3)(6)(V%)(N(x)-(0(x)3 P(x)P(7)N(a)f(0(a)P(a)us(6)(8)0(a)0尸(a)T (4)(7)(f)如果一个人怕困难，那麽他就不会获得成功。每个人或者获得成功或者失败过。有些人未曾失败过，所以，有些人不怕困难。解：首先定义如下谓词：(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)A Q(a)T(4)(13)(15)(3x)(2V(x)A 2(x)EG(14)尸(X)：%是人Q(x):尤怕困难/?(%):%曾获得成功S(x)：%曾获得失败于是命题符号化为：(Vx)(P(x)A Q(x)TR(x),(Vx)(P(x)T (/?(%)V S(x),0%)(P(X)AMX)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)v S(a)T(3)(6)解：错误，第 2 行的y 是泛指，第 4 行的y 是特制(8)R(a)T(4)(7)(9)(Vx)(P(x)A Q(x)t-J?(x)P(10)P(a)A Q(a)ijR(a)US(9)(11)(P(a)A Q(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)AQ(X)EG(14)4.第 4 0 页第5 题更改如下：(1)0 x)P(x)P(2)尸(y)ES(1)(3)(W x)(P(x)f Q(x)P(4)P(y)-Q(y)US(3)(5)Q(y)T(2)(4)(6)(3x)Q(x)EG(5)5.第 40页第6 题(a)(Bx)P(x)-(Vx)(P(x)v Q(x)-R(x),0 x)P(x),(川 匆 x)n (川 0y)(R(x)A R(y)证明:(1)(3x)P(x)PP(a)5,(1)(3x)2(x)P(4)Q(b)E S,(5)(玉)P(x)f(Vx)(P(x)vQ(x)-R(x)P(6)(Vx)(P(x)vQ(x)f R(x)(1),(5)(P(a)vQ(a)-R(a)US,(6 )(8)P(a)vQ(a)T,(2 )RT,，(1 0X P(b)vQ S)-R S)US,(6)(1 1)PS)vQ(b)T,(4)(1 2)R(b)T,(1 0),(U)(1 3)R(a)八 R(b)T,，（(1 4)(寺)(R(a)AR(y)E G,(1 3)(1 5)0 x)0y)(R(x)AR(y)E G,(1 4)(b)(3x)P(x)-(Vx)Q(x)n (Vx)(P(x)-0(x)证明：(1)0 x)P(x)-(Vx)Q(x)P(2)-0 x)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页 第1题(a)x)(P(x)f(十)。(田)解:(Vx)(P(x)r(寺)。(y)o (V元)(P(x)v(寺)Q(y)o (V%)0y)(P(x)v Q(y)(b)(Vx)(Vy)(3z)(P(x,y)AP(y,z)-(3u)Q(x,y,)解：(Wx)(W)，)(0z)(P(x,y)A P(y,z)f 0”)Q(x,)，,)o (Vx)(Vy)(切(P(x,y)A P(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)v Q(x,y,u)(c)(V x)6y)A(x,y)T (3x)(Vy)(B(x,y)(Vy)(A(y,x)T B(x,y)解：T V x)(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)T B(x,y)o (Vx)(3y)A(x,y)v(3x)(Vy)(B(x,y)(Vy)(A(y,x)v B(x,y)o (Vx)(3y)A(x,y)v(3w)(Vv)(B(u,v)A(VZ)(-V4(Z,W)V B(U,Z)O(VX)(39(3M)(VV)(VZ)(A(X,y)v(B(u,v)A(T1(Z,W)V B(U,Z)7.第42页第2题(b)(Vx)(P(x)T (Vy)(Vz)2(x,z)T TVz)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)vR(x,)o (Vx)(Vy)(七)G”)(P(x)vQ(x,z)v T?(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)vQ(x,z)v T?(龙,)(d)(Vx)(P(x)t Q(x,y)t (中)P(y)A 0z)Q(y,z)解：前束析取范式：(Vx)(P(x)t Q(x,y)-(寺)尸(y)A 0z)Q(y,z)o TVx)(P(x)-Qx,y)v(中)尸(y)A(出)。(%z)o(Vx)(P(x)v Q(x,)，)v(0y)P(y)A(Bz)g(y,z)o (3x)(P(x)A Q(x,y)v(十)P(y)A(玉)Q(y,z)o 0 x)(P(x)A 2(X,M)v(0y)P(y)A 0Z)Q(,Z)o (3x)(3y)(2z)(P(x)A Q(X,U)V(P(y)A Q(U,Z)前束合取范式：(Vx)(P(x)-Q(x,y)-(h)P(y)A 0z)Q(y,z)o (土)(力)0z)(P(x)A 0(xM)v(P(y)A 0 3,z)o (3x)(3y)(3z)(P(x)v(P(y)A Q(U,Z)A(Q(X,)V(P(y)A Q(U,Z)(3x)(3y)(3z)(P(x)v P(y)A(P(X)V Q(M,Z)A(Q(X,M)V P(y)A(Q(X,“)V Q(U,Z)第三章集合论1 .第 4 6 页第3题给出集合A、B和 C的例子，使得A e B,Be C而解：A=aB=a,bC=a,b,c2 .第 4 6 页第6题(2)1,2,3解：设4=1,2,3则 p(A)=0,l,2,3 p(p(0)解：夕(0)=0p(p(0)=0,0)3 .第 4 6 页第9题(1)解：子集个数2刈2 io i(2)解：元素的奇数的子集个数为=2102(3)解：不会有1 0 2 个元素的子集。4 .第 4 6 页 第 1 0 题解：把 1 7 化为二进制，是 0 0 0 1 0 0 0 1,Bl7=a4,a8；把 3 1 化为二进制，是 0 0 0 1 1 1 1 1,&=。4，。5，4 6，0 7，“8 4,4，%，编码为 0 1 0 0 0 1 1 0，为 B 0 q,如 ，编码为 1 0 0 0 0 0 0 1,为 B a5.第 5 3 页第5 题(1)(A-6)-C =A-(6 UC)证明：(A-B)-C=(AHB)-C=(4 n 8)n c=A P I(B H-c)=A n(6 UC)=A-(BJC)上面是一种简单的方法，还可以利用文字叙述，任取X属于(A-6)-C,。证明。还有一种方法，就是利用第五章的特征函数证明，下面给出过程匕 A-B)-C=匕 4-8)一匕=(A A *%)一A *%)*%A-(8 UC)”A7A*WBUCHA*WB+WC，B*WC)=A(1-(/+LB*C)=WAQTB)Q-C)所以，力(A-B)-C =4-(B UC)从而可得，(A-B)C =A-(B UC)。(2)(A-B)-C =(A-C)-5证明：(A-B)-C=(柏 6)-C=a n B PI c=a n cn 8=(A-C)n B=(A C)8(3)(A-B)-C=(A-C)-(B-C)证明：(A-C)-(B-C)=(A n c)-(3n c)=(A n c)n (8 n c)=(A n c)n(8 u c)=(A n cn B)u(A n cn c)=a n B n c=(A-B)n C=(A-B)-C因 止 匕，(A-5)-C =(A-C)-(5-C)6.第5 3页第9题(1)(A-B)n(A-C)=A解：由于(A B)n(A C)=A ,因此必有A 8 =A且A C =A。也就是4 0|8 =0并且 A P|C =。(2)(A-8)U(A-C)=0解：由于(A B)U(A C)=0，因此必有A 6 =0且A C =0。也就是A q B并且A C o(3)(A-5)n(A-C)=0解：(A-5)n(A-C)=(a n B)n(A n c)=a n c=a n (B U c)因此，(A-B)n(A C)=0意味着4 q(8 U C)(4)(A 6)(A C)=0解:（A-5）（A-C）=（A n B）（A n c）=（A n 6 n s n o）u （a n -cn （A C I 助=（a n B n（A U c）u（A n cn（A U 8）=（A n 8 n c）u（A n 8 n c）=a n。o两种可能，第一种8C =0,即 B=C；第二种，4=8 0。或者4=（8 0。）因此，此题答案为3=C或者 御DC A=（8UC）。7.第 5 3页 第 11题（1）A n（8。）=（4门6）s n o证明：（ADB）（API。）=（A n B n （A n o）u 缶 n cn 缶 n ）=（4rw（A U c）u（A n cn（A UB）=5询 A）u（a n 6 n c）u（A n cn A）u（A n cn 8）=（4 n B n c）u（A n cn B）=A n（6 n c）u（cn 8）=A D（B o因此，A n（BC）=（A A B）（A n o。（2）A U（6C）=（A U 6）（A U C）注 意:这个题目本身不正确，举例如下：全集为 1,2,3,A=,B=2,C=3则A U（8C）=1,2,3 ,（A U 8）（A U C）=2,3,不相等。8.第 5 7页第3 题解：设 A,B,C分别表示骑木马、坐滑行轨道和乘宇宙飞船的儿童集合。由公园的总收入知,IAI+1BI +1C1=70/0.5=140l/in 5 n C h 20iA nB nci+M n B nci+i A n B n ci+iA n 8 n ci=5lA n 5 i+iA n ci+ifin ci=3 8 0。1 +140始CI+IACI BCICI+I ACIBOCI因此，=55+2IAnBnCI=55+40=95没有坐过任何一种的儿童总数为|A n-5 n-c i=75-IAUBUCI=7(lAI+IBI+IC I-IA nB I-IA nC I-IB nC I+IAnBClCI)=75-(140-95+20)=10答：一 共10个儿童没有坐过其中任何一种游乐设备。9.第57页第5题解：设A,B,C分别是学习数学、物理、生物的大一学生集合。由题意可知，141=67,181=47,1 Cl=95,IA C l 81=28,1 A C l C 1=26,13rle 1=27,I An BPI ci=5 0l Af-BQ C I=200-IAUBUCI二2(HDAI+IBI+IC I-IA C lB I-IA nC I-IBClCI+IAnBClCI)=200-(67+47+95-26-27-28+1 AQ fiClCI)=50解方程，得iA n5nci=22因此，一共有22人三门功课都学。10.第5 9页 第1题(1)AX1XJB解：AX1X5=,(2)A2XB解A2X5=,(3)(B x A)2解：B x A =,(B x A)2=1,0 ,2,1 11.第6 0页第2题解：X xy表示在在笛卡尔坐标系中，-3 W x 2且-2 4 y 4 0的矩形区域内的点集。12.第6 0页第3题(1)(A n 6)x(C n O)=(A x C)n(8 x O)证明：任取 X,y6(4 0 8)*(。口。)，有e(AnB)x(CnD)=x e(A D 8)y w (C C l )(x eA A y eC)A(x eB A y G)=e A x CA E BX Du G(A x C)A(B x D)由%,y取值的任意性知，(A n 8)X (C n。)=(A X C)n (8 X。)。(2)当且仅当才，才有(A n B)U C =A n(6 U C)证明：当C =A时，AUC=A,于是(A n B)U C =(A U C)n(B U C)=A n(B U C)。当(A n s)u c =A n(B u c)时，任取 xe C,可知 x e(A n 5)U C，由(A n B)U C =A C K B U C)知 x e A n(8 U。)，于是得到xe A。所以，CqA。13.第 6 0 页第5 题(这种题目也可以不推理，只要举出反例即可)(1)(A U 8)x(C U O)=(A x C)U(5 x O)解：任取九,丁e(A U 8)x(C U 0 Me(A U B)x(C U D)o x e(A U B)y e(C U。)(xGAvxeB)A(y e C v y e D)o(x e A A(y e C v y e )v(x e B A(y e C v y e )(xeA A yeC)v(xeA A yeD)v(xeB A yeC)v(xeB A ye)0%,ye(4 x C)U(A x 0 U(8 x C)U(B x O)选择 A=1,B=2,C=a ,D=b 则(A U 8)x (C U 0=,(A x C)U(8 x O)=l,a ,2,b 因此该等式不成立。(2)(A-8)x(C-O)=(A x C)-(8 x)解：任取 龙,yc(A-8)x(C 。)，有e(A-B)x(C-D)=e(Afi 8)x(CQ D)o%e(Ad B)A y e(CH D)o(x c A/x e B)/(y e C/y e )(xeAAyeC)A(xB A yZ)(xeAAyeC)A(xjB A yD)0 (%eA A yeC)A-i(x e B v y e D)选择 A=1,2,B=,C=a,b ,D=a(A-B)x(C-D)=)(A x C)-(6 x O)=,因此，该等式不成立.(3)(A 5)x(C O)=(A x C)(B x O)解:设人=1,2,B=,C=3,4 ,D=4 则(4 B)x(C )=(AxC)3。)=1,3,因此，该等式不成立。(4)(A-8)xC=(AxC)-(8xC)解：取x,ye(A-3)xC,有e(A-B)x C=e(AH B)x Co x e(Ad S)A y G Co(x e A A)?eC)A(xB vyC)o(x e A A y eC)A i(x G B A y e C)O (X,ye A xC)(Bx C)o e(A x C-B x C)因此，该等式成立。(5)(A8)xC=(AxC)(BxC)解：任取取x,yG(AXC)(8xC),有%,yc(A x C)(8 x C)(x e A A y e C)A i(x c 8 A y c C)v(x e B A y e C)A I(X e A A y e C)o(x eA A y eC)A(xeB vy C)v(xeB A yeC)A(x g/lv y C)0(%eA/yeC/%e8)v(xeA/xeB/yeC)=(XGAA XJB)V(XWAAXG B)A y EC=尤 e(AC 8)U(A n 5)y c Co x e A B/yeC0%,ye(A B)x C因此，该等式成立。第四章二元关系1.第6 3页第2题解：&U&2=1，2,2,4,3,3,1,3,4,2 鸟(?&=2,4 0(7?,)=1,2,3)。()=1,2,4 R(R J =2,3,4 R()=2,3,4。(鸟 U%)=1,2,3,4 7?(-0&2)=42.第6 3页第3题解：L=1,1,1,2,3,3,3,6,6,6。=,2,2,2,6,L 0。=,3.第6 3页第4题证明：设 D(R)=A,D(S)=B。(1)任取xe AUB，则分为两种情况，1 6 4或%6 3。当c A时，由R是自反的，知 e/?,于是 x,%e RUS；当re B时，由S是自反的，知 九,xe S,于是 x,xe RUS。因此不管任何情况，(VX)X GA U B，e RJ S,RUS是自反的。(2)任取光e AClB,则为e A且xe B。由R和s都是自反的，知 x,xe R并且GS,于是 x,xe RnS。因此R C|S是自反的。4 .第6 3页第5题证明:设 D(R)=A,D(S)=B。(1)任取xe AnB,则X GA且尤由R和S都是自反的，知%,XGR并且 x,x eS,于是%,xe RnS。因此R C I S是自反的。(2)任取x,y A CR C IS,则%,yc R并且x,ye S。由R和s是对称的，知 e R并且 e S,于是丁,光6R|5。因此，A P I S是对称的。(3)任取 e Rd S,y,z e C l S,可得%,yeR,y,ze R 并且x,yeS,y,ze S。由R是可传递的，知%,ze/?；由s是可传递的，知x,ze S。于是x,ze RnS。因此，R p|S是可传递的。5 .第6 3页第7题解：任取X GS,除5外，E ,但5,5e R ,因 此R是不自反的；若 R ,即 +y =1 0,可得 y+x =1 0,e R ,知 R 是对称的;3,7eR,7,3e R,但3,3任火，可得R是不可传递的。综上，R是不自反的、对称的、不可传递的。6 .第6 3页第8题解：(1)R是集合A上的二元关系，A为空集。(2)R 是集合 A 上的二元关系，A=1,2,R =1,1。(3)R是集合A上的二元关系，A为空集。(4)R是集合A上的二元关系,A=1,2,3,/?=,1,37.第6 9页 第1题解：0肛=123010101001020001310108.第69页 第2题解：设乂=1,2,3,X中的二元关系有2寸=512个。9.第69页 第3题证明：集 合X中的每个二元关系都是X xX的子集，X有个元素，X xX有 2个元素,夕(XxX)有2/个 元 素，每一个元素都是X xX的一个子集，也是一种二元关系，因而,在X中有2一 个不同的二元关系。10.第69页 第4题(仅说明关系的性质)(a)(b)(c)(d)(e)(f)(g)(h)(i)(J)(k)(1)自反的、不对称的、不可传递的；不自反的、反对称的、不可传递的;自反的、对称的、可传递的；自反的、不对称的、不可传递的；不自反的、不对称的、不可传递的;不自反的、对称的、自反的、反对称的、自反的、不对称的、不自反的、对称的、自反的、反对称的、自反的、反对称的、不可传递的;可传递的；不可传递的;可传递的；不可传递的;可传递的；不自反的、反对称的、可传递的。11.第70页 第5题解:&=,&=2,0,3,l(1)RT=,(2)R2 O/?(=,(3)OR2ORI=,(4)R：=,0,3,1,2,(5)R；=01 2 .第70页第6题(1)证明：任取e X,由于K和7?2是自反的，因此%,xcR ，ER2,可得G耳。鸟,由X取值的任意性可知，凡。/?2是自反的。设X =1,2,3禹=1,3,&=,则 鸟。用=,不是反自反的。(3 )设 X =1,2,3,R =1,2,2,1,&=3,2,2,3,则/?!OR2=,不是对称的。(4 )设 X =1,2,3,/?!=,R2=,则/。/?2 =,不是反对称的。(5)设X =1,2,3,4,5,K=,/?,=,3,5,2,5,4,4,则 A。/?=,2,5,5,4,不可传递。1 3.第70页第7题证明：(1)任 取 龙,z6鸟。&，则 一 定 存 在 某 一 个yc X,使 得 x,ycR ,R3由用土宠2知，(3y)(R 八 )n (3y)(&R2 e R3)=G R,O R3根据 X,Z取值的任意性，问题得证，/?,O/?3C/?2O/?3O(2 )任 取 x,ze&。6，则 一 定 存 在 某 一 个ye X,使 得 x,ye/?3，y,ze R ,由&=/?2 知，(3y)(e R3/eRi)=0 y x x,yc&八 y,zc R?)oe R3。R2根据%,z取值的任意性，问题得证，&。飞=&。%。1 4.第75页第4题证明：设R是A上的二元关系，(1)若R是自反的，则由于，的转置仍是/4，因此，“RR，故R是自反的；(2)若R是反自反的，则 口 尺=0。把 和R都取转置，由于的转置仍是，因此，n R=。，故R是反自反的；(3)若R是对称的，任 取 w R,则 e R ,由R的对称性可知，G R,于是%,yG R。由x,y取值的任意性知，R是对称的：(4)若R是反对称的，任取 y,x c E,则 x,y e R,由R的反对称性可知，y,x R,于是由x,y取值的任意性知，R是反对称的；(5)若 R 是可传递得，任取 e R,y,zc R，则 y,xe R ,z,ye R，由R的可传递性，可知 z,xe R，于是 x,ze R。故R是可传递的。1 5 .第75页第5题解：R的关系矩阵上，主对角线有多少个非零值，R CI R的关系矩阵中就有多少非零记入值。1 6 .第79页第2题(画图略去)解：(a)r(7?)=,s(R)=0)=0(b)r(R)=,s(R)=,t(R)=,(c)(图中假设b与c的连线箭头方向指向c)r(7?)=,s(R)=,/(/?)=,1 7.第 8