离散数学2007-2008A卷

离散数学试卷第1页共9页北京科技大学2007–2008学年第I学期离散数学试卷（A）院(系)班级学号姓名试卷卷面成绩占课程考核成绩70平时成绩占30%课程考核成绩题号一二三四五六七八小计得分一、判断正误（共30分，每小题1.5分）1.树是无环连通简单图。()2.命题具有确定的真假值。()3.pq和p∨q命题等价。()4.有向图中结点入度之和等于出度之和。()5.设R和S是非空集合A上的等价关系，则RS也是A上的等价关系。()6.若A为矛盾式，则A的主析取范式为1。()7.量词的约束顺序对公式真假值无影响。()8.自然数集是无限集中最小的集合。()9.质数阶群必是循环群。()10.若r(R)=R，则R一定是自反的。()11.若f为函数，则(f-1)-1=f。()12.群中有幺元，零元。()13.若无向图中有两对结点的度数为奇数，则存在欧拉路。()14.任意一棵树至少有两片树叶。()15.(()())()()xyPxQyxPxyQy()16.设f是群G到群H的同态映射，若G是交换群，则H也是交换群。()17.设V＝Z,+,·，其中+和·分别代表普通加法和乘法，则集合S＝{-1,0,1}可以构成V的子代数。()得分装订线内不得答题自觉遵守考试规则，诚信考试，绝不作弊离散数学试卷第2页共9页18.偶数阶群必含2阶元。()19.任何一个循环群必定是阿贝尔群。()20.{,{}}–={,{}}()二、填空题（共30分，每个空格2分）1.已知集合A={，1，2}，则A的幂集合P（A）=。2.设集合A={a,b,c,d}，A上的关系R={a,a，a,c，b,d}，则关系R2=。3.设集合A={0,1,2,3,4,5}，A上的关系R={0,0，1,1，1,2，1,3，2,1，2,2，2,3，3,1，3,2，3,3，4,4，4,5，5,4，5,5}，则R在A上构成的等价类是_。4.设集合A={a,b,c,d,e}，A上半序关系R的哈斯图如图1所示，则A的极小元为_。图15.已知命题公式G=（PQ）R，则G的主析取范式是__。6.设D：{a,b}，将表达式xy(x,y)中的量词消除后，与之等价的命题公式是。7.设G是完全二叉树，G有15个点，其中有8个叶点，则G的分枝点数是。8.对下图（图2）中树的点图2中序遍历的次序是。9.设有限集A,B，|A|=m,|B|=n,则笛卡儿积AB的子集个数有__________________个.10.设X={x|xR,x0,1},在X上如下定义6个函数：f1(x)=x，f2(x)=1/x,f3(x)=1x,得分离散数学试卷第3页共9页f4(x)=1/(1x),f5(x)=(x1)/x,f6(x)=x/(x1),则G={f1,f2,f3,f4,f5,f6}关于函数合成运算构成群.则子群{f1,f2}的所有的右陪集是_______________________________________.11.设G是由K1,K2,K33个连通分支组成的平面图，则G共有个面。12.设G＝S4为4元对称群，则(1432)=.13.设S={12,,,naaa}，则下列集合S，P(S)，N，N×N×N，P(N)，R，R×R中基数为0的有：。14.一个班70个学生，在第一次考试中有36人得5分，在第二次考试中有29人得5分，如果两次考试中都没有得5分的有26人，那么两次考试都得5分的有人。15.(,)xyFxy的前束范式是。三、在自然推理系统F中构造下面推理的证明（8分）前提：()(()())xFxyGyHy，()()xRxyGy结论：(()())()xFxRxxHx得分装订线内不得答题自觉遵守考试规则，诚信考试，绝不作弊离散数学试卷第4页共9页四、试证：一个有限非交换群至少含有6个元（8分）五、设A={a,b,c}，求出A上所有的等价关系。（10分）得分得分离散数学试卷第5页共9页六、对下图（图3）所示无向带权图G求一棵最小生成树T，并计算出T的权W(T)。（6分）12357442113333442456823图3七、设:fAB为单射函数，:()()GPAPB，()GX为X在f下的像。证明G也是单射的。（4分）得分得分装订线内不得答题自觉遵守考试规则，诚信考试，绝不作弊离散数学试卷第6页共9页八、求当连通平面图的每个面至少有5条边围成时，边数与结点数所满足的关系式（4分）B卷北京科技大学200—200学年度第学期离散数学试题答案及评分标准一、判断正误（共36分，答错不扣分）1.√2.√3.4.√5.6.√7.√8.√9.√10.√11.√12.13.14.15.√16.√17.√18.19.20.√21.√22.√23.√24.√评分：每错一个扣1.5。二、填空（每题2分，共20分）1.2nn;2nn2.l,m;a,b,c;k;k,l,m3.64.65.e=v-16.b=c三、证明（12分）(1)证明：x(P(x)Q(x))x(P(x)∧Q(x))………………………得1分P(a)∧Q(a)………………………得1分x(A(x)Q(x))x(A(x)∨Q(x))A(a)∨Q(a)………………………得1分Q(a)得分离散数学试卷第7页共9页A(a)x(P(x)A(x)∨B(x))x(P(x)∨A(x)∨B(x))P(a)∨A(a)∨B(a)………………………得1分P(a),A(a)………………………得1分B(a)P(a)∧B(a)………………………得1分x(P(x)∧B(x))(2)证明：(P∨(P∧Q))P∧(P∧Q)………………………得1分P∧(P∨Q)………………………得1分(P∧P)∨(P∧Q)………………………得2分0∨(P∧Q)………………………得2分P∧Q四、(1)证明：1)R是自反的………………………得1分2)R是对称的………………………得1分3)R是传递的………………………得1分所以，R为等价关系。………………………得1分(2)[1]=[4]=[7]=[10]={1,4,7,10}………………………得2分[2]=[5]=[8]={2,5,8}………………………得1分[3]=[6]=[9]={3,6,9}………………………得1分五、证明：(1)∵a≤b,又∵b≤b离散数学试卷第8页共9页∴b≥a∨b………………………得1分∵b≤a∨b………………………得1分∴b=a∨b………………………得2分(2)∵b=a∨b∴b=a∨b≥a………………………得2分∴a≤b………………………得2分六、证明：设连通平面图G的面数为r，当v=3，e=2时，上式显然成立。………………………得1分若e≥3，则每一面的次数不小于3，面的次数之和为2e，因此2e≥3r,r≤2/3e………………………得2分带入欧拉定理:2=v-e+r≤v-e+2/3e………………………得2分2≤v-e/36≤3v-e即e≤3v-6.………………………得1分七、证明：(1)a,b∈C,∴a,b∈G1有f(a☆b)=f(a)*f(b)g(a☆b)=g(a)*g(b)∵f(a)=g(a),f(b)=g(b)∴a☆b∈C则，c,☆是封闭的。………………………得1分(2)设G1,☆的幺元为e，显然有a∈C,a∈G1离散数学试卷第9页共9页f(a☆e)=f(a)*f(e)=f(a)g(a☆e)=g(a)*g(e)=g(a)∵f(a)=g(a)∴f(e)=g(e)∴e∈C………………………得1分(3)a∈C,显然a∈G1f(a☆a-1)=f(a)*f(a-1)=f(e)g(a☆a-1)=g(a)*g(a-1)=g(e)∵f(a)=g(a),又∵f(e)=g(e)∴f(a-1)=g(a-1)∴a-1∈C………………………得1分∴C,☆为群。∴C,☆为子群。………………………得1分八、证明：只要证(1)显然，模6和模3同余关系是等价关系。………………得1分(2)列出模6同余类和模3同余类。………………得1分(3)证明下列之一，其它类以此类推。………………得2分[0]6[0]3，[1]6[1]3，[2]6[2]3，[3]6[0]3，[4]6[1]3，[5]6[2]3