离散数学及应用课后习题答案

【篇一：离散数学及其应用图论部分课后习题答案】

p165:习题九

1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表 示。

（1）g1??v1,e1?，v1?{v1,v2,v3,v4,v5}，

e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} （2）g2??v2,e2?，v2?v1，e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} （3）

d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v1?} （4）

d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v3?} 解答： （1） （2）

10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。

（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点 。

14、设g是n(n?2)阶无向简单图，g是它的补图，已知?(g)?k1,?(g)?k2，求?(g)， ?(g)。

解答：?(g)?n?1?k2；?(g)?n?1?k1。

15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。 解答：

（c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d）同构，同构函数为 ?1?2??f(x)??3 ?4???5 解答：

（1）三条边一共提供6度；所以点度序列可能是

x?ax?b

x?c x?dx?e

16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。 ①3，3，0，0，0，0；②3，2，1，0，0，0；③3，1，1，1，0，0；④2，2，2，0，0，0；⑤2，2，1，1，0，0；⑥2，1，1，1，1，0；⑦1，1，1，1，1，1； 由于是简单图，①②两种情形不可能 图形如下：

（2）三条边一共提供6度，所以点度序列可能为 ①3，3，0；②3，2，1；③2，2，2 由于是简单图，①②两种情形不可能

21、在图9.20中，下述顶点序列是否构成通路？哪些是简单通路？哪些是初级通路？哪些是回路？哪些是简单回路？哪些是初级回路？ （1）a,b,c,d,b,e；（2）a,b,e,d,b,a；（3）a,d,c,e,b；（4）d,b,a,c,e;

（5）a,b,c,d,e,b,d,c；（6）a,d,b,e,c,b,d；（7）c,d,a,b,c；（8）a,b,c,e,b 解答：（1）构成通路，且为初级通路，因为点不重复

（2）构成了回路，但是不为简单回路和初级回路，因为有重复的边(a,b) （3）构成了初级通路，因为点不重复； （4）不构成通路，因为边(a,c)不存在；

（5）构成通路，但是不为简单通路和初级通路，因为有重复的边(d,c) （6）构成了回路，但是不为简单回路和初级回路，因为有重复的边(d,b) （7）构成了初级通路；

（8）简单通路，但是不为初级通路，有重复边。

23、用dijkstra标号法求图9.22中各图从顶点v1到其余各点的最短路径和距离。

v1到v2最短路为v1?v2，路长为6； v1到v3最短路为v1?v3，路长为3； v1到v4最短路为v1?v3?v4，路长为5；

v1到v5最短路为v1?v3?v4?v5，路长为6； v1到v6最短路为v1?v2?v6，路长为12；

v1到v7最短路为v1?v3?v4?v5?v7，路长为7； v1到v8最短路为v1?v3?v4?v5?v7?v8，路长为10； （2）略。

25、图9.23中各图有几个连通分支？给出它们所有的连通分支。 解答：

（a）有两个连通分支：aec和bdf； （b）有三个连通分支：abd、c和ef； （c）连通图，只有一个连通分支； （d）两个连通分支：afbgd和ech。 38、写出图9.27的关联矩阵。

??11000000??10?111000???

00?1000?1? 解答：?0??0000?11?11????0?1100?110??

【篇二：离散数学及其应用(课后习题)】

出下列命题是原子命题还是复合命题。 （3）大雁北回，春天来了。 （4）不是东风压倒西风，就是西风压倒东风。 （5）张三和李四在吵架。 解：（3）和（4）是复合命题，（5）是原子命题。 习题1.2

1. 指出下列命题的真值：

（1）若2?2?4，则太阳从西方升起。 解：该命题真值为t（因为命题的前件为假）。 （3）胎生动物当且仅当是哺乳动物。

解：该命题真值为f（如鸭嘴兽虽是哺乳动物，但不是胎生动物）。 2. 令p：天气好。q：我去公园。请将下列命题符号化。 （2）只要天气好，我就去公园。 （3）只有天气好，我才去公园。 （6）天气好，我去公园。 解：（2）p?q。 （3）q?p。 （6）p?q。 习题1.3

2. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）： （1）我去新华书店（p），仅当我有时间（q）。 （3）只要努力学习（p），成绩就会好的（q）。 （6）我今天进城（p），除非下雨（q）。 （10）人不犯我（p），我不犯人（q）；人若犯我，我必犯人。 解：（1）p?q。 （3）p?q。 （6）?q?p。 （10）(?p??q)?(p?q)。 习题1.4

1. 写出下列公式的真值表： （2）p?(q?r)。 解：该公式的真值表如下表： 2. 证明下列等价公式：

（2）(p?q)??(p?q)??(p?q)。 证明：

?(p?q)??((p?q)?(?p??q))??(p?q)??(?p??q))??(p?q)?(p?q) ?(p?q)??(p?q)

（4）(p?q)?(p?r)?p?(q?r)。 证明：

(p?q)?(p?r)?(?p?q)?(?p?r)??p?(q?r)?p?(q?r)

3. 甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是丁。丙说：是乙。丁说：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是谁？

解：设a：甲成绩最好。b：乙成绩最好。c：丙成绩最好。d：丁成绩最好。四个人所说的命题分别用p、q、r、s表示，则

p??a；q??a??b??c?d；r??a?b??c??d；s??d。 则只有一人符合实际的命题k符号化为

k?(p??q??r??s)?(?p?q??r??s)?(?p??q?r??s)?(?p??q??r?s) p??q??r??s??a??(?a??b??c?d)??(?a?b??c??d)?d ??a?(a?b?c??d)?(a??b?c?d)?d ?(?a?d)?(a?b?c??d)?(a??b?c?d) ?(?a?b?c?d)?(?a?b?d)?(?a??b?c?d)?(?a?c?d)?0; 同理，

?p?q??r??s?a??a??b??c?d??(?a?b??c??d)?d?0; ?p??q?r??s?a??(?a??b??c?d)??a?b??c??d?d?0; ?p??q??r?s?a??(?a??b??c?d)??(?a?b??c??d)??d ?a?(a?b?c??d)?(a??b?c?d)??d ?a??d.

所以，当k为真时，a??d为真，即甲的成绩最好。 习题1.5

2. 证明下列各蕴含式：

（3）p?(q?r)?(p?q)?(p?r)。 证明：

方法一：真值表法（列出命题公式(p?(q?r))?((p?q)?(p?r))的真值表）。

方法二：等值演算法

(p?(q?r))?((p?q)?(p?r))??(p?(q?r))?((p?q)?(p?r))??(?p?(?q?r))??(?p?q)?(?p?r)?(p?q??r)?(p??q)?(?p?r)

?(p?q??r)?((p??p?r)?(?q??p?r))?(p?q??r)?(?q??p?r) ?(p??q??p?r)?(q??q??p?r)?(?r??q??p?r)?1. 方法三：分析法

（1）直接分析法：若前件p?(q?r)为真，分两种情况：

（i）p为假，则p?q为真，p?r为真，(p?q)?(p?r)为真。

（ii）p为真，则q?r为真，此时若q为真，则r为真，则p?q为真，p?r为

真，(p?q)?(p?r)为真；若q为假，则p?r为假，(p?q)?(p?r)为真。 综上，若前件为真，后件必为真，故该蕴含式成立。

(2）间接分析法：若后件(p?q)?(p?r)为假，则p?q为真，p?r为假。由

p?r为假可知，p为真，r为假。再由p?q可知，q为真。此时q?r为假，

p?(q?r)为假，即前件为假。故蕴含式成立。

5. 叙述下列各个命题的逆换式和逆反式，并以符号写出。 （1）如果下雨，我不去。 解：设p：天下雨。q：我去。

逆换式：如果我不去，天就下雨。符号表示为?q?p。 逆反式：如

果我去，天就不下雨。符号表示为q??p。 （2）仅当你走我将留下。 解：设p：我留下。q：你走。

逆换式：如果你走，我就留下。符号表示为：q?p。 逆反式：如果你不走，我就不留下。符号表示为：?q??p。 习题1.6

2. 将下列命题公式用只含?和?的等价式表达，并要求尽可能简单。 （1）(p?q)??p.

解： (p?q)??p?(p?? p)?q?0?q?0.（2）(p?(q??r))??p?q. 解： (p?(q??r))??p?q?(?p?(q??r))?(?p?q??r) ?p? q? ?p?q?

??p?q(?p??q

?p?)q?(?p?q?)q?(?r?) ?(p?q?) ?r?

?(?p?q)?(?p?q)?(?p?(?p?q)?(?p?q??r)??(p??q). （3）?p??q?(?r?p). (?p?q? ?r? ?p? q?

解：?p??q?(?r?p)??p??q?(r?p)

?(?p??q?r)?(?p??q?p)?(?p??q?r)?0 ??p??q?r??(p?q??r). 习题1.7

6．求下列命题公式的主析取范式和主合取范式： （1）((p?q)?r)?p. 解：

((p?q)?r)?p??(?(p?q)?r) ?p?((p?q)??r)?p?(p?q?p)?(p??r)?(p?q?(r??r))?(p?(q??q)? ?r?(p?q?r)?(p?q??r)?(p?q?r)?(p?q??r)?m0?m1?m3（主合取范式）

?m2?m4?m5?m6?m7.（主析取范式） ?(p?q)?(p ??r

?(p?q??r)(?p??q ?r??(p??q? ?r)

【篇三：《离散数学》试题及答案】

合a,b，其中a＝{1,2,3}, b= {1,2}, 则a - b＝

____________________;__________________________ .