第一篇：離散數(shù)學(xué)期末考試試題及答案

離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。下面是小編整理的離散數(shù)學(xué)期末考試試題及答案，歡迎閱讀參考！

一、【單項(xiàng)選擇題】

(本大題共15小題，每小題3分，共45分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在答題卷相應(yīng)題號(hào)處。

1、在由3個(gè)元素組成的集合上，可以有()種不同的關(guān)系。

[A] 3 [B] 8 [C]9 [D]272、設(shè)A1,2,3,5,8,B1,2,5,7,則AB()。

[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，則一定有()。

[A]X不屬于Y [B]X∈Y

[C]X真包含于 Y [D]X∩Y=X4、下列關(guān)系中是等價(jià)關(guān)系的是()。

[A]不等關(guān)系 [B]空關(guān)系

[C]全關(guān)系 [D]偏序關(guān)系

5、對(duì)于一個(gè)從集合A到集合B的映射，下列表述中錯(cuò)誤的是()。

[A]對(duì)A的每個(gè)元素都要有象 [B] 對(duì)A的每個(gè)元素都只有一個(gè)象

[C]對(duì)B的每個(gè)元素都有原象 [D] 對(duì)B的元素可以有不止一個(gè)原象

6、設(shè)p:小李努力學(xué)習(xí)，q:小李取得好成績(jī)，命題“除非小李努力學(xué)習(xí)，否則他不能取得好成績(jī)”的符號(hào)化形式為()。

[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、設(shè)A={a,b,c},則A到A的雙射共有()。

[A]3個(gè) [B]6個(gè) [C]8個(gè) [D]9個(gè)

8、一個(gè)連通G具有以下何種條件時(shí)，能一筆畫(huà)出：即從某結(jié)點(diǎn)出發(fā)，經(jīng)過(guò)中每邊僅一次回到該結(jié)點(diǎn)()。

[A] G沒(méi)有奇數(shù)度結(jié)點(diǎn) [B] G有1個(gè)奇數(shù)度結(jié)點(diǎn)

[C] G有2個(gè)奇數(shù)度結(jié)點(diǎn) [D] G沒(méi)有或有2個(gè)奇數(shù)度結(jié)點(diǎn)

9、設(shè)〈G,*〉是群，且|G|>1，則下列命題不成立的是()。

[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外無(wú)其他冪等元

10、令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為()

[A] p→┐q [B] p∨┐q

[C] p∧q [D] p∧┐q11、設(shè)G=的結(jié)點(diǎn)集為V={v1,v2,v3},邊集為E={,}.則G的割(點(diǎn))集是()。

[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}

12、下面4個(gè)推理定律中，不正確的為()。

[A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段論)

[C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式)

13、在右邊中過(guò)v1,v2的初級(jí)回路有多少條()

[A] 1 [B] 2 [C] 3 [D]

414、若R，是環(huán)，且R中乘法適合消去律，則R是()。

[A]無(wú)零因子環(huán)

[C]整環(huán) [B]除環(huán) [D]域

15、無(wú)向G中有16條邊，且每個(gè)結(jié)點(diǎn)的度數(shù)均為2，則結(jié)點(diǎn)數(shù)是()。

[A]8 [B]16 [C]4 [D]

32二、【判斷題】

(本大題共8小題，每小題3分，共24分)正確的填T，錯(cuò)誤的填F，填在答題卷相應(yīng)題號(hào)處。

16、是空集。()

17、設(shè)S,T為任意集合，如果S—T=，則S=T。()

18、在命題邏輯中，任何命題公式的主合取范式都是存在的，并且是唯一的。()

19、關(guān)系的復(fù)合運(yùn)算滿足交換律。()

20、集合A上任一運(yùn)算對(duì)A是封閉的。()

21、0,1,2,3,4,max,min是格。()

22、強(qiáng)連通有向一定是單向連通的。()

23、設(shè)都是命題公式，則(PQ)QP。()

三、【解答題】

(本大題共3小題，24、25每小題10分，26小題11分，共31分)請(qǐng)將答案填寫(xiě)在答題卷相應(yīng)題號(hào)處。

24、設(shè)集合A={a, b, c}，B={b, d, e}，求

(1)BA;(2)AB;(3)A-B;(4)BA.25、設(shè)非空集合A，驗(yàn)證(P(A)，,~，A)是布爾代數(shù)

26、如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過(guò)DELPHI語(yǔ)言而且學(xué)過(guò)C++語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)言或者C++語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。

離散數(shù)學(xué)試題答案

一、【單項(xiàng)選擇題】(本大題共15小題，每小題3分，共45分)

BDDCCCBABDADCBB

二、【判斷題】(本大題共8小題，每小題3分，共24分)

FFTFTTTF

三、【解答題】(本大題共3小題，24、25每小題10分，26小題11分，共31分)

24、設(shè)集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.標(biāo)準(zhǔn)答案：(1)BA={a, b, c}{b, d, e}={ b }

(2)AB={a, b, c}{b, d, e}={a, b, c, d, e }

(3)A-B={a, b, c}-{b, d, e}={a, c}

(4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e }

復(fù)習(xí)范圍或考核目標(biāo)：考察集合的基本運(yùn)算，包括交集，并集,見(jiàn)課件第一章第二節(jié),集合的運(yùn)算。

25、設(shè)非空集合A，驗(yàn)證(P(A)，,~，A)是布爾代數(shù)

標(biāo)準(zhǔn)答案：證明 因?yàn)榧螦非空，故P(A)至少有兩個(gè)元素，顯然，是P(A)上的二元運(yùn)算.由定理10，任給B,C,DP(A), H1 BD=DC CD=DC

H2 B(CD)=(BC)(BD)B(CD)=(BC)(BD)

H3 P(A)存在和A，BP(A), 有B=B，BA=B

H4，BP(A), BA，存在A~B，有

BA~B)= A B(A～B)=

所以(P(A)，,~，A)是布爾代數(shù).復(fù)習(xí)范圍或考核目標(biāo)：考察布爾代數(shù)的基本概念，集合的運(yùn)算，見(jiàn)課件代數(shù)系統(tǒng)中布爾代數(shù)小節(jié)。

26、如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過(guò)DELPHI語(yǔ)言而且學(xué)過(guò)C++語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)言或者C++語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。

標(biāo)準(zhǔn)答案：令p：他是計(jì)算機(jī)系本科生

q：他是計(jì)算機(jī)系研究生 r：他學(xué)過(guò)DELPHI語(yǔ)言

s:他學(xué)過(guò)C++語(yǔ)言

t:他會(huì)編程序

前提：(p∨q)→(r∧s),(r∨s)→t

結(jié)論：p→t

證①p P(附加前提)

②p∨q T①I(mǎi)

③(p∨q)→(r∧s)P(前提引入)

④r∧s T②③I

⑤r T④I

⑥r(nóng)∨s T⑤I

⑦(r∨s)→t P(前提引入)

⑧t T⑤⑥I

第二篇：離散數(shù)學(xué)期末考試

一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）

1、設(shè)集合M={a，?}，N ={{a}，?}則M?N=（）。A、? B、{?} C、{a} D、{{a}，?，a}

2、設(shè)關(guān)系F={<1，a >，<2，2>，}，G={，，<1，2>}則 F?G=（）。

A、{<1，b>，<1，c>，}

B、{，，<1，b>} C、{，<1，2>}

D、{，<2，2>，<1，b>}

3、設(shè)集合H={1，2，3，4}，則H上的關(guān)系R={

。x +y是偶數(shù)}具有（）A、自反性、反對(duì)稱性和傳遞性

B、反自反性、反對(duì)稱性和傳遞性

C、反自反性、對(duì)稱性和傳遞性

D、自反性、對(duì)稱性和傳遞性

4、設(shè)T是一棵完全二叉樹(shù)，則T的每個(gè)結(jié)點(diǎn)都（）。

A、至少有兩個(gè)子結(jié)點(diǎn)

B、至多有兩個(gè)子結(jié)點(diǎn)

C、恰有兩個(gè)子結(jié)點(diǎn)

D、可以有任意多個(gè)子結(jié)點(diǎn)

5、設(shè)R是實(shí)數(shù)集，“+，—，A、

?>是群

B、是群

? >是半群

D、是獨(dú)異點(diǎn)

6、下面關(guān)系中，函數(shù)關(guān)系是（）。

A、{，，}

B、{，，<1，x>} C、{<1，y>，<1，x>，}

D、{，，}

7、設(shè)是一個(gè)代數(shù)系統(tǒng)，若多任意的x，y?S，都有x?y=y?x，則稱運(yùn)算?在S上滿足（）。

A、結(jié)合律

B、交換律

C、分配律

D、冪等律

8、設(shè)Z是整數(shù)集，“—”是整數(shù)減法，則下列說(shuō)法正確的是（）。A、不是代數(shù)系統(tǒng)

B、的單位元是0

C、是代數(shù)系統(tǒng)

D、的單位元是1

9、設(shè)L是無(wú)向圖G中的一條通路，L中的頂點(diǎn)各不相同，則L是一條（）。A、簡(jiǎn)單通路

B、初級(jí)通路

C、簡(jiǎn)單回路

D、初級(jí)回路

10、設(shè)G有6個(gè)3度點(diǎn)，2個(gè)4度點(diǎn)，其余頂點(diǎn)的度數(shù)均為0，則G的邊數(shù)是（）。A、10

B、13

C、11

D、6

二、填空題(本大題共8題，共10個(gè)空，每空2分，共20分)

1、設(shè)關(guān)系R={，<2，1>，<2，b>}，則R逆關(guān)系R?1=_______________________________。

2、在代數(shù)系統(tǒng)（Q是有理數(shù)集，“+”是有理數(shù)加法）中，單位元是______，2的逆元是___________。

3、設(shè)集合M={1，2，3，5}，則M的冪集P（M）包含___________個(gè)元素。

4、設(shè)T是一棵有n(n?2)個(gè)頂點(diǎn)的樹(shù)，則T有_____________條邊。

5、設(shè)是一個(gè)代數(shù)系統(tǒng)，?是S上的二元運(yùn)算，若存在??S，對(duì)任意x?S，有??x=x??=?，則稱?是的_______________。

6、設(shè)是一個(gè)代數(shù)系統(tǒng)，若?滿足結(jié)合律且中有單位元，則稱為一個(gè)___________________。

7、設(shè)D是有向圖，若D的基圖是連通圖，則稱D是_________________圖

8、既不含________________也不含____________________的無(wú)向圖稱為簡(jiǎn)單圖。

三、計(jì)算題(本大題共3小題，每小題10分，共30分)

1、用等值演算法求公式A=(p??q)?(p?r)的主析取范式。

2、求公式?x(Q(x)?G(x，s))?(?yP(y)??zH(y，z))的前束范式。

3、設(shè)集合A={1，2，3，4，5}，關(guān)系R={（1）列出R的所有元素；（2）寫(xiě)出R的關(guān)系矩陣Mx，y? A且x整除y}，要求：

R；

（3）求偏序集的極大元、極小元和最小元。

四、應(yīng)用題(本大題共2小題，每小題5分，共10分)

1、用命題公式將下列命題符號(hào)化： 2和5是偶數(shù)，當(dāng)且僅當(dāng)5>2。

2、用謂詞公式將下列命題符號(hào)化：

每個(gè)計(jì)算機(jī)專業(yè)的學(xué)生都要學(xué)《編譯原理》，但有些計(jì)算機(jī)專業(yè)的學(xué)生不學(xué)《經(jīng)濟(jì)學(xué)》。

五、證明題（本大題共2小題，每小題10分，共20分）

1、在命題邏輯系統(tǒng)中用歸結(jié)法證明下列推理是有效的： 前提：?s?q，p??q，s 結(jié)論：?p

2、在謂詞邏輯系統(tǒng)中寫(xiě)出下列推理的（形式）證明：

前提：?x(M(x)?P(x))，?x(M(x)?G(x))，?x(?G(x))結(jié)論：?xP(x)

計(jì)算題

6.設(shè)命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。

7.(9分)設(shè)一階邏輯公式：G =(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.9.設(shè)R是集合A = {a, b, c, d}.R是A上的二元關(guān)系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)畫(huà)出r(R), s(R), t(R)的關(guān)系圖.11.通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：

(1)G =(P∧Q)∨(?P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(?P∧R))13.設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝

{(a, b),(b, c),(b, d),(d, d)}.(1)試寫(xiě)出R和S的關(guān)系矩陣；(2)計(jì)算R?S, R∪S, R1, S1?R1.－

－

－證明題

1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。2.設(shè)A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D。4.(本題10分)A, B為兩個(gè)任意集合，求證：

A－(A∩B)=(A∪B)－B.答案：

1-5

BADBB 6-10 BBABB

1.{<1，a>，<1，2>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱連通 8.平行邊

環(huán) 三．

??(p??q)?(p?r)?(?p?q)?(p?r)1.?(?p?q?r)?(?p?q??r)?(p?q?r)?(p??q?r)?m011?m010?m111?m1012.??x(Q(x)?G(x,s))??y?z(P(y)?H(y,z))

??y?z?x((Q(x)?G(x,s))?(P(y)?H(y,z))3.(1)R?{?1,1?,?2,2?,?3,3?,?4,4?,?5,5?,?1,2?,?1,3?,?1,4?,?1,5?,?2,4?}

??1??2(2)MR???3?4???512345?11111??01010??

（3）最小元=1 極小元=1 極大元=5 00100?00010??00001??四

1.令p表示2是偶數(shù)；令q表示5是偶數(shù)；r表示5>2；

(p?q)?r

2.S（x）：x是計(jì)算機(jī)專業(yè)的學(xué)生；G（x）：x要學(xué)《編譯原理》； F（x）：x學(xué)經(jīng)濟(jì)學(xué)；

?x(S(x)?G(x))??x(S(x)??F(x))

五 1，（1）

s

前提引入（2）

?s?q

前提引入（3）

q??s

置換規(guī)則

（4）

q

1,3析取三段論（5）

p??q

前提引入（6）

?p

4,5拒取

（1）

?x(M(x)?G(x))

前提引入（2）

M（x）v G（x）

EI規(guī)則（3）

?x(?G(x))

前提引入（4）

?G(x)（5）

M(x)

AI規(guī)則

2,4析取三段論

（6）

?x(M(x)?P(x))

前提引入（7）

M(x)→P（x）

AI規(guī)則（8）

P（x）

5,7假言推理（9）

?xP(x)

EG規(guī)則

6.G = ?(P→Q)∨(Q∧(?P→R))

= ?(?P∨Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧P)∨(Q∧R)=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = ?(3, 4, 5, 6, 7).7.G =(?xP(x)∨?yQ(y))→?xR(x)

= ?(?xP(x)∨?yQ(y))∨?xR(x)=(??xP(x)∧??yQ(y))∨?xR(x)=(?x?P(x)∧?y?Q(y))∨?zR(z)= ?x?y?z((?P(x)∧?Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)

關(guān)系圖: abr(R)dcabs(R)dabt(R)dc c

11.G＝(P∧Q)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)＝m6∨m7∨m3 ＝?(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(?P∧R))＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝?(3, 6, 7)G,H的主析取范式相同，所以G = H.?1?013.(1)MR???0??0000011000??0?00??

MS??1??0??0??0100001000?1?? 0??1?(2)R?S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1?R1＝{(b, a),(d, c)}.－－四 證明題

1.證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S

(1)P∨R

(2)?R→P(3)P→Q(4)?R→Q(5)?Q→R(6)R→S

P Q(1)P Q(2)(3)Q(4)P

(7)?Q→S(8)Q∨S Q(5)(6)Q(7)2.證明：(A-B)-C =(A∩~B)∩~C

3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D(1)A D(附加)P(2)?A∨B(3)B Q(1)(2)P Q(4)(4)?C→?B(5)B→C(6)C

Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D

所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D.1.證明：A－(A∩B)

= A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝?∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪? = A－B 所以：A－(A∩B)=(A∪B)－B.

第三篇：離散數(shù)學(xué)期末復(fù)習(xí)試題及答案(二)

第二章 二元關(guān)系

1.設(shè)A={1,2,3,4},A上二元關(guān)系

R={(a,b)|a=b+2}，S={(x,y)|y=x+1 or y=

x2} 求R?S,S?R,S?R?S,S2,S

3,S?Rc。

R?S={(3,2),(4,3),(4,1)} S?R={(2,1),(3,2)} S?R?S={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} S?Rc={(1,4),(2,3),(4,4)}

2．A={a,b,c,d,e,f,g,h}，給定A上關(guān)系R的 關(guān)系圖如下：

圖3－14 求最小正整數(shù)ｍ，ｎ，ｍ＜ｎ，使Ｒm＝Ｒn。

Ｒ1＝Ｒ16

這是因?yàn)镽15是8個(gè)頂點(diǎn)以及8個(gè)自回路，相 當(dāng)于左圖的點(diǎn)各走了5圈，左圖的點(diǎn)各走了3圈，R16就成了原來(lái)的R．

３．證明：

(1)(InA)?IA?(a,a)?I2nA,a?A,(a,a)?IA,...,(a,a)?IA, ?(b,b)?InA,b?A,(b,b)?IA.(2)IA?R?R?IA?R?(a,b)?R,?a,b?A,(a,a)?IA,(b,b)?IA,?(a,b)?IA?R,(a,b)?R?IA,即R?I

A?R,R?R?IA;?(a,b)?IA?R,若(a,b)?R,則(a,b)?IA?R,矛盾,得IA?R?R;同理,R?IA?R.事實(shí)上，當(dāng)|A|有限時(shí)，R與IA復(fù)合，相當(dāng)于矩陣與 單位矩陣相乘，不會(huì)變化。

(3)(R?In2nA)?IA?R?R?...?Rn?1(R?IA)?IA?R;設(shè)(R?Ik2A)?IA?R?R?...?Rk

(R?Ik?1?(I2A)...?RkA?R?R?)(R?IA)?(R?R2?...?Rk?1)?(I2A?R?R?...?Rk)?I?R2?...?Rk?Rk?1A?R

４．判斷下列等式是否成立（Ｒ,Ｒ1,Ｒ2均是Ａ到Ｂ的 二元關(guān)系）

(1)(Rccc1?R2)?R1?R2對(duì),(a,b)?(Rc1?R2)?(b,a)?R1?R2?(b,a)?R

1or(b,a)?R2?(a,b)?Rc1or(a,b)?Rc2?(a,b)?Rcc1?R2

(2)(Rcc1?R2)?R1?Rc2對(duì)(a,b)?(Rc1?R2)?(b,a)?R1?R2?(b,a)?R

1and(b,a)?R2?(a,b)?Rcc1and(a,b)?R2?(a,b)?Rcc1?R2

(3)(R1?R2)?R1?R2對(duì)cccc(a,b)?(R1?R2)?(R1?R2)c?(b,a)?R1?R2?(b,a)?R1,(b,a)?R2

?(a,b)?Rc1,(a,b)?Rc2?(a,b)?Rcccc1?R2?R1?R2(4)(A?B)c?A?B否,例:A?{1,2},B?{3,4},A?B?{(1,3),(2,3),(1,4),(2,4)}

(A?B)c?{(3,1),(3,2),(4,1),(4,2)}(5)?c??否,?c

與?的定義域,值域?qū)Q了一下.(6)(R)c?(Rc)對(duì),(a,b)?(R)c?(b,a)?R?(b,a)?R?(a,b)?Rc?(a,b)?Rc(7)(Rcc1?R2)?R2?Rc1否,R2的定義域不一定與R1的值域相同(8)如果Rcc1?R2,則R1?R2對(duì),?(a,b)?Rc1,(b,a)?R1?R2,(a,b)?Rc2.(9)如果R1?Rcc2,則R1?R2對(duì),?(a,b)?Rc1,(b,a)?R1?R2,(a,b)?Rc2，R1?R2,?(c,d)?R2,(c,d)?R1,(d,c)?Rc2,而(d,c)?Rc1..?

(10)R1?R2?R2?R1否,R

2的定義域不一定與R1的值域相同.5.設(shè)R1,R2是集合A上的二元關(guān)系，如果R2?R1，其中r,s,t分別是自反閉包，對(duì)稱閉包，傳遞閉包的 記號(hào)。試證明:(1)r(R2)?r(R1)?R2?R1,IA?IA, ?R2?IA?R1?IA

(2)s(R2)?s(R1)?R2?Rcc1,R2?R1

?Rcc2?R2?R1?R1

(3)t(R2)?t(R1)?R222?R1?(R2)1?(R1)1(即R2?R2?R1?R1)?(a,b)?R(a,b)?(R?2?R1?(R1)1b)?R22)1?(a,2,?c?A,(a,c),(c,b)?R2?R1,??(a,b)?R21,(a,b)?(R1)1?(a,b)?t(R2),?k,使(a,b)?(R2)k?(R1)k?t(R1).6.設(shè)R1,R2,R3,R4分別是A到B，B到C，B到C，Ｃ到D的二元關(guān)系，證明

(1)R1?(R2?R3)?R1?R2?R1?R3(x,y)?R1?(R2?R3)??z,(x,z)?R1,(z,y)?R2or(z,y)?R3??z,(x,z)?R1,(z,y)?R2or(x,z)?R

1,(z,y)?R3?(x,y)?R1?R2or(x,y)?R1?R3?(x,y)?R1?R2?R1?R3

(2)R1?(R2?R3)?R1?R2?R1?R3?(x,y)?R1?(R2?R3)??z,(x,z)?R1,(z,y)?R2and(z,y)?R3??z,(x,z)?R

1,(z,y)?R2and(x,z)?R1,(z,y)?R3?(x,y)?R1?R2and(x,y)?R1?R3?(x,y)?R1?R2?R1?R3(3)(4)類(1)(2)證明。

7.設(shè)R是A上的二元關(guān)系，證明對(duì)任意自然數(shù)m,n，(1)Rm?Rn?Rm?n(2)(Rm)n?Rm?n

由歸

(1)1)n?1,Rm?1?Rm?R2)假定Rm?Rn?Rm?n?{(a,b)|?c?A,(a,c)?Rm,(c,b)?Rn}n?1Rm?R?{(a,b)|?c?A,(a,c)?Rm,(c,b)?Rn?1}其中,Rn?1?{(c,b)|?d?A,(c,d)?Rn,(d,b)?R}Rm?Rn?1?{(a,b)|?c,d?A,(a,c)?Rm,(c,d)?Rn,(d,b)?R}?{(a,b)|?d?A,(a,d)?Rm?n,(d,b)?R}?Rm?n?R?R(m?n)?1?Rm?(n?1)

(2)1)n?1,Rm?Rm2)假定(Rm)n?Rm?n(Rm)n?1?(Rm)n?Rm?Rm?n?Rm

由(1)Rm?n?m?Rm?(n?1)8.設(shè)R是A上的二元關(guān)系，｜A｜＝n，證明存在 自然數(shù)s,t，使Rs?Rt,且0?s?t?2n2，其中定義

R0?{(a,a)|a?A}。

??0(ai,aj)?R證:R?(rij)n?n,rij????1(ai,aj)?R至多有2n2個(gè)不同的Rk(k?N)出現(xiàn),

0?k?2n2,由鴿洞原理,(2n2?1)個(gè)Rk中必存在s,t,0?s?t?2n2,Rs?Rt.9.R1，R2是Ａ上的二元關(guān)系，判別下列命題正確與否

(1)如果R1，R2自反，則R1?R2也自反。

對(duì),?a?A,(a,a)?R1,(a,a)?R2,?(a,a)?R

1?R2

(2)如果R1，R2反自反，則R1?R2也反自反。

否,若(a,b)?R1,(b,a)?R2,(a,a)?R1?R2

(3)如果R1，R2對(duì)稱，則R1?R2也對(duì)稱。

否,例:A?{1,2,3},R1?{(1,2),(2,1)},R2?{(2,3),(3,2)},(1,2)?R

1,(2,3)?R2,(1,3)?R1?R2,而(3,1)?R1?R2

(4)如果R1，R2反對(duì)稱，則R1?R2也反對(duì)稱。

否,例:A?{1,2,3},R1?{(1,2),(3,2)},R2?{(2,3),(2,1)},(1,2)?R,3)?R，1,(22,(1,3)?R1?R2(3,2)?R1,(2,1)?R2,(3,1)?R1?R2

(5)如果R1，R2傳遞，則R1?R2也傳遞。

否,例:A?{1,2,3,4},R1?{(1,1),(2,3)},R2?{(1,2),(3,3)},(1,1)?R1,(1,2)?R2,(1,2)?R1?R2，(2,3)?R1,(3,3)?R2,(2,3)?R1?R2,但(1,3)?R1?R2

10.設(shè)A={a,b,c}，以下分別給出一個(gè)P(A)上的二元 關(guān)系，確定它們哪些是自反的，反自反的，對(duì)稱的，反對(duì)稱的，傳遞的。

P(A)={?,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}（１）ｘ是ｙ的一個(gè)真子集

R1?{(x,y)|x?y,x,y?P(A)}

反自反，不對(duì)稱，反對(duì)稱，傳遞（２）ｘ與ｙ不相交

R2?{(x,y)|x?y??,x,y?P(A)}

不自反，也不反自反(?????)，對(duì)稱，不傳遞（３）x?y?A

R3?{(x,y)|x?y?A,x,y?P(A)}

不自反，也不反自反{a,b,c}?{a,b,c}?A，對(duì)稱，不傳遞。

11.設(shè)R是A上二元關(guān)系，證明R是傳遞的當(dāng)且僅當(dāng)

R2?R。

任(a,b)∈R2,?C,(a,c)(c,b)∈R ,由R傳遞(a,b)∈R , 即R2 ? R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2? R , 所以R傳遞。

12.R是A上反對(duì)稱的二元關(guān)系，問(wèn)t(R)總是反對(duì)稱 的嗎？

?010??111?否, 例： R???001??,t(R)???111??

??100????111??

13．設(shè)R是A上的一個(gè)自反關(guān)系，證明當(dāng)且僅當(dāng)(a,b)和(a,c)屬于R推出(b,c)屬于R時(shí)，R是一個(gè)等價(jià) 關(guān)系。

若(a,b)∈R，又自反(a,a)∈R, 推出(b,a)∈R, 所以對(duì)稱；

若(a,b)(b,c)∈R , 由對(duì)稱(b,a)(b,c)∈R , 推出(a,c)∈R ,所以傳遞。若R等價(jià),(a,b)(a,c)∈R , 由對(duì)稱性(b,a)(a,c)∈R , 由傳遞性 ,(b,c)∈R。

14.設(shè)R是A上的一個(gè)對(duì)稱和傳遞的關(guān)系，證明如果對(duì)A中的每個(gè)a，在A中存在b，使得(a,b)∈R，則R是一個(gè)等價(jià)關(guān)系。 ?a?A,?b?A,(a,b)?R,由對(duì)稱性,(b,a)?R,又由傳遞性,(a,a)?R.15.設(shè)R是A上的一個(gè)傳遞和自反的關(guān)系，設(shè)T是 A上的一個(gè)二元關(guān)系，使得當(dāng)且僅當(dāng)(a,b)和(b,a)同時(shí) 屬于R時(shí)，(a,b)∈T，證明T是一個(gè)等價(jià)關(guān)系。 ?a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R

=>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R

=>(a,c)∈R,(c,a)∈R

=>(a,c)∈T

16.設(shè)R是A上一個(gè)二元關(guān)系，設(shè)

S={(a,b)｜對(duì)某個(gè)C，(a,c)∈R且(c,b)∈R｝

證明如果R是等價(jià)關(guān)系，則Ｓ也是等價(jià)關(guān)系。

?a,(a,a)∈R,(a,a)∈R

=>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R對(duì)稱,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S

存在d,e

(a,d)(d,b)(b,e)(e,c)∈R

由R傳遞(a,b)(b,c)∈R 所以(a,c)∈S

17.設(shè)R是A上的二元關(guān)系，對(duì)所有的xi,xj,xk∈A，如果xiRxj∧xjRxk?xkRxi，則稱R為循環(huán)關(guān)系，試證明當(dāng)且僅當(dāng)R是等價(jià)關(guān)系時(shí)，R才是自反的和循環(huán)的。（其中aRb表示(a,b)∈Ｒ）。

R等價(jià), 當(dāng)然自反，如果xiRxj且xjRxk則由傳遞性，xiRxk, 由對(duì)稱性xkRxi，R是自反, 循環(huán)的；

若(a,b)∈R, 由R自反 ?a,(a,a)∈R, 又(a,b)∈R, 由循環(huán)(b,a)∈R，對(duì)稱，若(a,b)(b,c)∈R，由循環(huán)(c,a)∈R, 由對(duì)稱(a,c)∈R，傳遞。

18．設(shè)R1，R2是A上二元關(guān)系，證明(1)r(R1?R2)?r(R1)?r(R2)(2)s(R1?R2)?s(R1)?s(R2)(3)t(R1?R2)?t(R1)?t(R2)(1)r(R1?R2)?(R1?R2)?IA?R1?IA?R2?R1?(IA?IA)?R2?(R1?IA)?(IA?R2)?(R1?IA)?(R2?IA)?r(R1)?r(R2)(2)s(Rc1?R2)?(R1?R2)?(R1?R2)?Rcc1?R2?R1?R2

?(Rcc1?R1)?(R2?R2)?s(R1)?s(R2)(3)(R1?R2)2?{(a,b)|?c,(a,c)?R1orR2,(c,b)?R1orR2}?R221?R2?R1?R2?R2?R1 29 R2221?R2?(R1?R2)用歸納法可證RnRnn1?2?(R1?R2)

n??,可得t(R1)?t(R2)?t(R1?R2)

19.設(shè)A={a,b,c,d},A上二元關(guān)系

R={(a,b),(b,a),(b,c),(c,d)}

（１）用矩陣算法和作圖法求r(R),s(R),t(R)。（２）用Warshall算法求t(R)。

?1100??0100??1111?? r(R)=?1110????1010????1111???0011? s(R)= ?0101? t(R)=?0001???0001????0010????0000??

?0100??100??1110???1010?i?10??110?i?2???1110???000???11?0001???0001?

??0000?j?2???0000?j?1,2???0000??i?3?1111?111??1111????1110?i?3?1????1111?i?4???1111??j?2?0001??0001???0001???0000?j?2???0000?j?1,2,3???0000??

20.討論正實(shí)數(shù)集上二元關(guān)系Ｒ的幾何意義。（１）Ｒ是自反的（２）Ｒ是對(duì)稱的（３）Ｒ是傳遞的

（提示：以第一象限的點(diǎn)討論）

(1)第一象限角平分線

(2)關(guān)于對(duì)角平分線對(duì)稱的點(diǎn)對(duì)集合

(3)若有P1(x1,y1)、P2(x2,y2), 若x2=y1，必有第三個(gè)點(diǎn)P3(x1,y2)

第四篇：離散數(shù)學(xué)期末復(fù)習(xí)試題及答案(一)

離散數(shù)學(xué)習(xí)題參考答案

第一章 集合

１．分別用窮舉法，描述法寫(xiě)出下列集合（１）偶數(shù)集合

（２）36的正因子集合（３）自然數(shù)中3的倍數(shù)（４）大于１的正奇數(shù)

(1)E={?，-6，-4，-2，0，2，4，6，?}

={2 i | i? I }

(2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }

(3)N3= { 3, 6, 9, ```} = { 3n | n?N }

(4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | n?N }

２．確定下列結(jié)論正確與否（１）φ?φ

×（２）φ?｛φ｝√（３）φ?φ√（４）φ?｛φ｝√（５）φ?｛ａ｝×（６）φ?｛ａ｝√

（７）｛ａ，ｂ｝?｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝?｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝?｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝?｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√

３．寫(xiě)出下列集合的冪集（１）｛｛ａ｝｝

{φ, {{ a }}}

(2)φ

{φ}（３）｛φ，｛φ｝｝

{φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝

{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ））

{φ, {φ}, {{φ}}, {φ,{φ}} }

４．對(duì)任意集合Ａ，Ｂ，Ｃ，確定下列結(jié)論的正確與否（１）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ√（２）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ×（３）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ×（４）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ ×

５．對(duì)任意集合Ａ，Ｂ，Ｃ，證明

(1)A?(B?C)?(A?B)?(A?C)左差A(yù)?(B?C)差A(yù)?(B?C)D.MA?(B?C)

分配(A?B)?(A?C)?右(2)A?(B?C)?(A?B)?(A?C)1)左差A(yù)?(B?C)(1)的結(jié)論(A?B)?(A?C)差(A?B)?(A?C)?右

2)左差A(yù)?(B?C)D.MA?(B?C)分配(A?B)?(A?C)差(A?B)?(A?C)?右(3)A?(B?C)?(A?B)?(A?C)左差A(yù)?(B?C)D.MA?(B?C)冪等(A?A)?(B?C)

結(jié)合,交換(A?B)?(A?C)?右(4)(A?B)?B?A?B 左差(A?B)?B對(duì)稱差((A?B)?B)?((A?B)?B)

分配,結(jié)合((A?B)?(B?B))?(A?(B)?B))

互補(bǔ)((A?B)?U)?(A??)

零一

(A?B)???(A?B)?右(5)(A?B)?C?A?(B?C)左差(A?B)?C結(jié)合A?(B?C)

D.MA?(B?C)差A(yù)?(B?C)(6)(A?B)?C?(A?C)?B左差(A?B)?C結(jié)合A?(B?C)交換A?(C?B)結(jié)合(A?C)?B

差(A?C)?B?右(7)(A?B)?C?(A?C)?(B?C)右(5)A?(C?(B?C))差A(yù)?(C?(B?C))分配A?((C?B)?(C?C))互補(bǔ)A?((C?B)?U)

零一A?(C?B)交換A?(B?C)(5)(A?B)?C?左

６．問(wèn)在什么條件下，集合Ａ，Ｂ，Ｃ滿足下列等式

(1)A?(B?C)?(A?B)?C左?(A?B)?(A?C)?右若要右?左,須C?A?(B?C)，?C?A時(shí)等式成立?

(2)A?B?A左?右是顯然的,A?A?B?A?B,A?B，?A?B??時(shí)等式成立?

(3)A?B?BA?B?B,B?B,B??,代入原式得A????，?A?B??時(shí)等式成立?

(4)A?B?B?AA?B?B?A,只能??A?B??,A?B, B?A??,B?A,?A?B時(shí)等式成立?

(5)A?B?AB??,若B??,?b?B，當(dāng)b?A,b?A?B?A矛盾;當(dāng)b?A,b?A?B?A矛盾?

(6)A?B?A?B右?左是顯然的,A?B?A?B,??A?A?B,A?B?B?A?B,B?A?A?B?A?B時(shí)等式成立?

(7)(A?B)?(A?C)?A左?(A?B)?(A?C)?A?(B?C)?A?(B?C)?A?(B?C)?A

?A?B?C??時(shí)等式成立?

(8)(A?B)?(A?C)??左?(A?B)?(A?C)?A?(B?C)?A?(B?C)?A?(B?C)??

A?(B?C),?A?B,A?C時(shí)等式成立?

(9)(A?B)?(A?C)??左?(A?B)?(A?C)?A?(B?C)?A?(B?C)?A?(B?C)??

?A?(B?C)時(shí)等式成立?

(10)(A?B)?(A?C)??((A?B)?(A?C))?((A?B)?(A?C))??(A?B)?(A?C)?(A?B)?(A?C)

由(6)知,(A?B)?(A?C),A?B?A?C,?A?B?A?C時(shí)等式成立?

(11)A?(B?A)?BA?(B?A)?(A?B)?(A?A)?(A?B)?U?(A?B)?B

?A?B時(shí)等式成立?

７．設(shè)Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ

８．在下列條件下，一定有Ｂ＝Ｃ嗎？（１）A?B?A?C

否，例：A={1，2，3}，B={4}，C={3,4}, A?B?A?C?{1,2,3,4},而B(niǎo)?C。

（２）A?B?A?C

否，例：A={1，2，3}，B={2，3}，C={2，3，4} A?B?A?C?{2,3},而B(niǎo)?C。

（３）A?B?A?C

對(duì),若B?C,不妨,?a?B,a?C,若a?A,a?A?B,a?A?B,a?A?B,a?A?C,a?A?C,a?A?C;若a?A,a?A?B,a?A?B,a?A?B,a?A?C,a?A?C,a?A?C矛盾?（４）A?B?A?C且A?B?A?C

?b?B,若b?A,b?A?B?A?C,b?C,若b?A,b?A?B?A?C,b?C，?B?C,同理,C?B,?B?C?

9.(1)(A?B)?(B?C)?A?B

證:?a?左,a?(B?C),a?B,a?B;a?(A?B),而a?B,a?A,?a?A?B?

(2)若A?(B?C)且B?(A?C),則B??。

若B??,?a?B?(A?C)?(A?C),a?A?(B?C),?a?C,?a?B即a?B,矛盾?

10．化簡(jiǎn)

((A?B?C)?(A?B))?((A?(B?C))?A)?(A?B)?A?(A?B)?A

?(A?A)?(B?A)???(B?A)?B?A11.設(shè)A={2，3，4}，B={1，2}，C={4，5，6}，求（１）A?B?{1, 3, 4} （２）A?B?C?{1,3,5,6}（３）(A?B)?(B?C)?{2,3,5,6}

12.設(shè)A={1，2，3，4}，B={1，2，5}，求

(1)P(A)?P(B)?{φ,{1},{2},{1,2}}

(2)P(A)?P(B)?

{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }

(3)P(A)?P(B)?

{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} }

(4)P(A)?P(B)?

{{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} }

第五篇：離散數(shù)學(xué)習(xí)題及答案

離散數(shù)學(xué)考試試題（A卷及答案）

一、（10分）某項(xiàng)工作需要派A、B、C和D 4個(gè)人中的2個(gè)人去完成，按下面3個(gè)條件，有幾種派法？如何派？

(1)若A去，則C和D中要去1個(gè)人；

(2)B和C不能都去；

(3)若C去，則D留下。

解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時(shí)成立。因此

(A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))

?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T

故有三種派法：B∧D，A∧C，A∧D。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。S(x)：x是專家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為：

?x(S(x)∧W(x))，?xY(x)?x(S(x)∧Y(x))

下面給出證明：

(1)?xY(x)P

(2)Y(c)T(1)，ES

(3)?x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)?x(S(x)∧Y(x))T(6)，EG

三、（10分）設(shè)A、B和C是三個(gè)集合，則A?B??(B?A)。

證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)

???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)

??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))

??(B?A)。

四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i?1?4232－

15>}。

五、（10分）R是非空集合A上的二元關(guān)系，若R是對(duì)稱的，則r(R)和t(R)是對(duì)稱的。

證明對(duì)任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對(duì)稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對(duì)稱的。

下證對(duì)任意正整數(shù)n，R對(duì)稱。

因R對(duì)稱，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對(duì)稱。若Rn對(duì)稱，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對(duì)稱。因此，對(duì)任意正整數(shù)n，Rn對(duì)稱。對(duì)任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是對(duì)稱的。

六、（10分）若f：A→B是雙射，則f：B→A是雙射。

證明因?yàn)閒：A→B是雙射，則f是B到A的函數(shù)。下證f是雙射。

對(duì)任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。

對(duì)任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因?yàn)閒：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。

綜上可得，f：B→A是雙射。

七、（10分）設(shè)是一個(gè)半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明因?yàn)?S，*>是一個(gè)半群，對(duì)任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因?yàn)镾是有限集，所以必存在j＞i，使得bi＝bj。令p＝j(luò)－i，則bj＝bp*bj。所以對(duì)q≥i，有bq＝bp*bq。

因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對(duì)于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，則a∈S且a*a＝a。

八、（20分）（1）若G是連通的平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：

m≤

rl(n－2)。l?2l證明設(shè)G有r個(gè)面，則2m＝

2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii?

1（2）設(shè)平面圖G＝是自對(duì)偶圖，則| E|＝2(|V|－1)。

證明設(shè)G＝是連通平面圖G＝的對(duì)偶圖，則G? G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

離散數(shù)學(xué)考試試題（B卷及答案）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明因?yàn)镾∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R附加前提

(2)P?RP

(3)?PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)Q?SP

(7)ST(5)(6)，I

(8)?R?SCP

(9)S∨RT(8)，E

二、（15分）根據(jù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。

(1)??x(P(x)?Q(x))P

(2)??x(?P(x)∨Q(x))T(1)，E

(3)?x(P(x)∧?Q(x))T(2)，E

(4)P(a)∧?Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)?Q(a)T(4)，I

(7)?x(P(x)?(A(x)∨B(x))P

(8)P(a)?(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)?x(A(x)?Q(x))P

(11)A(a)?Q(a)T(10)，US

(12)?A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)?x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。

解設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不會(huì)打這三種球的共5人。

四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和

i?1

3A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。

證明小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)s1、s2、…、sr(r≤8)。

對(duì)任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個(gè)成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。

i?1i?1i?1i?1rrrr

任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。

五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。

證明(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對(duì)任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。證明對(duì)G的邊數(shù)m作歸納法。

當(dāng)m＝0時(shí)，由于G是連通圖，所以G為平凡圖，此時(shí)n＝1，r＝1，結(jié)論自然成立。

假設(shè)對(duì)邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對(duì)e分為下列情況來(lái)討論：

若e為割邊，則G?有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學(xué)歸納法知，結(jié)論成立。

七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：

(1)f?g是A到C的函數(shù)；

(2)對(duì)任意的x∈A，有f?g(x)＝f(g(x))。

證明(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對(duì)于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對(duì)任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。

綜上可知，f?g是A到C的函數(shù)。

(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函數(shù)，則可寫(xiě)為f?g(x)＝f(g(x))。

八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－

一個(gè)等價(jià)關(guān)系，且[a]R＝aH。

證明對(duì)于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，則a1*b∈H。因?yàn)镠是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，則a1*b∈H，b1*c∈H。因?yàn)镠是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

綜上可得，R是G中的一個(gè)等價(jià)關(guān)系。

對(duì)于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]R?aH。對(duì)任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R－

＝aH。