离散数学习题答案(耿素云屈婉玲)

离散数学习题答案习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()pqqr解：原式()pqqrqr()ppqr()()pqrpqr37mm，此即公式的主析取范式，所以成真赋值为011，111。6、求下列公式的主合取范式，并求成假赋值：（2）()()pqpr解：原式()()pprpqr()pqr4M，此即公式的主合取范式，所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）()pqr解：原式()(()())pqrrppqqr()()()()()()pqrpqrpqrpqrpqrpqr()()()()()pqrpqrpqrpqrpqr13567mmmmm，此即主析取范式。主析取范式中没出现的极小项为0m，2m，4m，所以主合取范式中含有三个极大项0M，2M，4M，故原式的主合取范式024MMM。9、用真值表法求下面公式的主析取范式：（1）()()pqpr解：公式的真值表如下：pqrppqpr()()pqpr00010000011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567mmmmmmm习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。前提：,,,pqqrrsp结论：s证明：①p前提引入②pq前提引入③q①②析取三段论④qr前提引入⑤r③④析取三段论⑥rs前提引入⑦s⑤⑥假言推理15、在自然推理系统P中用附加前提法证明下面推理：（2）前提：()(),()pqrsstu结论：pu证明：用附加前提证明法。①p附加前提引入②pq①附加③()()pqrs前提引入④rs②③假言推理⑤s④化简⑥st⑤附加⑦()stu前提引入⑧u⑥⑦假言推理故推理正确。16、在自然推理系统P中用归谬法证明下面推理：（1）前提：pq，rq，rs结论：p证明：用归谬法①p结论的否定引入②pq前提引入③q①②假言推理④rq前提引入⑤r③④析取三段论⑥rs前提引入⑦r⑥化简⑧rr⑤⑦合取由于0rr，所以推理正确。17、在自然推理系统P中构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。则前提：()pqr，p，qs，s结论：r证明：①qs前提引入②s前提引入③q①②拒取式④p前提引入⑤pq③④合取引入⑥()pqr前提引入⑦r⑤⑥假言推理习题五及答案：（P80-81）15、在自然推理系统N中，构造下面推理的证明：（3）前提：(()())xFxGx，()xGx结论：()xFx证明：①()xGx前提引入②()xGx①置换③()Gc②UI规则④(()())xFxGx前提引入⑤()()FcGc④UI规则⑥()Fc③⑤析取三段论⑦()xFx⑥EG规则22、在自然推理系统N中，构造下面推理的证明：（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x)：x为大学生，G(x)：想是勤奋的，c：王晓山则前提：(()())xFxGx，()Gc结论：()Fc证明：①(()())xFxGx前提引入②()()FcGc①UI规则③()Gc前提引入④()Fc②③拒取式25、在自然推理系统N中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海则前提：(()())xFxGx，(()()())xGxHxIx，()()FcHc结论：()Ic证明：①()()FcHc前提引入②()Fc①化简③()Hc①化简④(()())xFxGx前提引入⑤()()FcGc④UI规则⑥()Gc②⑤假言推理1243⑦()()GcHc③⑥合取引入⑧(()()())xGxHxIx前提引入⑨()()()GcHcIc⑧UI规则⑩()Ic⑦⑨假言推理习题七及答案：（P132-135）22、给定1,2,3,4A，A上的关系1,3,1,4,2,3,2,4,3,4R，试（1）画出R的关系图；（2）说明R的性质。解：（1）●●●●（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。26设1,2,3,4,5,6A，R为A上的关系，R的关系图如图7.13所示：（1）求23,RR的集合表达式；（2）求r(R),s(R),t(R)的集合表达式。解：（1）由R的关系图可得1,5,2,5,3,1,3,3,4,5R所以23,1,3,3,3,5RRR，323,1,3,3,3,5RRR，可得3,1,3,3,3,5,n=2nR当；（2）Ar(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6，1()R1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4sRR232()RR...R1,5,2,5,3,1,3,3,4,5,3,5tRRR46、分别画出下列各偏序集,AR的哈斯图，并找出A的极大元、极小元、最大元和最小元。（1）A,,,,,,,,,,,,,IRadacabaebecede解：哈斯图如下：A的极大元为e、极小元为a；A的最大元为e、最小元为a。48、设,B,SAR和为偏序集，在集合AB上定义关系T如下：112211221212,,,AB,,,abababTabaRabSb证明T为AB上的偏序关系。证明：（1）自反性：1111111111112212121111,ABRRSbSbRbSb,,,,TabaaaaabTabaRabSbabTab任取，则：为偏序关系，具有自反性，为偏序关系，具有自反性，又，，故满足自反性（2）反对称性：112211222211121221211221121221121122,,,AB,,,,RSbb,,TabababTababTabaRabSbaRabSbaRaaRaaabSbbSbabab任取，若且，则有：（1）（2），又为偏序关系，具有反对称性，所以，又为偏序关系，具有反对称性，所以，故满足反对称性eabcd（3）传递性：11223311222233112212122233232312231312231313131133,,,,AB,,,,,,,,,R,SbSbbSb,,TababababTababTababTabaRabSbabTabaRabSbaRaaRaaRabSbbSbaRaabTab任取，，若且，则有：又为偏序关系，具有传递性，所以又为偏序关系，具有传递性，所以，故满足传递性。综合（1）（2）（3）知T满足自反性、反对称性和传递性，故T为AB上的偏序关系。习题九及答案：（P179-180）8、S=QQ,QSa,b,x,ya,bx,yax,ay+bS为有理数集，为上的二元运算，有（1）S运算在上是否可交换、可结合？是否为幂等的？（2）S运算是否有单位元、零元？如果有，请指出，并求出中所有可逆元素的逆元。解：（1）,a,bxa,xb+yax,bx+ya,b,xyxy运算不具有交换律,a,bc,dax,bx+yc,dacx,adx+bx+y,a,bc,d,*ac,ad+bxac,xad+xb+yacx,adx+bx+y,a,bc,dxyxyxyxy而运算有结合律2a,bsa,ba,ba,a,badb任取，则有：运算无幂等律（2）a,b*,a,ba,bsax,ay+ba,ba,bsaxaax10a,baybbay0x10x1y0y0101010xy令对均成立则有：对均成立对成立必定有运算的右单位元为，，可验证，也为运算的左单位元，运算的单位元为，a,b*,,,a,bsa,b*,,ax,ay+b,a1x0axxa1y+b0aybya1y+b0a,bsa,b*,,a,bsxyxyxyxyxyxyxyxy令，若存在使得对上述等式均成立，则存在零元，否则不存在零元。由由于不可能对均成立，故不可能对均成立，故不存在零元；a,b,a,b*,e101xax1aaayb0byaa0a,b1baa,b,aaxyxy设元素的逆元为，则令，（当0）当时，的逆元不存在；当0时，的逆元是11、S12SS?设，，...,10，问下面的运算能否与构成代数系统，如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。（3）xyxy=大于等于和的最小整数；解：（3）由*运算的定义可知：xy=max(x,y)，x,yS,xySSS有，故运算在上满足封闭性，所以运算与非空集合能构成代数系统；x,yS,xy=max(x,y)=max(y,x)=y,x任取有所以运算满足交换律；x,y,zS,xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x(yz),任取有(所以运算满足结合律；xSx1=max(x,1)=x=max(1,x)=1x,任取，有所以运算的单位元是1；xSx10=max(x,10)=10=max(10,x)=10x,任取，有所以运算的零元是10；16、1212V1,2,3,,1,xyV5,6,,6xyVVxyxy设其中表示取和之中较大的数。，其中表示取和之中较小的数。求出和的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。111V1,2,3,,1,1,,1,1,2,,1,1,3,,1V1,2,3,,1,1,,1V1,,1,1,2,,1,1,3,,1解：（1）的所有的子代数是：；的平凡的子代数是：；的真子代数是：；222V5,6,,66,,6V5,6,,66,,6V6,,6（2）的所有的子代数是：，；的平凡的子代数是：，；的真子代数是：。习题十一及答案：（P218-219）1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（b）不是格，因为{d,e}的最大下界不存在；（d）不是格，因为{b,c}的最小上界不存在；（e）不是格，因为{a,b}的最大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。（1