2002年4月离散数学试题答案

《2002年4月离散数学试题答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2002年4月离散数学试题答案课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)1.B2.D3.A4.A5.D6.D7.D8.C9.D10.B11.A12.A13.C14.B15.C二、填空题16.0117.1018.单位元119.x∩yx∪y20.入射满射21.［x］R=［y］R22.A(x)B(y)23.(M(x)→D(x))M(x)→D(x)24.可满足式永假式(或矛盾式)25.陈述句真值三、计算题26.M=M2=G中长度为2的路总数为18，长度为2的回路总数为6。27.当n是偶数时，x∈P

2、(A),xn=当n是奇数时，x∈P(A),xn=x于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n=(｛a｝-1)n｛b｝n｛a｝n=当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n=｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝=28.(1)偏序关系R的哈斯图为3(2)B的最大元：无，最小元：无；极大元：2，5，极小元：1，3下界：4，下确界4；上界：无，上确界：无29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(

3、P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命题为真的赋值是P=1,Q=0和P=1,Q=130.令e1=(v1,v3),e2=(v4,v6)e3=(v2,v5),e4=(v3,v6)e5=(v2,v3),e6=(v1,v2)e7=(v1,v4),e8=(v4,v3)e9=(v3,v5),e10=(v5,v6)令ai为

4、ei上的权，则a1

5、x+y-1条边，由握手定理知T中所有顶点的度数之的=2(x+y-1)。又树叶的度为1，任一分支点的度大于等于2且度最大的顶点必是分支点，于是3≥x·1+2(y-2)+k+k=x+2y+2K-4从而2(x+y-1)≥x+2y+2k-4x≥2k-233.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可

6、结合的。(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元由此上知〈F，〉是群34.证明(x)(A(x)→B(x))x(┐A(x)∨B(x))(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨…∨(┐A(an)∨B(an)))(┐A(a1)∨A(a2)∨…∨┐A(an)∨(B(a1)∨B(a2)∨…∨(B(an))┐(A(a1)∧A(

7、a2)∧…∧A(an))∨(┐B(a1)∨B(a2)∨…∨(B(an))┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)五、应用题35.令p：他是计算机系本科生q：他是计算机系研究生r：他学过DELPHI语言s:他学过C++语言t:他会编程序前提：(p∨q)→(r∧s),(r∨s)→t结论：p→t证①pP(附加前提)②p∨qT①I③(p∨q)→(r∧s)P(前提引入)④r∧sT②③I⑤rT④I⑥r∨sT⑤I⑦(r∨s)→tP(前提引入)⑧tT⑤⑥I36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。根

8、据：构造无向简单图G=,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密