2016离散数学练习题-(答案修改)

PAGEPAGE2/92016注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍.2、第二遍复习按照考试大纲的总结把重点内容再做复习.另外,把大纲中指定的例题与书后习题认真做一做.检验一下主要内容的掌握情况.3注意做题思路与方法.离散数学综合练习题一、选择题令p:今天下雪了,q:路滑,r:他迟到了.则命题"下雪路滑,他迟到了"可符号化为〔A 〕.pqrB. pqrC. pqrD. pqr设P(x):x是整数,f(x):x的绝对值,L(x,y)：x大于等于y；命题所有整数的绝对值大于等于0"可符号化为〔B 〕.A.x(P(x)L(f(x),0))B. x(P(x)L(f(x),0))C.xP(x)L(f(x),0)D. xP(x)L(f(x),0)F(xx是人G(xx犯错误,命题"没有不犯错误的人"符号化为〔D〕.A．x(F(x)G(x))C．x(F(x)G(x))

B．x(F(x)G(x))D．x(F(x)G(x))*4.下列命题公式不是永真式的是〔 A 〕.(pq)pC.p(qp)

B.p(qp)D.(pq)pp,q,命题我们不能既划船又跳舞B.pqB.(pq)C.pq D.pq设R(x):x为有理数Q(x):x为实.命题任何有理数都是实数的符号化〔〕A．(x)(R(x)Q(x)) B．(x)(R(x)Q(x))C．(x)(R(x)Q(x)) D．x(R(x)Q(x))设个体域D{a,b},与公式xA(x)等价的命题公式是< C>A(a)A(b)B．A(a)A(b)C．A(a)A(b)D．A(b)A(a)G20条边,46度顶点,25度顶点,2度顶点,G一共有〔 C 〕个顶点.A.7 B.8 C.9 D.10*9.设集合A={c,{c}},下列命题是假命题的为〔C 〕.A.{c}P(B.{{c}}P(C.{c}P(A)D.{{c}}P(A)设X={,{a},{a,,则下列陈述正确的是〔C 〕.aXC.{{a,

B.{a,XD.{}X有向图D是连通图当且仅当〔D 〕.D中至少有一条通路D中有通过每个顶点至少一次的通路D的连通分支数为一D中有通过每个顶点至少一次的回路设A={a,b,c},则下列是集合A的划分的是< B A.{{b,c},{c}}B.{{a},{b,C.{{a,b},{a,D.{{a,下列谓词公式中是前束范式的是〔D 〕.A．xF(x)(x)G(x)B．xF(x)yG(y)C．x(P(x)yQ(x,y))D．xy(P(x)Q(x,y))设简单图G所有结点的度数之和为50,则G的边数为〔B 〕A.50 B.25C.10 D.515A,AR1,13,22,3,4,4IA,则对应于R的划分是〔 A 〕.A.{{1},{2,3},{4}}B.{{1,3},{2,4}}C.{{1,3},{2},{4}}D.{{1},{2},{3},{4}}16XYabcd},fa2,b3,c,f是< C >.XY的双射XY的满射,但不是单射XY的单射,但不是满射XY,XY的映射下列图是欧拉图的是〔D 〕.给定一个有n个结点的无向,下列陈述不正确的是〔 A 〕.所有结点的度数≥2B．无回路但若增加一条新边就会变成回路C．连通且ev1,e是边数,vD．无回路的连通图若供选择答案中的数值表示一个简单图中各个顶点的度 ,能画出图的是〔 C 〕.A.<1,2,2,3,4,5>C.<1,1,1,2,3>

B.<1,2,3,4,5,5>D.<2,3,3,4,5,6>设A{a,{a},{a,{a}}}则其幂集P(A)的元素总个数为〔C 〕.3 B.4C.8 D.16设简单图G所有结点的度数之和为48,则G的边数为< B A.48 B.24C.16 D.12下面既是哈密顿图又是欧拉图的图形是〔 B 〕.下列必为欧拉图的是〔 D 〕有回路的连通图C.1

B.不可以一笔画的图D.无奇数度结点的连通图KA.C.

是〔B 〕.3,3

B.哈密顿图D.完全图下列所示的哈斯图所对应的偏序集中能构成格的是C 〕.B.C. D.设集合A{a,b,c},A上的关系Ra,a,a,c,c,a},则R是〔B 〕自反的 B．对称的C．传递的 D．反对称的RRAabcd上的两个关系,R

a,a,b,b,1 2 1b,c,d,d},R2

aabbcbbcdd}R2

是R 的1〔B〕闭包.C．传递

对称DA〕.A．(x)(y)(F(z,x)G(y)) B．((x)F(x)(y)G(y))H(z)3/9PAGEPAGE5/9C．(x)F(x,y)(y)G(y)D．(x)(F(x,y)(y)G(x,y))R为实数集,fRR,f(x)x22x5,f是〔D〕.C．双射

满射而非单射D．既不是单射,C〕.A．B．C．D．12.设Mx|f(x)0},Nx|f(x)0},f(xf(x)0的解为〔B〕.1 2 1 2A．M∩N B．M∪NC．MN C．M-N设GA,是群,则下列陈述不正确的是〔C 〕.A.(a1)1aB.anamanmC.(ab)1a1b1D.(a1ba)na1bna二、填空题命题公式p(pq)的成真指派为0001成假指派为_10 .公式(x)(y)(Py)Q(xzy)R(x,y约束变元为x,y,自由变元为x,z.3Aab,{aBaBA,AB{{a,b}}.Aabc},ARabba},则对称闭包s(R){a,b,b,a},传递闭包t(R){a,b,b,a,a,a,b,b}.一棵无向树的顶点数n与边数mn-1.66构的生成树.6．设f(x)x1,g(x)x2,则复合函数(f g)(x)=(x1)2,(g f)(x)=x21.7.

Zn

{0,1,2, n1}xy(xymodn,则当n时,在

,中,2的阶为 3 ,3的阶为_2.68．设<A,≤>是格,其中A={1,3,4,6,8,12,24},≤为整除关系,则1的补元是 24 ,3的补元是 8 .9．设A=｛<1,3>,<3,5>,<4,4>｝,B=｛<1,3>,<4,5>,<5,5>｝,那么dom(A B)={1,3,4,5}ran(A B)={3}_.设 A={l,2,3,4},A 上 的 二 元 关 系R={<1,2>,<2,3>,<3,2>},S={<l,3>,<2,3>,<4,3>},则R S{<1,3>,<3,3>},(R S)1{<3,1>,<3,3>}.设复合函数gf是从A到C的函数,如果gf是满射,那么 g 必是满射如果gf是单射,那么 f_必是单射.12A={l,2}上的一个等价关系1,12,2并给出其对应的划分{{1},{2}}.设A{a,b,c,d},A上的二元关系Ra,b,a,d,b,b},则R的自反闭包r(R)R I,传递闭包t(R)RAg)(x)2x 4,设个体域是实数集,命题x(x3x的真值为1；命题x(x21g)(x)2x 4,f)(x)2x 7.15.设f)(x)2x 7.(g16．设Z,为模6加群,其中Z {0,1,2,3,4,5},则2-3=0,4-2=4.6 6nn<n-1>/2n-1.已知n阶无向简单图G有m条边,则G的补图Gn<n-1>/2-m条边.5设Kn是n个顶点的完全图,则K有_10 条边每个顶点的度数为 4 .540个人26人得优秀,21人得优秀,17人,10,30.三、计算题〔仅给出部分题目的解题思路,未给出答案自己完成〕已知命题公式pqpr)〔1〕构造真值表；〔21〕真值表pqrpqpr(pr)(pq)(pr)00000110010101010101101111001001100101110011011001111100〔2〕主析取范式求公式prpqp的主合取范式与主析取范式.3fRR,f(x)x22gRRg(x)x4hRRh(x)x31,R表示实数集.〔1〕求函数f g,g f；〔2〕f,g,h哪些函数有反函数？如果有,求出这些反函数.解〔1〕g f(x)f(g(x))f(x4)(x4)22x28x14〔2g和h有反函数g1RRg1(x)x4；4A为整除关系.〔1〕画出偏序集<A,>的哈斯图；〔2〕求A中的极大元；〔3B=｛369｝的上确界与下确界1〕哈斯图〔2〕A中的极大元为24,54；极小元为1；最大元：无；最小元：1〔3〕求子集B=｛3,6,9｝的上确界为54,下确界为3.5.设有向图D如图所示,用邻接矩阵计算v1到v4长度小于或等于3的通路数.解：有向图的邻接矩阵为1 1 0 0 1 1 1 00A1

0 1 0 ,A20 0 0

0 0 01 0 01 0 2 0 1 2 1 1 0 3

1 0 02 1 01A31

1 0 0 ,A41 1 0

1 1 01 1 03 3 1 0 4 3 3 03 v1v33的通路数为0123450012345110123450012345112345022345013345012445012355012346/9PAGEPAGE9/9P197-1989.49.57. 设A ＝{1,2,3,4,5},R 是A 上的二元关系, 且R ＝{〔2,1>,<2,5〕,<2,4>,<3,4>,<4,4>,<5,2>},求r<R>、s<R>和t<R>.s<R>=R∪R-1t<R>={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,〔2,2>,<5,5>}8.一棵〔无向〕树有22,13,34,都是叶结点,问该树有几个叶结点？解：在一个有限图中,各结点的度数总和是边数的2倍；而树中的边数为结点数减1.根据这两点,可知树中各结点的度数总和=2*〔树中点数-1x于是,2*2+3+3*4+x=2*〔2+1+3+x-1〕得x=9.四、简答题1R1,3,(1,42,23,13,3),4,1是A上的二元关系.〔1R的关系图；〔2R的关系矩阵；〔3〕讨论R的性质.〔4〕R1〕R的关系图00〔2〕R的关系矩阵 111

0 1 11 0 00 0 00 0 0〔3〕R非自反、非反自传、对称、非反对称、非传递的2.设集合A2.设集合A上的关系R{(1,1, 1,3 , 1,6 , 2,22,5 , 3,1 , 3,3 , 3,6 , 4,4 , 5,2 , 5,5 , 6,1 ,,6,3), 6,6 }〔1R的关系图,R的关系矩阵；〔2R是否为等价关系？若是,R的所有等价类1〕R的关系图为100〔2〕R的关系矩阵 000

0 1 0 01 0 0 10 1 0 00 0 1 01 0 0 1R是等价关系.或写为：A/R={{1,3,6},{2,5},{4}}3．判断下图是否为二部图？若是,找出它的互补结点子集.它是否为哈密顿图？biRbiR如下：x,yRu,vghdj四、证明题Axyxy为正整数},A上定义二元关c当且仅当xyuv. f证明：R是一个等价关系.证明： e任取x,y所以R自反的.任取x,y,u,v所以R是对称的.任取x,y,u,v,s,t所以R是传递的.因此,R是等价关系.设Aabab为正整数},AR如下：abRcd当且仅当abcd.R是一个等价关系证明：任取a,b所以R自反的.任取a,b,c,d所以R是对称的.任取a,bcd,f所以R是传递的.因此,R是等价关系.用一阶逻辑的推理理论证明：设代数系统VZ6构成群.

,,Z6

{0,1,2,3,4,5}为模6加法.6

关于运算证明：集合Z显然非空.66<1>a,bZ,abZ,从而集合Z 关于运算是封闭的.66 6<2>a,b,cZ6

,有(ab)ca(bc),故运算 是可结合的.<3>aZ6, a0a0Z6中的幺元.<4>aZ

,因为a(6a