您好,欢迎访问三七文档
离散数学习题答案习题一及答案:(P14-15)14、将下列命题符号化:(5)李辛与李末是兄弟解:设p:李辛与李末是兄弟,则命题符号化的结果是p(6)王强与刘威都学过法语解:设p:王强学过法语;q:刘威学过法语;则命题符号化的结果是(9)只有天下大雨,他才乘班车上班qp解:设p:天下大雨;q:他乘班车上班;则命题符号化的结果是(11)下雪路滑,他迟到了解:设p:下雪;q:路滑;r:他迟到了;则命题符号化的结果是15、设p:2+3=5.q:大熊猫产在中国.r:太阳从西方升起.求下列复合命题的真值:(4)解:p=1,q=1,r=0,,19、用真值表判断下列公式的类型:(2)解:列出公式的真值表,如下所示:001111011010100101110001由真值表可以看出公式有3个成真赋值,故公式是非重言式的可满足式。20、求下列公式的成真赋值:(4)解:因为该公式是一个蕴含式,所以首先分析它的成假赋值,成假赋值的条件是:成真赋值有:01,10,11。所以公式的习题二及答案:(P38)5、求下列公式的主析取范式,并求成真赋值:(2)解:原式,此即公式的主析取范式,所以成真赋值为011,111。*6、求下列公式的主合取范式,并求成假赋值:(2)解:原式,此即公式的主合取范式,所以成假赋值为100。7、求下列公式的主析取范式,再用主析取范式求主合取范式:(1)解:原式,此即主析取范式。主析取范式中没出现的极小项为,,,所以主合取范式中含有三个极大项,,MMmmm02024,故原式的主合取范式。9、用真值表法求下面公式的主析取范式:(1)解:公式的真值表如下:0011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式567习题三及答案:(P52-54)11、填充下面推理证明中没有写出的推理规则。前提:结论:s证明:①p前提引入②前提引入①②析取三段论④前提引入③④析取三段论前提引入⑦s⑤⑥假言推理15、在自然推理系统P中用附加前提法证明下面推理:(2)前提:结论:证明:用附加前提证明法。①p附加前提引入②①附加③前提引入④②③假言推理⑤s④化简⑥⑤附加⑦前提引入⑧u⑥⑦假言推理故推理正确。16、在自然推理系统P中用归谬法证明下面推理:(1)前提:,,结论:p证明:用归谬法①p结论的否定引入②前提引入③①②假言推理④前提引入⑤③④析取三段论⑥前提引入⑦r⑥化简⑧⑤⑦合取由于,所以推理正确。17、在自然推理系统P中构造下面推理的证明:只要A曾到过受害者房间并且11点以前没离开,A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开,看门人会看见他。看门人没有看见他。所以,A是谋杀嫌犯。解:设p:A到过受害者房间,q:A在11点以前离开,r:A是谋杀嫌犯,s:看门人看见过A。则前提:,,,结论:r证明:①前提引入②前提引入③①②拒取式④前提引入p⑤③④合取引入⑥前提引入⑦⑤⑥假言推理r习题四及答案:(P65-67)5、在一阶逻辑中将下列命题符号化:(2)有的火车比有的汽车快。解:设F(x):x是火车,G(y):y是汽车,H(x,y):x比y快;则命题符号化的结果是:(3)不存在比所有火车都快的汽车。解:方法一:设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快;则命题符号化的结果是:或方法二:设F(x):x是火车,G(y):y是汽车,H(x,y):x比y快;则命题符号化的结果是:或9、给定解释I如下:(a)个体域为实数集合R。(b)特定元素。(c)函数。谓词。给出以下公式在I下的解释,并指出它们的真值:(2)解:解释是:,含义是:对于任意的实数x,y,若x-y=0则xy。该公式在I解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式:(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}(b)(c)试求下列公式在I下的真值:(1)解:方法一:先消去存在量词15、在自然推理系统中,构造下面推理的证明:N(3)前提:,结论:证明:①前提引入②①置换③②UI规则④前提引入⑤④UI规则⑥③⑤析取三段论F(c)⑦⑥EG规则*22、在自然推理系统中,构造下面推理的证明:(2)凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解:设F(x):x为大学生,G(x):x是勤奋的,c:王晓山则前提:,结论:证明:①前提引入②①UI规则③前提引入④②③拒取式25、在自然推理系统中,构造下面推理的证明:每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者,并且是聪明的。所以,王大海在他的事业中将获得成功。(个体域为人类集合)解:设F(x):x是科学工作者,G(x):x是刻苦钻研的,H(x):x是聪明的,I(x):x在他的事业中获得成功,c:王大海则前提:,,结论:I(c)证明:①前提引入②①化简F(c)③①化简H(c)④前提引入⑤④UI规则⑥②⑤假言推理G(c)⑦③⑥合取引入⑧前提引入⑨⑧UI规则⑩⑦⑨假言推理I(c)习题六及答案(P99-100)28、化简下述集合公式:(3)解:30、设A,B,C代表任意集合,试判断下面命题的真假。如果为真,给出证明;如果为假,给出反例。(6),如果,则解:该命题为假,,否则,故为假。举反例如下:则。(8)一定成立,解:该命题为假,举反例如下:如果B,C都是A的子集,则但不一定成立,例如:,则,,,但。33、证明集合恒等式:(1)证明:习题七及答案:(P132-135)1,2,3,4,5,626设,R为A上的关系,R的关系图如图7.13所示:23(1)求的集合表达式;R,R(2)求r(R),s(R),t(R)的集合表达式。解:(1)由R的关系图可得所以,,可得;当n=2(2),1,541、设A={1,2,3,4},R为上的二元关系,,(1)证明R为等价关系;(2)求R导出的划分。(1)只需证明R具有自反性、对称性和传递性即可,证明过程如下:(a)任取,有,,所以R具有自反性;(b)任取,若,则有,,,所以R具有对称性;(c)任取,若且,则有且,,,所以R具有传递性,综合(a)(b)(c)可知:R为集合上的等价关系;(2)先求出集合的结果:再分别求集合各元素的等价类,结果如下:RRRRRRRRRRRR。RA/RA/R等价关系R导出的划分就是集合A关于R的商集,而集合A关于R的商集是由R的所有等价类作为元素构成的集合,所以等价关系R导出的划分是:A,R46、分别画出下列各偏序集的哈斯图,并找出A的极大元、极小元、最大元和最小元。(1)解:哈斯图如下:ebcdfaA的极大元为e、f,极小元为a、f;A的最大元和最小元都不存在。*22、给定,A上的关系,试(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如下:证明T为上的偏序关系。证明:(1)自反性:任取,则:11R为偏序关系,具有自反性,为偏序关系,具有自反性,11又,11221212,故T具有自反性1111(2)反对称性:任取,若a,bTa,b且a,bTa,b,则有:(1)(2)2121,又R为偏序关系,具有反对称性,所以,又S为偏序关系,具有反对称性,所以,故T具有反对称性1122(3)传递性:任取a,b,a,b,,若a,bTa,b且a,bTa,b,则有:11223311222233又R为偏序关系,具有传递性,所以aRa又S为偏序关系,具有传递性,所以bSb122313,故T具有传递性。13131133综合(1)(2)(3)知T具有自反性、反对称性和传递性,故T为上的偏序关系。习题九及答案:(P179-180)8、为有理数集,为上的二元运算,S有(1)运算在S上是否可交换、可结合?是否为幂等的?(2)。运算是否有单位元、零元?如果有,请指出,并求出S中所有可逆元素的逆元解:(1)运算不具有交换律而运算有结合律任取,则有:2运算无幂等律(2)令对均成立则有:对均成立对成立必定有运算的右单位元为1,0,可验证1,0也为运算的左单位元,运算的单位元为1,0令,若存在x,y使得对上述等式均成立,则存在零元,否则不存在零元。由由于不可能对均成立,故a,b*不可能对均成立,故不存在零元;设元素a,b的逆元为x,y,则令,(当)当时,a,b的逆元不存在;1b当时,a,b的逆元是aa11、设,,...,10,问下面的运算能否与S构成代数系统S,如果能构成代数系统则说明运算是否满足交换律、结合律,并求运算的单位元和零元。(3);大于等于x和y的最小整数解:(3)由*运算的定义可知:,有,故运算在S上满足封闭性,所以运算与非空集合S能构成代数系统;任取有所以运算满足交换律;任取有所以运算满足结合律;任取,有x,所以运算的单位元是1;任取,有所以运算的零元是10;16、设其中表示取x和y之中较大的数。,12其中表示取x和y之中较小的数。求出V和V的所有的子代数。12指出哪些是平凡的子代数,哪些是真子代数。解:(1)V中运算的单位元是1,V的所有的子代数是:;1V的平凡的子代数是:;V的真子代数是:;1(2)V中运算的单位元是6,V的所有的子代数是:,;2V的平凡的子代数是:,;V的真子代数是:。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是格,求以下公式的对偶式:)(2)解:对偶式为:,参见P208页定义11.2。、设L为格,,且,证明。证明: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,所以任何元素皆有补元,是有补格;,所以对运算不满足分配律,所以不是分配格,所以不是布尔格;(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都没有补元,所以不是有补格,所以不是布尔格。
本文标题:离散数学习题答案
链接地址:https://www.777doc.com/doc-3515349 .html