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

千里之行，始于足下。第2页/共2页精品文档推荐离散数学及应用课后习题答案离散数学及应用课后习题答案

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

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?cx?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＝

____________________;__________________________.

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≤x2,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变成彻底图。

16.设谓词的定义域为{a,b},将表达式?xr(x)→?xs(x)中量词消除，写成与之对应的命题公式是

__________________________________________________________________________.

17.设集合a＝{1,2,3,4}，a上的二元关系r＝{(1,1),(1,2),(2,3)},s

＝{(1,3),(2,3),(3,2)}。则r?s＝

r12

?(a)-?(b)＝

_____________________________________________________,r2＝

______________________________________________________.

二、挑选题

(c)??{{a}}?b?e(d){{a},1,3,4}?b.

(c)对称性

(d)反对称性

1设集合a={2,{a},3,4}，b={{a},3,4,1}，e为全集，则下列命题正

确的是()。

(a){2}?a(b){a}?a(a)自反性(a)下界

2设集合a={1,2,3},a上的关系r＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则

r别具备().

(b)传递性(b)上界

3设半序集(a,≤)关系≤的哈斯图如下所示，若a的子集b=

{2,3,4,5},则元素6为b的()。

(c)最小上界(d)以上答案都别对

4下列语句中，()是命题。

(a)请把门关上(b)地球外的星球上也有人(c)x+56(d)下午有会吗？

5设i是如下一具解释：d＝{a,b},

p(a,a)p(a,b)p(b,a)p(b,b)1010

则在解释i下取真值为1的公式是().

(a)?x?yp(x,y)(b)?x?yp(x,y)(c)?xp(x,x)(d)?x?yp(x,y).

(a)(1,2,2,3,4,5)(b)(1,2,3,4,5,5)(a)恒确实(b)恒假的

(c)(1,1,1,2,3)(d)(2,3,3,4,5,6).

6.若供挑选答案中的数值表示一具简单图中各个顶点的度，能画出

图的是().

7.设g、h是一阶逻辑公式，p是一具谓词，g＝?xp(x),h＝?xp(x),则一阶逻辑公式g?h是().

(c)可满脚的(d)前束范式.

8设命题公式g＝?(p?q)，h＝p?(q??p)，则g与h的关系是()。

(a)g?h(b)h?g(c)g＝h(d)以上都别是.(a)a＝b(a)自反性

(b)a?b(b)传递性

(c)b?a

(d)a＝b＝?.

9设a,b为集合，当()时a－b＝b.

10设集合a={1,2,3,4},a上的关系r＝{(1,1),(2,3),(2,4),(3,4)},则r具有()。

(c)对称性(d)以上答案都别对

11下列对于集合的表示中正确的为()。

(a){a}?{a,b,c}(b){a}?{a,b,c}(c)??{a,b,c}(d){a,b}?{a,b,c}(a)对

任意x，g(x)都取真值1.(b)有一具x0，使g(x0)取真值1.(c)有某些x，使g(x0)取真值1.(d)以上答案都别对.13.设g是连通平面图，有5个顶点，6个面，则g的边数是().

(a)9条(b)5条(c)6条(d)11条.(a)6(b)5

(c)10(d)4.

14.设g是5个顶点的彻底图，则从g中删去()条边能够得到树.

12命题?xg(x)取真值1的充分必要条件是().

?0

?1

15.设图g的相邻矩阵为?

?1??1??1

(a)4,5(b)5,6

三、计算证明题

1111?

0100?

?，则g的顶点数与边数分不为().

1011?

?

0101?0110??

(c)4,10

(d)5,8.

1.设集合a＝{1,2,3,4,6,8,9,12}，r为整除关系。

(1)画出半序集(a,r)的哈斯图；

(2)写出a的子集b={3,6,9,12}的上界，下界，最小上界，最大下界；(3)写出a的最大元，最小元，极大元，极小元。2.

设集合a＝{1,2,3,4}，a上的关系r＝{(x,y)|x,y?a且x?y},求(1)画出r的关系图；(2)写出r的关系矩阵.3.

设r是实数集合，?,?,?是r上的三个映射，?(x)=x+3,?(x)=

2x,?(x)＝x/4,试求复合映射???，???,???,???，?????.

4.设i是如下一具解释：d={2,3},

a3

b2

f(2)3

f(3)2

p(2,2)0

p(2,3)0

p(3,2)1

p(3,3)1

试求(1)p(a,f(a))∧p(b,f(b));

(2)?x?yp(y,x).

5.设集合a＝{1,2,4,6,8,12}，r为a上整除关系。

(1)画出半序集(a,r)的哈斯图；

(2)写出a的最大元，最小元，极大元，极小元；

(3)写出a的子集b={4,6,8,12}的上界，下界，最小上界，最大

下界.6.设命题公式g=?(p→q)∨(q∧(?p→r)),求g的主析取范式。

7.(9分)设一阶逻辑公式：g=(?xp(x)∨?yq(y))→?xr(x)，把g化

成前束范式.9.设r是集合a={a,b,c,d}.r是a上的二元关系,r={(a,b),(b,a),(b,c),(c,d)},

(1)求出r(r),s(r),t(r)；(2)画出r(r),s(r),t(r)的关系图.

11.经过求主析取范式推断下列命题公式是否等价：

(1)g=(p∧q)∨(?p∧q∧r)(2)h=(p∨(q∧r))∧(q∨(?p∧r))

13.设r和s是集合a＝{a,b,c,d}上的关系，其中r＝{(a,a),(a,

c),(b,c),(c,d)},c),(b,d),(d,d)}.

(1)试写出r和s的关系矩阵；(2)计算r?s,r∪s,r1,s1?r1.

－

－

－

s＝{(a,b),(b,

四、证明题

1.利用形式演绎法证明：{p→q,r→s,p∨r}蕴涵q∨s。

2.设a,b

为任意集合，证明：(a-b)-c=a-(b∪c).

3.(本题10分)利用形式演绎法证明：{?a∨b,?c→?b,c→d}蕴涵

a→d。4.(本题10分)a,b为两个任意集合，求证：

a－(a∩b)=(a∪b)－b.

参考答案

一、填空题

1.{3};{{3},{1,3},{2,3},{1,2,3}}.

2.2.

3.?1={(a,1),(b,1)},?2={(a,2),(b,2)},?3={(a,1),(b,2)},?4={(a,2),(b,1)};?3,?

4.4.(p∧?q∧r).

5.12,3.

6.{4},{1,2,3,4},{1,2}.

7.自反性；对称性；传递性.

8.(1,0,0),(1,0,1),(1,1,0).

9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2m?n.

11.{x