离散数学习题答案.doc

.离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 pq解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是 （9）只有天下大雨，他才乘班车上班 qp解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是 （11）下雪路滑，他迟到了 解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(pq)r 15、设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)111 19、用真值表判断下列公式的类型： (pp)q（2） 解：列出公式的真值表，如下所示： ppqq (pp)(pp)q 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： （4）(pq)q 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： p0(pq)1 q0q0成真赋值有：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，故原式的主合取范式。 MMMM4024 9、用真值表法求下面公式的主析取范式： （1） (pq)(pr)解：公式的真值表如下： pppqprq r (pq)(pr) 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 mmmmmmm1234567 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提： pq,qr,rs,p结论：s 证明： p 前提引入 前提引入 pq q 析取三段论 前提引入 qr r 析取三段论 rs 前提引入 s 假言推理 15、在自然推理系统P中用附加前提法证明下面推理： （2）前提： (pq)(rs),(st)u 结论： pu证明：用附加前提证明法。 p 附加前提引入 附加 pq 前提引入 (pq)(rs)rs 假言推理 s 化简 附加 st 前提引入 (st)u u 假言推理 故推理正确。 16、在自然推理系统P中用归谬法证明下面推理： rs（1）前提：， pqrq 结论： p证明：用归谬法 p 结论的否定引入 前提引入 pq 假言推理 q 前提引入 rq 析取三段论 rrs 前提引入 r 化简 合取 rr由于，所以推理正确。 rr017、在自然推理系统P中构造下面推理的证明： 只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。 s则前提：， pqs(pq)r 结论： r证明： 前提引入 qss 前提引入 拒取式 q 前提引入 p 合取引入 pq 前提引入 (pq)r 假言推理 r 习题四及答案：（P65-67） 5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。 解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是： $x$y(F(x)G(y)H(x,y) （3）不存在比所有火车都快的汽车。 解：方法一： 设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是： $x(F(x)y(G(y)H(x,y)x(F(x)$y(G(y)H(x,y)或 方法二： 设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是： $x(G(x)y(F(y)H(x,y)$xy(G(x)(F(y)H(x,y)或 9、给定解释I如下： (a) 个体域为实数集合R。 -a=0 (b) 特定元素。-f(x,y)=x-y,x,yR (c) 函数。-F(x,y):x=y,G(x,y):xy,x,yR (d) 谓词。 给出以下公式在I下的解释，并指出它们的真值： xy(F(f(x,y),a)G(x,y)（2） xy(x-y=0xy)解：解释是：，含义是：对于任意的实数x，y，若x-y=0则x=2 （2）， r(R)=RUI=1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6A-1 s(R)=RUR=1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4232 t(R)=RURURU.=RUR=1,5,2,5,3,1,3,3,3,5,4,541、设A=1，2，3，4，R为AA,AA上的二元关系，Ra+b=c+d （1）证明R为等价关系； （2）求R导出的划分。 （1）只需证明R具有自反性、对称性和传递性即可，证明过程如下： AARa+b=a+b（a）任取，有，所以R具有自反性； ,AAR（b）任取，若， Ra+b=c+dc+d=a+b则有，所以R具有对称性； ,AARR（c）任取，若且， c+d=e+fa+b=e+fRa+b=c+d则有且，所以R具有传递性， AA综合（a）（b）（c）可知：R为集合上的等价关系； AA（2）先求出集合的结果： AA=,AA再分别求集合各元素的等价类，结果如下： =, R=, RR=, RRR=, RRRR=, RRR=, RR=。 RA/RA/R等价关系R导出的划分就是集合A关于R的商集，而集合A关于R的商集是由R的所有等价类作为元素构成的集合，所以等价关系R导出的划分是： , A,R46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。 （1） R=a,d,a,c,a,b,a,e,b,e,c,e,d,eUI A解：哈斯图如下： e b c d f a A的极大元为e、f，极小元为a、f； A的最大元和最小元都不存在。 A=1,2,3,4*22、给定，A上的关系，试 R=1,3,1,4,2,3,2,4,3,4（1）画出R的关系图； （2）说明R的性质。 解：（1） 1 2 3 4 （2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的； R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的； R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。 A,R和B,S*48、设为偏序集，在集合上定义关系T如下： AB a,b,a,bAB,1122 a,bTa,baRabSb11221212证明T为上的偏序关系。 AB证明：（1）自反性： 任取a,bAB，则：11R为偏序关系，具有自反性，aRaQ11S为偏序关系，具有自反性，bSbQ11 aRabSb1111 又a,bTa,baRabSb，11221212 a,bTa,b，故T具有自反性1111（2）反对称性： 任取a,b,a,bAB，若a,bTa,b且a,bTa,b，则有：112211222211aRabSb（1）1212aRabSb（2）2121 aRaaRa，又R为偏序关系，具有反对称性，所以a=a122112bSbbSb，又S为偏序关系，具有反对称性，所以b=b122112 a,b=a,b，故T具有反对称性1122（3）传递性： 任取a,b,a,b，a,bAB，若a,bTa,b且a,bTa,b，则有：11223311222233 a,bTa,baRabSb11221212 a,bTa,baRabSb22332323aRaaRa,又R为偏序关系，具有传递性，所以aRa 122313bSbbSb,又S为偏序关系，具有传递性，所以bSb122313 aRabSba,bTa,b，故T具有传递性。13131133综合（1）（2）（3）知T具有自反性、反对称性和传递性，故T为上的偏序关系。 AB 习题九及答案：（P179-180） 8、 S=QQ,Q为有理数集，为*S上的二元运算，a,b,x,yS有 a,b*x,y=ax,ay+b（1） *运算在S上是否可交换、可结合？是否为幂等的？（2）。 *运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元解：（1） x,y*a,b=xa,xb+y =ax,bx+ya,b*x,y *运算不具有交换律 () x,y*a,b*c,d =ax,bx+y*c,d =acx,adx+bx+y() 而x,y*a,b*c,d =x,y*ac,ad+b =xac,xad+xb+y=acx,adx+bx+y() =x,y*a,b*c,d*运算有结合律 任取a,bs，则有： 2 a,b*a,b=a,ab+ba,b*运算无幂等律 （2） 令a,b*x,y=a,b对a,bs均成立 则有：ax,ay+b=a,b对a,bs均成立()ax=aax-1=0()对a,b成立ay+b=bay=0 x-1=0x=1必定有y=0y=0*运算的右单位元为1，0，可验证1，0也为*运算的左单位元， *运算的单位元为1，0 令a,b*x,y=x,y，若存在x,y使得对a,bs上述等式均成立，则存在零元，否则不存在零元。 由a,b*x,y=x,y ax,ay+b=x,y()a-1x=0ax=x()a-1y+b=0ay+b=y() 由于a-1y+b=0不可能对a,bs均成立，故a,b*x,y=x,y不可能对a,bs均成立，故不存在零元； 设元素a,b的逆元为x,y，则令a,b*x,y=e=1，01x= ax=1a（当a0）ay+b=0by=- a 当a=0时，a,b的逆元不存在； 1b当a0时，a,b的逆元是,- aa11、设S=12，.,10，问下面的运算能否与S构成代数系统S，*? 如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。（3）； x*y=大于等于x和y的最小整数解：（3）由*运算的定义可知：， x*y=max(x,y) x,yS,有x*yS，故*运算在S上满足封闭性，所以*运算与非空集合S能构成代数系统； 任取x,yS,有x*y=max(x,y)=max(y,x)=y*x,所以*运算满足交换律；任取x,y,zS,有(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、 设V=1,2,3,1,其中xy表示取x和y之中较大的数。V=5,6,*,6，12其中x*y表示取x和y之中较小的数。求出V和V的所有的子代数。 12指出哪些是平凡的子代数，哪些是真子代数。解：（1）V中运算的单位元是1，1 V的所有的子代数是：1,2,3,1,1,1,1,2,1,1,3,1；1 V的平凡的子代数是：1,2,3,1,1,1；1 V的真子代数是：1,1,1,2,1,1,3,1；1（2）V中*运算的单位元是6，2 V的所有的子代数是：5,6,*,6，6,*,6；2 V的平凡的子代数是：5,6,*,6，6,*,6；2 V的真子代数是：6,*,6。2 习题十一及答案：（P218-219） 1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由 解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界； （b）不是格，因为d,e的最大下界不存在； （d）不是格，因为b,c的最小上界不存在； （e）不是格，因为a,b的最大下界不存在。 2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。 （1）L=1，2，3，4，5； （2）L=1，2，3，6，12； 解：画出哈斯图即可判断出：（1）不是格，（2）是格。 4、设L是格，求以下公式的对偶式： a(bc)(ab)(ac)（2） a(bc)(ab)(ac)解：对偶式为：，参见P208页定义11.2。 a,b,cLabcab=bc6、设L为格，且，证明。 Qab,ab=b,证明： Qbc,bc=b, ab=bc 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都没有补元，所以不是有补格，所以不是布尔格； （c）图：a,f互为补元，c和d的补元都是b和e，b和e的补元都是c和d，所以任何元素皆有补元，是Qc(bd)=ca=c,(cb)(cd)=fd=dc(bd)(cb)(cd)有补格； ，所以对运算不满足分配律，所以不是分配格，所以不是布尔格； （f）图：经过分析知图（f）对应的格只有2个五元子格：L1=a,c,d,e,f, L2=a,b,c,d,f。画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格，根据分配格的充分必要条件（见P213页的定理11.5）得图（f）对应的格是分配格；c和d都没有补元，所以不是有补格，所以不是布尔格。 整理文档