《离散数学》第一章至第七章-习题详解

1、(2离学课后练习题答1、是命题的国家蒂品课程主讲教捌皿僦於耿索云菲上讣册、（）、（）、（6）H、（）、（$高等教育出版社蔘命题题逻辑基.本概念希PrRfls普通高等教育”十一五”国家级规划教材是简单命题的为（）、（）、（）、（）、（3是真命题的为（）、（）、（）、（）、（）真是值现在不知道的为（13是、3略将.下列命题符号化，并指出真值：（）pAq,其中，p是素数，q是素数，真值为；（）pAq,其中，p：是无理数，q自然对数的底是无理数,真值为；（）pAqq,其中，p是最小的素数，q是最小的自然数,真值为；（）pAq,其中，p是素数，q是偶数，真值为；（）npAqq,其中，p是素数，q是偶数，

2、真值为将下列命题符号化，并指出真值：（）pVq,其中，p是偶数，q是偶数，真值为；（）pVq,其中，p是偶数，q是偶数，真值为；（）pVqq,其中，p是偶数，q是偶数，真值为；（）pVq,其中，p是偶数，q是偶数，真值为；（）npVqq,其中，p是偶数，q是偶数，真值为；（）GpAq）V（pArq）,其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨;（）（pAqq）V（npAq），其中，p：刘晓月选学英语，q：刘晓月选学日语；因为p与q不能同时为真设p记为记可以用多种方法证明*为重言式，下面用等值演算法证明：使用了交换律pq!r)o(VqVqr-qVqVVqAVqVqOqVVqAq都是负数O

3、qVVqAq设两数之积为负数，两数种恰有一个负数，：推理的形式结构为pAqrqAqO-qpVqVAqpr-qqAqrVOqrqAq使用了吸收律OVqAq由于主析取范式中只含有个极小项，故推理不正确略.证.明的命题序列可不惟一，下面对每一小题各给出一个证明pq前提引入P前提引入假言推理前提引入假言推理前提引入前提引入置换前提引入析取三段论前提引入拒取式前提引入置换V置换置换置换一rr2）证明：TOC o 1-5 h zAnVqqpqp3）证明：pqqVqq（pVq）AqpV（AqfV.（证明1）：S结论否定引入前提引入假言推理一q前提引入q假言推论q前提引入r假言推理2）证明：p附加前提引入pr

4、q附加r）-r前提引入r假言推理s化简rst附加r）u前提引入拒取式（证明1）：pnr=rrrr结论否定引入前提引入假言推理前提引入析取三段论前提引入化简rN2)证明：rrrVrrrrprpqrqrpNrqr(Vpq)口pVq(11)口rV合取结论否定引入置换化简化简前提引入拒取式前提引入拒取式合取置换前提引入AV口合取7设：到过受害者房间，在点以前离开，：犯谋杀罪,：看门人看见过A前提：Ar结论：证明：q前提引入rs前提引入rq拒取式前提引入Pr合取（An）-前提引入假言推理（）设：今天是星期六，q我们要到颐和园玩，s颐和园游人太多。前提：一V一n结论：证明：一n前提引入s前提引入nq假言推

5、理p前提引入pV前提引入V假言推理析取三段论（）设小王是理科学生，q小王数学成绩好，r小王是文科学生。前提：一nn结论：证明：p前提引入前提引入r拒取式前提引入拒取式返回r拒取式r拒取式第四章(一阶)谓词逻辑基本概念本章自测答案(1)x(F(x)人rG(x)o*x(F(x)G(x)，其中,F(x)：x是有理数,G(x)：x能表示成分数；rx(F(x)G(x)x(F(x)AqG(x),其中,F(x):x在北京卖菜,G(x):x是外地人；x(F(x)G(x)，其中,F(x):x是乌鸦,G(x):x是黑色的；xF(x)AG(x),其中,F(x):x是人,G(x):x天天锻炼身体。因为本题中没有指明个

6、体域，因而使用全总个体域。.(1)x5(F(x)AG(y)H(x,y),其中,F(x):x是火车,G(y):y是轮船,H(x,y):x比y快；兀片(F(x)AG(y)H(x,y),其中,F(x)：x是火车,G(y)：y是汽车，H(x,y):x比y快；x(F(x)Ay(G(y)H(x,y)ox(F(x)y(G(y)AqH(x,y),其中,F(x)：x是汽车,G(y):y是火车,H(x,y)：x比y快;r*x(F(x)*y(G(y)H(x,y)O日y(F(x)AG(y)AH(x,y),其中,F(x)：x是汽车,G(y)：y是火车,H(x,y)：x比y慢。各命题符号化形式如下：(1y(x.y0)日x

7、y(x.y0)(3y(yx1)(4y(x.yyx)xj(x.)xt(xy=x+y)y0).(1对任意数的实数X和y,若Xy,则X工y；对任意数的实数x和y,若x-y0则xy；对任意数的实数x和y,若xy,则x-y#0；对任意数的实数x和y,若x-y0,则xy.其中,(1)(3)真值为1(2)与(4)真值为0.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。这里仅对、(4)、(给出证明。取解释为：个体域为自然数集合,F(x,y)xWy,在。下，王F(x,y)为真，而3yF(x,y)也为真(只需取x(即可)，于是(3)中公式为真，取解释为：个体域仍为自然数集合而F(x,y

8、)：xy此时，灯xyF(x,y)为真(取y为x即可)，可是3yF(x,y)为假,于是中公式在下为假,这说明(3)中公式为可满足式。设为任意一个解释，若在下，蕴涵式前件xyF(x,y)为假，则日术yF(x,y)灯y日xF(x,y)为真,若前件日xyF(x,y)为真,必存在的个体域1中的个体常项X。,使灯yF(X,y)为真,并且对于任意y1,F(X0,y)为真，由于有X0Z,F(X0,y)为真，所以日xF(x,y)为真,又其中y是任意个体变项，所以WxF(x,y)为真，由于的任意性，所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。(取解释为：个体域为自然数集合,F(x,y)

9、：x=丫在下，(中公式为真，而将F(x,y)改为F(x,y)：xy,(中公式就为假了，所以它为可满足式。(1)取解释为：个体域为自然数集合，F(x)：x为奇数，G(x)：x为偶数，在下，x(F(x)VG(x)为真命题。取解释为：个体域为整数集合，F(x)：x为正整数，G(x)：x为为负整数，在下，x(F(x)VG(x)为假命题。与(3)可类似解答。提示：对每个公式分别找个成真的解释，一个成假的解释。返回第五章谓词逻辑等值演算与推理本章自测答案2.(1)(F(a)AF(b)AF(c)A(G(a)VG(b)VG(c)(2)(F(a)AF(b)AF(c)V(G(a)AG(b)AG(c)(3)(F(a

10、)AF(b)AF(c)f(G(a)AG(b)AG(c)(4)(F(a,y)VF(b,y)VF(c,y)f(G(a)VG(b)VG(c)提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1.的演算如下：VyF(x,y)Ox(F(x,3)VF(x,4)o(F(3,3)VF(3,4)A(F(4,3)VF(4,4)O1A1O1乙说得对，甲错了。本题中，全称量词的指导变元为x，辖域为(F(x)fG(x,y),其中F(x)与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“r”。

11、演算的第二步，在原错的基础上又用错了等值式，即(F(x)A(G(y)fH(x,y)#(F(x)AG(y)-H(x,y)公式的前束范式不唯一，下面每题各给出一个答案。y(F(x)fG(z,y);t(x,y)fG(x,t,z);(3)(4)厂x4(F&,y)fG严，y)A(G(%y)fF(x4,y););(1y(F(x)(2y(F(x)(3y(F(x)(4)Py(F(x)(1)对F(x)f琳5(F(fG(y)f(H(用一L(竿用卢小亚(Fl/E)f(F1)frGU).AG(y)AH(x,y),其中，F(x)x是汽车，G(y)：y是火车，H(x,y)：x比y跑的快;AG(y)fH(x,y),其中，F

12、(x)x是火车，G(y)：y是汽车，H(x,y)：x比y跑的快;AG(y)ArH(x,y),其中，F(x)x是火车，G(y)：y是汽车，H(x,y)：x比y跑的快;AG(y)frH(x,y),其中，F(x)x是飞机，G(y):y是汽车，H(x，y):x比y慢;xG(x)不能使用规则，它不是前束范式，首先化成前束范式。F(x)fxG(x)x(F(y)fG(x)因为量词辖域(F(y)fG(x)中，除x外还有自由出现的y,所以不能使用规则。对xF(x)fyG(y)也应先化成前束范式才能消去量词，其前束范式为xy(F(x)-G(y),要消去量词，既要使用规则，又要使用规则。在自然推理系统F中(规则为A

13、(c)/.日X(x)其中C为特定的个体常项，这里A(y)=F(y)-G(y)不满足要求。这里，使F(a)为真的a不一定使G(a)为真，同样地使G(为真的不一定使卩(为真，如，F(x)x为奇数，G(x)x为偶数，显然肛3)AG为真，但不存在使F(x)AG(x)为真的个体。(这里c为个体常项，不能对F(c)-G(c)引入全称量词。证明：xF(x)前提引入3xF(x)-y(F(y)VG(y)-R(y)前提引入*y(F(y)VG(y)R(y)假言推理F(c)EI(F(c)VG(c)-R(c)UIF(c)VG(c)附加R(c)3xR(x)(证明xF(x)灯x(F(x)-G(a)AR(x)F(c)F(c)

14、-G(a)AR(a)假言推理EG前提引入前提引入EIUIG(a)AR(c)R(c)假言推理化简F(c)AR(c)x(F(x)AR(x)证明：rxF(x)灯xqF(x)rF(c)灯x(F(x)VG(x)F(c)VG(c)F(c)3xF(x)(4)证明灯x(F(x)VG(x)F(y)VG(y)x(qG(x)VqR(x)nG(y)qR(y)xR(x)R(y)hG(y)F(y)xF(x)合取EG前提引入置换UI前提引入UI析取三段论EG前提引入UI前提引入UI前提引入UI析取三段论析取三段论UG7本题不能用附加前提证明法.0.(与1()2)均可用附加前提证明法。设F)(x)：x为偶数，G(x)x能被整

15、除。前提：x(F(x)-G(x)，F()结论：G()(设F(x)：x是大学生，G(x)x是勤奋的，a：王晓山。前提：x(F(x)fG(x),G(a)结论：F(a)设F)(x)：x是有理数，G(x)x是实数，H(x)：x是整数。前提：x(F(x)-G(x)，x(F(x)AH(x)结论：x(G(x)AH(x)证明提示：先消存在量词。设F(x)：x是有理数，G(x)x是无理数，H(x)：x是实数，I(x)：x是虚数。前提:x(F(x)VG(x)H(x)，x(I(x)fH(x)结论：x(I(x)f(rF(x)ArG(x)证明*x(I(x)f(H(x)I(y)H(y)前提引入UIbx(F(x)VG(x)

16、-H(x)(F(y)VG(y)H(y)rH(y)f(F(y)AG(y)I(y)f(F(y)AG(y)前提引入UI置换假言三段论x(I(x)GF(x)AG(x)UG设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。前提：xGF(x)fG(x)，x(G(x)VH(x)，xqH(x)结论:xqF(x)证明日xH(x)hH(c)前提引入UIx(G(x)VH(x)G(c)VH(c)G(c)前提引入UI析取三段论灯x(F(x)G(x)F(c)fG(c)qF(c)日xF(x)前提引入UI拒取式UG设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x

17、在事业中获得成功。前提：x(F(x)fG(x)，*x(G(x)AH(x)fI(x)，a：王大海，F(a)，H(a)结论：I(a)证明F(a)前提引入bx(F(x)-G(x)F(a)fG(a)前提引入UIG(a)假言推理H(a)前提引入灯x(G(x)AH(x)fI(x)G(a)AH(a)-I(a)G(a)AH(a)前提引入UI合取I(a)假言推理返回第六章集合代数本章自测答案4.(1)(2)(3)(4)(5)只有(2)为真，其余为假。4(2)1,3,5,6(3)2,3,4,5,；(4),1；(5)4,1,4(1)；(2)1,4,522.(2)、(3)、(4)、(8)、(1为真，其余为假。24.(

18、1)为真，其余为假，因为(PQ)=PPQQ=PCQn0=PAQ(2)(3)(4)的反例：P=1；Q=22.(-B)U(B-A)=(ACb)u(BaSa)=(AUB)A(SbuB)A(AuSa)a(SbuSa)=(aub)aeaS(aab)=(AUB)(AAB)2.(1)(ABC=ASbaSc=aaS(buc)=A(BUC)(2)(AC)(Cs(bsc)=aaSca(sbuc)=(Ancnsb)u(aaScnc)=ACSAC=(A-B)C(3)(A-BC=AaSbaSc=AAScab=(A-C)-B28.(1)AA(BUSa)=(AnB)U(AA)=(AAB)U=AAB=BAAs(SauSb)a

19、Sa)=(Saub)U=(AnB)UA=AU(BA)由第2题有(AB)U(BA)=(AUB)-(AAB)，故(AB)U(Ba)auB。假若3xGAAB，那么xAUB，因此x芒(AUB)(AAB)，与(AB)(AUB)(AAB)=AUB矛盾.ABo*x(xWAfxWB)Ox(x芒Bx芒A)Ox(xWBfxsA)qSa侶BnsauaAUBnAUB而SauFe，因此A匸Bn“AUB=E反之，SauB=EnAA(SauB)=AnAAB=An店B综合上述，ABqSAUB=E店BnAB=nABB-、匚，、匚CC反之ABBn(AB)UBBnAUB_BnAUB=BnA_B综合上述A匚BOABB31任取x,xA

20、nxA=P(A)=年P(B)二xnxB，这可先证AABnAAB,任取x,xCnxCAxeCnxAAxBnxAUB,从而得至UCAUB.再证AABnAAC以由匸aaba,匸aaFb得到。FqnPQ=npQP，反之，PQPnPn(PQPAPnPQ=npQ令=，则有回UY凹，即Y=0.ABnAUa匚buanFbua因为E为全集,BuSae综合上述BA=E.3由AABAC,ACBC利用AUBUD有：(AAC)U(AC)(BAC)U(BC)n(AAC)U(AASc)匚(BAC)U(BASc)n(AA(CuSc)匚(BA(CuSc)nAAEBAEnA匚B37.恒等变形法B=BC(BUA)=BC(AB)=B

21、C(AC)=(BCA)U(BCC)=(ACC)U(BCC)=(AUB)nc=(Auc)nc=c任取x,有xGP(A)nxAnxBnxWP(B),因此P(A)匚P(B).(任取x有xWP(A)nP(B)OxP(A)AxGP(B)OxAAxBOx匚AnBOxWP(AnB)(2)任取x有xGP(A)UP(B)OxGP(A)VxGP(B)OxAAxBnAUBOxGP(AUB)注意与(的推理不同，上面的推理中有一步是“n”符号，而不是“o”符号。反例如下：A=B=2，贝P(A)UP(B)=円，,2P(AUB)=,2,2返回第七章二元关系本章自测答案(1)任取,有e(AnB)X(CnD)xAnBAyGCn

22、DOxGAAxgBAyGCAygDO(xGAAyGC)A(xGBAyGD)OGAXCAGBXDOG(AXC)n(BXD)(2)都为假,反例如下:A=1,B=1,2,C=2,D=3(为假，反例如下A=,B=,C=2为真，证明如下任取x,y有GAX(BnC)X(CnD)OxGAnBAyGBAyGCO(xGAAyGB)A(xGAAyGC)Ox,yGAXBAx,yGAXCOx,yG(AXB)n(AXC)为真，令A=回即可为假，反例如下A=0IA.=2,2,3,3,4,41=2.3，2,4，3,2，3,4，4,2，4,3ULA=2,2,2,3,2,4,3,3,3,4,4,4DA=2,2,2,4,3,3,

23、4,49.(1)1,2,1,4,1,6,2,1,2,2,2,42,6,4,1,4,2,4,4,4,66,1,6,2,6,46,6(2)1,2,2,1;1,1,2,1,4,1,6,1,2,2,4,2,4,4,6,61,2,2,2,4,2,6,2（略）ACB=1,2，2,4，3,3，1,3，4,2,AnB=2,4domA=l,2,3,domB=l,2,4,dom（AUB）=1,2,3,4ranA=2,3,4,ranB=2,3,4,ran（AUB）=4,fld（AB）=1,2,3RR=0,2，0,3，1,31R=1,0，2,0，3,0，2,1，3,1，3,2rRi0,1=0,1,0,2,0,3,1,

24、2,1,3R1,2=2,31.（1）F（GUH）=FGUFH任取x,y，有x,yWF（GUH）Ot（x,tWFAt,yWGUH）O日t（x,tWFA（t,yWGVt,yWH）t（x,tWFAt,yWG）V（x,tWFAt,yWH）0日t（x,tWFAt,yWG）V日t（x,tWFAt,yWH）ox,tFGVx,tFHOx,yWFGUFH(2)和(4)类似可证1.（2任取y,有yWRTUWomx（xWTUWAx,yWR）O日x（xWTVxWW）人x,yWRx（xWAAx,yWR）V（xWWAx,yWR）O日x（xWTAx,yWR）V日x（xWWAx,yWR）OyWRTVyWRWOyWRTnRW（

25、3）任取x,y,有r-x,yWFi（AnB）OxWAnBWFOxWAAxWBAx,yWFO（xWAAx,yWF）（xWBAx,yWF）hhOx,yWFAAx,yWFBFox,yWFAnFB(1)任取x,y，有R_R_x,yW(U)二y,xWUR.Ox,ywVy,xwR_-iRp-iOx,ywVx,ywR-_1Rn_1Ox,ywU(2)和(1)类似可证.只有对称性，因为1+1工10,1,1芒R,R不是自反的，又由于5,5WR，因此R不是反自反的，根据xRyOx+y=10=yRx，可知R是对称的，又由于1,，都是属于R,因此R不是反对称的，1,，都属于R,如果R是传递的，必有1,1属于R.但这是不

26、成立的，因此R也不是传递的.22.(1)关系图如图7.15所示;(P148)(2)具有反自反性、反对称性、传递性.26.（1）R=3,3,3,1,3,5,=3,3,3,1,3,5(2)r(R)=1,1,1,5,2,2,2,5,3,3,3,1,4,4,4,5,5,5,6,6(R)=1,5,5,1,2,5,5,2,3,3,3,1,1,3,4,5,5,4T(R)=1,5,2,5,3,3,3,1,3,5,4,531.(1)R=2,3，3,2，2,4，4,2，3,4，4,3U；(2)R；(3)R.32不是等价关系，因为1,1R,R不是自反的；2不是等价关系，因为R不是传递的，1R3,3R2但是没有1R2；3不是等价关系，因为2,2R，R不是自反的；4不是等价关系，因为R不是传递的。是等价关系。33关系图如图1说示151d=c,d3现取x,有xWAnx,xwRnx,xwRAx,xwRinx,xwRAx,xwnx,xwRQR任取x,y，有x,y丘RAnGRAG1neAy,xwRny,xwRAR任取x,y，y,z，有x,yWRAAy,zWRAnx,ywRAx,ywAy,zwRAy,zwnx,y)ERAy,zGRAx,y)EAy,zw-i-inx,zwRAx