20062010自学考试离散数学试题汇编

1、全国2006年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列命题公式为重言式的是（ ）Ap (pq)B(pp)qCqqDpq2下列语句中不是命题的只有（ ）C飞碟来自地球外的星球。D凡石头都可练成金。3设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是ApqBpqCpqDpq4下列等价式正确的是（ ）AABCAD5在公式中变元y是（ ）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自

2、由变元，又不是约束变元6设A=1，2，3，A上二元关系S=<1，1>，<1，2>，<3，2>，<3，3>，则S是（ ）A自反关系B反自反关系C对称关系D传递关系7设集合X为人的全体，在X上定义关系R、S为R=<a，b|a，bXa是b的父亲，S=<a，b>|a，bXa是b的母亲，那么关系<a，b>|a，bx a是b的祖母的表达式为（ ）ARSBR-1SCSRDRS-18设A是正整数集，R=(x，y)|x，yAx+3y=12，则R (2，3，4，6×2，3，4，6)=（ ）AO/B<3，3>C<

3、;3，3>，<6，2>D<3，3>，<6，2>，<9，1>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在下列代数系统中，不是环的只有（ ）A<Z，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。B(Q，+，*)，其中Q为有理数集，+，*分别为有理数加法和乘法。C<R，

4、+，*>，其中R为实数集，+为实数加法，a*b=a+2b。D<Mn (R)，+，*>，其中Mn(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。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平面图(如下)的三个面的次数分别是（）

5、A11，3，4B11，3，5C12，3，6D10，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=<a，

6、b>，<a，c>，<a，d>，<b，c>，<b，d>， <e，d>，则R的自反闭包r(R)= _，对称闭包s(R)= _。20已知G=<l，-1，i，-i，·>(其中i=，是数的乘法)是群，则-l的阶是_；i的阶是_。21对代数系统<S，*>，其中*是S上的二元运算，若a，bS，且对任意的xS，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的_，称b为运算“*”的_。22设<S，*>是群，则<S，*>满足结合律和_；若S>l，S中不可能有_。23写出

7、如右有向图的一条初级回路：_，其长度是_。24一个_且_的无向图称为树。25在简单无向图G=<V，E>中，如果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<V，E>的可达矩阵，其中Vv1,v2,v3,v4E(v1,v2), (v2,v3), (v2,v4), (v3,v2),

8、(v3,v4), (v3,v1), (v4,v1)29求下列公式的主析取范式和主合取范式：（PQ）（PR）30设A2，3，4，6，8，12，24，R为A上整除关系，试画<A，R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。四、证明题（本大题共3小题，第31、32小题各6分，第33题8分，共20分）31设M是偶数集，和·是数的加、乘运算，证明<M，·>是一个环。32设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。33设G是简单平面图，G有n个顶点m条边，且m<30，证明G中存在一项点v，d（v）4。五、应用题（本大题共2小题

9、，第34题6分，第35题9分，共15分）34判断下面推理是否正确，并证明你的结论。如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。35有6个村庄Vi，i=l，2，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。2006年7月全国自考离散数学试题试卷真题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小

10、题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列语句中不是命题的只有（）A鸡毛也能飞上天？B或重于泰山，或轻于鸿毛。C不经一事，不长一智。D牙好，胃口就好。2从真值角度看，命题公式的全部类型是（）A永真式B永假式C永真式，永假式D永真式，永假式，可满足式3设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）ABCD4下列公式是前束范式的是（）ABCD5设论域为整数集，下列真值为真的公式是（）A BCD6下列是谓词演算中的合式公式的是（）ABCD（ ）（）ABCD（）8下列式子正确的是（

11、）A（AB）-C=A-（BC）BA（BC）=（AB）CC（AB）=（BA）D（AB）A9下列集合对所给的运算是封闭的只有（）A非零整数集合Z*上的除法运算B全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算C全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算DA=1，2，10，x*y=LCM（x，y），即x，y最小公倍数10设<A，*>是环，则下列说法不正确的是（）A<A，>是交换群B<A， *>是半群C*对是可分配的D对*是可分配的11下列四个格，是分配格的是（）CD（）AB12下列各图是无向完全图的是（）13下列各有向图是强连

12、通图的是（）14设是具有n个结点的无向简单图，若在中存在一条汉密尔顿路，则中每一对结点的度数之和与n-1的关系为（）A大于B大于等于C等于D小于15设连通平面图，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）Ae-n+r=2Bn+r-e=2Cn-r+e=2Dn-e-r=2二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16所谓_是指不能再分解的命题，而复合命题是由一些_经过联结词复合而成的命题。17在命题演算中，两个_的合取、析取、条件、双条件均为_。18使公式成立的条件是_中不含y，_中不含x。19设A=1，2，3，4，R是A上

13、的二元关系，R=<x,y>|x/y是素数，则domR=_;ranR=_。20设无向图有n个结点m条边，每个结点的度数为k或k+1，记Nk为度数等于k的结点数，则Nk=_。如果无向简单图C的结点的度数均为相同的偶数，且m=7，则n=_。21设X=1，3，5，9，15，45，R是X上的整除关系，则R是X上的偏序，其最大元是_，极小元是_。22设<>是有界格，a,bL,若ab=0,则a=b=_；若ab=1,则a=b=_。23设e是群G上的幺元，若aG且a2=e,则a-1=_ ,a-2=_。24代数系统<A,。>，其中A为命题公式集合，。为析取运算，则<A，。

14、>中零元素是_，幺元是_。25树是不包含_的_图。三、计算题（本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分）26如果论域是集合a,b,c，试消去下面公式中的量词：27求公式（的主析取范式。28设A=a,b,c,A上二元关系R=<a,a>,<a,c>,<b,a>,用关系矩阵法求最小的自然数m,n,m<n使Rm=Rn。29根据下列条件如果能画则请画出一个欧拉图，如果不能画则请说明理由。（1）偶数个顶点，偶数条边（2）奇数个顶点，奇数条边（3）偶数个顶点，奇数条边（4）奇数个顶点，偶数条边30下列各整数集合

15、对于整除关系“|”都构成偏序集，判断哪些偏序集能构成格？并说明理由。1)L=1,2,3,4,52) L=1,2,3,6,123)L=1,2,3,4,6,9,12,18,364)L=1,2,22,23,2n31设A=2，3，5，12，19，等价关系R=<x,y>|x,(mod 3),写出各元素的等价类，并求A/R。四、证明题（本大题共3小题，第32、33题各6分，第34题8分，共20分）32用等价变换法证明：是永真式。33若无向图G是欧拉图，G中是否存在割边？为什么？34设A是一个集合，X=P（A），R是X上元素之间的包含关系，试证明<X,R>是偏序集。（注：P（A）为A

16、的幂集）五、应用题（本大题共2小题，第35题6分，第36题9分，共15分）35设有n个村庄要修路，（1）若要使所有村庄之间都有通路，问需在两村之间至少修几条路？（2）若要使任意两村庄之间有一条直接的路，则至少修几个路？（3）若修一条连接所有村庄的环路，问有多少种修路方案？36设有推理：(a)没有不守信用的人是可信赖的；(b)有些可以信赖的人是受过教育的人；(c)因此有些受过教育的人是守信用的。试构造推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推理过程。（个体域：人的集合）提示：设F（x）表示x是守信用的人；G（x）表示x是可信赖的人；H（x）表示x是受过教育的人。全国2007年4

17、月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列命题公式中不是重言式的是（）Ap(qr)Bp(qp)Cp(pp)D(p(qr)(q(pr)2下列语句中为命题的是（）A这朵花是谁的？B这朵花真美丽啊！C这朵花是你的吗？D这朵花是他的。3设个体域是整数集，则下列命题的真值为真的是（）Ayx(x·y=1)Bxy (x·y0)Cxy (x·y=y2)Dyx(x·y=x2)4关于谓词公式（x）(y

18、)(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上的下列关系矩阵中符合等价关系条件的是（）ABCD7设A=Ø，B=P（P（A），以下不正确的式子是（）AØ ，Ø ，Ø，Ø 包含于BBØ 包含于BCØ，Ø 包括于BD&#

19、216; ，Ø，Ø 包含于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

20、*b=a+bCa*b=a+b+abDa*b=a-b12下列集合关于所给定的运算成为群的是（）A已给实数a的正整数次幂的全体，且a0，1，-1，关于数的乘法B所有非负整数的集合，关于数的加法C所有正有理数的集合，关于数的乘法D实数集，关于数的除法13设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A3B4C5D614下列各图中既是欧拉图，又是汉密尔顿图的是（）A B C D15设无向图G的边数为m，结点数为n，则G是树等价于（）AG连通且m=n+1BG连通且n=m+1CG连通且m=2nD每对结点之间至少有一条通路二、填空题（本大题共10小题，每小题2分，共2

21、0分）请在每小题的空格中填上正确答案。错填、不填均无分。16不能再分解的命题称为_，至少包含一个联结词的命题称为_。17在命题演算中，五个联结词的含义是由其_表唯一确定的，而不是由其类似的_语言的含义确定。18使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的条件是_不含有y，_不含有x。19设A为任意集合，请填入适当的运算符，使式子A_A=Ø；A_A=Ø成立。20设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，则domR=_，ranR=_。21称集合S是给定非空集合A的覆盖：若S=S1，S2，Sn，其中SiA，SiØ

22、，i=1，2，n，且_；进一步若_，则S是集合A的划分。22对实数的普通加法和乘法，_是加法的幂等元，_是乘法的幂等元。23在代数系统A，*中，A=a，*是A上二元运算，则该代数系统的单位元是_，零元是_。24设A，是偏序集，若A中_都有最小上界和_则称A关于偏序构成格。25若一条路中，所有边均不相同，则此路称作_；若一条路中所有的结点均不相同，则称此路为_。三、计算题（本大题共6小题，第26、27小题各4分，第28、29小题各5分，第30、31小题各6分，共30分）36试画出结点数为3的（1）强连通图；（2）单向连通图；（3）弱连通图；（4）非连通图。27设A=0，1，2，3，R=x,y|x

23、,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。试求RSR28在全体正整数集合Z+中规定，为：对任意的a,bZ+，ab=a,b，即求a,b的最小公倍数；ab=(a,b)，即求a,b的最大公约数；则运算，满足结合律，交换律和吸收律，于是Z+，是一个格。判断下列集合是否是<Z+，>的子格？1）A=1，2，3，9，12，722）A=1，2，3，12，183）A=5，52，53，5n4）T=2Z+=2k|kZ+29求命题公式（pq）（qp）的主析取范式。30结出命题公式（p(pq)）(pq)q)的二叉树表示。31设A=a,b,c,d, R=a,c，c,b，b,a，a,d，求R

24、，r(R),s(R),t(R)的关系图。四、证明题（本大题共3小题，第32、33小题各6分，第34小题8分，共20分）32设A是非空集合，P（A）是A的幂集，是集合的包含关系，则P（A），是格，证明：P（A），是有补格。33设a,b,*是半群，其中a*a=b，证明：（1）a*b=b*a；（2）b*b=b。34若一棵树恰有2个结点的度数为1，则它必是一条欧拉路。五、应用题（本大题共2小题，第35小题6分，第36小题9分，共15分）35设I是整数集，<，>，是上的二元关系，分别表示小于，大于、等于、小于等于，大于等于，不等于，那么这些关系会满足什么性质？试填写下表自反反自反对称反对称传

25、递<>=36设R=，Z是整数集，则：（1）R对矩阵的加法和乘法构成一个环；（2）R中存在元素x是右零因子但不是左零因子。全国2007年7月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）APQBPQCPQDPQ2下列命题公式为重言式的是（）AQ（PQ）BP（PQ）C（PQ）PD（PQ）Q3下列4个推理定律中，不正确的是（）AA（AB）B（AB）

26、ABC（AB）ABD（AB）BA4谓词公式x(P(x)yR(y)Q(x)中量词的辖域是（）ABP（x）C(P(x)yR(y)DP(x), Q(x)5设个体域A=a,b，公式xP(x)xS(x)在A中消去量词后应为（）AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)6下列选项中错误的是（）AØØBØØCØØDØØ7设A=a,b,c,d，A上的等价关系R=<a, b>, <b, a>, <c, d>, <d, c>

27、IA，则对应于R的A的划分是（）Aa,b, c,dBa, b,c, dCa,b,c,dDa, b, c,d8设R为实数集，函数f：RR，f(x)=2x，则f是（）A满射函数B入射函数C双射函数D非入射非满射9设R为实数集，R+=x|xRx>0，*是数的乘法运算，<R+，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）AR+中的有理数BR+中的无理数CR+中的自然数D1，2，310下列运算中关于整数集不能构成半群的是（）Aab=maxa, bBab=bCab=2abDab=|a-b|11设Z是整数集，+，分别是普通加法和乘法，则（Z，+，）是（）A域B整环和域C整

28、环D含零因子环12设A=a, b, c，R是A上的二元关系，R=<a, a>, <a, b>, <a, c>, <c, a>，那么R是（）A反自反的B反对称的C可传递的D不可传递的13设D=<V, E>为有向图，V=a, b, c, d, e, f, E=<a, b>, <b, c>, <a, d>, <d, e>, <f, e>是（）A强连通图B单向连通图C弱连通图D不连通图14在有n个结点的连通图中，其边数（）A最多有n-1条B至少有n-1条C最多有n条D至少有n条15连

29、通图G是一棵树，当且仅当G中（）A有些边不是割边B每条边都是割边C无割边集D每条边都不是割边二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16任意两个不同的小项的合取为_式，全体小项的析取式必为_式。17公式x(P(x)Q(x,y)zR(y, z)S(x)中的自由变元为_，约束变元为_。18设集合M=x|1x12,x被2整除，xZ,N=x|1x12,x被3整除，xZ，则 MN=_，MN=_。19设X=1，2，3，f：XX，g：XX，f=<1, 2>,<2,3>,<3,1>,g=<1,2>,&

30、lt;2,3>,<3,3>，则fg=_，gf=_。20设A=a,b,c，R是A上的二元关系，且给定R=<a,b>,<b,c>,<c,a>，则R的自反闭包r(R)= _，对称闭包s(R)= _。21设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，<a, b>,<x, y>S, <a, b>*<x, y>=<ax, y+b>, 则*运算的幺元是_。<a, b>S, 若a0，则<a, b>的逆元是_。22设*是集合S上的二元运算，若运算*满足_且

31、存在_，则称<S，*>为独异点。23令A=a, b, c，<A, *>是循环群，a是单位元，则b2=_，c的阶是_。24如下无向图割点是_，割边是_。25无向图G具有生成树，当且仅当_。G的所有生成树中_的生成树称为最小生成树。三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）26集合A=a, b, c, d, e上的二元关系R为R=<a,a>, <a,b>, <a,c>, <a,d>, <a,e>, <b,b>, <b,c>, <

32、;b,e>, <c,c>, <c,d>, <c,e>, <d,d>, <d,e>, <e,e>（1）写出R的关系矩阵；（2）判断R是不是偏序关系，为什么？27利用真值表判断公式（PQ）（QR）（PR）是否为重言式。28给定图G如下所示，（1）写出G的可达矩阵；（2）G中长度为4的路有几条？29求下列公式的主析取范式和主合取范式：（PQ）（QR）30设A为54的因子构成的集合，RA×A，x,yA, xRyx整除y。画出偏序集<A,R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。五、证明题（

33、本大题共3小题，第31、32小题各6分，第33小题8分，共20分）31设R是A上的一个自反关系，证明：R是一个等价关系，当且仅当若<a,b>R，<a,c>R，则<b,c>R。32设<G，*>是一个群，xG，定义：ab=a*x*b，a,bG。证明：<G,>也是一个群。33设图G是具有6个结点，12条边的无向简单图，证明图G是汉密尔顿图。五、应用题（本大题共2小题，第34小题8分，第35小题7分，共15分）34构造下面推理的证明。 如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园

34、游人太多，所以我们去圆明园玩。35n个城市用k条公路的网络连结。一条公路定义为两个城市间的一条不穿过任何中间城市的道路。任意两个城市之间至多修一条公路。证明如果k>(n-1)(n-2)，则人们总能通过连结的公路，在任何两个城市间旅行。全国2008年4月自考离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）A.ùPQB.ùPQC.

35、9;PùQùQ2.下列命题联结词集合中，是最小联结词组的是（）A.ù， B.ù，C.ù，D.，假命题的是（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一x(P(x)$yR(y)Q(x)中变元x是（）5.若个体域为整数减，下列公式中值为真的是（）A.x$y(x+y=0)B.$yx(x+y=0)C.xy(x+y=0)D.ù$x$y(x+y=0)不正确的是（）x-xB.xÍx-xC.A=xx,则x

36、A且xÍAD.A-B=ÆÛA=B7.设P=x|(x+1)24，Q=x|x2+165x,则下列选项正确的是（）ÉQÊQÉPD.Q=P不成立的是（）(BÅC)=(AB) Å (AC)(BÅC)=(AB) Å (AC)C.(AÅB)×C=(A×C) Å (B×C)D.(A-B) ×C=(A×C)-(B×C)9.半群、群及独异点的关系是（）A.群Ì独异点Ì半群B.独异点Ì半群Ì群C.独

37、异点Ì群Ì半群D.半群Ì群Ì独异点10.下列集合对所给的二元运算封闭的是（）+上规定*为a*b=ab-a-b a,bR+上的二元运算*为x*y=min(x,y) x,yZ+×n实可逆矩阵集合Rn×n上的矩阵加法11.设集合A=1，2，3，下列关系R中不是等价关系的是（）A.R=<1,1>,<2,2>,<3,3>B.R=<1,1>,<2,2>,<3,3>,<3,2>,<2,3>C.R=<1,1>,<2,2>,<3

38、,3>,<1,2>D.R=<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>12.下列函数中为双射的是（）A.f：ZZ,f(j)=j(mod)B.f：NN,f(j)=C.f：ZN,f(j)=|2j|+1D.f：RR,f(r)=2r-1513.设集合A=a,b, c上的关系如下，具有传递性的是（）A.R=<a,c>,<c,a>,<a,b>,<b,a>B.R=<a,

39、c>,<c,a>C.R=<a,b>,<c,c>,<b,a>,<b,c>D.R=<a,a>14.含有5个结点，3条边的不同构的简单图有（）15.设D的结点数大于1，D=<V,E>是强连通图，当且仅当（）二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.设A=1,2,3，B=3,4,5，则AÅA=_，AÅB=_。17.设A=1,2,3,4,5，RÍA×A，R=<1,2>，<3,4>,<

40、;2,2>，则R的自反闭包r(R)=_。对称闭包t(R)=_。18.设P、Q为两个命题，德摩根律可表示为_，吸收律可表示为_。x(P(x)Q(x)，其中P(x)x=1,Q(x)x=2,当论域为1,2时，其真值为_ ,当论域为0,1,2时，其真值为_。RR,f(x)=x+3,gRR,g(x)=2x+1,则复合函数,。21.3个结点可构成_个不同构的简单无向图，可构成_个不同构的简单有向图。22.无向图G=<V,E>如左所示，则G的最大度(G)=_，G的最小度(G)=_。23.设图G<V,E>,V=v1,v2,v3,v4,若G的邻接矩阵，则deg-(v1)=_ _,d

41、eg+(v4)=_。24.格L是分配格，当且仅当L既不含有与_同构的子格，也不含有与_同格的子格。25.给定集合A=1,2,3,4,5，在集合A上定义两种关系：R=<1,2>,<3,4>,<2,2>,S=<4,2>,<2,5>,<3,1>,<1,3>，则，。三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）26.设A=a,b,c,d，A上的等价关系R=<a,b>,<b,a>,<c,d>,<d,c>IA，画出R的关系图，

42、并求出A中各元素的等价类。ù（PQ） （ùPQ）的真值表。28.求下列公式的主析取范式和主合取范式：P（QP）（ùPQ）29.设A=a,b,c,d,e，R为A上的关系，R=<a,d>，<a,c>，<a, b>, <a, e>, <b, e>,<c, e>, <d, e>IA，试画<A，R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。四、证明题（本大题共3小题，第31、32题各6分，第33题8分，共20分）31.设（L，）是格，试证明：a, b, c L, 有a（bc）（ab）（ac）；a（bc）（ab）（ac）。32.设R是A上的自反和传递关系，如下定义A上的关系T，使得x, yA，<x, y>T<x, y>R(y, x)R。证明T是A上的等价关系。33.设有G=<V, E>, V的结点数|V|=n，称该图为n阶图，若从结点vi到vj存在路，证明从vi到vj必存在长度小于等于n-1的一条路