1、习题1.12. 指出下列命题是原子命题还是复合命题。(3)大雁北回,春天来了。(4)不是东风压倒西风,就是西风压倒东风。(5)张三和李四在吵架。解:(3)和(4)是复合命题,(5)是原子命题。习题1.21. 指出下列命题的真值:(1)若,则太阳从西方升起。解:该命题真值为T(因为命题的前件为假)。(3)胎生动物当且仅当是哺乳动物。解:该命题真值为F(如鸭嘴兽虽是哺乳动物,但不是胎生动物)。2. 令P:天气好。Q:我去公园。请将下列命题符号化。(2)只要天气好,我就去公园。(3)只有天气好,我才去公园。(6)天气好,我去公园。解:(2)。 (3)。(6)。习题1.32. 将下列命题符号化(句中括
2、号内提示的是相应的原子命题的符号表示):(1)我去新华书店(P),仅当我有时间(Q)。(3)只要努力学习(P),成绩就会好的(Q)。(6)我今天进城(P),除非下雨(Q)。(10)人不犯我(P),我不犯人(Q);人若犯我,我必犯人。解:(1)。 (3)。 (6)。 (10)。习题1.41. 写出下列公式的真值表:(2)。解:该公式的真值表如下表: 0 0 0110 0 111 0 1 0000 1 1111 0 0111 0 1111 1 0011 1 111 2. 证明下列等价公式:(2)。证明:(4)。证明:3. 甲、乙、丙、丁4人参加考试后,有人问他们谁的成绩最好,甲说,不是我。乙说:是
3、丁。丙说:是乙。丁说:不是我。已知4个人的回答只有一个人符合实际,问成绩最好的是谁?解:设:甲成绩最好。:乙成绩最好。:丙成绩最好。:丁成绩最好。 四个人所说的命题分别用表示,则;。则只有一人符合实际的命题符号化为 同理,所以,当为真时,为真,即甲的成绩最好。习题1.52. 证明下列各蕴含式:(3)。证明:方法一:真值表法(列出命题公式的真值表)。 0 0 01111110 0 11111110 1 01101110 1 11111111 0 00011111 0 10111111 1 01000011 1 1111111方法二:等值演算法方法三:分析法(1)直接分析法:若前件为真,分两种情况
4、:(I)为假,则为真,为真,为真。(II)为真,则为真,此时若为真,则为真,则为真,为真,为真;若为假,则为假,为真。综上,若前件为真,后件必为真,故该蕴含式成立。(2)间接分析法:若后件为假,则为真,为假。由为假可知,为真,为假。再由可知,为真。此时为假,为假,即前件为假。故蕴含式成立。5. 叙述下列各个命题的逆换式和逆反式,并以符号写出。(1)如果下雨,我不去。解:设:天下雨。:我去。逆换式:如果我不去,天就下雨。符号表示为。逆反式:如果我去,天就不下雨。符号表示为。(2)仅当你走我将留下。解:设:我留下。:你走。逆换式:如果你走,我就留下。符号表示为:。逆反式:如果你不走,我就不留下。符
5、号表示为:。习题1.62. 将下列命题公式用只含和的等价式表达,并要求尽可能简单。(1)解: (2)解: (3)解: 习题1.76求下列命题公式的主析取范式和主合取范式:(1)解: (主合取范式) (主析取范式)习题1.81. 证明证明: (1) P(附加前提) (2) P (3) T(2)E (4) T(1)(3)I (5) P (6) T(5)E (7) T(4)(6)I (8) P (9) T(7)(8)I (10) CP2用间接证法证明,证明: (1) P(附加前提) (2) P (3) T(1)(2)I (4) P (5) P (6) T(4)(5)I (7) T(3)(6)I (8
6、) P (9) T(7)(8)I (10)(矛盾式) T(4)(9)I 由(10)得出了矛盾,根据归谬法说明原推理正确。5.“如果下雨,春游就会改期;如果没有球赛,春游就不会改期。结果没有球赛,所以没有下雨。”证明上述论断正确。解:设:下雨。:有球赛。:春游改期。则上述论断转化为要证明,证: (1) P (2) P (3) T(1)(2)I (4) P (5) T(3)(4)I 因此,上述推理正确。7. 证明是前提,的有效结论。证明: (1) P (2) T(1)E (3) P (4) T(2)(3)I (5) P (6) T(5)E (7) T(4)(6)I (8) T(7)E习题2.1用谓
7、词表达式写出下列命题:(5)每个有理数是实数。解:,其中:是有理数。:是实数。(6)有的函数连续。解:,其中:是函数。:连续。习题2.22. 将下列命题符号化:(3)没有人登上过木星。解:设:是人。:登上过木星。则命题可表示为3. 符号化下列命题:(2)尽管有人聪明,但未必一切人都聪明。解:设:是人。:聪明。则命题可表示为 习题2.32. 对下列谓词公式中约束变元进行换名:(1)(2)解:(1) (2)3. 对下列谓词公式中自由变元进行代入:(1)(2)解:(1) (2)习题2.43. 证明下列等价式:(1)证明: (2)证明: 习题2.5求下列谓词公式的前束析取范式和前束合取范式:(1)解:
8、 (前束析取范式、前束合取范式)(2)证明: (辖域扩张) (辖域扩张)(前束析取范式) (前束合取范式)习题2.61. 证明下列各式。(2)证明:(1) P (2) US(1) (3) P (4) US(3) (5) T(2)(4)I (6) P (7) US(6) (8) T(5)(7)I (9) UG(8)2. 符号化下列命题并推证其结论。(3)所有有理数是实数,某些有理数是整数,因此,某些实数是整数。解:设:是有理数。:是实数。:是整数。则命题可符号化为:,。证明如下:(1) P(2) ES(1)(3) P(4) US(3)(5) T(2)I(6) T(4)(5)I(7) T(2)I(
9、8) T(6)(7)I(9) EG(8)(4)每个大学生不是文科生就是理科生,有的大学生是优等生,小张不是理科生,但他是优等生,因此如果小张是大学生,他就是文科生。解:设:是大学生。:是文科生。:是理科生。:是优等生。:小张。该命题可符号化为:,。证明如下:(1) P(2) US(3)(3) 附加前提(6) T(4)(5)I(7) P(8) T(6)(7)I(9) CP习题3.13. 确定下列命题是真还是假,并简要说明为什么。(1) (2) (3) (4)解:(1)该命题为真,因为是任何集合的子集。 (2)该命题为假,因为不包含任何元素。 (3)该命题为真,因为属于集合。 (4)该命题为真,因
10、为是任何集合的子集。6. 求下列集合的幂集:(2) (3)解:(2)该集合的幂集为。 (3)该集合的幂集为习题3.26. 证明下列等式:(4)。证明:= 因此,。(5)。证明:=。因此,。(8)。证明:因此,。习题3.43. 下列等式能否成立?(3)。解:该等式成立。证明如下:设 因此,。(4)。解:该等式成立。证明如下:设 因此,。习题3.51. 对于下列各种情况,用列举法求出到的关系、,画出的关系图,写出的关系矩阵。(1),。解:, ,。关系图如下: 关系矩阵为。习题3.65. 设,上的关系的关系矩阵如下,试问是不是自反的、反自反的、对称的、反对称的和传递的?(1) (4)解:(1)是反自
11、反的、反对称的、非传递的。因为但。 (2)是自反的、对称的、非传递的。因为但。习题3.75. (1)设,上关系的关系矩阵是 试求出、。解:,。习题3.94. 设,试根据以下的划分求上相应的等价关系,并画出关系图。(3)解:关系图如下: 习题3.101. 对于下列集合上的“整除”关系,画出其哈斯图。(1)解:该整除关系的哈斯图如下:习题4.11. 指出下列各关系是否为到的函数:(1),(3),解:(1)不是从到的函数; (2)是从到的函数,不是从到的函数。习题4.21. 设,分别表示正整数集、整数集、实数集、复数集,试指出下列映射中哪些是单射、满射、双射,并写出定义域和值域。(1)为。(2)为。
12、(4)为。解:(1)为一般映射,定义域为,值域为。 (2)为一般映射,定义域为,值域为。 (4)为单射,定义域为,值域为。习题4.34. 设。(3)能否找到另一的单射,有?解:能。例如。(4)试定义一个映射使且。解:例如。习题7.11. 设无向图,。(1)画出的图形。(2)求的各节点的度数,并验证握手定理。(3)是否是简单图?解:(1)(2),。,握手定理成立。(3)图中存在环,故不是简单图。4. 下面各图有几个节点?(2)21条边,3个度为4的节点,其余都是度为3的节点。解:设度数为3的节点个数为x,由握手定理, 解得 故该图有13个节点。习题7.24. 分别指出图7-32中的3个图分别属于
13、哪种类型(强连通,单侧连通,弱连通)。 (a) (b) (c)解:(a)是强连通的,(b)是单侧连通的,(c)是弱连通的。习题7.31. 图7-39给出了一个有向图,试求(1)邻接矩阵。(2)、,并找出从到长度为1、2、3、4的路各有几条?(3)可达性矩阵。 图 7-39解:(1)邻接矩阵。(2)从邻接矩阵及其幂可知,从到长度为1的路有1条,从到长度为2的路有1条,从到长度为3的路有2条,从到长度为4的路有3条。(3)令,则,可达性矩阵。习题7.42. 确定取怎样的值,完全图有一条欧拉回路。解:完全图有一条欧拉回路的充要条件是每个节点的度数都是偶数。而在中,每个节点的度数都是。故当为奇数时,完
14、全图有一条欧拉回路。习题7.65. 设是一个连通平面图,它有个节点,条边,且每个面由条边围成。试证 。证明:设图有个面,由平面图的面的次数的定理, (1)再由欧拉定理, (2)由(1)得,代入(2)式得习题7.71. 一棵树有5个度为2的节点,3个度为3的节点,4个度为4的节点,2个度为5的节点,其余均是度为1的节点,问有几个度为1的节点?解:设有x个度为1的节点,则的节点数 ,的边数 又由 得 所以,即树有19个度为1的节点。2. 一棵树有个2度节点,个3度节点,L ,个度节点,求其叶节点的数目。解:设该树有个叶节点,则该树的节点数 该树的边数 又由 得 所以,即该树叶节点数为。习题7.85
15、. 对图7-101给出的二元有序树进行3种方式的遍历,并写出遍历结果。 图 7-101解:前序遍历的结果为 ;中序遍历的结果为 ;后序遍历的结果为 。6在通信中,、出现的频率分别是: :25%; :20%; :15%; :15%; :10%; :5%; :5%; :5%(1)求传输它们的最佳前缀码(2)用最佳前缀码传输10000个按上述频率出现的数字需要多少个二进制码? 解:令对应的树叶的权,则; ; ; ; ; ; 构造一颗带权5,5,5,10,10,15,20,30的最优二叉树(如下图): 01111011000011000110000100000故其最优前缀码为: (2)(2(20%+25%)+3(10%+15%+15%)+45%+5(5%+5%)10000=28000,即传输10000个数字需28000个二进制码 21
版权声明:以上文章中所选用的图片及文字来源于网络以及用户投稿,由于未联系到知识产权人或未发现有关知识产权的登记,如有知识产权人并不愿意我们使用,如有侵权请立即联系:2622162128@qq.com ,我们立即下架或删除。
Copyright© 2022-2024 www.wodocx.com ,All Rights Reserved |陕ICP备19002583号-1
陕公网安备 61072602000132号 违法和不良信息举报:0916-4228922