《离散数学屈婉玲耿素云张立昂主编课后答案.doc》由会员分享,可在线阅读,更多相关《离散数学屈婉玲耿素云张立昂主编课后答案.doc(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、【精品文档】如有侵权,请联系网站删除,仅供学习与交流离散数学屈婉玲耿素云张立昂主编课后答案课后练习题答案1.将下列命题符号化,并指出真值:(1)pq,其中,p:2是素数,q:5是素数,真值为1;(2)pq,其中,p:是无理数,q:自然对数的底e是无理数,真值为1;(3)pq,其中,p:2是最小的素数,q:2是最小的自然数,真值为1;(4)pq,其中,p:3是素数,q:3是偶数,真值为0;(5)pq,其中,p:4是素数,q:4是偶数,真值为0.2.将下列命题符号化,并指出真值:(1)pq,其中,p:2是偶数,q:3是偶数,真值为1;(2)pq,其中,p:2是偶数,q:4是偶数,真值为1;(3)p
2、q,其中,p:3是偶数,q:4是偶数,真值为0;(4)pq,其中,p:3是偶数,q:4是偶数,真值为1;(5)pq,其中,p:3是偶数,q:4是偶数,真值为0;3.(1)(pq)(pq),其中,小丽从筐里拿一个苹果,q:小丽从筐里拿一个梨;(2)(pq)(pq),其中,p:刘晓月选学英语,q:刘晓月选学日语;.4.因为p与q不能同时为真.5.设p:今天是星期一,q:明天是星期二,r:明天是星期三:(1)pq,真值为1(不会出现前件为真,后件为假的情况);(2)qp,真值为1(也不会出现前件为真,后件为假的情况);(3)pq,真值为1;(4)pr,若p为真,则pr真值为0,否则,pr真值为1.返
3、回第二章 命题逻辑等值演算本章自测答案5.(1):,成真赋值为00、10、11;(2):0,矛盾式,无成真赋值;(3):,重言式,000、001、010、011、100、101、110、111全部为成真赋值;7.(1):;(2):;8.(1):1,重言式;(2):;(3):0,矛盾式. 11.(1):;(2):1;(3):0. 12.A.第三章 命题逻辑的推理理论本章自测答案6.在解本题时,应首先将简单陈述语句符号化,然后写出推理的形式结构*,其次就是判断*是否为重言式,若*是重言式,推理就正确,否则推理就不正确,这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确,其余的均不正确,
4、下面以(1)、(2)为例,证明(1)推理正确,(2)推理不正确(1)设p:今天是星期一,q:明天是星期三,推理的形式结构为(pq)pq(记作*1)在本推理中,从p与q的内在联系可以知道,p与q的内在联系可以知道,p与q不可能同时为真,但在证明时,不考虑这一点,而只考虑*1是否为重言式.可以用多种方法(如真值法、等值演算法、主析取式)证明*1为重言式,特别是,不难看出,当取A为p,B为q时,*1为假言推理定律,即(pq)pq q(2)设p:今天是星期一,q:明天是星期三,推理的形式结构为(pq)pq(记作*2) 可以用多种方法证明*2不是重言式,比如,等值演算法、主析取范式(主和取范式法也可以)
5、等(pq)qp(pq) q pq ppq从而可知,*2不是重言式,故推理不正确,注意,虽然这里的p与q同时为真或同时为假,但不考虑内在联系时,*2不是重言式,就认为推理不正确.9.设p:a是奇数,q:a能被2整除,r:a:是偶数推理的形式结构为 (pq)(rq)(rp) (记为*)可以用多种方法证明*为重言式,下面用等值演算法证明:(pq)(rq)(rp)(pq) (qr)(qr) (使用了交换律)(pq)(pr)qr(pq)(qr)p(qq)r110.设p:a,b两数之积为负数,q:a,b两数种恰有一个负数,r:a,b都是负数.推理的形式结构为(pq)p(qr)(pq) p(qr)p(qr)
6、 (使用了吸收律)p(qr)由于主析取范式中只含有5个W极小项,故推理不正确.11.略14.证明的命题序列可不惟一,下面对每一小题各给出一个证明 p(qr)前提引入 P前提引入 qr 假言推理 q前提引入 r 假言推理 rs 前提引入(2)证明: (pr) 前提引入 qr 置换 r前提引入 q 析取三段论 pq 前提引入 p拒取式(3)证明: pq 前提引入 qq 置换 (pq)(pp) 置换 p(qp 置换 p(pq) 置换15.(1)证明: S结论否定引入 SP 前提引入 P假言推理 P(qr)前提引入 qr 假言推论 q前提引入 r假言推理(2)证明: p附加前提引入 pq 附加 (pq
7、)(rs)前提引入 rs 假言推理 s化简 st 附加 (st)u前提引入 u拒取式16.(1)证明: p结论否定引入 p q前提引入 q 假言推理 rq 前提引入 r析取三段论 rs 前提引入 r化简 rr 合取(2)证明: (rs) 结论否定引入 rs 置换 r化简 s化简 pr 前提引入 p拒取式 qs 前提引入 q拒取式 pq 合取 (pq) 置换口 pq 前提引入口 (pq) (pq) 口合取17设p:A到过受害者房间,q: A在11点以前离开,r:A犯谋杀罪,s:看门人看见过A。前提:(pq) r , p ,q s , s结论:r证明: qs 前提引入 s 前提引入 q 拒取式 p
8、 前提引入 pq 合取(pq)r 前提引入 r 假言推理18(1)设 p:今天是星期六,q:我们要到颐和园玩,s:颐和园游人太多。前提:p(pr) , sq , p , s结论:r证明: sq 前提引入 s前提引入 q假言推理 p前提引入 p(qr)前提引入 qr 假言推理r 析取三段论(2)设p:小王是理科学生,q:小王数学成绩好,r:小王是文科学生。前提:pq ,rp ,q结论:r证明: pq 前提引入 q前提引入 p拒取式 rp 前提引入 r拒取式返回第四章 (一阶)谓词逻辑基本概念本章自测答案4.(1)x(F(x) G(x)x( F (x) G (x) ),其中,F(x):x是有理数,
9、G(x) :x能表示成分数;(2)x( F (x) G (x) ) x(F(x) G(x),其中,F (x):x在北京卖菜,G (x) :x是外地人;(3)x( F (x) G (x) ),其中,F (x):x是乌鸦,G (x) :x是黑色的;(4)xF(x) G(x),其中,F (x):x是人,G (x) :x天天锻炼身体。因为本题中没有指明个体域,因而使用全总个体域。5.(1)xy (F(x) G( y ) H(x,y),其中,F(x):x是火车,G(y) :y是轮船,H(x,y):x比y快;(2)xy (F(x) G( y ) H(x,y),其中,F(x):x是火车,G(y) :y是汽车
10、,H(x,y):x比y快;(3)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快;(4)x(F(x)y(G(y) H(x,y)xy(F(x)G(y)H(x,y),其中,F(x):x是汽车,G(y) :y是火车,H(x,y):x比y慢。6.各命题符号化形式如下:(1)xy (x y = 0);(2)xy (x y = 0);(3)xy (y =x+1)(4)xy(x y = yx)(5)xy(x y =x+ y)(6)xy (x + y 0 )9.(1)对任意数的实数x和y,若x y,则x
11、 y;(2)对任意数的实数x和y,若xy = 0,则xy;(3)对任意数的实数x和y,若xy,则xy0;(4)对任意数的实数x和y,若xy 0,则x=y.其中,(1)(3)真值为1(2)与(4)真值为0.11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。这里仅对(3)、(4)、(5)给出证明。(3)取解释I 为:个体域为自然数集合N,F(x,y):x y,在下,xy F(x,y)为真,而xy F(x,y)也为真(只需取x =0即可),于是(3)中公式为真,取解释 为:个体域仍为自然数集合N,而F(x,y):x = y。此时,xyF(x,y)为真(取y为x即可),可
12、是xyF(x,y)为假,于是(3)中公式在 下为假,这说明(3)中公式为可满足式。(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则xyF(x,y)yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常项x0,使yF(x0,y)为真,并且对于任意y,F(x0,y)为真,由于有x0,F(x0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以 yxF(x,y )为真,由于I的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。(5)取解释为:个体域为自然数集合,F(x,y):x = y在下,(5)中公式为真,
13、而将F(x,y)改为F(x,y):x y,(5)中公式就为假了,所以它为可满足式。13(1)取解释为:个体域为自然数集合N,F(x):x为奇数,G(x):x为偶数,在 下, x(F(x)G(x)为真命题。取解释为:个体域为整数集合Z,F(x):x为正整数,G(x):x为为负整数,在 下, x(F(x)G(x)为假命题。(2)与(3)可类似解答。14提示:对每个公式分别找个成真的解释,一个成假的解释。返回第五章 谓词逻辑等值演算与推理本章自测答案2.(1) (F(a) F(b) F (c) (G (a )G (b)G (c)(2) (F(a) F(b) F (c) (G (a)G (b)G (c
14、)(3) (F(a) F(b) F (c) (G (a)G (b)G (c)(4) (F(a ,y) F(b,y) F (c,y) (G (a)G (b)G (c)5.提示:先消去量词,后求真值,注意,本题3个小题消去量词时,量词的辖域均不能缩小,经过演算真值分别为:1,0,1 .(1) 的演算如下:xyF(x,y)x (F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4 ,4)1116.乙说得对,甲错了。本题中,全称量词 的指导变元为x ,辖域为(F (x)G(x,y),其中F(x )与G(x,y)中的x都是约束变元,因而不能将量词的辖域缩小。7.演算的第一步,应用量词辖
15、域收缩与扩张算值式时丢掉了否定联结词“ ”。演算的第二步,在原错的基础上又用错了等值式,即(F(x)(G(y) H(x,y) (F(x) G(y)H (x,y)12.公式的前束范式不唯一,下面每题各给出一个答案。(1) xy (F(x) G(z,y);(2) xt (x,y) G(x,t,z);(3) x4 (F(,y) G(,y)(G(,y) F(x4,y);(4) (F()G(,) (H () L(,);(5) (F(,)(F() G (,).13.(1)xy(F(x) G(y) H(x ,y),其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y跑的快; (2)xy(F(x
16、) G(y)H(x ,y),其中,F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑的快; (3)xy(F(x) G(y) H(x ,y),其中,F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑的快; (4)xy(F(x) G(y) H(x ,y),其中,F(x):x是飞机,G(y):y是汽车,H(x,y):x比y慢;14.(1)对F(x) xG(x)不能使用EI规则,它不是前束范式,首先化成前束范式。F(x) xG(x) x(F(y)G(x)因为量词辖域(F(y)G(x)中,除x外还有自由出现的y,所以不能使用EI规则。 (2)对 x F(x) y G(y)也应先化
17、成前束范式才能消去量词,其前束范式为 x y(F(x) G(y),要消去量词,既要使用UI规则,又要使用EI规则。 (3)在自然推理系统F中EG规则为A(c)/x(x)其中c为特定的个体常项,这里A(y) = F(y) G(y)不满足要求。 (4)这里,使F(a)为真的a不一定使G(a)为真,同样地使G(b)为真的b不一定使F(b)为真,如,F(x):x为奇数,G(x):x为偶数,显然F(3)G(4)为真,但不存在使F(x)G(x)为真的个体。 (5)这里c为个体常项,不能对F(c)G(c)引入全称量词。15.(1)证明:xF(x)前提引入xF(x) y(F(y)G(y) R(y) 前提引入y
18、(F(y)G(y) R(y) 假言推理F(c) EI(F(c)G(c)R(c) UIF(c)G(c) 附加R(c) 假言推理xR(x) EG(2)证明xF(x) 前提引入x(F(x)G(a)R(x) 前提引入F(c) EIF(c)G(a)R(a) UIG(a)R(c) 假言推理R(c) 化简F(c)R(c) 合取x(F(x)R(x)EG(3)证明:xF(x) 前提引入xF(x)置换F(c) UIx(F(x)G(x) 前提引入F(c)G(c) UIF(c) 析取三段论xF(x)EG(4)证明x(F(x)G(x)前提引入F(y)G(y) UIx(G(x)R(x) 前提引入G(y)R(y) UIx
19、R(x) 前提引入R(y) UIG(y) 析取三段论F(y) 析取三段论xF(x) UG17本题不能用附加前提证明法.20.(1)与(2)均可用附加前提证明法。22.(1)设F(x):x为偶数,G(x):x能被2整除。前提:x(F(x)G(x),F(6)结论:G(6)(2)设F(x):x是大学生,G(x):x是勤奋的,a:王晓山。前提:x(F(x)G(x),G(a)结论:F(a)23.(1)设F(x):x是有理数,G(x):x是实数,H(x):x是整数。前提:x( F(x)G(x), x(F(x)H(x)结论:x(G(x)H(x)证明提示:先消存在量词。(2)设F(x):x是有理数,G(x):
20、x是无理数,H(x):x是实数,I(x):x是虚数。前提:x(F(x)G(x) H(x), x( I(x)H(x)结论:x(I(x)(F(x)G(x)证明x(I(x)(H(x)前提引入I(y)H(y) UIx(F(x)G(x)H(x) 前提引入(F(y)G(y)H(y)UIH(y)(F(y)G(y)置换I(y)(F(y)G(y)假言三段论x(I(x)(F(x)G(x)UG24.设F(x):x喜欢步行,G(x):x喜欢骑自行车,H(x):x喜欢乘汽车。前提:x(F(x)G(x), x(G(x)H(x), xH(x)结论:xF(x)证明xH(x) 前提引入H(c)UIx(G(x)H(x)前提引入G
21、(c)H(c)UIG(c)析取三段论x(F(x) G(x) 前提引入F(c)G(c)UIF(c)拒取式xF(x) UG25.设F(x):x是科学工作者,G(x):x是刻苦钻研的,H(x):x是聪明的,I(x):x在事业中获得成功。前提:x(F(x)G(x),x(G(x)H(x)I(x),a:王大海,F(a),H(a)结论:I(a)证明F(a)前提引入x(F(x)G(x) 前提引入F(a)G(a)UIG(a)假言推理H(a)前提引入x(G(x)H(x)I(x)前提引入G(a)H(a)I(a) UIG(a)H(a)合取I(a)假言推理返回第六章 集合代数本章自测答案4.(1) (2) (3) (4
22、) (5) 6.只有(2)为真,其余为假。9.(1) 4;(2) 1,3,5,6;(3) 2,3,4,5,6;(4) , 1 ;(5) 4 ,1,4.11.(1); (2) 1,4,5.22.(2)、(3)、(4)、(8)、(10)为真,其余为假。24.(1)为真,其余为假,因为(P-Q) = P (P-Q)Q = PQ = PQ(2)(3)(4)的反例:P =1 ,Q =226.(AB)(BA) = (AB)(BA)=(AB)(BB)(AA)(BA)=(AB)E(AB)=(AB)-(AB)27.(1)(A-B)-C = ABC =A(BC) = A-(BC) (2)(A-C)-(B-C)AC
23、(BC) =AC(BC) = (ACB)(ACC) =AC=(AB)- C (3)(AB-C=ABC =ACB=(AC)B28.(1)A(BA) = (AB)(AA) =(AB) =AB=BA (2)(AB)A) = (AB)A =(AB)A = A29.由第26题有(A-B)(B-A)=(AB)(AB),故(A-B)(B-A)AB。假若xAB,那么xAB,因此x(AB)-(AB),与(A-B)(B-A) = (AB)-(AB) = AB矛盾.30.ABx(xAxB)x(xBxA) x(xBxA)BA AB AAAB EAB而ABE,因此AB AB=E反之, AB = E A(AB)= A A
24、B = A AB 综合上述,ABAB = E AB A-B = A-BB反之A-BB (A-B)BB ABB AB = B AB综合上述ABA-BB31.任取x ,xA x A=xP(A)=xP(B)=xB xB32.先证CACB CAB,任取x,xC xCxC xAxB xAB,从而得到CAB.再证CAB CACB,这可以由CABA,CABB得到。33.PQ P-Q= P-QP,反之,P-QP P(P-Q)PP P-Q= PQ34.令X=,则有Y =,即Y = .35.AB AABA EBA因为E为全集,BAE综合上述BA=E.36.由ACBC,A-CB-C,利用ACBD有: (AC)(A-
25、C) (BC)(B-C) (AC)(AC)(BC)(BC) (A(CC)(B(CC) AEBE AB37.恒等变形法B=B(BA)=B(AB)=B(AC) =(BA)(BC)=(AC)(BC) =(AB)C=(AC)C=C39.任取x,有xP(A) x A x B xP(B),因此P(A)P(B).40.(1)任取x有xP(A)P(B)xP(A)xP(B)xAxBxABxP(AB)(2)任取x有xP(A)P(B)xP(A)xP(B)xAxB xABxP(AB)注意与(1)的推理不同,上面的推理中有一步是“ ”符号,而不是“”符号。(3)反例如下:A = 1,B = 2,则P(A)P(B)= ,
26、1,2P(AB)=,1,2,1,2返回第七章 二元关系本章自测答案3.(1) 任取,有(A B)(C D) xA B y C Dx Ax By Cy D(x Ay C )(xByD)ACBD(AC)(BD)(2)都为假,反例如下:A =1, B =1,2, C =2, D =34.(1)为假,反例如下:A =1, B =,C = 2;(2)为真,证明如下:任取有A(BC)(CD)xAByByC(xAyB)(xAyC)ABAC(AB)(AC)(3)为真,令A = 即可;(4)为假,反例如下: A = 7.=,=, LA=,DA=,9.(1), , , , (2),;(3),(4),12.(略)1
27、3.AB = , A B =domA = 1,2,3,domB = 1,2,4,dom(A B) = 1,2,3,4ranA = 2,3,4,ranB = 2,3,4,ran(A B) = 4,fld(A - B) = 1,2,314.RR = , R= , R0,1 = , R1,2 = 2,318.(1)F(GH) = FGFH任取 ,有F (GH)t(FGH)t(F(GH)t(FG)(FH)t(FG)t(FH)FGFHFGFH (2)和(4)类似可证19.(2)任取y,有yRTWx(xTWR)x(xTxW)Rx(xAR)(xWR)x(xTR)x(xWR)yRTyRWyRTRW(3)任取,
28、有F(AB)xABFxAxBF(xAF)(xBF)FAFBFAF B20.(1)任取,有() (2)和(1)类似可证.21.只有对称性,因为1+110,R,R不是自反的,又由于R,因此R不是反自反的,根据xRyx+y = 10=yRx ,可知R是对称的,又由于,都是属于R,因此R不是反对称的, ,都属于R,如果R是传递的,必有属于R.但这是不成立的,因此R也不是传递的.22.(1)关系图如图7.15所示; (P148) (2)具有反自反性、反对称性、传递性.26.(1)R=, = , (2)r(R)=,s(R)=,T(R)=,31.(1)R = ,;(2)R; (3)R.32.(1)不是等价关
29、系,因为 R,R不是自反的; (2)不是等价关系,因为R不是传递的,1R3,3R2但是没有1R2; (3)不是等价关系,因为 R,R不是自反的; (4)不是等价关系,因为R不是传递的。 (5)是等价关系。33关系图如图7.17说示 (P151) a = b =a,b,c = d = c,d 38.现取x,有xA R RR R RR 任取,有 R R R RR 任取,有 R R R R (RR)( RR RR 42.x,xA R RR T,T是自反的。 x,yA,TRR RR T,T是对称的。 x,y,zA,TT RRRR RRRR RR T T是传递的。43哈斯图如下图所示. 44.(a)偏序集,A=1,2,3,4,5,R=, (b)偏序集,A=a,b,c,d,e,f,R=, (c)偏序集,A=1,2,3,4,5, R=,45.(a)A=a,b,c,d,e,f,g, =, , (b)A = a,b,c,d,e,f,g,R口 = , 46.哈斯图如图7.19所示 (P153)(1)极大元e,f;极小元a,f;没有最大与最小元。(2)极大元a,b,d,e;极小元a,b,c,e;没有最大与最小元。返回第八章 函数本章自测答案2. = , = , = , = ,= , = , = ,= , = , =
限制150内