离散数学自学考试真题附答案.doc

全国2002年4月离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路 B.欧拉回路C.汉密尔顿通路 D.初级回路2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A.10 B.12 C.16 D.143.在布尔代数L中，表达式(ab)(abc)(bc)的等价式是( )A.b(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)4.设i是虚数，是复数乘法运算，则G=是群，下列是G的子群是( )A. B.-1, C.i, D.-i,5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，为集合的交运算，下列系统中是代数系统的有( )A.Z，+，/ B.Z，/C.Z，-，/ D.P(A)，6.下列各代数系统中不含有零元素的是( )A.Q，*Q是全体有理数集，*是数的乘法运算B.Mn(R),*,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C.Z，Z是整数集，定义为xxy=xy,x,yZD.Z，+，Z是整数集，+是数的加法运算7.设A=1,2,3，A上二元关系R的关系图如下：R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A=a,b,c，A上二元关系R=a,a，b,b,a,c，则关系R的对称闭包S(R)是( )A.RIA B.R C.Rc,a D.RIA9.设X=a,b,c,Ix是X上恒等关系，要使Ixa,b，b,c，c,a，b,aR为X上的等价关系，R应取( )A.c,a，a,c B.c,b，b,aC.c,a，b,a D.a,c，c,b10.下列式子正确的是( )A. B. C. D.11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):xy.下列公式在R下为真的是( )A.( x)( y)( z)(A(x,y)A(f(x,z),f(y,z)B.( x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x)D.(x)(y)(A(x,y)A(f(x,a),a)12.设B是不含变元x的公式，谓词公式(x)(A(x)B)等价于( )A.(x)A(x)B B.(x)A(x)BC.A(x)B D.(x)A(x)(x)B13.谓词公式(x)(P(x,y)(z)Q(x,z)(y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )A.PQ B.PQ C.PQ D.PQ15.以下命题公式中，为永假式的是( )A.p(pqr) B.(pp)pC.(qq)p D.(qp)(pp)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为_，称为树根，其余结点的入度均为_。17.A=1,2,3,4上二元关系R=2，4，3，3，4，2，R的关系矩阵MR中m24=_,m34=_。18.设s,*是群，则那么s中除_外，不可能有别的幂等元；若s,*有零元，则|s|=_。19.设A为集合，P(A)为A的幂集，则P(A)，是格，若x,yP(A),则x,y最大下界是_，最小上界是_。20.设函数f:XY,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是_函数，如果ranf=Y，则称f是_函数。21.设R为非空集合A上的等价关系，其等价类记为xR。x,yA，若x,yR，则xR与yR的关系是_，而若x,yR，则xRyR=_。22.使公式(x)( y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x。23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)_,其中量词(x)的辖域是_。24.若H1H2Hn是_，则称H1,H2,Hn是相容的，若H1H2Hn是_，则称H1,H2,Hn是不相容的。25.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的 。三、计算题 (共30分)26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。27.(5)设A=a,b,P(A)是A的幂集，是对称差运算，可以验证是群。设n是正整数，求(a-1ba)na-nbnan28.(6分)设A=1,2,3,4,5,A上偏序关系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序关系R的哈斯图(2)令B=1,2,3,5，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6分)求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。31.(4分)求公式(x)F(x,y)(y)G(x,y)(x)H(x)的前束范式。四、证明题 (共20分)32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k2),证明T中至少有2k-2片树叶。33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。 证明：F, 是群。34.(6分)在个体域D=a1,a2,，an中证明等价式： (x)(A(x)B(x)(x)A(x)(x)B(x)五、应用题(共15分)35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C+语言。只要他学过DELPHI语言或者C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?答案：一、单项选择题(本大题共15小题，每小题1分，共15分) 1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C二、填空题16.0 117.1 018.单位元 119.xy xy20.入射 满射21.xR=yR 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是偶数时，xP(A),xn= 当n是奇数时，xP(A),xn=x 于是：当n是偶数，(a-1ba)na-nbnan =(a-1)nbnan= 当n是奇数时， (a-1ba)na-nbnan =a-1ba(a-1)nbnan =a-1baa-1ba=28.(1)偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4， 下确界4； 上界：无，上确界：无29.原式(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (PQPQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) P(QQ) P(QQ) (PQ)(PQ) 命题为真的赋值是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为ei上的权，则 a1a2a3a4a5=a6=a7=a8a9=a10 取a1的e1T,a2的e2T,a3的e3T,a4的e4T,a5的e5T,即， T的总权和=1+2+3+4+5=1531.原式(x1F(x1,y)y1G(x,y1)x2H(x2) (换名) x1y1(F(x1,y)G(x,y1)x2H(x2) x1y1(F(x1,y1)G(x,y1)x2H(x2) x1y1x2(F(x1,y1)G(x,y1)H(x2) 四、证明题32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的 =2(x+y-1)。 又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是 x1+2(y-2)+k+k=x+2y+2K-4 从而2(x+y-1)x+2y+2k-4 x2k-233.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空 (1)f,gF,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。 (2)f,g,hF,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。 (3)A上的恒等函数IA也是A到A的双射函数即IAF,且fF有IAf=fIA=f,故IA是F，中的幺元 (4)fF,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=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(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:他会编程序 前提：(pq)(rs),(rs)t 结论：pt 证 p P(附加前提) pq TI (pq)(rs) P(前提引入) rs TI r TI rs TI (rs)t P(前提引入) t TI36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。 根据：构造无向简单图G=,其中V=v1,v2,，V20是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。 ViV,d(vi)是与vi相互认识的人的数目，由题意知vi,vjV有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。 设C=Vi1Vi2Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。全国2004年4月高等教育自学考试离散数学试题课程代码：02324第一部分 选择题 （共15分）一、单项选择题（本大题共15小题，每小题1分，共15分）1下列是两个命题变元p，q的小项是（ ）AppqBpqCpqDppq2令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）ApqBpqCpqDpq3下列语句中是命题的只有（ ）A1+1=10Bx+y=10Csinx+siny0Dx mod 3=24下列等值式不正确的是（ ）A(x)A(x)AB(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5谓词公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z)中量词x的辖域是（ ）A(x)Q(x,z)(x)(y)R(x,y,z)BQ(x,z)(y)R(x,y,z)CQ(x,z)(x)(y)R(x,y,z)DQ(x,z)6设R为实数集，函数f：RR，f(x)=2x，则f是（ ）A满射函数B入射函数C双射函数D非入射非满射7设A=a,b,c,d，A上的等价关系R=,IA，则对应于R的A的划分是（ ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d8设A=，B=P(P(A)，以下正确的式子是（ ）A,BB,BC,BD,B9设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ ）A(X-Y)-Z=X-(YZ)B(X-Y)-Z=(X-Z)-YC(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)10设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ）A有x*Z=Z*x=ZBZA，且有x*Z=Z*x=ZCZA，且有x*Z=Z*x=xDZA，且有x*Z=Z*x=Z11在自然数集N上，下列定义的运算中不可结合的只有（ ）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公约数)Da*b=a(mod b)12设R为实数集，R+=x|xRx0，*是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）AR+中的有理数BR+中的无理数CR+中的自然数D1，2，313设是环，则下列正确的是（ ）A是交换群B是加法群C对*是可分配的D*对是可分配的14下列各图不是欧拉图的是（ ）15设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）A2个面B3个面C4个面D5个面第二部分 非选择题（共85分）二、填空题（本大题共10小题，每空1分，共20分）16一公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。17前束范式具有形式(Q1V1)(Q2V2)(QnVn)A，其中Qi(1in)为 ，A为 的谓词公式。18设论域是a,b,c，则(x)S(x)等价于命题公式 ；()S(x)等价于命题公式 。19设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。20某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是 。21设是一个偏序集，如果S中的任意两个元素都有 和 ，则称S关于构成一个格。22设Z是整数集，在Z上定义二元运算*为a*b=a+b+ab，其中+和是数的加法和乘法，则代数系统的幺元是 ，零元是 。23如下平面图有2个面R1和R2，其中deg(R1)= ，deg(R2)= 。24无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。25在下图中，结点v2的度数是 ，结点v5的度数是 。三、计算题（本大题共6小题，第2627小题每小题4分，第28、30小题每小题5分，第29、31小题每小题6分，共30分）26（4分）求出从A=1,2到B=x,y的所有函数，并指出哪些是双射函数，哪些是满射函数。27（4分）如果论域是集合a,b,c，试消去给定公式中的量词：。28（5分）设A=a,b,c ，P（A）是A的幂集，是集合对称差运算。已知是群。在群中，找出其幺元。找出任一元素的逆元。求元素x使满足ax=b。29（6分）用等值演算法求公式(pq)(pq)的主合取范式30（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。31（6分）在偏序集中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除关系，求集合D=2,3,4,6的极大元，极小元，最大元，最小元，最小上界和最大下界。四、证明题（本大题共3小题，第3233小题每小题6分，第34小题8分，共20分）32（6分）用等值演算法证明(qs)r)(s(pr)(s(pq)r33（6分）设n阶无向树G=中有m条边，证明m=n-1。34（8分）设P=,1,1,2,1,2,3，是集合P上的包含关系。（1）证明：是偏序集。（2）在（1）的基础上证明是全序集五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）35（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）36（6分）设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论方法安排园桌座位，使每人都能与其身边的人交谈。. .全国2005年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列各图是平面图的是( ) 2.设G是n个顶点的无向简单图，则下列说法不正确的是 )A.若G是树，则其边数等于n-1B.若G是欧拉图，则G中必有割边C.若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D.若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路3.格L是分配格的充要条件是L不含与下面哪一个选项同构的子格( )A.链B.钻石格C.五角格D.五角格与钻石格4.设是有限循环群，则下列说法不正确的是( )A.的生成元是唯一的B.有限循环群中的运算*适合交换律C.G中存在一元素a，使G中任一元素都由a的幂组成D.设a是的生成元，则对任一正整数i，存在正整数j使a-i=aj5.在实数集合R上，下列定义的运算中是可结合的只有( )A.a*b=a+2bB.a*b=a+b-2abC.a*b=a-b+2abD.a*b=a-b-2ab6.设群G=中,A的元素个数大于1，若元素aA的逆元素为bA，则a*b的运算结果是( )A.aB.bC.G中零元素D.G中幺元7.非空集合A上的二元关系R若是自反和对称的，则R是( )A.偏序关系B.等价关系C.相容关系D.拟序关系8.下面的图是A=1,2,3上关系R的关系图G(R),从G(R)可判断R所具有的性质是( )1。2。 3。A.自反，对称，传递B.反自反，非对称C.反自反，对称，非传递D.反自反，对称，反对称，传递9.设A=1，2，3，B=a,b，下列二元关系R为A到B的函数的是( )A.R=,B.R=,C.R=,D.R=,10.设为空集，P(x)是集合x的幂集，下列论断不正确的是( )A. P(), P()B.P（），P（）C. P（P（），P（P（）D.P（P（）,P（P（）11.利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：改写成( )A. B. C. D. 12.设论域为整数集，下列谓词公式中真值为假的是( )A.B. C. D. 13.在命题演算中，语句为真为假的一种性质称为( )A.真值B.陈述句C.命题D.谓词14.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( )A.B. C. D. 15.下列命题公式是永真式的是( )A. qB.C. D.二、填空题(本大题共10小题，每空1分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.一棵有6个叶结点的完全二叉树，有_个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_个叶结点。17.在一棵根树中，有且只有一个结点的入度为_，其余所有结点的入度均为_。18.设是格，其中一个命题P是a(ab) (ac),则P的对偶命题是a_(ab)_(ac)。19.设Z是整数集，+是整数加法运算，则是群，其幺元是_，对任一整数i,其逆元是_。20.当f:XY是_函数时，f有逆函数，且f -1。f=_。21.设E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4,则(AB)C=_,幂集P(AB)C)=_。22.设论域D=a,b,则(x)P(x)_,(x)(y)Q(x,y)_。23.使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x。24.由命题变元及其否定所组成的有限个析取式的合取式称为_，由命题变元及其否定所组成的有限个合取式的析取式称为_。25.不包含_的命题叫做原子命题，包含_的命题称为复合命题。三、计算题(本大题共7小题，第26、28小题每小题5分，第27、31小题每小题7分，第29、30小题每小题8分，第32小题9分，共49分)26.用等值演算法，求P(QR)的主析取范式，并按P，Q，R顺序，写成编码形式。27.设A=1,2,3，给定A上二元关系R=,，求r(R),s(R)和t(R)。28.求公式的前束范式。29.对如下有向图D，求D中长度为4的路有多少条?其中回路有多少条?30.设A=a,abc,bc,bcd,bd，定义A上二元关系R=|x,yA且字符串x包含于字符串y中，即R=IA,，可以验证R是A上偏序关系。作出R的哈斯图向R中最少添加几个序偶可使之成为等价关系?求出该等价关系所确定的集合A的划分。31.某科研所要从3个项目A、B、C中选择12个项目上马，由于某种原因，立项时要满足以下条件：(1)若A上，则C也要上；(2)若B上，则C不能上；(3)若C不上，则A或B可以上。请找出所有的立项方案32.设有6个城市V1，V2，V6，它们之间有输油管连通，其布置如下图(a),Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的矩离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守管道的最短的总长度。(要求写出求解过程)四、证明题(本大题共2小题，每小题8分，共16分)33.证明(x) (P(x) Q(x)(x)P(x)(x)Q(x)34.证明当每个结点的度数大于等于3时，不存在有7条边的连通简单平面图。全国2006年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列命题公式为重言式的是（ ）Ap (pq)B(pp)qCqqDpq2下列语句中不是命题的只有（ ）A这个语句是假的。B1+1=1.0C飞碟来自地球外的星球。D凡石头都可练成金。3设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ ）ApqBpqCpqDpq4下列等价式正确的是（ ）AABCAD5在公式中变元y是（ ）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自由变元，又不是约束变元6设A=1，2，3，A上二元关系S=，则S是（ ）A自反关系B反自反关系C对称关系D传递关系7设集合X为人的全体，在X上定义关系R、S为R=a，b|a，bXa是b的父亲，S=|a，bXa是b的母亲，那么关系|a，bx a是b的祖母的表达式为（ ）ARSBR-1SCSRDRS-18设A是正整数集，R=(x，y)|x，yAx+3y=12，则R (2，3，4，62，3，4，6)=（ ）A O/BC，D，9下列式子不正确的是（ ）A(A-B)-C=(A-C)-BB(A-B)-C=A-(BC)C(A-B)-C=(A-C)-(B-C)DA-(BC)=(A-B) C10下列命题正确的是（ ）Al，21，2，l，2，3，1B1，21，l，2，l，2，3，2C1，21，2，1，2D1，21，2，2，l，2，311在下列代数系统中，不是环的只有（ ）AZ，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。B(Q，+，*)，其中Q为有理数集，+，*分别为有理数加法和乘法。C，其中R为实数集，+为实数加法，a*b=a+2b。D，其中Mn(R)为实数集nn阶矩阵结合，+，*是矩阵加法和乘法。12下列整数集对于整除关系都构成偏序集，而能构成格的是（ ）Al，2，3，4，5B1，2，3，6，12C2，3，7Dl，2，3，713结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ）A欧拉图B汉密尔顿图C非平面图D不存在的14无向图G是欧拉图当且仅当G是连通的且（ ）AG中各顶点的度数均相等BG中各顶点的度数之和为偶数CG中各顶点的度数均为偶数DG中各顶点的度数均为奇数15平面图(如下)的三个面的次数分别是（）A11，3，4 B11，3，5C12，3，6 D10，4，3二、填空题（本大题共10小题，每小题2分，共20分）16求一个公式的主析取或主合取范式的方法，有_法和_法。17给定谓词合式公式A，其中一部分公式形式为()B(x)或(x)B(x)，则量词，后面所跟的x称为_，而称B为相应量词的_。18设X，U，V，Y都是实数集，f1：XU，且fl(x)ex； f2：UV，且f2(u)u (1+u)；f3：VY，且f3(v)=cosv。那么f3f2f1的定义域是_，而复合函数(f3f2f1)(x)= _。19集合X=a，b，c，d上二元关系R=， ，则R的自反闭包r(R)= _，对称闭包s(R)= _。20已知G=(其中i=，是数的乘法)是群，则-l的阶是_；i的阶是_。21对代数系统，其中*是S上的二元运算，若a，bS，且对任意的xS，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的_，称b为运算“*”的_。22设是群，则满足结合律和_；若Sl，S中不可能有_。23写出如右有向图的一条初级回路：_，其长度是_。24一个_且_的无向图称为树。25在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_，如果V有n个结点，那么它还是_度正则图。三、计算题(本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分)26若集合A=a，b，c的幂集为P(A)，集合B= O/， O/ 的幂集为P(B)，求P(A)P(B)。27构造命题公式(p (q r)p的真值表。28求图G的可达矩阵，其中Vv1,v2,v3,v4E(v1,v2), (v2,v3), (v2,v4), (v3,v2), (v3,v4), (v3,v1), (v4,v1)29求下列公式的主析取范式和主合取范式：（PQ）（PR）30设A2，3，4，6，8，12，24，R为A上整除关系，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。四、证明题（本大题共3小题，第31、32小题各6分，第33题8分，共20分）31设M是偶数集，和是数的加、乘运算，证明是一个环。32设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。33设G是简单平面图，G有n个顶点m条边，且m30，证明G中存在一项点v，d（v）4。五、应用题（本大题共2小题，第34题6分，第35题9分，共15分）34判断下面推理是否正确，并证明你的结论。如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。35有6个村庄Vi，i=l，2，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。全国2007年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列命题公式中不是重言式的是（）Ap(qr) Bp(qp)Cp(pp)D(p(qr)(q(pr)2下列语句中为命题的是（）A这朵花是谁的？B这朵花真美丽啊！C这朵花是你的吗？D这朵花是他的。3设个体域是整数集，则下列命题的真值为真的是（）Ayx(xy=1)Bxy (xy0)Cxy (xy=y2)Dyx(xy=x2)4关于谓词公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中错误的是（）A（x）的辖域是（y）（P（x,y）Q(y,z)）Bz是该谓词公式的约束变元C（x）的辖域是P（x,y）Dx是该谓词公式的约束变元5设论域D=a,b，与公式xA（x）等价的命题公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）6集合A=1，2，3上的下列关系矩阵中符合等价关系条件的是（）A BC D7设A=，B=P（P（A），以下不正确的式子是（）A ， ， ， 包含于BB 包含于BC ， 包括于BD ， ， 包含于B8设Z是整数集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，则f（）A仅是满射 B仅是入射C是双射 D无逆函数9设A=1，2，3，4，5，A上二元关系R=1，2，3，4，2，2，S=2，4，3，1，4，2，则S-1R-1的运算结果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，410设有代数系统G=A，*，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A矛盾式 B重言式C可满足式D公式pq11在实数集合R上，下列定义的运算中不可结合的是（）Aa*b=a+b+2abBa*b=a+bCa*b=a+b+abDa*b=a-b12下列集合关于所给定的运算成为群的是（）A已给实数a的正整数次幂的全体，且a0，1，-1，关于数的乘法B所有非负整数的集合，关于数的加法C所有正有理数的集合，关于数的乘法D实数集，关于数的除法13设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A3 B4C5 D614下列各图中既是欧拉图，又是汉密尔顿图的是（）A B C D15设无向图