离散数学及其应用(课后习题).doc

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