离散数学习题答案

1、离散数学习题答案习题一及答案：(P14-15)14、将下列命题符号化：(5)李辛与李末是兄弟解：设p：李辛与李末是兄弟，则命题符号化的结果是p(6)王强与刘威都学过法语解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是Paq(9)只有天下大雨，他才乘班车上班解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是q-*p(11)下雪路滑，他迟到了解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(PAq)Tr15、设p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：(4) (pq一卜(P飞)>r)解：p=1,q=1,r=0,(pAqA-

2、'r)(IrdA-1。)1,(-p-q).r)=(-1-1)-；0)=(0.0)=1.(pqr)(pq)rr)=1二119、用真值表判断下列公式的类型：(2)(pp)q解：列出公式的真值表，如下所示:pq*q(pT%)(pT”)Tq001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：(4)(p，q)Tq解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：厂(pq)：=1p：=0q=0q=0所以公式的成真赋值有：01,10,11。习题二及答案：(P38)5、求下列公式的主析取范式，

3、并求成真赋值：(2) (ptq)A(qAr)解：原式:(pq)qr=qr=(-pp)qra(-'pAqAr)v(pAqAr)m3vm7,此即公式的主析取范式，所以成真赋值为011,111。6、求下列公式的主合取范式，并求成假赋值：(2) (pAq)v(pvr)解：原式二(pvpvr)A(pvqvr)(pqDuM4,此即公式的主合取范式，所以成假赋值为10007、求下列公式的主析取范式，再用主析取范式求主合取范式：(1) (pAq)vr解：原式=pq(-rr)(一pp)(一qq)r)=(pq-r)(pqr(pq)r(p_q)r(pqr(pqr二(下qr)(pqr(pq-)r(pq)r-(

4、pqr:二m1m3m5m6m7此即主析取范式。主析取范式中没出现的极小项为m。，m2,m4,所以主合取范式中含有三个极大项M。，M2,M4,故原式的主合取范式UM0AM2AM409、用真值表法求下面公式的主析取范式:(1)(pvq)v(pAr)解：公式的真值表如下:pqrFpvqp(pvq)v(-pAr)000100000110110101101011111110001011；010110111001011110101由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式um1Vm2Vm3Vm4Vm5Vm6Vm7习题三及答案：(P52-54)11、

5、填充下面推理证明中没有写出的推理规则。前提：一pq,-qr,rs,p结论：s证明：p前提引入pq前提引入q析取三段论qr前提引入r析取三段论rts前提引入s假言推理15、在自然才t理系统P中用附加前提法证明下面推理:(2)前提：(p¥q)T(rAS),(SMt)Tu结论：p-u证明：用附加前提证明法。p附加前提引入pq附加(pvq)->(raS)前提引入rssstft言推理化简附加(st)u前提引入u故推理止确。ft言推理16、在自然推理系统P中用归谬法证明下面推理:(1)前提：ptrq,rq,ras结论：-p证明：用归谬法p结论的否定引入p-q前提引入-q假言推理一rq前提引

6、入一r-srr-r析取三段论前提引入化简合取由于rAr=0,所以推理正确。17、在自然推理系统P中构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过Ao则前提：(pAq)Tr,p,qTs,s结论：r证明：q-s前提引入前提引入-q拒取式p前提引入合取引入前提引入假言推理p-q(p-q)>rr习题四及答案：(P65-67)5、在一阶逻辑中将下列命题符号化：(2)有的火车比有的汽车

7、快。解：设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快；则命题符号化的结果是：xy(F(x)G(y)H(x,y)(3)不存在比所有火车都快得汽车。解：设F(x):x是汽车，G(y):y是火车，H(x,y):x比y快；则命题符号化的结果是：Fx(F(x)八/y(G(y)TH(x,y)或Vx(F(x)t三y(G(y)八H(x,y)9、给定解释I如下：(a)个体域为实数集合R。(b)特定元素a=0。(c)函数f(x,y)=xy,x,y亡R。(d)谓词F(x,y):x=y,G(x,y):x<y,x,y亡R。给出以下公式在i下的解释，并指出它们的真值：3y(F(f(x,y),a)

8、TG(x,y)解：解释是：VxVy(x-y=0Tx<y),含义是：对于任意的实数x,y,若x-y=0则x<y。该公式在I解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式：(1)Vx(F(x)T3y(G(y)AH(x,y)解：取解释I如下：个体域为全总个体域，F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快，则该公式在解释I下真值是1;取解释I如下：H(x,y)：x比y跑得慢，其它同上，则该公式在解释I下真值是0;故公式(1)既不是永真式也不是矛盾式。此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。习题五及答案：(P80-81)1

9、5、在自然才t理系统N七中，构造下面推理的证明:(3)前提：Vx(F(x)yG(x),FxG(x)结论：xF(x)证明：-xG(x)-xG(x)-G(c)-x(F(x) G(x) F(c) G(c) F(c) xF(x)前提引入置换UI规则前提引入UI规则析取三段论EG规则22、在自然推理系统N中，构造下面推理的证明：(2)凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x):x为大学生，G(x):x是勤奋的，c：王晓山则前提：/x(F(x)tG(x),G(c)结论：-F(c)证明：Vx(F(x)tG(x)前提引入F(c)tG(c)UI规则G(c)前提引入F(c)拒取式25、

10、在自然才t理系统N七中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。(个体域为人类集合)解：设F(x):x是科学工作者，G(x):x是刻苦钻研的，H(x):x是聪明的，I(x):x在他的事业中获得成功，c：王大海则前提：/x(F(x)TG(x),Vx(G(x)aH(x)tI(x),F(c)aH(c)结论：1(C)证明： F(c)H(c) F(c) H(c)-x(F(x)>G(x) F(c)>G(c) G(c) G(c)H(c) -x(G(x) H (x) &

11、gt; I (x)G(c)H(c)I(c)I(c)前提引入化简化简前提引入UI规则假言推理合取引入前提引入UI规则假言推理习题六及答案14习题七及答案：(P132-135)*22、给定A=1,2,3,4,A上的关系R=(1,3,1,4),2,3),2,4),(3,4),试(1)画出R的关系图;(2)说明R的性质。解：(1)(2) R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的;R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。26设A=1,2,3,4,5

12、,6,R为A上的关系，R的关系图如图7.13所示:(1)求R2,R3的集合表达式；(2)求r(R),s(R),t(R)的集合表达式。解：(1)由R的关系图可得R=(1,5),2,5),3,1,(3,3,4,5户所以R2=RnR=(3,1),3,3),3,5),R3=R2R=«3,1),(3,3),(3,5),可得Rn=3,1,(3,3),3,5),当2=2;(2)r(R尸RJa=4,5,2,5),3,1,3,3),4,5),(1,1),<2,2),(4,4),5,5),(6,6户，s(R)=RUR'=1,5；5,1；,25：,；5,2；,：3,1,1,3不3,3；,：4

13、,5；5,4t(R)=RUr2Ur3U.=RUR2=1,5；,：2,5；,；3,1：,；3,3,；3,5,.4,5：)46、分别画出下列各偏序集(A,R的哈斯图，并找出A的极大元、极小元、最大元和最小元。(1) R«=(a,d),(a,c),(a,b),(a,e),(b,e),(c,e),(d©UlA解：哈斯图如下：eA的极大元为e、f,极小元为a、f;A的最大元和最小元都不存在。48、设A,R和(B,S)为偏序集，在集合AmB上定义关系T如下：-ai,b1；,；a2,b2：AB,:a1,b1T:a2,b2Ma1Ra2b1Sb,证明T为AmB上的偏序关系。证明：(1)自反性

14、：任取(aih)EAg则：:R为偏序关系，具有自反性，aiRai'；S为偏序关系，具有自反性，.“Sb,.aRaibiSbi又a,bi.Ta2,b2：=a1Ra2b|Sb2,二(司由广侬心)，故t具有自反性(2)反对称性：任取侬,片),但2口2)亡A黑B,若(a,b)T(a2,b2且色2,4)丁佃川,则有:aRa2八bSb(1)a2RaiAb2Sb(2).aR%a2Ra1,又R为偏序关系，具有反对称性，所以a1=a2.hSbb2Sb,又S为偏序关系，具有反对称性，所以b1=b2二(a1,b1)=(a2,b2),故T具有反对称性(3)传递性：任取回”),92扫2),3也)AmB,若(a1

15、,bi)T心且心广，则有：:ai,nT色2由2.=a1Ra2biSb?:以2力2：丁泪3,上；=a2Ra3bzSba1Ra2na2Ra3，又R为偏序关系，具有传递性，所以a1Ra3二bSt2Ab2S*又S为偏序关系，具有传递性，所以b1Sb3,a1Ra3八b1Sb3n(a1,b1)T(a3,b3),故T具有传递性。综合(1)(2)(3)知T具有自反性、反对称性和传递性，故T为AxB上的偏序关系习题九及答案：(P179-180)8、S=QmQ,Q为有理数集，为*S上的二元运算，V(a,b),(x,y)wS有；a,b)-：x,y)=;：ax,ay+b:(1)邛运算在S上是否可交换、可结合？是否为曷

16、等的？(2) *运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元，解：(1)-x,y；，；a,b；=：xa,xb+y)三；ax,bx+y：=：；a,b;:x,y.产运算不具有交换律x,y'；a,b；c,d=ax,bx+y；cd：二:acx,adx+bx+y而x,y.：a,bc,d；=：x,y,*ac,ad+b=：xac,xad+xb+y；=acx,adx+bx+y二；x,y；:a,b：c,d；产运算有结合律任取；a,b，s,则有：a,b:a,b=a2,adb;=；a,b).产运算无幕等律(2)令(a,b)*(x,y)=(a,b)对V(a,b)ws均成立则有:;ax,

17、ay+b=；a,b；对-a,b；三s均成立1 axafax-10j.«nJl对V(a,b惘乂ayb=bay=0xx-1=0lx=1二必定有口iy=0y=0产运算的右单位元为(1,0),可验证(1©也为“运算的左单位元，产运算的单位元为(1,0)令；a,b*；x,y.;=x,yj,若存在：x,y：使得又t：a,bs±述等式均成立,则存在零元，否则不存在零元。由a,b；*;：x,y；=；x,y=ax,ay+b=；x,y产片ax=xa-1x=0ayb=ya-1y+b=0由于a-1y+b=0不可能对a,bs均成立,故.a,b*；：x,y)=；x,y；不可能对一：a,b-s

18、均成立，故不存在零元;设元素(a,b)的逆元为(x,y),则令(a,b)*(x,y)=e=(1,0)b =0by 二 一一（当 a=0）二当a=0时，(a,b)的逆兀不存在；当a=0时，ab：的逆元是：，-：11设$=12,10,问下面的运算能否与S构成代数系统S)？如果能构成代数系统则说明中运算是否满足交换律、结合律，并求“运算的单位元和零元。(3)*丫=大于等于x和y的最小整数；解：(3)由*运算的定义可知：x*y=max(x,y),x,ywS,有x*ywS,故中运算在S上满足封闭性，所以好运算与非空集合S能构成代数系统；任取x,ysS,<x*y=max(x,y)=max(y,x)=

19、y*x,所以“运算满足交换律；任取x,y,zsS,有(x*y)*z=max(max(x,y),z尸max(x,y,z尸max(x,max(y,z)尸x*(y*z),所以中运算满足结合律;任取xS,有x琳1二max(x,1)=x=max(1,x)=1*x,所以琳运算的单位元是1;任取xS,有x*10=max(x,10)=10=max(10,x)=10*x,所以用运算的零元是10;16、设V1=(1,2,3,*,其中x*y表示取x和y之中较大的数。V2=5,6,6),其中x*y表示取x和y之中较小的数。求出修和V2的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。解：(1)V1的所有的子代数

20、是：Hl,2,3),1；,飞；1m2：",三1,3：1,1)；V1的平凡的子彳t数是：三1,2,3),1；1：1),1；V1的真子代数是：”1，1；,“1,2)，1,.：1,3),1；(2)V2的所有的子代数是：。5,6卜,6,(6,*,6)；V2的平凡的子彳t数是：j5,6,中,6),(6,*,6)；V2的真子代数是：6/,6)。习题H一及答案：(P218-219)1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：(a)、(c)、(f)是格；因为任意两个元素构成的集合都有最小上界和最大下界；(b)不是格，因为d,e的最大下界不存在；(d)不是格，因为b,c的最小上界不存在；(e)不是格，因为a,b的最大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。(