形成性考试

1离散数学作业要求：（1）禁止用附件提交作业。附件提交的作业计0分。（2）作业按题号顺序作答，乱序、不写题号等视情况扣分。（3）选择题直接提供答案，不要抄题。（4）卷面整洁，文字、符号以及粘贴的图等要清晰可辨。一、单选题（每题2分，共15小题）1.集合}}}{{},{,{cbaA，则下列不属于A的子集的是（）A.}}{{aB.}}{{bC.}}}{{{cD.}}{,{ba2.设全集{1,2,...,9,10}U的子集为A={偶数}，B={奇数}，则下列选项正确的是（）A.ABB.ABC.ABUD.以上答案都不对3.已知集合}4,3,2,1{A，},,{cbaB，}8,6,4,2,1{C,定义A到B的关系c)}(4,b),(3,a),(2,a),{(1,1，B到C的关系(c,1)}(b,6),{(a,4),2，则下列属于21的是（）A.)8,1(B.)4,1(C.)6,2(D.)1,3(4.集合}3,2,1{A上的关系)}3,1(),1,2(),2,1{(R，则R具有（）2A.对称性B.自反性C.可传递性D.以上说法都不对5.集合{1,2,3}A上的下列关系，是由A到A的函数的是（）A.{(1,3),(2,3),(3,1)}fB.{(1,2),(3,1)}gC.{(1,1),(2,1),(3,2),(1,3)}hD.{(1,3),(2,1),(2,2)}I6.集合},,{},3,2,1{cbaBA，则A到B的映射中，是单射的是（）A.}b)b)(3,a)(2,(1,{B.}b)b)(3,a)(1,(1,{C.}c)b)(3,a)(2,(1,{D.}b)b)(3,b)(2,(1,{7.下面各集合都是N的子集，（）集合在普通加法运算下是封闭的。A.}16|{整除的幂可以被xxB.}5|{互质与xxC.}30|{的因子是xxD.}30|{xx8.设集合A={1，2，3，4，5}上偏序关系图为，3则子集B={2，3，4}的最大下界为（）A.1B.4C.5D.无9.设,L是格，则对任意12,llL，有（）A.12212()()lllllB.12212()()lllllC.12112()()lllllD.以上答案都不对10.设图G的相邻矩阵为0110110101110110010111110，则G的顶点数与边数分别为（）A.5,4B.6,5C.10,4D.8,511.无向简单图EVG,，},,,,{54321vvvvvV，则||E的最大值是（）A.8B.10C.124D.1612.在如下各图中是欧拉图的是（）13.QP,是真命题，R是假命题，则（）A.RQP为真B.QPR为真C.RPQ为假D.PQR为假14.设是乌鸦x:P(x)，一样黑yx,:y),Q(x，则命题“天下乌鸦一般黑”可符号化为（）A.),()(yxQxxPB.),()()(yxQyPxPC.),())()()(((yxQyPxPyxD.)),()()((yxQxPx15.谓词公式)())()((xQyySxFx中变元是（）。A.自由变元B.约束变元C.既是自由变元也是约束变元D.以上答案都不对二、简答题（每题5分，共6小题）1.写出集合{,,{}}aa的幂集.52.设(4,5)}(3,3),(2,4),{(1,2),1，(5,4)}(4,2),(2,4),{(1,3),2，试求关系12的定义域和值域。3.说明什么是等价关系。4.请解释什么是群.5.给定如图所示的图,GVE，求出从A到E的所有初级路。6.用二叉树表示算术表达式()abcd。三、证明题（每题10分，共4小题）1.已知CBgBAf:,:，f是单射，g是单射，证明gf是单射。2.设（L,≤）是一个格，,,abcL试证明:若cba，则)()()()(cabacbba3.用推理法证明下式成立：(),,|PQQRRP4.由等值演算证明下列蕴涵式成立:(()())()xyPxQyxPx二：简答题：61.：2.：3.：等价关系定义为：设R是非空集合A上的二元关系，若R是自反的、对称的、传递的，则称R是A上的等价关系。研究等价关系的目的在于将集合中的元素进行分类，选取每类的代表元素来降低问题的复杂度，如软件测试时，可利用等价类来选择测试用例。4.群表示一个拥有满足封闭性、结合律、有单位元、有逆元的二元运算的代数结构5.：6.：三：证明题：1.反证若f不是单射,则存在a不等于b,且都属于A满足f(a)=f(b)因为gf是A到A的恒等映射,则有a=gf(a)=gf(b)=b==a=b矛盾故f是单射若g不是满射,则存在a∈A,满足对任何b∈B,有g(b)≠a故gf(a）含于g(B),所以gf(a)≠a又因为gf是A到A的恒等映射,则有a=gf(a)故矛盾2.：证明因为a∧b是a,b的最大下界,a∨b是a,b的最小上界,故得a∧b≤a,a≤a∨b,再由关系≤的传递性得a∧b≤a∨b因为b∧c是b,c的最大下界,b∨c是a,c的最小上界,故得7b∧c≤c,c≤b∨c,再由关系≤的传递性得b∧c≤b∨c...同理：(a∧b)∨(b∧c)≤(a∨b)∧(b∨c)3.：1）r→s（2）¬s（3）¬r（4）¬(p∧q)∨r（5）¬(p∧q)（6）¬p∨¬q（7）p（8）¬q4.：用附加前提证明法前提：∃x(P(x)→Q(x)),∀xP(x)结论：∃xp(x)证明：1、∀xP(x)2、P(a)3、∃x(P(x)→Q(x))4、P(a)→Q(a)5、q(a)6、∃xp(x)已阅1、答案：AABDACABADBBBCC，24分2、20分3、20分