发布时间 : 星期二 文章【2016西南●最新版】[0004]《离散数学》网上作业及课程考试复习资料(有答案)更新完毕开始阅读2bf905c8cc175527072208d6
(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次作业