安徽大学离散数学(上)试卷及参考答案

安徽高校2009—2010学年第1学期

《离散数学》考试试卷(A卷)

(时间120分钟)

院/系专业姓名学号

题

—•四五七总分

号

得分

得

分

一、单项选择题(每小题2分，共20分)

1.设P：天没下雪，Q：我去镇上，则命题“天正在下雪，我没去镇上”可符号化为

()

A.B.f->P；C.P/\「Q；D.

2.下列命题是重言式的是()

A.(PfQ)A(Q-»P)；B.(P/、QCP)C(PCQ)；

C.P八D.(P.(QV「R))八「PAQ。

3.设说明R如下：论域。为实数集，。=0,f(xyy)=x-yff^y)=x<y,下列公式

在R下为真的是()

A.VxVjVz(A(x,y)->A(/(x,z),/(j,z)));B.VxA(f(ayx),a);

C.VxV)，A(/(x,y),x);

D.y)-A(f(x1a),a))。

4.对随意集合AB,。，下列结论正确的是()

A.B.[A$BA3qC]=AEC；

D.[/lc^ABeC]=>y4eCo

5.关于X={a,"c}到丫={1,2,3}的函数/={<〃/>,<〃」>,vc,3>},下列结论不正确的是

()

A、尸(⑶)=依；B、广(3)=c；C、f({c})={3}；D、/(c)=3o

6.设/为整数集合，则/上的二元关系R={<x,y>||x-y|=4}具有()

A.自反性和对称性；B.反自反性和对称性；C.反自反性和传递性；D.反对称性

和传递性。

7.设我为非空集合A上的关系R的逆关系，则下列结论不成立的是()

A.若R为偏序，则A为偏序；B.若R为拟序，则R为拟序；

C.若R为线序，则尺为线序；D.若R为良序，则左为良序。

8.设/和叼是非空集合A的划分，则下列结论正确的是()

A.々细分乃।•乃2；B.勺细分乃#T2；C.非空集合A的划分勺Cl乃2细分匹；D.

勺细分非空集合A的划分勺U%;。

9.设乂={a,6©,%是X上恒等关系，要使4D{va，b>，v"，c>，vc，a>，vbM>}=R为

X上的等价关系，R应取()

A.{<c.a>,<a,c>}；B.{<c,b>,</?,«>}；

C.{<c,a>,<b,a>]；D.{<a,c>,<c.b>}o

10.设N和/?分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合

是()

A.R；B.NN；C.p(N)；D.N”

得分

二、推断题(每小题2分，共10分。对的打J,错的打X)

1.()(。八。)八「。为冲突式。

2.()A、B、C是随意集合，假如ADC=AD4,肯定有3=C。

3.()若集合A上的二元关系R是对称的，R的肯定补齐肯定是对称的。

4.()有理数集是可数的。

5.()若函数/,g为单射，则它们的复合函数也为单射的。

三、填空题（每小空2分，共20分）得分

1.设R（x）：x是实数，Q（x）：工是有理数，Z（x）：x是整数，则

“有理数都是实数，但实数并非都是有理数”符号化

为：;

“不是这样状况：某些整数不是有理数”符号化

为：O

2.设集合4={〃/,c},B={a,b},贝ljp（B）-p（A）=；p（B-A）=°

3.设4={0,1,2,3,4,5},则定义在集合A上二元关系R={<x,y>|,（x=Z”a<2}的关系

矩阵为M犬-;M,（R）=

4.设（7=[0刀，A=[1,1],3=（；]）,则以豆⑶=,%$8*）=—

.1I

5.设N为自然数集合，Q为有理数集合，R为实数集合，则|NxQ|—|/V|,\R-Q\

\Q\（填二，>，<）o

二、解答题（每小题10分，共20分）得分

1.求（PfQAR）A（「P-（「Q八［R））的主析取范式和主合取范式。

2.给定集合A={123,4,5,6}上的偏序关系

求：（1）给出了偏序集合<AA〉的哈斯图；（2分）

（2）完成下表。（每空2分）

生入

k-l最大元最小元极大元微小元

5={2,3,4}

杲口上界下界上确界下确界

得分

C={3,4,5,6}

四、证明题（每小题10分，共30分）

1.用推理规则证明：

2.设吊是/I上的等价关系，用是4上的等价关系，后且胖。关系4满意：＜＜X,

%），＜房,y»RR〈由，也＞£6且〈必，出＞金尼，证明〃是4X8上的等价关系。

3.设/为整数集合，E为偶数集合，函数广/x/fExE定义为：

/（＜＞）=＜x+y,x-y＞，

证明：/是双射函数。

安徽高校200一20B_学年第，学期

《离散数学》考试试题(A卷)参考答案与评分标准

一、单项选择题(每小题2分，共20分)

1；2；3；4；5；6；7；8；9；100

二、推断题(每空2分，共10分)

1.J,2.X,3.V,4.V,5.J

三、填空题(每小空2分，共20分)

1.Vx(g(x)fR(x))A3x(/?(x)A」Q。))或Vx(Q(x)fR(x))AfQ(x))；

—)Hx(Z(x)A—iQx))或Vx(Z(x)fQ(x))。

2.p(B)-p(A)={{c},{a,c},{〃c},{a,b,c}};

11111

0100001000

3.MR=00100，•Mt(R)二00100

0001000010

0000100001

当xe[0,—]<J[—,1]

4,匕g万(劝=

当*

42

5.|NxQ|二|N|；|R-Q|上Q|。

三、解答题(每小题10分，共30分)

1.(P->QAR)A(―\P—>(—iQA—iR))

=(「尸VQAR)人(PVIQA-J?)2分

<=>(-iPv0A(-1PV/?)A(PV-,Q)A(PV—I7?)4分

。4(1,2,3,4,5,6)(主合取范式)8分

oZ(0,7)(主析取范式)10分

2.(1)vA,R>的哈斯图为

(2)(空2分)

集合最大元最小元极大元微小元

8={2,3,4}不存在42,34

集合上界下界上确界下确界

C={3,4,5,6)1不存在1不存在

10分

四、证明题(每小题10分，共30分)

1.依据规则，上式等价于

Vx(P(x)TQ(x))AVx(H(x)T-1Q(X))=(H(x)T-1P(X))2分

而

oWx((尸(x)->Q(x))A(R(x)->iQ(x)))Gio4分

oDx((-iQ(x)f->P(X))A(/?(X)T-iQ(x)))反，J6分

n(—iQ(x)―>—)P(x))A(H(x)—>—iQ(x))8分

=>R(x)->「尸(工)/610分

所以,Vx(P(x)-Q(x))nVx(R(x)t[Q(X))f(R(x)t-1P(X))

2.证明对随意的3,y＞£力X8,由凡是力二的等价关系可得＜x,才＞£用，由此是台

上的等价关系可得＜八尸＞£兄。再由〃的定义，有《刈"，＜*,)，＞＞£〃，所以兄是自

反的。2分

对随意的〈必y＞、＜11,力w/XA,若y＞水u,r＞,则力@/?且＜人力£兆。

由用对称得＜〃，x〉GR,由此对称得＜匕y〉匕也再由〃的定义，有＜＜〃，/＞,＜x,y»

eR,即＜〃，v＞R＜x,y＞,所以〃是对称的。

6分

对随意的y>、<u,r>><s,t>eAXB,若y>R<u,力且<u,\>R(s,t>,

则<x,心£发且<y,力仁尼，<u,s>£A且<心力£足。由<x,u〉GR、<u9s>eR与

北的传递性得<x，s>£R\,由<y,力£尼、<r,1>仁尼与尼的传递性得〈y,t>GR。再

由〃的定义，有<<>,y>,<s,f»GR,即<x,y>欣s,t>,所以〃是传递的。

10分

综上可得，"是/X〃上的等价关系。

3.(1)T<21>，<"2>E/X/,若/—>)=/(<%,%>),即