09信管离散数学考试卷(A)

2010－2011学年第一学期计算机学院09信管《离散数学》期末试卷（A卷）年级＿＿＿专业＿＿＿＿＿＿班级学号＿＿＿＿姓名＿＿＿注：考试时间共100分钟，试卷总分100分题号一二三四五六总分签名得分一得分一、选择题（每小题2分，共20分），请将所选答案填入下表中。题号12345678910答案1.以下语句中_____是命题.A.禁止吸烟!B.063x.C.蚊子是鸟类动物.D.2是偶数吗?2.命题公式qqpp))((是______.A.重言式B.矛盾式C.非重言式的可满足式D.析取范式3．A={a,b,c},AIaccaR},,,{，则R是A上的。A.等价关系B.偏序关系C.反自反关系D.对称关系4.设)(xS表示“x是学生。”，)(xP表示“x考试及格。”，则对命题“有的学生考试不及格.”可符号化为______。A.))()((xPxSxB.))()((xPxSxC.))()((xPxSxD.))()((xPxSx5.设)|{ZxxA，则A关于如下_____定义的*运算不能构成半群。A.xyxB.yxyxC.),min(yxyxD.),max(yxyx6.一个5阶简单平面图，最多有____边数。A.6B.7C.8D.97.有12个顶点、3棵树的森林共有条边。A.6B.7C.8D.98.以下各命题中为真。A.}{B.C.)(}{D.)(}{9.设F={-1，1}，运算是普通乘法，则(F,)。A.是独异点但不是群B.是群但不是阿贝尔群C.是阿贝尔群但不是循环群D.是阿贝尔群并且是循环群10.设E={1,3,4,5,6，7},A={x|x4},B={x|1x5},则BA____。A.{1，4}B.{1，2，4}C.{1，3，4,5}D.{1，2，4,5}二得分一、填空题（本大题共10小题，每小题3分，共30分）1.含两个变元p,q的命题公式A的成真赋值为10，11，则A的主合取范式为。A的类型为。2．公式),()),(),((yxHyxyGyxFx中,y的辖域是，x自由出现次。3.设集合},{baA,}2,1{B,则BA=__________________。)(A。4.Q为有理数集，运算+是普通加法，则群〈Q，+〉上，13，32。5.6个点4条边3个面的平面图共有个连通分支。n个点m条边k个面的连通平面图的欧拉公式为。6.A={1,2,3,4},R={3,3,1,2,2,4},)(Rs___，)(Rt。7．欧拉图共有个奇点，无向完全图6K共有条边。8.X={1,2,3,4,5},X上的等价关系R={1,2,2,1,4,5,5,4}∪Ix,则[2]R=___________,X/R=__________________________.9．G是交换群，则其运算满足、、。10．偏序关系具有的性质是、、。《离散数学》期末考试试卷（A卷）第1页共3页三得分一、判断题（错的打“×”，对的打“√”；每小题1分，共10分。）1.无向图G是哈密顿图，则G一定是欧拉图。（）2.命题公式)qq不是重言式。（）3.循环群一定是交换群。（）4.群中一定没有零元。（）5.一个关系是对称的就一定不是反对称的。（）6．f，g是A上的函数，若gf是双射，则g一定是双射。（）7．一个有5个结点，4条边的无向连通图是树。（）8．关系的复合满足结合律。（）9．A的等价关系与A的划分一一对应。（）10．一个公式的主析取范式与主合取范式是不等值的。（）四得分四.(每小题4分,共12分)1．一棵无向树T有4个2度结点，1个3度结点，3个4度结点，其余为叶。则T共有多少个结点，多少片叶？2．},,{cbaA,A上函数},,,,,{accbbaf，},,,,,{accbcag，判断f，g是否为双射？,并求fg,1fg.3．求公式rqp)(的主析取范式和主合取范式《离散数学》期末考试试卷（A卷）第2页共3页五得分五（每小题10分，共20分）1、(10分)已知偏序集〈X,R〉,其中X={2,3，4,6,8,12，24},R为X上的的整除关系，Y={4，6，8}①画出R的哈斯图；②.找出X的极大元、极小元、最大元、最小元；③.找出Y的上界、下界、最小上界、最大下界。2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,a,a,ba,d,b,a,b,b,c,a,c,b，c,c，c,d,d,c,d,d}(1).求出G中顶点的入度序列。(2).写出G的邻接矩阵；(3).求出图中所有长度等于2的路的条数。六得分六、证明题（8分，）构造下面推理的证明：前提：,,,srqppr结论：.qs《离散数学》期末考试试卷（A卷）第3页共3页