2020年自考離散數(shù)學(xué)02324真題含答案44版

2020年自考離散數(shù)學(xué)02324真題含

答案44版

全國4月自學(xué)考試離散數(shù)學(xué)試題（附答案）

課程代碼：02324

一、單項選擇題（本大題共15小題，每小題1分，共15

分）

在每小題列出的四個備選項中只有一個是符合題目

要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、

多選或未選均無分。

1.下列為兩個命題變元P,Q的小項是（）

A.PAQA1PB.1PVQ

C.1PAQD.1PVPVQ

2.下列語句中是真命題的是（）

A.我正在說謊B.嚴禁吸煙

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

雪是黑的

3.設(shè)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}上的關(guān)系R={?,J>|X+J=10,

xEA,y《A},則R的性質(zhì)是（）

A.自反的B.對稱的

C.傳遞的、對稱的D.反自反的、傳遞的

8.若R和S是集合A上的兩個關(guān)系，則下述結(jié)論正確

的是（）

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.設(shè)人={{1,2,3},{4,5},{6,7,8}）,下列選項正

確的是（）

A.leAB.{1,2,3bA

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

11.在自然數(shù)集N上，下列運算是可結(jié)合的是（）

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

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

12.在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系是（）

A.整環(huán)一定是域B.域不一定是整環(huán)

C,域一定是整環(huán)D,域一定不是整環(huán)

13.下列所示的哈斯圖所對應(yīng)的偏序集中能構(gòu)成格的是

14.設(shè)G為有〃個結(jié)點的簡單圖，則有（）

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

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

15.具有4個結(jié)點的非同構(gòu)的無向樹的數(shù)目是（）

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.設(shè)N是自然數(shù)集合，/和g是N到N的函數(shù)，且/

2

(〃)=2n+lfg(w)=n,那么復(fù)合函數(shù)(/o/)(〃)

=(go/)(n)=o

19.設(shè)復(fù)合函數(shù)g。/是從A到C的函數(shù),如果g。/是滿射，

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

必是入射。

20.設(shè)A={1,2},B={2,3},則A-A=,

A-B=o

21.設(shè)S是非空有限集，代數(shù)系統(tǒng)VP(S),U＞中，其中

P(S)為集合S的嘉集，則P(S)對U運算的單位

元是，零元是O

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

23.設(shè)vA,是格，其中A={1,2,3,4,6,8,12,

24),《為整除關(guān)系，則3的補元是o

24.在下圖中，結(jié)點電的度數(shù)是______o

V}

°2

V3

為(y---------式)為

題24圖

25.設(shè)圖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.構(gòu)造命題公式((PAQ)fP)VR的真值表。

28.下圖給出了一個有向圖。(1)求出它的鄰接矩陣A；

(2)求出A?,A3,A，及可達矩陣P。

力4

。3

題28圖

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

(QV(]QfR)))

30.設(shè)人={1,2,3,4,6,8,12,24},R為A上的整

除關(guān)系，試畫vA,R＞的哈斯圖，并求A中的最大元、最

小元、極大元、極小元。

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

第33小題8分，共20分)

31.在整數(shù)集Z上定義Za°b=a+b-2,Va,beZ，證明:VZ,。＞是一

個群。

32.R是集合A上自反和傳遞的關(guān)系，試證明:R°R=R。

33.證蜂邊e是圖G的一條割邊，當且僅當圖G中不存

在包含邊e的簡單回路。

五、應(yīng)用題（本大題共2小題，第34小題6分，第35

小題9分，共15分）

34.構(gòu)造下面推理的證明。

如果小張和小王去看電影，則小李也去看電影。小

趙不去看電影或小張去看電影。小王去看電影。所

以，當小趙去看電影時，小李也去。

35.今有〃個人，已知他們中任何2人的朋友合起來一

定包含其余n-2人。試證明：

（1）當〃23時，這〃個人能排成一列，使得中間

任何人是其兩旁的人的朋友，而兩頭的人是其

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

（2）當〃24時，這〃個人能排成一圓圈，使得每

個人是其兩旁的人的朋友。

2009年4月高等教育自學(xué)考試全國統(tǒng)一命題考試

離散數(shù)學(xué)試題答案及評分參考

（課程代碼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.

離散數(shù)學(xué)試題答案及評分參考第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.證明:顯然?是二元運算,根據(jù)群的定義，需證明運算滿足結(jié)合律、有單位元和每個

元素有逆元。

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),結(jié)合律成立。(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,由關(guān)系復(fù)合的定義，存在”A,使得〈明力6R,(,v.;)6R.

因R傳遞，有GMeR,可得RoRUR。(3分)

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

RCR.Ro

綜合可得RoR=R。證畢。(3分)

離散數(shù)學(xué)試題答案及評分參考第2頁(共3頁)

33.證明："）充分性,設(shè)圖C的邊e=（u,u）不包含在G的任一條簡單何路中,則u,u

之間除c外無任何通路.否則.若間存在另一條通路，那么加上邊（，就

形成一條回路，這與題意矛盾。因此，去掉邊％則G不連通，故e為G的

割邊「（4分）

（2）必要性。設(shè)邊c是G的割邊,e包含在某一條簡單回路中，刪去e則不影

響G的連通性，這與e是割邊矛盾.所以?不包含在C的任何茴單回路

中，（4分）

五、應(yīng)用題（本大題共2小題，第34小題6分，第35小題9分,共15分）

34.解：令P：小張去看電影,Q：小王去看電影，R：小李去看電影，S：小趙去看電影

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

結(jié)論:S-R（2分）

證明:用“規(guī)則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）（；中存在漢密爾頓通道，.也

路上的人按在通路中的順序排成一列.滿足要求.當〃學(xué)4時,由①式與③

式可知（定理5.4.5）C中存在漢密爾頓回路，回路L的人按在回路中的

牘序排成圓圈滿足要求.（2分）

離散數(shù)學(xué)試題答案及評分參考第3頁（共3頁）

全國4月自學(xué)考試離散數(shù)學(xué)試題

課程代碼：02324

一、單項選擇題(本大題共15小題，每小題1分，共15

分)

在每小題列出的四個備選項中只有一個是符合題目

要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、

多選或未選均不得分。

()

!=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

:個體域為自然數(shù)集；特定元素斫0;特定函數(shù)

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)

+是正整數(shù)集合，/:Z+-Z+,/5)=2〃2則/()

()

rior100

A.oiiB.oii

100101

roofrior

C.001D.010

100100

,下列關(guān)于鳥十&的說法正確的是()

,下列構(gòu)成獨異點的是()

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

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

,下列說法正確的是()

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

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

()

,乘法對加法是可分配的

,加法對乘法是可分配的

，u對n是可分配的

，n對u是可分配的

()

題13圖

,2個2度結(jié)點，其它的都是1度結(jié)點，那么這棵樹的結(jié)

點數(shù)是

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

請在每小題的空格中填上正確答案。錯填、不填均

不得分。

，-------O

,其中每個變元與它的否定不能同時出現(xiàn)，但兩者必須

_______O

，由(Vx)P(x)得到P(〃)，其中a為論域的某個個體，用的是

規(guī)則，記為規(guī)則。

?v表示聯(lián)結(jié)詞人和聯(lián)結(jié)詞,O

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

A十3=o

={1,2}上的一個等價關(guān)系,并給出其對應(yīng)的劃

分O

={1,2,3,4},A上的二元關(guān)系R={<1,2>,<2,3>,

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

(RT)」=o

<A,+,o>是域，則和都是交換群。

，它經(jīng)過圖中所有的，則稱該圖為漢密爾頓圖。

，那么當時，扁是平面圖，當時，扁是非

平面圖。

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

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

⑷浦主析取范式。

二{1,2,3,4}，給定A上的二元關(guān)系

1?={<1,2>,<2,1>,<2,3>,<3,4>},求R的傳遞閉包。

g

b

題29圖

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

其中兇為模7乘法。

，山之間長度為2的路徑的數(shù)目。

Vlv2v3

題31圖

四、證明題（本大題共3小題，第32小題8分，第33、

34小題各6分，共20分）

:PTQ、「Q7RfP八S）YO

33.設(shè)H是G的非空子集，貝k“，?＞是群＜G,?＞的子群

當且僅當對任意〃，兒“有a?bhHo

34.證明整數(shù)集Z上的大于等于關(guān)系”「是一個偏序關(guān)

系。

五、綜合應(yīng)用題（本大題共2小題，第35小題6分，第

36小題9分，共15分）

35.將下面命題符號化，并構(gòu)造推理證明：

所有有理數(shù)是實數(shù)，有些有理數(shù)是整數(shù)，所以有些實數(shù)

是整數(shù)。

36.某城市擬在六個區(qū)之間架設(shè)有線電話網(wǎng)，其網(wǎng)點間

的距離如下列有權(quán)矩陣給出，請繪出有權(quán)圖，給出架設(shè)

010290

104085

線路的最優(yōu)方案，并計算線路的總長度。0403010

203076

980700

0510600

2010年4月高等教育自學(xué)考試全國統(tǒng)一命題考試

離散數(shù)學(xué)試題答案及評分參考

（課程代碼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.析取式，出現(xiàn)且出現(xiàn)一次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.回路，結(jié)點恰好一次

25*幾經(jīng)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

離散數(shù)學(xué)試題答案及評分參考第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分）

離散數(shù)學(xué)試題答案及評分參考第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)

所以，圖中結(jié)點巧，心之間反為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分)

現(xiàn)證充分性:因為目非空，故有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關(guān)系“N”具有自反性?！?2分)

(2)反對稱性：Va,b號Z,若有a26且6Na,則有a=/＞,關(guān)系“二”具有反對稱

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

(3)傳遞性：Va,b,ceZ,若有aMb且b〉c,則有aNc,關(guān)系“三”具有傳遞性。

絳上，關(guān)系“N”具有自反性、反對稱性和傳遞性，因此它是偏序關(guān)系?！?2分)

離散數(shù)學(xué)試題答案及評分參考第3頁(共4頁)

五、綜合應(yīng)用感（本大題共2小題，第35小題6分，第36小題9分，共15分）

35.證明:令K（X）：H是實數(shù),Q⑷:工是有理數(shù),/（*）：%是整數(shù)。............(1分)

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

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

結(jié)論：（三工）（口動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.解：由有權(quán)矩陣可得到有權(quán)圖如下:

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

為求線路的最優(yōu)方案，我們求其最小生成樹如下：

最優(yōu)方案如上面最后一圖所示，其線路總長度為18。..................（6分）。

離散數(shù)學(xué)試題答案及評分參考第4頁（共4頁）

全國4月自學(xué)考試離散數(shù)學(xué)試題

課程代碼：02324

一、單項選擇題(本大題共15小題，每小題1分，共15

分)

在每小題列出的四個備選項中只有一個是符合題目要

求的,請將其代碼填寫在題后的括號內(nèi)。錯選、多選或

未選均不得分。

1.設(shè)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.設(shè)4Q)：%是實數(shù),3(%)：x是有理數(shù)，命題”有的實數(shù)是有理數(shù)"符號化為【]

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.設(shè)X={a,E,{a,㈤1},則下列陳述承送的是【1

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

6.設(shè)4U8=4,則有【]

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

7.設(shè)4=10,|0}},則其塞集。(4)的元素總個數(shù)為【1

A.OB.1C.2D.4

8.在整數(shù)集Z上，下列定義的運算滿足結(jié)合律的是【】

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

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

9.在整數(shù)集Z上,下列定義的運算能構(gòu)成一個群的是【】

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

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

12.下列無向圖一定是樹的是【】

A.連通圖B.無回路但添加一條邊則有回路的圖

C.每對結(jié)點之間都有通路的圖D.有n個結(jié)點小-1條邊的圖

13.設(shè)與，均是4上的兩個關(guān)系，則下列描述錯誤的是【】

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.結(jié)點度數(shù)都是偶數(shù)的連通圖B.奇數(shù)度結(jié)點最多2個的連通圖

C.存在歐拉路的圖D.無回路的連通圖

15.設(shè)/=|a|，下列關(guān)于代數(shù)系統(tǒng)＜P(X),U＞的陳述正確的是【】

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

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

16設(shè)眸觸矍黑黜黜

不得的s|1,2,3,4,5|上的兩個關(guān)系，則R。S=

S?R=o

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

18.公式(三工)(Vz)(P(%y)/\Q(z))VR(z)的約束變元為自由變元

為O

19.設(shè)4=\2,a],B="，2,3},則4十8=A?0=。

20.設(shè)/(工)=2-g(x)=2x+1,那么復(fù)合函數(shù)(Ag)G)=,

(g°/)(?)=o

21.整數(shù)集Z中的運算*定義如下：a*b=a+b-3ab,則*運算的單位元為

；設(shè)。有逆元，則其逆元屋'為O

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

<Z*十>中，1的階為,9的階為o

23.K.是n個結(jié)點的完全圖，則Kg邊數(shù)為每個結(jié)點的度

數(shù)為O

24.如題24圖所示的格中,6的補元是,c的補元是。

25.設(shè)4=|<2,2>,<3,5>,<3,4>[,B=|<1,3>,<2,5>,

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

ran(AUB)=o

題24圖

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

26.設(shè)集合4=|0,|a,A||,B=|a,|0||,P(A),P(B)為其騫集，計算P(4)DP(B)O

27.構(gòu)造命題公式(PVrQ)—(PAR)的真值表。

28.設(shè)R=|<1,1>,<1,3>,<2,1>,<2,2>,<3,3>,<4,3>,<4,4>|

是4=|1,2,3,41上的二元關(guān)系。

(1)畫出K的關(guān)系圖；(2)寫出K的關(guān)系矩陣；(3)說明R是否具有自反、反自反、對稱、

反對稱性質(zhì)。

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

30.設(shè)4=!1,2,3,6,9,18!,<為整除關(guān)系。

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

7Go

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

31.設(shè)<G,*>是一個群，a,bEGo

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

32.設(shè)4:|<a,6>1a,6為正整數(shù)｝，在4上定義二元關(guān)系~如下：<a,6>~<c,d>

當且僅當ab=cdo

證明：~是一個等價關(guān)系。

33.設(shè)圖G有n個結(jié)點,2m條邊,且存在度數(shù)為3的結(jié)點。

證明：G中至少有一個結(jié)點度數(shù)N5。

五、綜合應(yīng)用題(本大題共2小題，每小題7分，共14分)

34.構(gòu)造下列推理的證明。如果天氣很好并且他沒去公司，他必去釣魚。如果他去公司，他會

乘1路公交車。今天天氣很好。他沒有乘1路公交車。所以他去釣魚。

35.今布a,b,c,d,ej,g1人，已知下列事實:《會講德語和漢語;6會講英語和漢語;c會講俄

語和英語;d會講日語和漢語;e會講德語；/會講法語