离散数学习题答案

离散数学习题答案习题一及答案：（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)(110)1，((pq)r)((11)0)(00)1(pqr)((pq)r)11119、用真值表判断下列公式的类型：(pp)q（2）解：列出公式的真值表，如下所示：ppqq(pp)(pp)q001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：（4）(pq)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：p0(pq)1q0q0成真赋值有：01，10，11。所以公式的习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）(pq)(qr)解：原式(pq)qr(pp)qrqr，此即公式的主析取范式，mm(pqr)(pqr)37所以成真赋值为011，111。*6、求下列公式的主合取范式，并求成假赋值：（2）(pq)(pr)解：原式，此即公式的主合取范式，M(ppr)(pqr)(pqr)4所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）(pq)r解：原式pq(rr)((pp)(qq)r)(pqr)(pq)r(pq)r(pq)r(pq)r(pqr(pqr)(pq)r(pq)r(pq)r(pqr，此即主析取范式。mmmmm13567主析取范式中没出现的极小项为，，，所以主合取范式中含有三个极大项，，MMmmm02024，故原式的主合取范式。MMMM40249、用真值表法求下面公式的主析取范式：（1）(pq)(pr)解：公式的真值表如下：pppqprqr(pq)(pr)00010000011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式mmmmmmm1234567习题三及答x(F(x)y(G(y)H(x,y)))（1）I解：取解释如下：个体域为全总个体域，F(x)H(x,y)G(y)：x是兔子，：y是乌龟，：x比y跑得快，则该公式在解释I下真值是1；''IIH(x,y)取解释如下：：x比y跑得慢，其它同上，则该公式在解释下真值是0；故公式（1）既不是永真式也不是矛盾式。此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。习题五及答案：（P79-81）5、给定解释I如下：(a)个体域D={3,4}f(x):f(3)4,f(4)3(b)F(x,y):F(3,3)F(4,4)0,F(3,4)F(4,3)1(c)试求下列公式在I下的真值：xyF(x,y)(1)解：方法一：先消去存在量词xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4)F)((4F,3)(01)(10)115、在自然推理系统中，构造下面推理的证明：N（3）前提：，x(F(x)G(x))xG(x)结论：xF(x)证明：①前提引入xG(x)②①置换xG(x)③②UI规则G(c)④前提引入x(F(x)G(x))⑤④UI规则F(c)G(c)⑥③⑤析取三段论F(c)⑦⑥EG规则xF(x)*22、在自然推理系统中，构造下面推理的证明：N（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山则前提：，x(F(x)G(x))G(c)结论：F(c)证明：①前提引入x(F(x)G(x))②①UI规则F(c)G(c)③前提引入G(c)④②③拒取式F(c)25、在自然推理系统中，构造下面推理的证明：N每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海则前提：，，x(F(x)G(x))x(G(x)H(x)I(x))F(c)H(c)结论：I(c)证明：①前提引入F(c)H(c)②①化简F(c)③①化简H(c)④前提引入x(F(x)G(x))⑤④UI规则F(c)G(c)⑥②⑤假言推理G(c)⑦③⑥合取引入G(c)H(c)⑧前提引入x(G(x)H(x)I(x))⑨⑧UI规则G(c)H(c)I(c)⑩⑦⑨假言推理I(c)习题六及答案（P99-100）28、化简下述集合公式：((AB)C)((AB)C)((AB)C)((AB)C)（3）((AB)C)((AB)C)((AB)C)((AB)C)解：(AB)(AB)A30、设A,B,C代表任意集合，试判断下面命题的真假。如果为真，给出证明；如果为假，给出反例。(AB)AB（6）(AB)ABABABBA，如果，则解：该命题为假，，否则BABBAB，故为假。(AB)A{3}BA{1,2},B{1,3},举反例如下：则。ABACBC（8）ABAC一定成立，解：该命题为假，举反例如下：如果B，C都是A的子集，则B{1}C{2}1,2}A{ABACABC但不一定成立，例如：，则，,，BC但。33、证明集合恒等式：A(BA)BA（1）A(BA)证明：(AB)(AA)(AB)BAAB习题七及答案：（P132-135）A1,2,3,4,5,626设，R为A上的关系，R的关系图如图7.13所示：23（1）求的集合表达式；R,R（2）求r(R),s(R),t(R)的集合表达式。解：（1）由R的关系图可得R1,5,2,5,3,1,3,3,4,5232所以，，RRR3,1,3,3,3,5RRR3,1,3,3,3,5n可得；R3,1,3,3,3,5,当n>=2（2），r(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6A1s(R)RR1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4232t(R)RRR...RR1,5,2,5,3,1,3,3,3,5,4,541、设A={1，2，3，4}，R为AAa,b,c,dAA上的二元关系，，a,bRc,dabcd（1）证明R为等价关系；（2）求R导出的划分。（1）只需证明R具有自反性、对称性和传递性即可，证明过程如下：a,bAAa,bRa,babab（a）任取，有，，所以R具有自反性；a,b,c,dAAa,bRc,d（b）任取，若，c,dRa,babcdcdab则有，，，所以R具有对称性；a,b,c,d,e,fAAa,bRc,dc,dRe,f（c）任取，若且，cdefabefa,bRe,fabcd则有且，，，所以R具有传递性，AA综合（a）（b）（c）可知：R为集合上的等价关系；AA（2）先求出集合的结果：AA{1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}AA再分别求集合各元素的等价类，结果如下：[1,1]{1,1},R[1,2][2,1]{1,2,2,1},RR[1,3][2,2][3,1]{1,3,2,2,3,1},RRR[1,4][2,3][3,2][4,1]{1,4,2,3,3,2,4,1},RRRR[2,4][3,3][4,2]{2,4,3,3,4,2},RRR[3,4][4,3]{3,4,4,3},RR[4,4]{4,4}。RA/RA/R等价关系R导出的划分就是集合A关于R的商集，而集合A关于R的商集是由R的所有等价类作为元素构成的集合，所以等价关系R导出的划分是：{{1,1},{1,2,2,1},{1,3,2,2,3,1},{1,4,2,3,3,2,4,1},{2,4,3,3,4,2},{3,4,4,3},{4,4}}A,R46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。（1）Ra,d,a,c,a,b,a,e,b,e,c,e,d,eIA解：哈斯图如下：ebcdfaA的极大元为e、f，极小元为a、f；A的最大元和最小元都不存在。A1,2,3,4*22、给定，A上的关系，试R1,3,1,4,2,3,2,4,3,4（1）画出R的关系图；（2）说明R的性质。解：（1）12●●●●34（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。A,R和B,S*48、设为偏序集，在集合上定义关系T如下：ABa,b,a,bAB,1122a,bTa,baRabSb11221212证明T为上的偏序关系。AB证明：（1）自反性：任取a,bAB，则：11R为偏序关系，具有自反性，aRa11S为偏序关系，具有自反性，bSb11aRabSb1111又a,bTa,baRabSb，11221212a,bTa,b，故T具有自反性1111（2）反对称性：任取a,b,a,bAB，若a,bTa,b且a,bTa,b，则有：112211222211aRabSb（1）1212aRabSb（2）2121aRaaRa，又R为偏序关系，具有反对称性，所以aa122112bSbbSb，又S为偏序关系，具有反对称性，所以bb122112a,ba,b，故T具有反对称性1122（3）传递性：任取a,b,a,b，a,bAB，若a,bTa,b且a,bTa,b，则有：11223311222233a,bTa,baRabSb11221212a,bTa,baRabSb22332323aRaaRa,又R为偏序关系，具有传递性，所以aRa122313bSbbSb,又S为偏序关系，具有传递性，所以bSb122313aRabSba,bTa,b，故T具有传递性。13131133综合（1）（2）（3）知T具有自反性、反对称性和传递性，故T为上的偏序关系。AB习题九及答案：（P179-180）8、S=QQ,Q为有理数集，为S上的二元运算，a,b,x,yS有a,bx,yax,ay+b（1）运算在S上是否可交换、可结合？是否为幂等的？（2）。运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元解：（1）x,ya,bxa,xb+yax,bx+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成立aybbay0x10x1必定有y0y0运算的右单位元为1，0，可验证1，0也为运算的左单位元，运算的单位元为1，0令a,b*x,yx,y，若存在x,y使得对a,bs上述等式均成立，则存在零元，否则不存在零元。由a,b*x,yx,yax,ay+bx,ya1x0axxa1y+b0ayby由于a1y+b0不可能对a,bs均成立，故a,b*x,yx,y不可能对a,bs均成立，故不存在零元；设元素a,b的逆元为x,y，则令a,b*x,ye1，01xax1a（当a0）ayb0bya当a0时，a,b的逆元不存在；1b当a0时，a,b的逆元是,aa11、设S12，，...,10，问下面的运算能否与S构成代数系统S，?如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。（3）；xy=大于等于x和y的最小整数解：（3）由*运算的定义可知：，xy=max(x,y)x,yS,有xyS，故运算在S上满足封闭性，所以运算与非空集合S能构成代数系统；任取x,yS,有xy=max(x,y)=max(y,x)=yx,所以运算满足交换律；任取x,y,zS,有(xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x(yz),所以运算满足结合律；任取xS，有x1=max(x,1)=x=max(1,x)=1x,所以运算的单位元是1；任取xS，有x10=max(x,10)=10=max(10,x)=10x,所以运算的零元是10；16、设V1,2,3,,1,其中xy表示取x和y之中较大的数。V5,6,,6，12其中xy表示取x和y之中较小的数。求出V和V的所有的子代数。12指出哪些是平凡的子代数，哪些是真子代数。解：（1）V中运算的单位元是1，1V的所有的子代数是：1,2,3,,1,1,,1,1,2,,1,1,3,,1；1V的平凡的子代数是：1,2,3,,1,1,,1；1V的真子代数是：1,,1,1,2,,1,1,3,,1；1（2）V中运算的单位元是6，2V的所有的子代数是：5,6,,6，6,,6；2V的平凡的子代数是：5,6,,6，6,,6；2V的真子代数是：6,,6。2习题十一及答案：（P218-219）1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（b）不是格，因为{d,e}的最大下界不存在；（d）不是格，因为{b,c}的最小上界不存在；（e）不是格，因为{a,b}的最