离散数学2006-2007B

北京科技大学2006—2007学年度第1学期离散数学试题（B卷）（时间120分钟）学院班级学号姓名题号一二三四五六七八卷面实际评分卷面分占总分%平时成绩占总分%成绩总分得分一、判断正误（共36分，答错不扣分）1.集合的∩、∪运算满足结合律，吸收率。2.命题具有确定的真假值。3.量词的约束顺序对公式真假值无影响。4.pq和p∨q命题等价。5.xθ(x)与xθ(x)等价。6.任何质数阶群不可能有非平凡群。7.质数阶群必是循环群。8.自然数集是无限集中最小的集合。9.有理数集是可数集。10.若r(R)=R，则R一定是自反的。11.有限半群必有幂等元。12.群中有幺元，零元。13.若f为函数，则(f-1)-1=f。14.若f，q为函数，则(f◦g)-1=f-1◦g-1。acbdefighjklm15.若f，g为入射，则f◦g也是入射。16.无向连通图的所有结点度数之和等于边数的2倍。17.有向图中结点入度之和等于出度之和。18.若无向图中有两对结点的度数为奇数，则存在欧拉路。19.无向图中有哈密尔顿路的必要条件是任意两对结点度数之和大于n-1。20.任何一个循环群必定是阿贝尔群。21.设A，≤是一个代数系统，若∨、∧都是满足交换律，结合律和吸收率，则A上存在偏序关系≤，使A,≤是一个格。22.若A，≤为格，则有A，≤诱导的代数系统满足幂等律。23.任意一棵树至少有两片树叶。24.树是无环连通图。二、填空（每题2分，共20分）1.n元集合上共有_____________个关系，____________个自反关系。2.左图中，极大元素是____________，极小元素为____________，{a,b,c}的最小上界____________，{f,g,h}的所有下界____________。3.在平面图中，若v=6，e=10，则r=____________。4.树中边数和结点的关系是____________。5.任意一个正整数n，必存在含有____________个元素的布尔代数。6.设G，*为群，对任意的a,b,c∈G,若有a*b=a*c，则有____________。三、证明（12分）(1)前提x(P(x)A(x)∨B(x))x(A(x)Q(x))x(P(x)Q(x))结论x(P(x)∧B(x))(2)(P∨(P∧Q))P∧Q四、设x={1,2,…,10}，定义x上一个关系R，a,b∈x，a，b∈R当且仅当a-b被3整除。（8分）(1)证明R为等价关系.(2)求由R确定的等价类。五、设A，≤是一个格，那么对于任意的a，b∈A，有a≤ba∨b=b。（8分）六、设G是一个有v个结点，e条边的连通简单平面图，若v≥3，则e≤3v-6。（6分）七、设f，g都是群G1，☆到群G2，*的同态，证明C，☆是G1，☆的一个子群。其中C={x|x∈G1，且f(x)=g(x)}。（6分）八、设P1，P2均为某集合的划分，如果在划分P1中的每个集合都是划分P2中每个集合的子集，则P1叫做P2的加细。证明：整数集上由模6同余类构成的划分是模3同余类构成划分的加细。。（4分）B卷北京科技大学200—200学年度第学期离散数学试题答案及评分标准九、判断正误（共36分，答错不扣分）a)√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)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∴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∈G1f(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