离散数学试卷及答案(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?AD.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（ ） A.P?QB.P?QC.Q?PD.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上的矩阵加法 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.下列函数中为双射的是（ ）

?1,j是奇数A.f：Z→Z,f(j)=j(mod)B.f：N→N,f(j)=?C.f：Z→N,f(j)=|2j|+1D.f：R→R,f(r)=2r-15

0,j是偶数?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)=_ ________,deg+(v4)=____________。 100??000?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>}，则，S?R?_______________。 R?S?_______________三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共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）你能给出几种不同的分组方案？

2008年4月全国自考离散数学参考答案

一．填空题（每小题2分，共10分）

1. 谓词公式?xP(x)??xQ(x)的前束范式是__ ?x?y?P(x)∨Q(y) __________。 2. 设全集E??1,2,3,4,5?,A??1,2,3?,B??2,5?,则A∩B =__{2}__，A?_{4,5}____，

A?B?__ {1,3,4,5} _____ 3. 设A??a,b,c?,B??a,b?，则?(A)??(B)?__ {{c},{a,c},{b,c},{a,b,c}} __________，?(B)??(A)?_____Φ_______。 4. 在代数系统（N，+）中，其单位元是0，仅有 _1___ 有逆元。 5．如果连通平面图G有n个顶点，e条边，则G有___e+2-n____个面。 二．选择题（每小题2分，共10分）

1. 与命题公式P?(Q?R)等价的公式是（ ）

（A）(P?Q)?R （B）(P?Q)?R （C）P?(Q?R) （D）P?(Q?R) 2. 设集合A??a,b,c?,A上的二元关系R???a,a?,?b,b??不具备关系( )性质 （A）

(A)传递性 (B)反对称性 (C)对称性 (D)自反性