2013年春西南大学离散数学作业答案

一、填空题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)},则SR{(1,5),(3,2),(2,5)},RS{(4,2),(3,2),(1,4)},RR{(1,2),(2,2)}.3.在同构意义下，3阶群有(1)个，4阶群有(2)个，5阶群有(1)个.4.任意有限布尔代数)1,0,,,,(B均与集合代数,,,),((XP,X)同构，其元素个数为(2n),其中(n)是B的所有原子组成的集合.5.不同构的5阶无向树有(3)棵，不同构的5阶根树有(9)棵.二、单选题1.在有理数集合Q上定义运算“*”如下：对于任意x,yQ，yx=x+y–xy，则Q关于*的单位元是(D).(A)x.(B)y.(C)1.(D)0.2.设A={1,2,3},下图分别给出了A上的两个关系R和S，则SR是(B)关系.(A)自反.(B)对称.(C)传递.(D)等价.3.令T(x):x是火车，B(x):x是汽车，F(x,y):x比y快，则“某些汽车比所有的火车慢”符号化为(A).(A)),()()(yxHxTxyBy.(B)),()()(yxHxTxyBy.(C)),()()(yxHxTyByx.(D)),()()(yxHxTxyBy.4.整数集合Z关于数的加法“+”和数的乘法“”构成的代数结构(Z,+,)是(C).112233GSGR(A)域(B)域和整环(C)整环(D)有零因子环5.设G是简单图，G是G的补图，若GG，则称G为自补图.5阶不同构的自补图个数为(C).(A)0.(B)1.(C)2.(D)3.三、设CBgBAf:,:,若gf是单射，证明f是单射，并举例说明g不一定是单射.证对于任意，若)()(21xfxf，则))(())((21xfgxfg，于是))(())((21xfgxgf.由于gf是单射，所以21xx，因此f是单射.例如，A={a,b},B={1,2,3},C={,,},f={(a,1),(b,2)},g={(a,),(b,),(c,)},这时)},2(),,1{(gf，它是A到C的单射，但g不是单射.四、设A={a,b,c,d}上的关系R={(a,b),(b,d),(c,c),(a,c)},画出R的关系图，并求出R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R).解R的关系图如下：,}),(),,(),,(),,(),,(),,(),,{()(acbdabcaccdbbaRs.}),(),,(),,(),,(),,{()(dacaccdbbaRt.五、设G是(6，12)的简单连通平面图，则G的面由多少条边围成，为什么？证根据Euler公式，G的面数为r=12–6+2=8.由握手定理知，vv24122)deg(，Axx21,}),(),,(),,(),,(),,(),,(),,{()(ddbbaacaccdbbaRrabcd而简单连通平面图的每个面至少由3条边围成，所以G的每个面恰由3条边围成.六、任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.证用6个节点分别表示这6个人，可得6阶完全无向图6K.若两个人认识，则在相应的两个节点所在的边上涂上红色，若两个人不认识，则在相应的两个节点所在的边上涂上蓝色.对于任意的6K的节点v，因为5)deg(v，与v邻接的边有5条，当用红、蓝颜色去涂时，至少3条边涂的是同一种颜色，不妨设321,,vvvvvv是红色.若3条边21vv，32vv，31vv是红色，则存在红色3K，这意味着有3个人相互认识;若21vv，32vv，31vv都是蓝色，则存在蓝色3K，这意味着有3个人相互不认识.结论成立