离散数学习题答案(二)

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

2、)(11)0)(00)1(pqr)(Pq)r)11119、用真值表判断下列公式的类型：(pp)q(2)解：列出公式的真值表，如下所示：ppqq(pp)(pp)qooiiiioiioioiooioiiioooi由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：(pq)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：p(pq)1成真赋值有：01,10,11。所以公式的习题二及答案：(P38)5、求下列公式的主析取范式，并求成真赋值:(2)(pq)(qH解：原式(pq)|r(pp)qrqr,此即公式的主析取范式，mm(pqr)(pq

3、r)37所以成真赋值为011,111。*6、求下列公式的主合取范式，并求成假赋值：(2)(Pq)(P力解：原式，此即公式的主合取范式，M(Ppr)(pqr)(pqr)4所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：(1)(pq)r解：原式p|(rr)(pp)(qq)r)(pqr)(pq)r(pq)r(p()r(pq)r(pqr(PqB(Pq)HPq(pq)r(pq，此即主析取范式。mmminm13567主析取范式中没出现的极小项为，所以主合取范式中含有三个极大项，MMmmm02024,故原式的主合取范式。MMMM40249、用真值表法求下面公式的主析取范式:(1

4、)(pq)(Pr)解：公式的真值表如下:PPPqPr(pq)(Pr)00010000011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式mmmmmmm1234567习题三及答案：(P52-54)11、填充下面推理证明中没有写出的推理规则。前提：P%qUs,p结论：s证明：p前提引入前提引入pqq析取三段论前提引入qrr析取三段论rs前提引入s假言推理15、在自然推理系统P中用附加前提法证明下面推理：(2)前提：(pq)(rs),(st)U结论：Pu证明

5、：用附加前提证明法。p附加前提引入附加pq前提引入(pq)as)rs假言推理s化简 附加St 前提引入(st)Uu假言推理故推理正确。16、在自然推理系统P中用归谬法证明下面推理:rs(1)前提：，pqrq结论：p证明：用归谬法p结论的否定引入前提引入pq 假言推理 前提引入rq 析取三段论rfs 前提引入r化简 合取rr由于，所以推理正确。rr017、在自然推理系统P中构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。解：设p：A到过受害者房间，q：A在11点以前离

6、开，r：A是谋杀嫌犯，s：看门人看见过AoS则前提：，pqs(Pq)r结论：r证明: 前提引入qsS 前提引入 拒取式qp 前提引入合取引入q前提引入q)r假言推理习题四及答案：(P65-67)5、在一阶逻辑中将下列命题符号化：(2)有的火车比有的汽车快。解：设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快；则命题符号化的结果是：工y(F(x)G(y)H(xfy)(3)不存在比所有火车都快的汽车。解：方法一：设F(x):x是汽车，G(y):y是火车，H(x,y):x比y快；则命题符号化的结果是：x(F(x)y(Gfr)H(x,y)工(Fy(C(y)H(x,y)方法二：设F(x)

7、:x是火车，G(y):y是汽车，H(x,y):x比y快；则命题符号化的结果是：x(G(x)y(F(y)H(x,y)ky(G(x)(F(y)或9、给定解释I如下：(a)个体域为实数集合Ro30(b)特定元素。ffey)x禹)R(c)函数。F(*y):y,G(i,y):x国丫R(d)谓词。给出以下公式在I下的解释，并指出它们的真值：Ky(F(ffcy),a)G亿y(2)工yGyoky)解：解释是：，含义是：对于任意的实数x,y,若x-y=0则x=2，HR尸RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6A1s(l)RR1,55，L24523,U”JC4232t(R

8、)RRK.RR13M.541、设A=1,2,3,4,R为AAa.b,qdAA上的二元关系，a.bRc.dabed(1)证明R为等价关系；(2)求R导出的划分。(1)只需证明R具有自反性、对称性和传递性即可,证明过程如下：lbAAa：bRa：babab(a)任取，有，所以R具有自反性；a,b,c.dAAa.bRc.d(b)任取，若，cJRa：babc-dcdab则有，所以R具有对称性；a,b,c,d，也fAAa.bRc?dchdRchf(c)任取，若且，edefabefRcfabed则有且，所以R具有传递性，AA综合(a)(b)(c)可知：R为集合上的等价关系；AA(2)先求出集合的结果:AA1

9、.1.1,2.1.3,L4.2.1,2.2.2,3、2.4.3d.3.2,3:4:4,1:4:2.蜡：4,4jAA再分别求集合各元素的等价类，结果如下：1：11U：R1:2f2:11(L2:2:1RR1,32,23,11,3,2,2,3,1,RRRL42,33,24,11,4,2,3,3,2,4,1,RRRR2,43,34,22,4,3,3,4,2,RRR3,44,33,4,4,3,RR4,44,4ORA/RA/R等价关系R导出的划分就是集合A关于R的商集，而集合A关于R的商集是由R的所有等价类作为元素构成的集合，所以等价关系R导出的划分是：14,1,2,2,1,1,3,2,2，3,1,1,4

10、,2,3,3,2,4,1,2,4,3,3,4,2,3,4,4,3,494)A,R46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。(1)Ra,d,c,a,b,a,e,b,e,c,e,d?eI解：哈斯图如下:ebcdfaA的极大元为e、f,极小元为a、f;A的最大元和最小元都不存在。A1,2,3,4*22、给定，A上的关系，试R1,3,142,3,2,4,3,4(1)画出R的关系图；(2)说明R的性质。解：(1)1234(2)R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的;R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系

11、图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。A,R和B,S*48、设为偏序集，在集合上定义关系T如下：ABa?b,a,bAB,1122a,bTa,baRabSb证明T为上的偏序关系。AB证明：（1）自反性：任取a,bAB,则：11r为偏序关系，具有自反性，aRa11s为偏序关系，具有自反性，bSb11aRabSb1111又a.bTa,baRabSb,a,bTa?b,故T具有自反性1111(2)反对称性：任取aMbAB,若a,bTa,b且a,bTa,b,则有：1aRabSb(1)1212aRabSb2121aRaaRa,又r为偏序关系，具有反对

12、称性，所以aa122112bSbbSb,又s为偏序关系，具有反对称性，所以bb122112a,ba,b?故t具有反对称性1122(3)传递性：任取a,b,a,b,卜B,若a,bTa,b且a,bTa,b,则有:222233a,bTa,baRabSba,bTa,baRabSbaRaaR4又r为偏序关系，具有传递性，所以aRa122313bSbbSb,又s为偏序关系，具有传递性，所以bSb122313aRabSba?bTa,b,故t具有传递性。综合(1)(2)(3)知T具有自反性、反对称性和传递性，故T为上的偏序关系。AB习题九及答案:P179-180)8、S=QQ，Q为有理数集，为S上的二元运算，

13、a,b,x,ys有a,bx，yax,ay+b(1)运算在S上是否可交换、可结合？是否为哥等的？。运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元解：(1)x,ya,bxa,xb+yaxbx+ya,bx,y运算不具有交换律x,ya,bc,dax?bx+yc,dacx,adx+bx+y而x,ya,bc,dx,y*ac,ad+bxac,xad+xb+yacx,adx+bx+yx,ya,bc,d运算有结合律任取a,bs,则有：2a,ba,ba,abba,b运算无募等律(2)令a,b*x,ya,b对a,bs均成立则有：ax,ay+ba,b对a,bs均成立axaax10对a,b成立ay

14、bbay0X1Ox1必定有yOy0运算的右单位元为1,0,可验证1,0也为运算的左单位元，运算的单位元为1,0令a,b*x,yx,y,若存在x,y使得对a,bs上述等式均成立，则存在零元，否则不存在零元。由a,bAx,yx,yax,ay+bx,yalx0axXaly+b0ayby由于aly+b0不可能对a,b均成立，故a,b*x,yJ不可能对均成立，故不存在零设元素a,b的逆元为x,y,则令4b*&yel,。1ax1a（当a0）aybOba当a。时，a,b的逆元不存在;1b当a。时，a,b的逆元是！aa11、设SS,?12,10,问下面的运算能否与s构成代数系统如果能构成代数系统则说明运算是否

15、满足交换律、结合律，并求运算的单位元和零元。X丫二大于等于x和y的最小整数解：(3)由*运算的定义可知：，xy=max(x,y)x,y3,有xyS,故运算在s上满足封闭性，所以运算与非空集合S能构成代数系统；任取x,yS,有xy=max(x,y)=max(y,x)=y%所以运算满足交换律；任取x,y,zS,有(xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z)=x(yZ),所以运算满足结合律；任取X3,有xl=max(x?l)=x=max(l,x)=l%所以运算的单位元是1；任取XS,有X1O=max(x,l0)=1O=max(l0,x)=10%所以运

16、算的零元是10;16、设V1,2,3,其中xy表示取x和y之中较大的数。V5,6,6,12其中Xy表示取x和y之中较小的数求出V和V的所有的子代数。12指出哪些是平凡的子代数，哪些是真子代数。解：(1)V中运算的单位元是1,1V的所有的子代数是:1,2,3,1,1,2,1,1,3,1；V的平凡的子代数是：1，2,3,JJ,J；1V的真子代数是:(2)V中运算的单位元是6,V的所有的子代数是:5,63,6,6,6；2V的平凡的子代数是：5,6,6,6, ,6；2V的真子代数是：6,6。2习题H一及答案：（P218-219）1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说

17、明理由解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（b）不是格，因为d,e的最大下界不存在;(d)不是格，因为b,c的最小上界不存在；(e)不是格，因为a,b的最大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。(1) L=1,2,3,4,5;L=1,2,3,6,12;解：画出哈斯图即可判断出：(1)不是格，(2)是格。4、设L是格，求以下公式的对偶式：a(bc)(ab)(ac)(2)a(bc)(ab)(ac)解：对偶式为：，参见P208页定义112a,b,cLabcabbc6、设L为格，且，证明ab,abb,证明：bc,bcb,9、针对图11.11中的每个格，如果格中的元素存在补元，则求出这些补元。解：(a)图：a,d互为补元，其中a为全下界，d为全上界，b和c都没有补元；(c)图：a,f互为补元，其中a为全下界，f为全上界，c和d的补元都是b和e,b和e的补元都是c和d；(f)图：a,f互为补元，其中a为全下界，f为全上界，b和e互为补元，c和d都没有补元。10、说明图11.11中每个格是否为分配格、有补格和布尔格，弁说明理由。解：(a)图：是一条链，所以是分配格，b和c都没有补元，所