2023年7月19日发(作者：)

离散数学综合练习题答案

一、 判断下列命题是否正确

（1）错误； （2）错误； （3）正确； （4）错误； （5）错误；

（6）正确； （7）错误； （8）正确； （9）正确； （10）错误；

（11）正确；（12）正确；（13）正确；（14）正确；（15）正确；

（16）正确；（17）正确；（18）正确；（19）正确；（20）正确；

（21）正确；（22）错误；（23）正确；（24）正确；（25）正确；

（26）正确；（27）正确；（28）正确；（29）正确；（30）错误；

（31）正确；（32）错误；（33）错误；（34）错误；（35）错误；

（36）正确；（37）正确；（38）正确；（39）错误；（40）错误.

二、 填空题

n~~ （1）2； （2）{,{},{{}},{,{}}}； （3）3； （4）40； (5)21(6)

； (7)a称c为外祖父； (8)5，9；

(9)[赵]= {赵茵，赵萍}，[钱]= {钱小滨，钱浩，钱钰}，[孙]={ 孙丽春}，

[李]= {李靖华，李秀娟，李惠芝，李莉}.

(10)

{,,,{a},,{b},,A,{a},{a},{a},A,{b},{b},{b},A,A,A}(11)

,S； (12) 1和2；

(13){0},6，{0,3},6，{0,2,4},6，I6,6；

(14)

x； (15) –2； (16) 1，1； (17)

axb，yab； (18)

bc；

(19)

e； (20) 0； (21) 5； (22) m-n＋1； (23) 1； (24) 0； (25) 1；

(26)

n(n1)2； (27)

2m； (28) 11； (29)

k1； (30) 偶数；

(31)

pq； (32)

pq； (33)

pq； (34) 0； (35) 0；

(36)

2； (37)F(a1)F(a2)F(an)； (38)

(x)(N(x)(F(x)G(x))；

(39)

F(a)G(a)； (40)

(x)(G(x)F(x))(x)(F(x)G(x)).

三、 选择题

（1） A； （2） C； （3） C； （4） B； （5） B；

（6） A； （7） B； （8） D； （9） B； （10）B；

（11）B； （12）D； （13）B； （14）D； （15）D；

（16）C； （17）C； （18）D； （19）C； （20）A；

（21）A； （22）B； （23）B； （24）C； （25）B；

（26）B； （27）B； （28）A； （29）B； （30）C；

（31）B； （32）C； （33）B； （34）A； （35）A；

（36）D； （37）D； （38）B； （39）B； （40）B.

四、 解答题

1. 解 （1）的关系矩阵为

2n1

11

M00又由于

1100001100

11（2）从的关系矩阵可知：是自反的和对称的。

110011001100110011001100M

MM001100110011001100110011所以是传递的。

因为是自反的、对称的和传递的，所以是A上的等价关系。

（3）

[a][b]{a,b}，[c][d]{c,d}

2. 解：

24

8 12

4

2 3

6

3. 解：

32 24

16 12

8 6

2 3

4. 解：由于是A上的整除关系，所以是A上的偏序关系，A,的

哈斯图为

4 6

2 3 5

1

（1）集合A的最大元：无，最小元：1

（2）

2

子集 上界

无

6

下界

1

1

上确界

无

6

下确界

1

1

A1{2,3,5}

A2{2,3,6}

5. 解：（1）a,d之间的所有初级通路共有7条，分别为

aed，aecd，aebcd，abed，abcd，abecd，abced

（2）a,d之间的长度最短的通路只有1条，即aed，因而它是a,d之间

唯一的短程，d(a,d)2

（3）由于无向图G中有两个奇度顶点deg(b)3,deg(c)3，所以无向图G没有欧拉图回路，因而不是欧拉图。

6. 解：图（1）中各顶点的度数为

deg(a)4，deg(b)4，deg(c)4，deg(d)4，deg(e)4，

deg(f)2，deg(g)4，deg(h)4，deg(i)2

由于图（1）中各顶点的度数均为偶数，所以图（1）为欧拉图。

回路abihecdgfa为经过图（1）中每个结点一次且仅一次的回路，所以回路abihecdgfa为哈密尔顿回路，因此图（1）是哈密尔顿图。

图（2）中各顶点的度数为

deg(v1)2，deg(v2)4，deg(v3)3，deg(v4)4，deg(v5)5，

deg(v6)4，deg(v7)2，deg(v8)4，deg(v9)2

由于图（2）中有两个奇度顶点，所以图（2）存在欧拉图通路，但是没有欧拉图回路，因此图（2）不是欧拉图。

回路v2v1v4v7v8v9v6v5v3v2为经过图（2）中每个结点一次且仅一次的回路，所以回路v2v1v4v7v8v9v6v5v3v2为哈密尔顿回路，因此图（2）是哈密尔顿图。

7. 解 由于(1)只有两个奇度结点，b,e. 因此，要由(1)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加一条边才能使(1)为欧拉图。

由于(2)有 4个奇度结点，因此，要由(2)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加两条边才能使(2)为欧拉图。

例如，可在(1)中添加边(b,e), 在(2)中添加边(a,b),(c,d)

a a

b e

b d

c d c

（1） （2）

8. 解：(1) 求D的邻接矩阵

3

10A00(2)

2000110100；

1010A200200030101121003A,

00000141013120004A,

001000601041

01D中长度为4的通路数为4ai1j144(4)ij16，其中对角元素之和为3，D中长度为4的回路(4)有3条。由于A中a14所以D中v1到v4长度为4的通路有4条。即e1e1e4e6，e4e6e7e6，4，e1e2e5e6，e1e3e5e6，其中e1e2e5e6为简单通路。

(3) 由于

40234

BAAAA00由B可知道D是单向连通图。

9. 解：(1) 有向图D为

8148022

022022

v4

v3

v5

v1

(2) 由于

v2

004

A004400040

40D中长度为4的通路数为32。因对角元素之和为0，故D中无长度为4的回路。

(4) 从图可得D的可达矩阵为

4

11

P1111111111

11从P可知D是强连通的。

10. 解：

a

b c

e f

五、 构造下列推理的证明

1. 证明：

①

r 前提引入；

②

qr 前提引入；

③

q ①② 析取三段论；

④

(pq) 前提引入；

⑤

pq 置换；④

⑥

p ③⑤析取三段论。

2. 证明 ①

t

前提引入；

②

st

前提引入；

③

s ①②拒取式；

④

sr

前提引入；

⑤

r ③④假言推理；

⑥

pr

前提引入；

⑦

p ⑤⑥拒取式；

⑧

pq

前提引入；

⑨

q ⑦⑧析取三段论。

3. 证明 ①

sp 前提引入；

②

s 前提引入；

③

p ①②析取三段论；

④

p(qr) 前提引入；

⑤

qr ③④假言推理；

⑥

q 前提引入；

⑦

r ⑤⑥假言推理。

4. 证明：

5

①

(x)(C(x)Q(x)) 前提引入；

②

(C(c)Q(c)) ①EI；

③

C(c) ②化简；

④

(x)(C(x)(W(x)R(x)) 前提引入；

⑤

C(c)(W(c)R(c) ④UI；

⑥

W(c)R(c) ③⑤ 假言推理；

⑦

R(c) ⑥化简；

⑧

Q(c) ②化简；

⑨

Q(c)R(c) ⑦⑧合取引入

(10)

(x)(Q(x)R(x)) ⑨EG

5. 解：设F(x):x是学术委员会的成员，G(x):x是专家，H(x):x是大学生，R(x):x是青年人。

前提

(x)(F(x)(G(x)H(x)),(x)(F(x)R(x))

结论(x)(F(x)G(x)R(x))

证明：

①

(x)(F(x)R(x)) 前提引入；

②

F(c)R(c) ①EI；

③

(x)(F(x)(G(x)H(x)) 前提引入；

④

F(c)(G(c)H(c)) ③UI；

⑤

F(c) ②化简；

⑥

G(c)H(c) ④⑤ 假言推理；

⑦

R(c) ②化简；

⑧

G(c) ⑥化简；

⑨

F(c)G(c)R(c) ⑤⑦⑧合取引入

(10)

(x)(F(x)G(x)R(x)) ⑨EG

6. 解：记F(x):x是病人，

G(x):x是医生，

H(x):x是骗子，

L(x,y):x相信y。

则上述推理符号化为

前提：x(F(x)y(G(y)L(x,y)))

x(F(x)y(H(y)L(x,y)))

结论：x(G(x)H(x))

证明： ①

x(F(x)y(G(y)L(x,y))) 前提引入；

②

F(a)y(G(y)L(a,y)) ①存在量词消去规则；

③

F(a) ②化简规则；

④

x(F(x)y(H(y)L(x,y))) 前提引入；

⑤

F(a)y(H(y)L(a,y)) ④全称量词消去规则；

⑥

y(H(y)L(a,y)) ③⑤假言推理规则；

⑦

H(y)L(a,y) ⑥全称量词消去规则；

⑧

L(a,y)H(y) ⑦置换；

⑨

y(G(y)L(a,y)) ②化简规则；

（10）G(y)L(a,y) ⑨全称量词消去规则；

（11）G(y)H(y) ⑧（10）假言三段论规则；

6

（12）x(G(x)H(x)) （11）全称量词引入规则；

六、 证明题

1. 证明：由于1,2是自反的，所以对任意aA,a,a1,而a,a12，即12是自反的。

若a,b12，则a,b1,a,a2, 因a,b2,由于1,2是对称的，所以b,a1,b,a2, 从而b,a12，即12是对称的。

若a,b,b,c12，则

a,b,b,c1,a,b,b,c2,由于1,2是传递的，所以a,c1,a,c2, 从而a,c12，即12是传递的。

由于12是自反的、对称的和传递的，所以12是等价关系。

2. 证明：由于G的连通性，则d(u,w)l，u,w之间必存在短程Puv1v2vl1w,(l2)，取v为P上除u,w外的任意一点vi(1il1)，都有u,vi之间的短程为P1uv1v2vi，vi,w之间的短程为P2vivi1vl1w.

否则，若u,vi之间存在比P1uu1u2vi，则1uv1v2vi短的短程P'P'uu1u2vivi1vl1w比P短，这与P为u,w之间的短程矛盾。

同理可证：P2vivi1vl1w为vi,w之间的短程。

因而d(u,vi)d(vi,w)等于P1的长度加上P2的长度，而P1的长度加上P2的长度为P的长度 ，即为l，所以d(u,vi)d(vi,w)ld(u,w).

3. 证明：令A为由上述四个矩阵组成的集合，是矩阵乘法运算，容易验证上述四个矩阵关于矩阵乘法运算是封闭的。

(1)由矩阵乘法运算知识知，是可结合的；

a0A，由于

0ba010a010a0a0，

0b010b010b0b

10所以矩阵01是运算的单位元。

(2)任取矩阵(3)由于

100111010，

01011010，

01017

11001，

1001，

1001

11所以A中每个元素都是可逆的。

由上面的1，2，3知，A,是群。

4. 解：充分性

若在群G,中，对任意的a,bG ,有a2b2(ab)2 .

则

(aa)(bb)(ab)(ab)

a(ab)ba(ba)b

abba

从而

G, 是一个交换群。

必要性

若G, 是一个交换群，对任意的a,bG ,有abba，则

a(ab)ba(ba)b

(aa)(bb)(ab)(ab)

即a2b2(ab)2.

5. 证明：由于对任意的x,yH，有

axxa,ayya

所以

(xy1)ax(aa1)y1a

(xa)(a1y1)a

(ax)(ya)1a

(ax)(ay)1a

axy1a1a

a(xy1)

即

xy1H，由子群的判定定理知H,是G,的子群。

6. 证明 显然，*是G上的二元运算。

先证结合律成立。a,b,cG，有

(a*b)*c(au1b)u1c

au1(bu1c)

au1(b*c)

a*(b*c)

即运算是可结合的.

由于aG，有

故u是运算*的单位元.

最后证明aG，ua1u是a在G,*中的逆元。由于

a*uau1ua

u*auu1aa

a*(ua1u)au1(ua1u)

a(u1u)a1u

(aa1)u

u

(ua1u)*a(ua1u)u1a

ua1(uu1)a

u(a1a)

u

8

因此G,*是一个群.

9