【2016西南●最新版】[0004]《离散数学》网上作业及课程考试复习资料(有答案)

(C) (1, 3) (D) (1, 4).

5．设p：我们划船，q：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ?p∧?q (B) ?p∨?q (C) ? (p? q) (D) ? (?p∨?q).

三、构造下面推理的证明：如果小张和小王去看电影, 则小李也去看电影. 小赵不去看电影

或小张去看电影. 小王去看电影. 所以, 当小赵去看电影时, 小李也去.

四、设R是集合A上自反和传递的关系，试证明：R?R=R.

+B，A的幂集P(A). 五、已知A ={{?}, {?, 1}}, B = {{?, 1}, {1}}, 计算A∪B, A○

六、今有n个人, 已知他们中任何2人的朋友合起来一定包含其余n -2人. 试证明：

(1) 当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边(或右边)的人的朋友.

(2) 当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友.

参考答案：第2次作业答案 一、1. ?, {1}, {3}.

2. 4n + 2, (2n + 1)2, 2n2 + 1. 3. 2n, ?, X.

4. v4v2v1v3v5v2v3v4v5. 5. 2, 3, 2. 二、1—5: CBABB.

三、解令p: 小张去看电影, q: 小王去看电影,r: 小李去看电影,s: 小赵去看电影.

p?q?r,?s?p,q?s?r (1) sP(附加)

(2) ?s?p P (3) p T(1)(2)I (4) q P

(5) p?qT(3)(4)I (6)p?q?r P

(7)r T(5)(6) 四、证因为R传递，所以R?R?R. (5分)

对于任意(x,y)?R，由于R自反，于是(y,y)?R，进而(x,y)?R?R，因此

R?R?R.

故R?R?R.

五、解A∪B = {{?}, {?, 1}, {1}}.

+B= (A - B)∪(B - A) = {{?}}∪{{1}} = {{?}, {1}}. A○

P(A) = {?, {{?}}, {{?, 1}}, A}.

六、证用一个节点代表一个人, 若两个人是朋友，则对应的两个节点邻接，于是得到一个n阶简单无向图G = (V, E).

对于G的任意两个不相邻的节点u和v, 考虑w?V– {u, v}, 根据已知条件知，u与w或v与w必相邻. 由于节点u和v不相邻，于是u与w且v与w必相邻. 根据w的任意性知, deg(u)≥n– 2且deg(u)≥n– 2, 因而有deg(u) + deg(u)≥2(n– 2).

(1)当n≥3时, deg(u) + deg(u)≥2(n– 2)≥n– 1, 因而G中存在H路. (2)当n≥4时, deg(u) + deg(u)≥2(n– 2)≥n, 因而G中存在H回路.

1：[论述题]第3次作业

《离散数学》第3次作业

一、填空题

1.设A = {2, {3}, 4, a}, B = {1, 3, 4, {a}},则{3}( )A，{a}( )B，{{a}}( )B. 2.设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则

R?S?{ }, S?R?{ }, R?R?{ }.

3.在同构意义下，3阶群有( )个，4阶群有( )个，5阶群有( )个. 4.任意有限布尔代数(B,?,?,,0,1)均与集合代数( )同构，其元素个数为( ), 其中( )是B的所有原子组成的集合.

5.不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵.

二、单选题

1.在有理数集合Q上定义运算“*”如下：对于任意x, y?Q，x?y = x + y – xy，则Q关于*的单位元是( ).

(A)x. (B)y. (C)1. (D)0.

2.设A = {1, 2, 3}, 下图分别给出了A上的两个关系R和S，则R?S是( )关系.

1 2 G3 1 2 GS

3

(A)自反.(B)对称.(C)传递.(D)等价.

3.令T(x): x是火车，B(x): x是汽车，F(x, y): x比y快，则“某些汽车比所有的火车慢”符

号化为( ).

(A)?y?B(y)??x?T(x)?H(x,y)??. (B)?y?B(y)??x?T(x)?H(x,y)??. (C)?x?y?B(y)??T(x)?H(x,y)??. (D)?y?B(y)??x?T(x)?H(x,y)??.

4.整数集合Z关于数的加法“+”和数的乘法“?”构成的代数结构(Z, +, ?)是( ). (A)域 (B)域和整环 (C)整环 (D)有零因子环

5.设G是简单图，G是G的补图，若G?G，则称G为自补图. 5阶不同构的自补图个数为( ).

(A)0. (B)1. (C)2. (D)3.

三、设f:A?B,g:B?C, 若f?g是单射，证明f是单射，并举例说明g不一定是单

射.

四、设A = {a, b, c, d}上的关系R = {(a, b), (b, d), (c, c), (a, c)}, 画出R的关系图，并求出R的自

反闭包r(R)、对称闭包s(R)和传递闭包t(R).

五、设G是(6，12) 的简单连通平面图，则G的面由多少条边围成，为什么？ 六、任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.

参考答案：第3次作业答案

《离散数学》第3次作业参考答案

一、1.?，?，?.

2.{(1,5), (3, 2), (2, 5)}, {(4, 2), (3, 2), (1, 4)}, {(1, 2), (2, 2)}. 3.1,2, 1.

4.(P(X),?,?,,?, X), 2n, n. 5. 3, 9.

二、1(D); 2(B); 3(A); 4(C); 5(C).

三、证对于任意x1,x2?A，若f(x1)?f(x2)，则g(f(x1))?g(f(x2))，于是

(f?g)(x1)?(g?f)(x2). 由于f?g是单射，所以x1?x2，因此f是单射.

例如，A = {a, b}, B = {1, 2, 3}, C = {?, ?, ?}, f = {(a, 1), (b, 2)}, g = {(a, ?), (b, ?), (c, ?)}, 这时

f?g?{(1,?),(2,?)}，它是A到C的单射，但g不是单射.

四、解R的关系图如下：

a

b

d

c

r(R)?{(a,b),(b,d),(c,c),(a,c),(a,a),(b,b),(d,d)},

s(R)?{(a,b),(b,d),(c,c),(a,c),(b,a),(d,b),(c,a)}. t(R)?{(a,b),(b,d),(c,c),(a,c),(a,d)}.

五、证根据Euler公式，G的面数为r = 12 – 6 +2 = 8. 由握手定理知，

?deg(v)?2?12?24，

v而简单连通平面图的每个面至少由3条边围成，所以G的每个面恰由3条边围成. 六、证用6个节点分别表示这6个人，可得6阶完全无向图K6. 若两个人认识，则在相应的两个节点所在的边上涂上红色，若两个人不认识，则在相应的两个节点所在的边上涂上蓝色.

对于任意的K6的节点v，因为deg(v)?5，与v邻接的边有5条，当用红、蓝颜色去涂时，至少3条边涂的是同一种颜色，不妨设vv1,vv2,vv3是红色.若3条边v1v2，v2v3，v1v3是红色，则存在红色K3，这意味着有3个人相互认识; 若v1v2，v2v3，v1v3都是蓝色，则存在蓝色K3，这意味着有3个人相互不认识. 结论成立.

1：[论述题]第4次作业

《离散数学》第4次作业