离散数学期末试卷(A)

XXXX大学XX学院2007～2008学年第一学期《离散数学》期末试卷（A）年级专业班级学号姓名____________题号一二三四总分得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题（共20小题，每小题1分，共20分）1．下列语句中只有不是命题。CA．今年元旦会下雪。B．1+1=10。C．嫦娥一号太棒了！D．嫦娥奔月的神话已成为现实。2．pq的主合取范式是。BA．(pq)(pq)B．(pq)(pq)C．(pq)(pq)D．(pq)(pq)3．与pq等值的命题公式是。DA．pqB．pqC．pqD．pq4．在一阶逻辑中使用的量词只有个。BA．1B．2C．3D．45．xA(x)。CA．xA(x)B．xA(x)C．xA(x)D．xA(x)6．若|A|=4，则|P(A)|=。CA．4B．8C．16D．647．设A、B、C为任意集合，集合的对称差运算不具有的性质是。DA．AB=BAB．(AB)C=B(AC)C．AA=D．AA=A8．二元关系是。BA．两个集合的笛卡儿积B．序偶的集合C．映射的集合D．以上都不是9．下面关于函数的叙述中正确的是。DA．函数一定是满射B．函数一定是单射C．函数不是满射就单射D．函数是特殊的关系10．半群中的二元运算一定满足=。BA．交换律B．结合律C．分配律D．幂等律11．环中有个二元运算。BA．一B．二C．三D．四12．群与独异点的区别是。CA．满足交换律B．满足结合律C．每个元素都有逆元D．满足分配律13．九阶轮图的点色数是。BA．2B．3C．4D．914．设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，＋表示数的加法，则下面的代数系统中，不是群。AA．N，＋B．Q，＋C．Z，＋D．R，＋15．简单通路是没有的通路。AA．重复边B．重复顶点C．平行边D．环16．设个体域为N（非负整数集），下列公式为真的是。BA．yx(xy=1)B．yx(xy=x)C．xy(x+y=0)D．xy(xy)17．非平凡树一定是。BA．正则图B．二部图C．欧拉图D．哈密顿图18．环R，+，中的运算只要求满足。BA．交换律B．结合律C．分配律D．幂等律19．集合A上的等价关系与一一对应。BA．集合A的子集B．集合A的划分C．集合A到A的双射D．集合A与A的单射20．全序关系一定不是。AA．等价关系B．偏序关系C．线序关系D．整除关系二、填空题（共10题，每题2分，共20分）11．设S(x)：x是计算机学院的学生。L(x)：x学离散数学。则“计算机学院的学生都要学离散数学。”可符号化为：__x(S(x)L(x))_____________________________________。12．设A={a,b,c}，A上的等价关系R={a,b,b,a}IA，则商集A/R=____{{a,b},{c}}13．设B={}，则幂集P(B)=___________{,{}}。14．xA(x)yB(x,y)的前束范式是____．uv(A(u)B(x,v))或xy(A(x)B(u,y))15．设集合A={0，1}，则A上可定义的二元运算有____16_______个。16．设A={1，2，3，4}，A上关系R={1,3,3,1,4,1}IA，则t(R)=__{1,3,3,1,4,1,4,3}IA17．设函数f：NN，f=x-1，函数h：NN，h(x)=x2+1，则复合函数fh(x)=_______(x-1)2+118．完全二部图Kr,s（rs）的最大度(Kr,s)=______S____，最小度(Kr,s)=_____r___。19．设一棵树有4个2度顶点，3个3度顶点，其余顶点都是1度顶点，则该树有_______5___片树叶。20．命题公式(p(pq))的成假赋值是__00，01，10，11三、运算题（共5小题，每小题8分，共40分）21．求命题公式(pq)(qr)的主析取范式，并指出其类型。解：(pq)(qr)(pq)(qr)(pr)q(p(qq)r)((pp)q(rr))(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)该公式是可满足式22．设A={a,b,c,d,e,f}，A上的偏序关系：R={a,b,a,d,a,c,a,f,a,e,b,d,b,e,c,e,c,f}IA画出该偏序关系的哈斯图，并求A的极大元、极小元、最大元和最小元。解：极大元为d、e、f；极小元为a；无最大元；最小元为a23．设个体域D={a,b,c}，消去一阶公式x（F(x)yG(y)）中的量词，并在下述解释下求其真值：F(a)=F(b)=1,F(c)=0，G(a)=1，G(b)=G(c)=0。解：x（F(x)yG(y)）xF(x)yG(y)（F(a)F(b)F(c)）（G(a)G(b)G(c)）（110）（100）11124．画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W(T)。解：W(T)=7125．设Z为整数集合，V=Z,*，*是二元运算，定义为：x*y=x+y-xy说明V是含幺半群而不是群。解：（1）*运算在Z上封闭：（2）*运算可结合，对任意a、b、cZa*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-ac-bc+abc(a*b)*c=(a+b-ab)*c=a+b-ab+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc所以a*(b*c)=(a*b)*c（3）*运算的幺元是0（4）任意xZ，x*1=1*x=1，所以1是零元，它没有逆元。由上述可知，故Z,*是含幺半群而不是群。四、证明题（共3小题，共20分）26（10分）．在一阶逻辑中构造下面推理的证明：前提：x(F(x)G(x))，x(G(x)R(x))，xR(x)结论：xF(x)（10分）证:①xR(x)前提引入②R(c)①EI③x(G(x)R(x))前提引入④G(c)R(c)③UI⑤G(c)②④析取三段论⑥x(F(x)G(x))前提引入⑦F(c)G(c)⑥UI⑧F(c)⑤⑦拒取式⑨xF(x)⑧EG27（5分）．证明，若非空集合A上的关系R和S是反对称的，则RS也是反对称的。证:任取x,y，x≠yx,yRSx,yRx,ySy,xRy,xSy,xRS。故RS是对称的。28（5分）．若无向图G中恰有两个奇度顶点，证明这两个奇度顶点必连通。证:用反证法。假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。2007～2008学年第一学期《离散数学》期末试卷（A）答案适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题（共20小题，每小题1分，共20分）1C2B3D4B5C6C7D8B9D10B11B12C13B14A15A16B17B18B19B20A二、填空题（共10题，每题2分，共20分）11．x(S(x)L(x))12．{{a,b},{c}}13．{,{}}14．uv(A(u)B(x,v))或xy(A(x)B(u,y))15．1616．{1,3,3,1,4,1,4,3}IA17．(x-1)2+118．s,r19．520．00，01，10，11三、运算题（共5小题，每小题8分，共40分）21．解：(pq)(qr)(pq)(qr)(pr)q(p(qq)r)((pp)q(rr))(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)该公式是可满足式22．解：极大元为d、e、f；极小元为a；无最大元；最小元为a23．解：x（F(x)yG(y)）xF(x)yG(y)（F(a)F(b)F(c)）（G(a)G(b)G(c)）（110）（100）11124．解：W(T)=7125．解：（1）*运算在Z上封闭：（2）*运算可结合，对任意a、b、cZa*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-ac-bc+abc(a*b)*c=(a+b-ab)*c=a+b-ab+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc所以a*(b*c)=(a*b)*c（3）*运算的幺元是0（4）任意xZ，x*1=1*x=1，所以1是零元，它没有逆元。由上述可知，故Z,*是含幺半群而不是群。四、证明题（共3小题，共20分）26（10分）证:①xR(x)前提引入②R(c)①EI③x(G(x)R(x))前提引入④G(c)R(c)③UI⑤G(c)②④析取三段论⑥x(F(x)G(x))前提引入⑦F(c)G(c)⑥UI⑧F(c)⑤⑦拒取式⑨xF(x)⑧EG27（5分）证:任取x,y，x≠yx,yRSx,yRx,ySy,xRy,xSy,xRS。故RS是对称的。28（5分）证:用反证法。假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。