离散数学及应用课后习题答案【篇一:离散数学及其应用图论部分课后习题答案】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,v 1?} (4)d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答:(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)同构,同构函数为12f(x)345解答:(1)三条边一共提供6度;所以点度序列可能是x?ax?bx?c x?dx?e16、画出所有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的关联矩阵。
1100000010?111000?00?1000?1? 解答:?0??0000?11?110?1100?110??【篇二:离散数学及其应用(课后习题)】出下列命题是原子命题还是复合命题。
(3)大雁北回,春天来了。
(4)不是东风压倒西风,就是西风压倒东风。
(5)张三和李四在吵架。
解:(3)和(4)是复合命题,(5)是原子命题。
习题1.21. 指出下列命题的真值:(1)若2?2?4,则太阳从西方升起。
解:该命题真值为t(因为命题的前件为假)。
(3)胎生动物当且仅当是哺乳动物。
解:该命题真值为f(如鸭嘴兽虽是哺乳动物,但不是胎生动物)。
2. 令p:天气好。
q:我去公园。
请将下列命题符号化。
(2)只要天气好,我就去公园。
(3)只有天气好,我才去公园。
(6)天气好,我去公园。
解:(2)p?q。
(3)q?p。
(6)p?q。
习题1.32. 将下列命题符号化(句中括号内提示的是相应的原子命题的符号表示):(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.41. 写出下列公式的真值表:(2)p?(q?r)。
解:该公式的真值表如下表:2. 证明下列等价公式:(2)(p?q)??(p?q)??(p?q)。
证明:(pq)((pq)(pq))(pq)(pq))(pq)(pq) (p q)(pq)(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 cd)(abcd)d (ad)(abcd)(abcd)(abcd)(abd)(abcd)(acd)0;同理,pqrsaabcd(abcd)d0; pqr s?a??(?a??b??c?d)??a?b??c??d?d?0; ?p??q??r?s?a??(?a? bcd)(abcd)d a(abcd)(abcd)d ad.所以,当k为真时,a??d为真,即甲的成绩最好。
习题1.52. 证明下列各蕴含式:(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?qr)?(pq)?(?p?r)(pqr)((ppr)(qpr))(pqr)(qpr)(pqpr)(qqpr)(rqpr)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.62. 将下列命题公式用只含?和?的等价式表达,并要求尽可能简单。
(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 qpqp?q(?pqp)q(pq)q(r)(pq)r(pq)(pq)(p(pq)(pqr)(pq).(3)?p??q?(?r?p).(?p?q? ?r?p q解:?p??q?(?r?p)??p??q?(r?p)(pqr)(pqp)(pqr)0 pqr(pqr).习题1.76.求下列命题公式的主析取范式和主合取范式:(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(主合取范式)m2m4m5m6m7.(主析取范式)(pq)(p r(pqr)(pq r(pq r)【篇三:《离散数学》试题及答案】合a,b,其中a={1,2,3}, b= {1,2}, 则a - b=____________________;__________________________ .3. 设集合a = {a, b}, b = {1, 2}, 则从a到b的所有映射是__________________________ _____________, 其中双射的是__________________________.4. 已知命题公式g=?(p?q)∧r,则g的主析取范式是_____________________________________________________________________________________ ____.5.设g是完全二叉树,g有7个点,其中4个叶点,则g的总度数为__________,分枝点数为________________.___________________;a-b= _____________________ .7. 设r是集合a上的等价关系,则r所具有的关系的三个特性是______________________, ________________________,_______________________________.8. 设命题公式g=?(p?(q?r)),则使公式g为真的解释有__________________________,_____________________________,__________________________.9. 设集合a={1,2,3,4}, a上的关系r1 = {(1,4),(2,3),(3,2)}, r1 = {(2,1),(3,2),(4,3)}, 则 r1?r2 = ________________________,r2?r1 =____________________________,=________________________.10. 设有限集a, b,|a| = m, |b| = n, 则| |?(a?b)| =_____________________________.11 设a,b,r是三个集合,其中r是实数集,a = {x | -1≤x≤1, x?r}, b = {x | 0≤x 2, x?r},则a-b = __________________________ , b-a = __________________________ , a∩b =__________________________ , .13. 设集合a={2, 3, 4, 5, 6},r是a上的整除,则r以集合形式(列举法)记为_________________________________________________________________ _.14. 设一阶逻辑公式g = ?xp(x)??xq(x),则g的前束范式是__________________________ _____. 15.设g是具有8个顶点的树,则g中增加_________条边才能把g变成完全图。