离散数学2006-2007A

北京科技大学2006—2007学年度第1学期离散数学试题（A卷）（时间120分钟）学院班级学号姓名题号一二三四五六七八卷面实际评分卷面分占总分%平时成绩占总分%成绩总分得分一、判断正误（共36分，答错不扣分）1.命题具有确定的真假值。2.pq和p∨q命题等价。3.量词的约束顺序对公式真假值无影响。4.xθ(x)与xθ(x)等价。5.自然数集是无限集中最小的集合。6.有理数集是可数集。7.任何质数阶群不可能有非平凡群。8.质数阶群必是循环群。9.若r(R)=R，则R一定是自反的。10.若f为函数，则(f-1)-1=f。11.若f，q为函数，则(f◦g)-1=f-1◦g-1。12.若f，g为入射，则f◦g也是入射。13.有限半群必有幂等元。14.群中有幺元，零元。acbdefighjklm15.无向连通图的所有结点度数之和等于边数的2倍。16.有向图中结点入度之和等于出度之和。17.若无向图中有两对结点的度数为奇数，则存在欧拉路。18.无向图中有哈密尔顿路的必要条件是任意两对结点度数之和大于n-1。19.任意一棵树至少有两片树叶。20.树是无环连通图。21.设A，≤是一个代数系统，若∨、∧都是满足交换律，结合律和吸收率，则A上存在偏序关系≤，使A,≤是一个格。22.若A，≤为格，则有A，≤诱导的代数系统满足幂等律。23.任何一个循环群必定是阿贝尔群。24.集合的∩、∪运算满足结合律，吸收率。二、填空（每题2分，共20分）1.n元集合上共有_____________个关系，____________个自反关系。2.左图中，极大元素是____________，极小元素为____________，{a,b,c}的最小上界____________，{f,g,h}的所有下界____________。3.任意一个正整数n，必存在含有____________个元素的布尔代数。4.在平面图中，若v=6，e=10，则r=____________。5.树中边数和结点的关系是____________。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分）七、设P1，P2均为某集合的划分，如果在划分P1中的每个集合都是划分P2中每个集合的子集，则P1叫做P2的加细。证明：整数集上由模6同余类构成的划分是模3同余类构成划分的加细。（4分）八、设f，g都是群G1，☆到群G2，*的同态，证明C，☆是G1，☆的一个子群。其中C={x|x∈G1，且f(x)=g(x)}。（6分）北京科技大学2006--2007学年第I学期离散数学试卷参考答案及评分标准（A）一、判断正误（共30分，每小题1.5分）1.√2.√3√4.√5.6.7.8.√9.√10.√11.12.13.14.15.√16.17.18.√19.√20.√二、填空题（共30分，每个空格2分）1.{φ，{φ}，{1}，{2}，{φ，1}，{φ，2}，{1，2}，A}2.{a，a，a，c}3.M1＝{0}，M2＝{1，2，3}，M3＝{4，5}4.c，d5.P∧Q∧R或m56.（F（a，a）∨F（a，b））∧（F（b，a）∨F（b，b））或（F（a，a）∧F（b，a））∨（F（a，b）∧F（b，b））7.78.DBKHLEAFICGMJN9.2mn10.{f1,f2}，{f1,f2}f3={f3,f5},{f1,f2}f4={f4,f6}.11.2个12.{(1234),(13)(24),(1432),(1)}13.N，N×N×N14.21人15.(,)xyFxy三、证明（8分）在自然推理系统F中构造下面推理的证明前提：()(()())xFxyGyHy，()()xRxyGy结论：(()())()xFxRxxHx证明：(1)(()())xFxRx附加前提引入(2)()()FcRc(1)EI（1分）(3)()Fc(2)化简(4)()Rc(2)化简(5)()(()())xFxyGyHy前提引入(6)()xFx(3)EG（1分）(7)(()())yGyHy(5)(6)假言推理（1分）(8)()()xRxyGy前提引入(9)()xRx(4)EG（1分）(10)()yGy(8)(9)假言推理（1分）(11)()Gd(10)EI（1分）(12)()()GdHd(7)UI（1分）(13)()Hd(11)(12)假言推理（1分）(14)()xHx(13)EG四、试证：一个有限非交换群至少含有6个元（8分）证明：由拉格朗日定理的推论知，1，2，3，5阶群都是循环群，从而是可交换的。（4分）若G为4阶群，除单位元e外，G的元素的阶或为2或为4。只有两种可能。(1)G中存在一个阶为4的元素a。此时必有G=a，是由a生成的循环群，由上一步的讨论知G是可交换的。（2分）(2)若G中不存在阶为4的元素，由拉格朗日定理的推论知，除e外，G的所有元素的阶为2。设G={e,a,b,c}。则222abce。由于aba，abb（反之有a或b等于e），且abe，所以必有abc。同理，bac，accab，bccba。也是可交换的。（2分）故非交换群至少有6个元素。五、设A={a,b,c}，求出A上所有的等价关系。（10分）解先求出A上有多少个不同的分划。分成一个分划块的分划1{{,,}}abc分成两个分划块的分划2{{},{,}}abc、3{{},{,}}bac、4{{},{,}}cab分成三个分划块的分划5{{},{},{}}abc因此，A上有5个不同的分划（5分），记与分划i相对应的等价关系为i1{(,),(,),(,),(,),(,),(,),(,),(,),(,)}AaaabacbabbbccacbccU2{(,),(,),(,),(,),(,)}aabbbccbcc3{(,),(,),(,),(,),(,)}bbaaaccacc4{(,),(,),(,),(,),(,)}ccaaabbabb5{(,),(,),(,)}AaabbccI（5分）六、对下图所示无向带权图G求一棵最小生成树T，并计算出T的权W(T)。（6分）12357442113333442456823解：按Kruskal算法，细心的寻找在最小生成树中的边，所得最小生成树如下图所示（4分），W(T)＝31。（2分）1234211333242七、设:fAB为单射函数，:()()GPAPB，()GX为X在f下的像。证明G也是单射的。（4分）证明：假设12,()AAPA，且12AA。（1分）不妨设存在12xAxA，因此1()()fxfA且2()()fxfA，于是12()()fAfA，（2分）从而12()()GAGA。（1分）八、求当连通平面图的每个面至少有5条边围成时，边数与结点数所满足的关系式（4分）解：设平面图G有n个结点，m条边和r个面，则欧拉公式为：n－m+r＝2。（1分）因图中每个面至少有5条边围成，所以有25mr，即25rm，（2分）代入欧拉公式化简后得：5103nm（1分）即为所求。