最新离散数学课后习题答案优秀名师资料.doc
《最新离散数学课后习题答案优秀名师资料.doc》由会员分享,可在线阅读,更多相关《最新离散数学课后习题答案优秀名师资料.doc(33页珍藏版)》请在三一文库上搜索。
1、习题参考解答习题1.1 1、(3)P:银行利率降低 Q:股价没有上升 PQ(5) P:他今天乘火车去了北京 Q:他随旅行团去了九寨沟 (7) P:不识庐山真面目 Q:身在此山中 QP,或 PQ(9) P:一个整数能被6整除 Q:一个整数能被3整除 R:一个整数能被2整除 T:一个整数的各位数字之和能被3整除 PQR ,QT2、(1)T (2)F (3)F (4)T (5)F (6)T (7)F (8)悖论习题 1.31(3)(4)2、不,不,能习题 1.4 主合取范式主析取范式3、解:根据给定的条件有下述命题公式:(A(CD)(BC)(CD)(A(CD)(CD)(BC)(CD)(AB)(CDB
2、)(CDB)(AC)(CDC)(CDC)(CD)(AB)(CDB)(CDB) (AC)(CDC) (CD)(ABC)(CDBC)(CDBC)(ACC)(CDCC)(ABD)(CDBD)(CDBD)(ACD)(CDCD)(由题意和矛盾律)(CDB)(AC)(CD)(CDB)(CDBA) (CDBA) (ACB) (ACB) (CDA) (CDA)(CDBA)(CDBA)(CDBA) (ACBD) (ACBD) (ACBD) (ACBD) (CDAB) (CDAB) (CDAB) (CDAB)(CDBA)(CDBA)(CDBA) (ACBD) (CDAB) (CDAB) (CDBA)(CDBA)
3、(ACBD)(CDBA)三种方案:A和D、B和D、A和C习题 1.51、 (1)需证为永真式(3)需证为永真式为永真式。即永真永真当且仅当4、设:P:珍宝藏在东厢房Q:藏宝的房子靠近池塘R:房子的前院栽有大柏树S:珍宝藏在花园正中地下t:后院栽有香樟树m:珍宝藏在附近(后院)命题化后进行推理:即S为真,珍宝藏在花园正中地下5、(1)F (P=0,Q=1) (2)F (P=1,Q=R=0) (3)F (P=0,Q=1)习题 1.61.(1)证:利用CP规则 P P(附加前提) I I 结论成立 CP规则(2) 证: (附加) PQ T SE T SEB P ()2. (2) P:无任何痕迹 Q:
4、失窃时,小花在OK厅 R:失窃时,小英在OK厅 S:失窃时,小胖在附近 T:金刚是偷窃者M:瘦子是偷窃者命题可符号化为:证:金刚是窃贼。3. (1) 不相容 (2) 相容 (3)不相容 (4)不相容4. (1)证:即 利用消解原理:P P P 习题 2.11. (1):是实数 :是有理数(2):是直线:与平行:与相交(3):是会员:有意义:参加:这个活动或者(4):是正整数:是合数:是质数(5):是人B(x):x存钱a:利息 P:存钱有利息 :想有2.(1)(2)4.(1)习题 2.21.(1)D:数 可满足式(2)是诚实的人讲实话a:小林可满足式 (3) 不便宜是好货买的a:衣服b:小王可满
5、足式(4)是作家 懂得人性本质是诗人是真正的能刻画人们内心世界很高明创作了a:莎士比亚b:哈姆雷特2.(1) 3.(1) (2) 4. 习题 2.31.(1)2. 不成立D=0,1,2 3.(1) skolem范式(2) 前束范式 skolem范式习题 2.41. (1)证:在某个解释下,取值1,必有,,取值1,因此, 取值1。取值1,由定义,蕴含关系成立。(2)(2) 证: 在某个解释下,取值1即取值0,分二种情况:i),则无论为何值,取值1。ii) ,则取值1由定义,蕴含关系成立。习题 2.51(2)(反证法)PT,ET,IT,IUST,IUGPT,IT,I USTI2. (1) 错误,应
6、换元,即, (2) 正确 (3) 错误,a、b应是同一个常元 (4) 错误,因为在 中x并不是自由出现(5) 错误,因为在中,前件是命题,而后件不是命题(6) 错误,因为a、b并不是同一个常量(7) 错误,和的顺序不对应先使用ES,再使用US3(1)解:设F(x,y):xy; G(z):z0 ; f(x,y)=x-y前提: (x)(y)(F(x,y)G(f(x,y) (x)(y)(F(x,y)G(f(x,y) (x)(y)(G(f(x,y) G(f(y,x)结论: (x)(y)(G(f(x,y)G(f(y,x))证明(反证法): (x)(y)(G(f(x,y)G(f(y,x)) ($)($)(
7、G(f(x,y)G(f(y,x)) G(f(a,b) G(f(b,a) (x)(y)(F(x,y)G(f(x,y) F(a,b)G(f(a,b) G(f(a,b)F(a,b) (x)(y)(G(f(x,y) G(f(y,x) G(f(b,a)G(f(a,b) (x)(y)(F(x,y)G(f(x,y) F(a,b)G(f(a,b) G(f(a,b) F(a,b) F(a,b) F(a,b)4. (2)证:首先,将结论否定否作为前提加入到原有前提中 Skolem 范式子句集为,代换a/x代换c/x,代换c/w代换c/y习题 3.43、习题 5.22. 关系性质R1R2R3R4R5自反性反自反性对
8、称性反对称性传递性习题 5.32. (3)“”R是对称的,设则 ,即“” ,由的定义,即R是对称的。(5)“”R是传递的,对即“”,对,由R2的定义,有,即R是可传递的。4. 解:,且需3|m,5|m,即 故使的最小正整数习题 5.42、解:3. (3)证:由归纳法可证:对(4)证:由归纳法可证:习题 5.51. 证:自反性 由A的定义, 对称性 设,则即 传递性 设,则,则3. 解:设4. 解:每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系种。5. 解:不是A上的等价关系是A上的等价关系 是A上的等价关系不是A上的等价关系习题 5.62. 解:Fabca,ba,
9、cb,ca,b,c3. 解:集合A上的空关系、恒等关系IA都是等价关系和偏序关系。6. 解:7. 证:i)自反性,对,(的自反性)显然ii)反对称性,对即,由R的反对称性,iii)传递性,对,设,则,。由R的传递性,显然习题6.24、证: 7、证:习题6.4:3证明:非空有限集A与可数集B的笛卡尔积AB也是可数集。证明:设A=a1,a2,an B=b1,b2,bn,令Bi =(ai,b1),(ai,b2),(ai,bn), (in),则 AB= ,因为B为可数集,所以Bi为可数集。AB为有限个可数集的并集。下面用归纳法证明有限个(m个)可数集的并集为可数集。设Cm=cm1,cm2, ,cmn,
10、 当m=2时,构造双射f:NC1C2, N 1 2 3 4 5 6 n-1 n f(N) c11 c21 c12 c22 c13 c23 c1(n/2) c2(n/2) 所以2个可数集的并集为可数集。假设m=k-1(k3)时结论成立,即k-1个可数集的并集为可数集,记为D。则m=k时,可以构造类似的双射g:NDCk,所以为可数集。因而有限个可数集的并集为可数集。所以AB是可数集。习题9.11设G是一个(n,m)简单图。证明:m ,等号成立当且仅当G是完全图.证明:由欧拉定理,2m= ,d(k)表示第k个结点的度因为G是简单图,所以d(k) n-1,等号成立当且仅当G是完全图2m= ,所以 2m
11、n(n-1)即 m =3、解:(1)不是图的序列,因为奇数度结点的个数不是偶数。(2)、(3)、(4)都是图的序列。4、证:9若,称G是自补图。确定一个图为自补图的最低条件;画出一个自补图来。解:设G=(n,m),G=(n,m)则m+m=n(n-1)/2,所以m=m=n(n-1)/4v2v1v3v4Gv2v1v3v4习题9.21、若u和v是图中仅有的两个奇度数结点,证明u和v必是连通的。证:(反证法)设v与u不连通G=V1,V2 ,v与u分别属于V1,V2二个子图 v与u是G中仅有的二个奇数度结点v与u即是V1与V2中仅有的一个奇数度结点,与欧拉定理的推论(9-1.1.1相矛盾,故v与u必连通
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 离散数学 课后 习题 答案 优秀 名师 资料
链接地址:https://www.31doc.com/p-1507496.html