2020年自考离散数学02324真题含答案44版

2020年自考离散数学02324真题含

答案44版

全国4月自学考试离散数学试题（附答案）

课程代码：02324

一、单项选择题（本大题共15小题，每小题1分，共15

分）

在每小题列出的四个备选项中只有一个是符合题目

要求的，请将其代码填写在题后的括号内。错选、

多选或未选均无分。

1.下列为两个命题变元P,Q的小项是（）

A.PAQA1PB.1PVQ

C.1PAQD.1PVPVQ

2.下列语句中是真命题的是（）

A.我正在说谎B.严禁吸烟

C.如果1+2=3,那么雪是黑的D.如果1+2=5,那么

雪是黑的

3.设P:我们划船，Q:我们跑步。命题“我们不能既划船

又跑步”符号化为（）

A.IPAIQB.IPVIQ

C.1（P—Q）D.1（IPVlQ）

4.命题公式（PA（PfQ））fQ是（）

A.矛盾式B.蕴含式

C.重言式D.等价式

5.命题公式1（PAQ）-R的成真指派是（）

A.000,001,110,B.001,Oil,101,110,111

C.全体指派D.无

6.在公式（一）F（x,y）f（aj）G（x,y）中变元x

是（）

A.自由变元B.约束变元

C.既是自由变元，又是约束变元D.既不是自由变元,

又不是约束变元

7.集合A={1,2,…，10}上的关系R={«,J>|X+J=10,

xEA,y《A},则R的性质是（）

A.自反的B.对称的

C.传递的、对称的D.反自反的、传递的

8.若R和S是集合A上的两个关系，则下述结论正确

的是（）

A.若R和S是自反的，则RHS是自反的

B.若R和S是对称的，则R°S是对称的

C.若R和S是反对称的，则R°S是反对称的

D.若R和S是传递的，则RUS是传递的

9.R={<1,4>,<2,3>,<3,1>,<4,3>},则下列不*

是*，（R）中元素的是（）

A.<1,1>B.<1,2>

C.<1,3>D.<1,4>

10.设人={{1,2,3},{4,5},{6,7,8}）,下列选项正

确的是（）

A.leAB.{1,2,3bA

C.{{4,5}}uAD.0WA

11.在自然数集N上，下列运算是可结合的是（）

A.a*b=a-2bB.a*A=min{〃,b}

C.a*b=-a-bD.a^b=\a-b\

12.在代数系统中，整环和域的关系是（）

A.整环一定是域B.域不一定是整环

C,域一定是整环D,域一定不是整环

13.下列所示的哈斯图所对应的偏序集中能构成格的是

14.设G为有〃个结点的简单图，则有（）

A.A（G）＜HB.A（G）W〃

C.A（G）＞nD.A（G）2〃

15.具有4个结点的非同构的无向树的数目是（）

A.2B.3

C.4D.5

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无

分。

16.(vx)(vy)(P(x,y)=Q(y，z))APP(X,y)

中V”的辖域为，江的辖域为O

17.两个重言式的析取是式，一个重言式与一个

矛盾式的析取是式。

18.设N是自然数集合，/和g是N到N的函数，且/

2

(〃)=2n+lfg(w)=n,那么复合函数(/o/)(〃)

=(go/)(n)=o

19.设复合函数g。/是从A到C的函数,如果g。/是满射，

那么必是满射，如果go/是入射，那么

必是入射。

20.设A={1,2},B={2,3},则A-A=,

A-B=o

21.设S是非空有限集，代数系统VP(S),U＞中，其中

P(S)为集合S的嘉集，则P(S)对U运算的单位

元是，零元是O

22.在vZ6,O＞中，2的阶是______o

23.设vA,是格，其中A={1,2,3,4,6,8,12,

24),《为整除关系，则3的补元是o

24.在下图中，结点电的度数是______o

V}

°2

V3

为(y---------式)为

题24图

25.设图D=<V,E>,V={vi,v2,v3,v4},若D的邻接

-

矩阵A=]o,贝!)deg(vi)=，从也到

1001

以长度为2的路有条。

三、计算题(本大题共5小题，第26、27小题各5分，

第28、29小题各6分，第30小题8分，共30分)

26.已知A={{0},{0,1}},B={{0,1},{1}},计算A

UB,AOB,A的募集P(A)o

27.构造命题公式((PAQ)fP)VR的真值表。

28.下图给出了一个有向图。(1)求出它的邻接矩阵A；

(2)求出A?,A3,A，及可达矩阵P。

力4

。3

题28图

29.求下列公式的主合取范式和主析取范式:PV(IP-

(QV(]QfR)))

30.设人={1,2,3,4,6,8,12,24},R为A上的整

除关系，试画vA,R＞的哈斯图，并求A中的最大元、最

小元、极大元、极小元。

四、证明题(本大题共3小题，第31、32小题各6分,

第33小题8分，共20分)

31.在整数集Z上定义Za°b=a+b-2,Va,beZ，证明:VZ,。＞是一

个群。

32.R是集合A上自反和传递的关系，试证明:R°R=R。

33.证蜂边e是图G的一条割边，当且仅当图G中不存

在包含边e的简单回路。

五、应用题（本大题共2小题，第34小题6分，第35

小题9分，共15分）

34.构造下面推理的证明。

如果小张和小王去看电影，则小李也去看电影。小

赵不去看电影或小张去看电影。小王去看电影。所

以，当小赵去看电影时，小李也去。

35.今有〃个人，已知他们中任何2人的朋友合起来一

定包含其余n-2人。试证明：

（1）当〃23时，这〃个人能排成一列，使得中间

任何人是其两旁的人的朋友，而两头的人是其

左边（或右边）的人的朋友。

（2）当〃24时，这〃个人能排成一圆圈，使得每

个人是其两旁的人的朋友。

2009年4月高等教育自学考试全国统一命题考试

离散数学试题答案及评分参考

（课程代码2324）

一、单项选择题（本大题共15小题，每小改】分，共］5分）

I.C2.D3.B4.C5.B6.C7.B8.A9.B10.C

11.B12.C13.C14.A15.A

二、填空题（本大题共10小题,每小题2分，共20分）

16.(P(x,y)-Q(y,z))P(»,y)17.垂言式重言式

18.4/1+3(2n+1)219”/20.0111

21.0S22.323.8

24.425.32

三、计算题（本大题共5小题，第26,27小题各5分，第28,29小题各6分，第30小题8

分,共30分）

26.«：AUB=I101J0JIJ1H（I分）

A〶R="011（2分）

P（A）=«J0J|0||,H0,1H,|101,10,11H（2^）

27.解：

PQRPAQPAQ-P((PAQ)-*P)VR(1分)

00001I

001011(1分)

0100I

01101I(1分)

100011

J01011(1分)

1!011!

11I11_________“分）

010K

0011

28.解：（D邻接矩阵A为(1分)

0101

.0100.

离散数学试题答案及评分参考第I页（共3页）

29.解:PV(1P-(QV(1Q-R)))

«PV(PV(QV(QVR)))

oPVQVR

所以主合取范式为:PVQVR=n(o)(3分)

主析取范式为：SPA1QAK)V(IPAQAIR)V(lPAQAR)V(PAIQ/MR)

V(PAIQAR)V(PAQAIR)V(PAQAR)

=£(1,2,3,4,5,6,7)(3分)

30.解：〈A.R〉的哈斯图如下:

A中最大元24,最小元I,极大元24.极小元1(4分)

四、证明题(本大题共3小题，第31、32小题各6分，第33小时8分，共20分)

31.证明:显然•是二元运算,根据群的定义，需证明运算满足结合律、有单位元和每个

元素有逆元。

Va,6,ceZ.^(a»6)«c=a»6+c-2=(a+6-2)+c-2=a+/»+c-4

ao(6oc)=a+6oc-2=a+(6+c-2)-2=a+6+c-4

故(a。B)oc=a。(6。c),结合律成立。(2分)

2是单位元.事实上,ao2=a+2-2=«,2«o=2+a-2sa,V<ieZ0(2分)

Va&Z,由ao(4-a)=a+(4-a)-2=2,(4-a)°a=(4-a)+r?-2=2.

可知4-a是a的逆元。(2分)

由上可知是群。

32.证明：VG,:)eRoR,由关系复合的定义，存在”A,使得〈明力6R,(,v.;)6R.

因R传递，有GMeR,可得RoRUR。(3分)

另一方就VG,y〉wR,因R自反.〈y,y〉ER,由R传递，G，y)uR。上可得

RCR.Ro

综合可得RoR=R。证毕。(3分)

离散数学试题答案及评分参考第2页(共3页)

33.证明："）充分性,设图C的边e=（u,u）不包含在G的任一条简单何路中,则u,u

之间除c外无任何通路.否则.若间存在另一条通路，那么加上边（，就

形成一条回路，这与题意矛盾。因此，去掉边％则G不连通，故e为G的

割边「（4分）

（2）必要性。设边c是G的割边,e包含在某一条简单回路中，删去e则不影

响G的连通性，这与e是割边矛盾.所以«不包含在C的任何茴单回路

中，（4分）

五、应用题（本大题共2小题，第34小题6分，第35小题9分,共15分）

34.解：令P：小张去看电影,Q：小王去看电影，R：小李去看电影，S：小赵去看电影

前提：（PAQ）-R.ISVP.Q

结论:S-R（2分）

证明:用“规则0

①SP（附加前提）■

②1SVPP

③PT（DQ）1

④（PAQ）-RP

⑤QP

⑥PAQ-

⑦RT®@I

⑧S+RCP（4分）

35.证明：做”阶无向简单图C；=〈V,E〉，V=””为此人群中的成员|,E=!（u,”）l%

veVJju与v是朋友且由已知条件可知，VutV.无论。与V是否

是朋友，均有

d（u）+d⑴小-2,记为（*）（1分）

下面再对u与，，是否姑朋友进行讨论.

⑴若u与”是朋友,则由（•）可知

d（u）+d（a）Mn-2+2=n①（2分）

（2）若u与“不是朋友，则VweV.mMu.wWv,贝（］u与v都是卬的朋友.否

则,比如“与卬不是朋友，则v,w都不是u的朋友，于是。与卬的朋友合

起来不包含其余的n-2个人，这与已知条件矛盾.因而

d（u）+d⑺1（n-2）②（2分）

由②式,对n进行讨论:当nM3时，有

2（n-2）-J③

当“叁4时，有

2（n-24n4（2分'

当时，由①式与③式可知（定理5.4.4）（；中存在汉密尔顿通道，.也

路上的人按在通路中的顺序排成一列.满足要求.当〃学4时,由①式与③

式可知（定理5.4.5）C中存在汉密尔顿回路，回路L的人按在回路中的

牍序排成圆圈满足要求.（2分）

离散数学试题答案及评分参考第3页（共3页）

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

课程代码：02324

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

分)

在每小题列出的四个备选项中只有一个是符合题目

要求的，请将其代码填写在题后的括号内。错选、

多选或未选均不得分。

()

!=0

()

A•(Vx)(P(x,y)-Q(x,z))V(3z)/?(x,z)

B•(Vx)(V>')P(x,y)vQ(x,z)A(3X)P(X,y)

C.(Vx)P(x)fQ(x))o(Vx)(-iP(x)vQ(x))

D・(土)尸(X)AQ(%Z)

()

A.PA^PB.PV(PAQ)

C.Pv—iPD・一i(Pv0Jf-iP/\—\Q

:个体域为自然数集；特定元素斫0;特定函数

f(x,y)=x+yfg(x,y)=xy；特定谓词"xj)为x=jo在赋值N

下，下列公式为真的是()

A・(Vx)F(g(x,a),x)

B・(Vx)(Vy)(F(/(x,a),y)->F(f(y,a),x))

C.(Vx)(Vy)(Vz)F(/(x,y),z)

D•(Vx)(Vy)F(f(x,y),g(x,y))

(Vx)(P(x,y)->Q(x,z))v0z)R(x,z)，下列说法正确的是()

C.(Vx)的辖域是(P(x,y)fQ(x,z))v0z)R(x,z)

D.(Vx)的辖域是P(XJ)

{1,2},与公式(3x)A(x)等价的是()

(l)vA(2)B.A(1)^A(2)

(1)D.42)-41)

+是正整数集合，/:Z+-Z+,/5)=2〃2则/()

()

rior100

A.oiiB.oii

100101

roofrior

C.001D.010

100100

,下列关于鸟㊉&的说法正确的是()

,下列构成独异点的是()

A.<A,+>B.<A,->

C.<A,X>D.<A,-?>

,下列说法正确的是()

A.<A,+>有零元B.<A,小>有零元

C.<A,+>有幺元D.<A,+>有幺元

()

,乘法对加法是可分配的

,加法对乘法是可分配的

，u对n是可分配的

，n对u是可分配的

()

题13图

,2个2度结点，其它的都是1度结点，那么这棵树的结

点数是

二、填空题(本大题共10小题，每小题2分，共20分)

请在每小题的空格中填上正确答案。错填、不填均

不得分。

，-------O

,其中每个变元与它的否定不能同时出现，但两者必须

_______O

，由(Vx)P(x)得到P(〃)，其中a为论域的某个个体，用的是

规则，记为规则。

〜v表示联结词人和联结词,O

={1,2,3,4},B={2,4,6},贝！IA-B=,

A㊉3=o

={1,2}上的一个等价关系,并给出其对应的划

分O

={1,2,3,4},A上的二元关系R={<1,2>,<2,3>,

<3,2>},S={<1,3>,<2,3>,<4,3>},贝!)RQS=,

(RT)」=o

<A,+,o>是域，则和都是交换群。

，它经过图中所有的，则称该图为汉密尔顿图。

，那么当时，扁是平面图，当时，扁是非

平面图。

三、计算题(本大题共6小题,每小题5分，共30分)

(QIP)6vR)fQ)的真值表。

⑷浦主析取范式。

二{1,2,3,4}，给定A上的二元关系

1?={<1,2>,<2,1>,<2,3>,<3,4>},求R的传递闭包。

g

b

题29图

30.求VZ7—{0},C的所有生成元及所有2阶、3阶子群,

其中凶为模7乘法。

，山之间长度为2的路径的数目。

Vlv2v3

题31图

四、证明题（本大题共3小题，第32小题8分，第33、

34小题各6分，共20分）

:PTQ、「Q7RfP八S）YO

33.设H是G的非空子集，贝k“，•＞是群＜G,•＞的子群

当且仅当对任意〃，儿“有a•bhHo

34.证明整数集Z上的大于等于关系”「是一个偏序关

系。

五、综合应用题（本大题共2小题，第35小题6分，第

36小题9分，共15分）

35.将下面命题符号化，并构造推理证明：

所有有理数是实数，有些有理数是整数，所以有些实数

是整数。

36.某城市拟在六个区之间架设有线电话网，其网点间

的距离如下列有权矩阵给出，请绘出有权图，给出架设

010290

104085

线路的最优方案，并计算线路的总长度。0403010

203076

980700

0510600

2010年4月高等教育自学考试全国统一命题考试

离散数学试题答案及评分参考

（课程代码02324）

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

1.D2.C3.A4.B5.A6.A7.D8.C9.B10.C

11.C12.B13.1314.A15.B

二、填空题(本大题共10小题,每小题2分，共20分)

16.PV(QAVQ)A(PV/?),PA(QVR)o(PAQ)V(PAX)

17.析取式，出现且出现一次18.全称指定，US

19.PAQor(rPVrQ),p—Q=rP\JQ20.|1,3),[1,3,6}

21.|<1,1>,<2,2>,<1,2>,<2,1},(或{<1,1>,<2,2>j,

{UIJ2H)•

22.J<2,3>|,|<2,1>,<2,3>|

23.<4,+>,<A-(0],o>24.回路，结点恰好一次

25*几经4,几n5

三、计算题(本大题共6小题,每小题5分，共30分)

26.

PQRQT。PYR(PVK)-Q(QTP)=((PVR)T。)

0001011

0011100

0100010

0110110

1001100

1011!00

1101111

11111I1

(每做对一列得1分,完成得5分，没完成最多得3分)

27：解4-((2二外•

orpV(QA幻V(rQArR)

0(rPA(rQVQ))V(QAR)V(r0ArR)

o(rPArQ)V(rpAQ)V(QAR)V(rQArR)..........(3分)

O(rPArQA(rRVH))VJPAQASVR))V((rPVP)AQ

离散数学试题答案及评分参考第1页(共4页)

AK)V((r，VP)ArQArR)

O(r/>八rQAR)V(r尸AQQAA))V(rpj\Q人rR)V(rPA

0A")V(PAQ八律)V(rPAf。ArR)V(PArQ八rR)

=(r/)ArQArR)V(rp人rQ人R))\j(rP[\Q'rR)\j(rP卜Q

A尺))V(/)ArQArR)V(PAQAR)

oZ(0,l,2,3,4,7)(2分)

第二种答案:，一（QHH）

V((Q-R)A(/?-Q))..................................(3分)

u>("ViQVR)A("VQV、R)

0n(5,6)

=2(0,1,2,3,4,7)(2分)

28.解:易知

/000\

1010

(1分)

0001

lo

000>

计算

ri010\ro1o八o10A

010100001

*2(3分)

000000000000

vo000>lo000；VO0007

得到“K)=R(J*U炉U尸I<1,1>,<1,2>,<],3>,<1,4>,

<2,1>,<2,2>,<2,3>,<2,4>,<3,4>|0.........(1分)

29.解:所有的5元子格如下:（3分）

（2分）

30.解」生成的子群为...........................................（1分）

2,4生成的子群为［2,4,1|,.......................................（1分）

3,5生成的子群为13,2,6,4,5,1|,................................（1分）

离散数学试题答案及评分参考第2页（共4页）

6生成的子群为｛6」］,(1分)

因此3,5为其生成元,2阶子群为|1,61,3阶子群为｛1,2,4、...........(1分)

(010111

10111

31.解:M(C)01011(2分)

11101

U1110>

计算

[32322)

24233

M?(C)=32322(2分)

23243

123234)

所以，图中结点巧，心之间反为2的路径有3条。.................(I分)

四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分'共20分)

32.证明：(1)PTQP

⑵rQVKP

(3)。一HT(2)£

(4)P-R7,(1),(3)/

⑸rKp

「(4),(5)/

(7)-(-PAS)P

(8)尸VrST(7)E

(9)r户一rST(8)£

(10)-5H6),(9)/

(每有效推理一步得1分，完成证明得8分，没完成证明最多得4分)

33.证明：必要性是显然的。..........................................(I分)

现证充分性:因为目非空，故有be",由已知条件则有小尸eH,即ee也

任取ae由e€H,ae”,则有

e'a-1=a_1wH............................................(3分)

任意a,bE〃，类似上面证明有U'G"，由已知条件得

11

a,(/＞)=a•bG.H

已知凡是C的非空子集，由上将证＜”,•＞是群＜C,,＞的子群。……(2分)

34.证明：(1)自反性:显然，Vae3均有a关系“N”具有自反性。……(2分)

(2)反对称性：Va,b号Z,若有a26且6Na,则有a=/＞,关系“二”具有反对称

性。...........................................................(2分)

(3)传递性：Va,b,ceZ,若有aMb且b〉c,则有aNc,关系“三”具有传递性。

绦上，关系“N”具有自反性、反对称性和传递性，因此它是偏序关系。……(2分)

离散数学试题答案及评分参考第3页(共4页)

五、综合应用感（本大题共2小题，第35小题6分，第36小题9分，共15分）

35.证明:令K（X）：H是实数,Q⑷:工是有理数,/（*）：%是整数。............(1分)

前提：（VQ（Q（公一曲幻）

（3X）（＜2（X）A/（H））

结论：（三工）（口动A/（工））.......................................(2分)

证明如下：

(1)(九)(Q(x)A/(»))P

(2)Q(a)A/(a)£5(1)

⑶Q(a)T⑵I

(4)(Vx)((?(x)->«(«))P

⑸Q(a)-R(a)US(4)

(6)R(a)?,(3),⑸/

(7)/(«)T(2)I

(8)R(a)A/(a)「⑹，(7”

(9)(3x)(/?(x)A/(吟)EC(8)....................................(3分)

36.解：由有权矩阵可得到有权图如下:

.............................................................................(3分)

为求线路的最优方案，我们求其最小生成树如下：

最优方案如上面最后一图所示，其线路总长度为18。..................（6分）。

离散数学试题答案及评分参考第4页（共4页）

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

课程代码：02324

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

分)

在每小题列出的四个备选项中只有一个是符合题目要

求的,请将其代码填写在题后的括号内。错选、多选或

未选均不得分。

1.设P:他用功，。:他成绩好，命题“只有他用功，他成绩才好”的符号化正确的是【]

A.P—QB.PVQC.rPVrQD.QTP

2.下列命题公式是永真式的是【]

A.PVrQB.(PrrQ)VPC.PV(r尸八Q)D.r(PVQ)\/Q

3.下列等价式第候的是[]

A.->(3x)A(x)<=>(A(x)

B.(3x)(A(x)VB(%))0(Bx)A(x)V(3x)B(x)

C.(3x)(4A5(《))o4A(3x)B(x)

D.A—►(3x)B(x)<=>(3%)(A—►B(x))

4.设4Q)：%是实数,3(%)：x是有理数，命题”有的实数是有理数"符号化为【]

A.(3x)(A(x)-8(%))B.(3%)(A(x)V8(%))

C.(3x)(A(x)AB(x))D.1(Vx)(A(x)A-1B(x))

5.设X={a,E,{a,㈤1},则下列陈述承送的是【1

A.\a\eXB.|a|CXC.|a,{a||CXD.||a||eX

6.设4U8=4,则有【]

A.4-B=0B.B-4=0C.B=0D.ACB

7.设4=10,|0}},则其塞集。(4)的元素总个数为【1

A.OB.1C.2D.4

8.在整数集Z上，下列定义的运算满足结合律的是【】

A.a*6=Ia-6lB.a*6=3a+6

C.a*6-ab-\D.a*6=2ab

9.在整数集Z上,下列定义的运算能构成一个群的是【】

A.a♦6=maxja,6|B・a*b=a-b

C.a*6=a+6+lD.a*6=

12.下列无向图一定是树的是【】

A.连通图B.无回路但添加一条边则有回路的图

C.每对结点之间都有通路的图D.有n个结点小-1条边的图

13.设与，均是4上的两个关系，则下列描述错误的是【】

A.s(&U/?2)=s(R])US(R2)B.s(R]Di?2)=s(%)Cs(/?2)

C.t(RtUR2)=MR)Ut(R2)D.“R|nR2)Cn：(«2)

14.以下必为欧拉图的是[]

A.结点度数都是偶数的连通图B.奇数度结点最多2个的连通图

C.存在欧拉路的图D.无回路的连通图

15.设/=|a|，下列关于代数系统＜P(X),U＞的陈述正确的是【】

A.a是么元B.X是么元C.0是么元D.没有么元

二、填空题(本大题共10小题，每小题2分，共20分)

16设眸触矍黑黜黜

不得的s|1,2,3,4,5|上的两个关系，则R。S=

S»R=o

17.命题公式P-(尸AQ)的成真指派为成假指派为。

18.公式(三工)(Vz)(P(%y)/\Q(z))VR(z)的约束变元为自由变元

为O

19.设4=\2,a],B="，2,3},则4㊉8=A®0=。

20.设/(工)=2-g(x)=2x+1,那么复合函数(Ag)G)=,

(g°/)(«)=o

21.整数集Z中的运算*定义如下：a*b=a+b-3ab,则*运算的单位元为

；设。有逆元，则其逆元屋'为O

22.<Z“，㊉>是一个群，其中Z.=!0,1,2,--,n-11,=(x+y)modn,则在

<Z*㊉>中，1的阶为,9的阶为o

23.K.是n个结点的完全图，则Kg边数为每个结点的度

数为O

24.如题24图所示的格中,6的补元是,c的补元是。

25.设4=|<2,2>,<3,5>,<3,4>[,B=|<1,3>,<2,5>,

<3,4)],那么dom(4DB)=,

ran(AUB)=o

题24图

三、计算题(本大题共5小题,每小题6分，共30分)

26.设集合4=|0,|a,A||,B=|a,|0||,P(A),P(B)为其骞集，计算P(4)DP(B)O

27.构造命题公式(PVrQ)—(PAR)的真值表。

28.设R=|<1,1>,<1,3>,<2,1>,<2,2>,<3,3>,<4,3>,<4,4>|

是4=|1,2,3,41上的二元关系。

(1)画出K的关系图；(2)写出K的关系矩阵；(3)说明R是否具有自反、反自反、对称、

反对称性质。

29.求公式r(PT(QAR))的主析取范式和主合取范式。

30.设4=!1,2,3,6,9,18!,<为整除关系。

(1)画出<A,W>的哈斯图；(2)求子集8=|3,6,9|的极大元、极小元、最大元、最小

7Go

四、证明题(本大题共3小题,每小题7分，共21分)

31.设<G,*>是一个群，a,bEGo

证明:必存在惟一的工eG,使x*a=bo

32.设4:|<a,6>1a,6为正整数｝，在4上定义二元关系~如下：<a,6>~<c,d>

当且仅当ab=cdo

证明：~是一个等价关系。

33.设图G有n个结点,2m条边,且存在度数为3的结点。

证明：G中至少有一个结点度数N5。

五、综合应用题(本大题共2小题，每小题7分，共14分)

34.构造下列推理的证明。如果天气很好并且他没去公司，他必去钓鱼。如果他去公司，他会

乘1路公交车。今天天气很好。他没有乘1路公交车。所以他去钓鱼。

35.今布a,b,c,d,ej,g1人，已知下列事实:《会讲德语和汉语;6会讲英语和汉语;c会讲俄

语和英语;d会讲日语和汉语;e会讲德语；/会讲法语