2008年4月到2013年7月自考离散数学试题附答案 - 图文 下载本文

全国2008年4月自考离散数学试题

课程代码:02324

一、单项选择题(本大题共15小题,每小题1分,共15分)

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.设P:天下大雨,Q:他在室内运动,命题“除非天下大雨,否则他不在室内运动”可符合化.为( ) A.?P∧Q B.?P→Q C.?P→?Q D.P→?Q 2.下列命题联结词集合中,是最小联结词组的是( ) A.{?, } B.{?,∨,∧} C.{?,∧} D.{∧,→} 3.下列命题为假命题的是( ) .

A.如果2是偶数,那么一个公式的析取范式惟一 B.如果2是偶数,那么一个公式的析取范式不惟一 C.如果2是奇数,那么一个公式的析取范式惟一 D.如果2是奇数,那么一个公式的析取范式不惟一

4.谓词公式?x(P(x)∨?yR(y))→Q(x))中变元x是( ) A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数减,下列公式中值为真的是( ) A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不正确的是( ) .A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B

7.设P={x|(x+1)2≤4},Q={x|x2+16≥5x},则下列选项正确的是( ) A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不成立的是( ) .A.A∪(B?C)=(A∪B) ? (A∪C) B.A∩(B?C)=(A∩B) ? (A∩C) C.(A?B)×C=(A×C) ? (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是( ) A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群} C.{独异点}?{群}?{半群} D.{半群}?{群}?{独异点} 10.下列集合对所给的二元运算封闭的是( ) A.正整数集上的减法运算

B.在正实数的集R+上规定?为a?b=ab-a-b ?a,b∈R+ C.正整数集Z+上的二元运算?为x?y=min(x,y) ?x,y∈Z+

×

D.全体n×n实可逆矩阵集合Rnn上的矩阵加法

第 1 页

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,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:Z→Z,f(j)=j(mod)

?1,j是奇数B.f:N→N,f(j)=?

0,j是偶数?C.f:Z→N,f(j)=|2j|+1 D.f:R→R,f(r)=2r-15

13.设集合A={a,b, c}上的关系如下,具有传递性的是( ) A.R={,,,} B.R={,} C.R={,,,} D.R={} 14.含有5个结点,3条边的不同构的简单图有( ) .

A.2个 B.3个 C.4个 D.5个

15.设D的结点数大于1,D=是强连通图,当且仅当( ) A.D中至少有一条通路 B.D中至少有一条回路 C.D中有通过每个结点至少一次的通路 D.D中有通过每个结点至少一次的回路 二、填空题(本大题共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>,<2,2>},则R的自反闭包r(R)=__________。

对称闭包t(R)=__________。

18.设P、Q为两个命题,德摩根律可表示为_____________,吸收律可表示为____________。 19.对于公式?x(P(x)∨Q(x)),其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时,其真值为

_____________ ,当论域为{0,1,2}时,其真值为_____________。

20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(f?g)(x)?____________,

(g?f)(x)?__________________。 21.3个结点可构成_________个不同构的简单无向图,可构成________个不同构的简单有向

图。

22.无向图G=如左所示,则G的最大度

Δ(G)=_____________,G的最小度δ(G)=_____________。 ?0?123.设图G,V={v1,v2,v3,v4},若G的邻接矩阵A???1??1101?011??,则deg-(v1)=_ ________, 100??000?deg+(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>},则R?S?_______________,S?R?_______________。 三、计算题(本大题共5小题,第26、27题各5分,第28、29题各6分,第30题8分,

第 2 页

共30分)

26.设A={a,b,c,d},A上的等价关系R={,,,}∪IA,画出R的关系图,并求出A中各元素的等价类。

27.构造命题公式?(P∨Q) (?P∧Q)的真值表。 28.求下列公式的主析取范式和主合取范式:P→((Q→P)∧(?P∧Q))

29.设A={a, b, c, d, e},R为A上的关系,R={, , ,, }∪IA,试画的哈斯图,并求A中的最大元,最小元,极大元,极小元。 30.给定图G如图所示,(1)G中长度为4的路有几条?其中有几条回路?(2)写出G的可达矩阵。

四、证明题(本大题共3小题,第31、32题各6分,第33题8分,共20分) 31.设(L,≤)是格,试证明:?a, b, c ∈L, 有a∧(b∨c)≥(a∧b)∨(a∧c); a∨(b∧c)≤(a∨b)∧(a∨c)。

32.设R是A上的自反和传递关系,如下定义A上的关系T,使得?x, y∈A,∈T? ∈R∧(y, x)∈R。

证明T是A上的等价关系。

33.设有G=, V的结点数|V|=n,称该图为n阶图,若从结点vi到vj存在路,证明从vi

到vj必存在长度小于等于n-1的一条路。

五、应用题(本大题共2小题,第34题7分,第35题8分,共15分) 34.构造下面推理的证明。

每个喜欢步行的人都不喜欢坐汽车,每个人或者喜欢坐汽车或者喜欢骑自行车。有

的人不喜欢骑自行车,因而有的人不喜欢步行。

35.今要将6人分成3组(每组2个人)去完成3项任务。已知每个人至少与其余5个人中

的3个人能相互合作。

(1)能否使得每组的2个人都能相互合作? (2)你能给出几种不同的分组方案?

第 3 页

第 4 页