一、填空题
1.设A = {1, 2, 3, {1, 2}, {3}}, B = {2, {2,3}, {1}} , 则A – B = { }, B – A = { }, A?B = { }.
2.实数集合R关于加法运算“+”的单位元为( ), 关于乘法运算“?”的单位元为( ),关于乘法运算“?”的零元为( ).
3.令Z(x): x是整数，O(x): x是奇数，则“不是所有整数都是奇数”符号化为( ).
4.有限域的元素个数为( ), 其中( )且( ).
5.设G是(7, 15)简单平面图，则G一定 ( )连通图，其每个面恰由( )条边围成，G的面数为( ).
二、单选题
1.函数的复合运算“?”满足( )
(A)交换律. (B)结合律. (C)幂等律. (D)消去律. 2.设集合A中有4个元素，则A上的等价关系共有( )个. (A)13(B)14 (C)15 (D)16 3.下列代数结构(G, *)中，( )是群.
(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q, “*”是数的乘法.
(C)G = Z, “*”是数的减法. (D)G = {1, 3, 4, 5, 9}, “*”是模11乘法. 4.下列偏序集，( )是格.
5.不同构的(5, 3)简单图有( )个.
(A)4 (B)5 (C)3 (D)2
三、设f:A?B,g:B?C, 若f?g是满射，证明g是满射，并举例说明f不一定是满
射.
四、在整数集合Z上定义关系R如下：对于任意x,y?Z，
(x,y)?R?x2?x?y2?y.
判断R是否具有自反性、反自反性、对称性、反对称性及传递性.
五、利用真值表求命题公式
A??(p?q))?(p??q)
的主析取范式和主合取范式.
六、将6阶完全无向图K6的边随意地涂上红色或蓝色，证明：无论如何涂法，总存在红色
的K3或蓝色的K3.
参考答案：第4次作业答案
《离散数学》第4次作业参考答案
一、1.{1, 3, {1, 2}, {3}}；{{2, 3}, {1}}；{1, 3, {1, 2}, {3}, {2, 3}, {1}}.
2.0，1，0.
3.??x(Z(x)?O(x)). 4.pn, p为素数，n为正整数. 5.是，3，10.
二、1(B); 2(C); 3(D); 4(C); 5(A).
三、证对于任意z?C，由于f?g是满射，必存在x?A，使得(f?g)(x)?g(f(x))?z.令y?f(x)?B，有g(y)?z，因此，g是满射.
设A?{a,b,c}，B?{1,2,3}，C?{?,?}，令f:A?B，g:B?C,
f(a)?2,f(b)?3,f(c)?3,
g(1)??,g(2)??,g(3)??.这时，
(f?g)(a)?g(f(a))??，(f?g)(b)?g(f(b))??，显然有ran(f?g)?{?,?}，f?g是满射. 而ranf = {2, 3}，f不是满射.
22四、证 (1)对于任意x?Z, 由于x?x?x?x, 所以(x, x) ?R, 即R是自反的.
(2)因为(0, 0) ?R, 因此R不是反自反的.
(3)对于任意x, y?Z, 若(x, y) ?R,则x?x?y?y, 于是y?y?x?x, 进而(y, x) ?R,
2222即R是对称的.
(4)因为(2, -3) ?R且(-3, 2) ?R，因此R不是反对称的.
(5)对于任意x , y, z?Z, 若(x, y) ?R且(y, z) ?R, 则x2?x?y2?y且y2?y?z2?z，于是
x2?x?z2?z，所以(x, z) ?R, 即R是传递的.
综上所述，知R是自反的、对称的和传递的.
五、解命题公式A??(p?q))?(p??q)的真值表如下：
pq 1 1 1 0 0 1 0 0 ?(p?q) 0 1 0 0 p??q 0 1 1 1 A 1 1 0 0 A的主析取范式为：
A?(p?q)?(p??q).
A的主合取范式为：
A?(p??q)?(p?q).
六、证对于任意的K6的节点v，因为deg(v)?5，与v邻接的边有5条，当用红、蓝颜色去涂时，至少3条边涂的是同一种颜色，不妨设vv1,vv2,vv3是红色.若3条边v1v2，v2v3，
v1v3是红色，则存在红色K3; 若v1v2，v2v3，v1v3都是蓝色，则存在蓝色.
1：[论述题]第5次作业
《离散数学》第5次作业
一、填空题
1.集合A上的等价关系R必满足( 、、 ). 2.任意6阶群的平凡子群一定是( )群. 3.设集合A = {1, 2, 3}，则A上的置换共有( )个.
4.设集合A关于?满足( 、 )，则(A, ?)构成独异点. 5. ( )无向图称为无向树.
二、单选题
1.设集合A中有99个元素，则A的子集有( )个. (A)299. (B)99. (C)2100. (D)100.
2.设集合A中有4个元素，则A上的划分共有( )个. (A)13(B)14 (C)15 (D)16
3.设集合A = {1, 2, 3, 4, 5}上的关系R = {(x, y)|x, y?A且x + y = 6}，则R的性质是( ). (A) 自反的. (B)对称的.(C)对称的、传递的. (D)反自反的、传递的. 4.下列联结词中，不满足交换律的是( ).
(A)?. (B)?. (C)?. (D)?.
5.谓词公式?x(P(x)??yQ(y))?R(x)中，?x的辖域为( ).
(A)?x(P(x)??yQ(y)). (B)P(x). (C)P(x)??yQ(y). (D)P(x)和R(x).
三、设(A,?)是偏序集，定义函数f:A?P(A)如下：
对于任意a?A，f(a)?{x|x?A,x?a}.
证明f是单射，且当a?b时有f(a)?f(b).
四、(1)列出与非联结词“?”的运算表.
(2)仅使用与非联结词“?”分别表示?,?,?.
五、求?x?y(?zP(x,y,z)?(?uQ(x,u)??vQ(y,v)))的前束范式. 六、 (1)给出(n, m)连通平面图的面数r计算公式.
(2)若(n, m)连通平面图的每个面至少由5条边围成，给出n和m所满足的关系式. (3)证明：Petersen图不是平面图.
参考答案：第5次作业答案
《离散数学》第5次作业参考答案
一、1.自反性、对称性和传递性.
2. Abel. 3. 6.
4. 封闭性和结合性. 5. 不含圈的连通. 二、1(A); 2(C); 3(B); 4(D); 5(C).
三、证对于任意a,b?A，假定f(a)?f(b).由于?是偏序，于是a?a，所以a?f(a)，
相关推荐：
loading