第一篇：離散數(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個頂點(diǎn)以及8個自回路，相 當(dāng)于左圖的點(diǎn)各走了5圈，左圖的點(diǎn)各走了3圈，R16就成了原來的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|有限時，R與IA復(fù)合，相當(dāng)于矩陣與 單位矩陣相乘，不會變化。

(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對,(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對(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對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)對,(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對,?(a,b)?Rc1,(b,a)?R1?R2,(a,b)?Rc2.(9)如果R1?Rcc2,則R1?R2對,?(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分別是自反閉包，對稱閉包，傳遞閉包的 記號。試證明:(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)系，證明對任意自然數(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個不同的Rk(k?N)出現(xiàn),

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

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

對,?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對稱，則R1?R2也對稱。

否,例: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反對稱，則R1?R2也反對稱。

否,例: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}，以下分別給出一個P(A)上的二元 關(guān)系，確定它們哪些是自反的，反自反的，對稱的，反對稱的，傳遞的。

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

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

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

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

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

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

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

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上反對稱的二元關(guān)系，問t(R)總是反對稱 的嗎？

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

??100????111??

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

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

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

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

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

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

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

=>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R對稱,(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)系，對所有的xi,xj,xk∈A，如果xiRxj∧xjRxk?xkRxi，則稱R為循環(huán)關(guān)系，試證明當(dāng)且僅當(dāng)R是等價關(guān)系時，R才是自反的和循環(huán)的。（其中aRb表示(a,b)∈Ｒ）。

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

若(a,b)∈R, 由R自反 ?a,(a,a)∈R, 又(a,b)∈R, 由循環(huán)(b,a)∈R，對稱，若(a,b)(b,c)∈R，由循環(huán)(c,a)∈R, 由對稱(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)系Ｒ的幾何意義。（１）Ｒ是自反的（２）Ｒ是對稱的（３）Ｒ是傳遞的

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

(1)第一象限角平分線

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

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

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

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

第一章 集合

１．分別用窮舉法，描述法寫出下列集合（１）偶數(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é)論正確與否（１）φ?φ

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

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

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

{φ, {{ a }}}

(2)φ

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

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

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

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

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

５．對任意集合Ａ，Ｂ，Ｃ，證明

(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對稱差((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?左

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

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

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

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

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

(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時等式成立?

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

?A?B?C??時等式成立?

(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時等式成立?

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

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

(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時等式成立?

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

?A?B時等式成立?

７．設(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?C。

（２）A?B?A?C

否，例：A={1，2，3}，B={2，3}，C={2，3，4} A?B?A?C?{2,3},而B?C。

（３）A?B?A?C

對,若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．化簡

((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é)》期末復(fù)習(xí)

《離散數(shù)學(xué)》期末復(fù)習(xí)

內(nèi)容：第一章~第七章 題型：

一、選擇題（20%，每題2分）二．填空題（20%，每題2分）

三、計算題（20%，每題5分）

四、證明題（20%，每題5分）

五、判斷題（20%，每題2分）

第1章 數(shù)學(xué)語言與證明方法

1.1 常用的數(shù)學(xué)符號

1.計算常用的數(shù)學(xué)符號式子 1.2 集合及其表示法

1.用列舉法和描述法表示集合

2.判斷元素與集合的關(guān)系(屬于和不屬于)3.判斷集合之間的包含與相等關(guān)系，空集(E)，全集(?)4.計算集合的冪集

5.求集合的運(yùn)算：并、交、相對補(bǔ)、對稱差、絕對補(bǔ)

6.用文氏圖表示集合的運(yùn)算 7.證明集合包含或相等

方法一： 根據(jù)定義, 通過邏輯等值演算證明

方法二： 利用已知集合等式或包含式, 通過集合演算證明

1.3 證明方法概述

1、用如下各式方法對命題進(jìn)行證明。? 直接證明法：A?B為真

? 間接證明法：“A?B為真” ? “ ?B? ?A為真” ? 歸謬法(反證法)： A??B?0為真

? 窮舉法： A1?B, A2?B,…, Ak?B 均為真

? 構(gòu)造證明法：在A為真的條件下, 構(gòu)造出具有這種性質(zhì)的客體B ? 空證明法：“A恒為假” ? “A?B為真” ?平凡證明法：“B恒為真” ? “A?B為真” ? 數(shù)學(xué)歸納法： 第2章 命題邏輯

2.1 命題邏輯基本概念

1、判斷句子是否為命題、將命題符號化、求命題的真值（0或1）。

命題的定義和聯(lián)結(jié)詞(?, ?, ?, ?, ?)

2、判斷命題公式的類型

賦值或解釋.成真賦值,成假賦值；重言式(永真式)、矛盾式(永假式)、可滿足式:。2.2 命題邏輯等值演算

1、用真值表判斷兩個命題公式是否等值

2、用等值演算證明兩個命題公式是否等值

3、證明聯(lián)結(jié)詞集合是否為聯(lián)結(jié)詞完備集 2.3 范式

1、求命題公式的析取范式與合取范式

2、求命題公式的主析取范式與主合取范式（兩種主范式的轉(zhuǎn)換）

3、應(yīng)用主析取范式分析和解決實(shí)際問題 2.4 命題邏輯推理理論

1、用直接法、附加前提、歸謬法、歸結(jié)證明法等推理規(guī)則證明推理有效 第3章 一階邏輯

3.1 一階邏輯基本概念

1、用謂詞公式符號命題（正確使用量詞）

2、求謂詞公式的真值、判斷謂詞公式的類型 3.2 一階邏輯等值演算

1、證明謂詞公式的等值式

2、求謂詞公式的前束范式 第4章 關(guān)系

4.1 關(guān)系的定義及其表示

1、計算有序?qū)?、笛卡兒積

2、計算給定關(guān)系的集合

3、用關(guān)系圖和關(guān)系矩陣表示關(guān)系 4.2 關(guān)系的運(yùn)算

1、計算關(guān)系的定義域、關(guān)系的值域

2、計算關(guān)系的逆關(guān)系、復(fù)合關(guān)系和冪關(guān)系

3、證明關(guān)系運(yùn)算滿足的式子 4.3 關(guān)系的性質(zhì)

1、判斷關(guān)系是否為自反、反自反、對稱、反對稱、傳遞的2、判斷關(guān)系運(yùn)算與性質(zhì)的關(guān)系

3、計算關(guān)系自反閉包、對稱閉包和傳遞閉包 4.4 等價關(guān)系與偏序關(guān)系

1、判斷關(guān)系是否為等價關(guān)系

2、計算等價關(guān)系的等價類和商集

3、計算集合的劃分

4、判斷關(guān)系是否為偏序關(guān)系

5、畫出偏序集的哈期圖

6、求偏序集的最大元、最小元、極小元、極大元、上界、下界、上確界、下確界

7、求偏序集的拓?fù)渑判?第5章 函數(shù)

1.判斷關(guān)系是否為函數(shù) 2.求函數(shù)的像和完全原像

3.判斷函數(shù)是否為滿射、單射、雙射 4.構(gòu)建集合之間的雙射函數(shù) 5.求復(fù)合函數(shù)

6.判斷函數(shù)的滿射、單射、雙射的性質(zhì)與函數(shù)復(fù)合運(yùn)算之間的關(guān)系 7.判斷函數(shù)的反函數(shù)是否存在，若存在求反函數(shù) 第6章 圖

1.指出無向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的度數(shù)、最大度、最小度

2.指出有向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根據(jù)握手定理頂點(diǎn)數(shù)、邊數(shù)等

4.指出圖的平行邊、環(huán)、弧立點(diǎn)、懸掛頂點(diǎn)和懸掛邊 5.判斷給定的度數(shù)列能否構(gòu)成無向圖

6.判斷圖是否為簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補(bǔ)圖、生成子圖、導(dǎo)出子圖 8.判斷兩個圖是否同構(gòu) 6.2 圖的連通性

1.求圖中給定頂點(diǎn)通路、回路的距離

2.計算無向圖的連通度、點(diǎn)割集、割點(diǎn)、邊割集、割邊 3.判斷有向圖的類型：強(qiáng)連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示

1.計算無向圖的關(guān)聯(lián)矩陣 2.計算有向無環(huán)圖的關(guān)聯(lián)矩陣 3.計算有向圖的鄰接矩陣 4.計算有向圖的可達(dá)矩陣

5.計算圖的給定長度的通路數(shù)、回路數(shù) 6.4 幾種特殊的圖

1、判斷無向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹及其應(yīng)用 7.1 無向樹

1.判斷一個無向圖是否為樹

2.計算無向樹的樹葉、樹枝、頂點(diǎn)數(shù)、頂點(diǎn)度數(shù)之間的關(guān)系 3.給定無向樹的度數(shù)列，畫出非同構(gòu)的無向樹 4.求生成樹對應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng) 5.求最小生成樹 7.2 根樹及其應(yīng)用

1.判斷一個有向圖是否為根樹

2.求根樹的樹根、樹葉、內(nèi)點(diǎn)、樹高 3.求最優(yōu)樹

4.判斷一個符號串集合是否為前綴碼 5.求最佳前綴碼

6.用三種方法遍歷根樹

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

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

一、（10分）求(P?Q)?(P∧?(Q∨?R))的主析取范式 解：(P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R))

?(P∨Q)∨(P∧?Q∧R))

?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R)

?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1

?m2∨m3∨m4∨m5∨m6∨m7

二、（10分）在某次研討會的休息時間，3名與會者根據(jù)王教授的口音分別作出下述判斷： 甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教授既不是上海人，也不是杭州人。

王教授聽后說：你們3人中有一個全說對了，有一人全說錯了，還有一個人對錯各一半。試判斷王教授是哪里人？

解 設(shè)設(shè)P：王教授是蘇州人；Q：王教授是上海人；R：王教授是杭州人。則根據(jù)題意應(yīng)有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R

王教授只可能是其中一個城市的人或者3個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因?yàn)?，若甲全錯了，則有?Q∧P，因此，乙全對。同理，乙全錯則甲全對。所以丙必是一對一錯。故王教授的話符號化為：

((?P∧Q)∧((Q∧?R)∨(?Q∧R)))∨((?Q∧P)∧(?Q∧R))?(?P∧Q∧Q∧?R)∨(?P∧Q∧?Q∧R)∨(?Q∧P∧?Q∧R)?(?P∧Q∧?R)∨(P∧?Q∧R)??P∧Q∧?R ?T 因此，王教授是上海人。

三、（10分）證明tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。

證明 設(shè)R是非空集合A上的二元關(guān)系，則tsr(R)是包含R的且具有自反性、對稱性和傳遞性的關(guān)系。

若R是包含R的且具有自反性、對稱性和傳遞性的任意關(guān)系，則由閉包的定義知r(R)?R。則 ''sr(R)?s(R)＝R，進(jìn)而有tsr(R)?t(R)＝R。

綜上可知，tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。

四、（15分）集合A＝{a，b，c，d，e}上的二元關(guān)系R為R＝{，，，，，，，，，，，，，}，(1)寫出R的關(guān)系矩陣。

(2)判斷R是不是偏序關(guān)系，為什么？ 解(1)R的關(guān)系矩陣為： ''''?1??0M(R)??0??0?0?1111??1101?0101?

?0011?0001??(2)由關(guān)系矩陣可知，對角線上所有元素全為1，故R是自反的；rij＋rji≤1，故R是反對稱的；可計算對應(yīng)的關(guān)系矩陣為：

?1??0M(R2)??0??0?0?由以上矩陣可知R是傳遞的。

1111??1101?0101??M(R)

?0011?0001??

五、（10分）設(shè)A、B、C和D為任意集合，證明(A－B)×C＝(A×C)－(B×C)。證明：因?yàn)?/p>

∈(A－B)×C?x∈(A－B)∧y∈C

?(x∈A∧x?B)∧y∈C

?(x∈A∧y∈C∧x?B)∨(x∈A∧y∈C∧y?C)?(x∈A∧y∈C)∧(x?B∨y?C)?(x∈A∧y∈C)∧?(x∈B∧y∈C)?∈(A×C)∧?(B×C)?∈(A×C)－(B×C)所以，(A－B)×C＝(A×C－B×C)。

六、（10分）設(shè)f：A?B，g：B?C，h：C?A，證明：如果h?g?f＝IA，f?h?g＝IB，g?f?h＝IC，則f、g、h均為雙射，并求出f、g和h。

解 因IA恒等函數(shù)，由h?g?f＝IA可得f是單射，h是滿射；因IB恒等函數(shù)，由f?h?g＝IB可得g是單射，f是滿射；因IC恒等函數(shù)，由g?f?h＝IC可得h是單射，g是滿射。從而f、g、h均為雙射。

由h?g?f＝IA，得f＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。－

1－1

－1－1－1

－1

七、（15分）設(shè)是一代數(shù)系統(tǒng)，運(yùn)算*滿足交換律和結(jié)合律，且a*x＝a*y?x＝y(tǒng)，證明：若G有限，則G是一群。

證明 因G有限，不妨設(shè)G＝{a1，a2，…，an}。由a*x＝a*y?x＝y(tǒng)得，若x≠y，則a*x≠a*y。于是可證，對任意的a∈G，有aG＝G。又因?yàn)檫\(yùn)算*滿足交換律，所以aG＝G＝Ga。令e∈G使得a*e＝a。對任意的b∈G，令c*a＝b，則b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由運(yùn)算*滿足交換律得e*b＝b，所以e是關(guān)于運(yùn)算*的幺元。對任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由運(yùn)算*滿足交換律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每個元素都存在逆元。故G是一群。

八、（20分）（1）證明在n個結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。

證明 不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對應(yīng)的無向圖）。

設(shè)G中結(jié)點(diǎn)為v1、v2、…、vn。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結(jié)點(diǎn)相鄰，得新邊en?1，由此可見G中至少有n－1條邊。

2（2）給定簡單無向圖G＝，且|V|＝m，|E|＝n。試證：若n≥Cm?1＋2，則G是哈密爾頓圖。

2證明 若n≥Cm。?1＋2，則2n≥m－3m＋6（1）

2若存在兩個不相鄰結(jié)點(diǎn)u、v使得d(u)＋d(v)＜m，則有2n＝

w?V?d(w)＜m＋(m－2)(m－3)＋m＝m－

23m＋6，與（1）矛盾。所以，對于G中任意兩個不相鄰結(jié)點(diǎn)u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密爾頓圖。離散數(shù)考試試題（B卷及答案）

一、（10分）使用將命題公式化為主范式的方法，證明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。證明：因?yàn)?P?Q)?(P∧Q)??(?P∨Q)∨(P∧Q)

?(P∧?Q)∨(P∧Q)(Q?P)∧(P∨Q)?(?Q∨P)∧(P∨Q)?(P∧?Q)∨(?Q∧Q)∨(P∧P)∨(P∧Q)?(P∧?Q)∨P

?(P∧?Q)∨(P∧(Q∨?Q))?(P∧?Q)∨(P∧Q)∨(P∧?Q)?(P∧?Q)∨(P∧Q)所以，(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。

二、（10分）證明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。

解 設(shè)A：A努力工作；B、C、D分別表示B、C、D愉快；則推理化形式為： A?B∨C，B??A，D??CA??D

(1)A 附加前提(2)A?B∨C P(3)B∨C T(1)(2)，I(4)B??A P(5)A??B

T(4)，E(6)?B T(1)(5)，I(7)C T(3)(6)，I(8)D??C P(9)?D T(7)(8)，I(10)A??D CP

三、（10分）證明?x?y(P(x)?Q(y))?(?xP(x)??yQ(y))。?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y))??x(?P(x)∨?yQ(y))??x?P(x)∨?yQ(y)???xP(x)∨?yQ(y)?(?xP(x)??yQ(y))

四、（10分）設(shè)A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}}

五、（15分）設(shè)X＝{1，2，3，4}，R是X上的二元關(guān)系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。

(3)說明R是否是自反、反自反、對稱、傳遞的。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：

?1??0M(R)??1??1?反自反的；由于矩陣不對稱，R不是對稱的；

經(jīng)過計算可得

101110110??0? 0??0??(3)對于R的關(guān)系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是?1??0M(R2)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0??

六、（15分）設(shè)函數(shù)f：R×R?R×R，f定義為：f()＝。(1)證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f。

(4)求復(fù)合函數(shù)f?f和f?f。

證明(1)對任意的x，y，x1，y1∈R，若f()＝f()，則＝，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y(tǒng)1，故f是單射。

(2)對任意的∈R×R，令x＝－1－

1u?wu?wu?wu?wu?w，y＝，則f()＝<＋，－22222u?w>＝，所以f是滿射。2(3)f()＝<－1－1u?wu?w，>。22－1

－1(4)f?f()＝f(f())＝f()＝<

x?y?x?yx?y?(x?y)，>＝

444

55f?f()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）給定群，若對G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，3試證是Abel群。

證明 對G中任意元a和b。

因?yàn)閍*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。

于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。

由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。

八、（15分）（1）證明在n個結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。

證明 不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對應(yīng)的無向圖）。

設(shè)G中結(jié)點(diǎn)為v1、v2、…、vn。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結(jié)點(diǎn)相鄰，得新邊en?1，由此可見G中至少有n－1條邊。

（2）試給出|V|＝n，|E|＝(n－1)(n－2)的簡單無向圖G＝是不連通的例子。解 下圖滿足條件但不連通。

12344

333334

34333

4333

?133

?1?13

?122244 6

第五篇：大學(xué)離散數(shù)學(xué)復(fù)習(xí)試題

離散數(shù)學(xué)練習(xí)題目

一、選擇題

1．設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是錯的。

A、??A； B、{6，7，8}?A； C、{{4，5}}?A； D、{1，2，3}?A。

2.已知集合A={a,b,c},B={b,c,e},則 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列語句中，不是命題的是____A_________ A.我說的這句話是真話； B.理發(fā)師說“我說的這句話是真話”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以這些煤不會燃燒；

4.下面___D______命題公式是重言式。

A.P?Q?R ； B.(P?R)?(P?Q)；C.(P?Q)?(Q?R)；

D、(P?(Q?R))?((P?Q)?(P?R))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．設(shè)L(x)：x是演員，J(x)：x是老師，A(x , y)：x欽佩y，命題“所有演員都?xì)J佩某些老師”符號化為___D______。

A、?x(L(x)?A(x,y))； B、?x(L(x)??y(J(y)?A(x,y)))； C、?x?y(L(x)?J(y)?A(x,y))； D、?x?y(L(x)?J(y)?A(x,y))。7.關(guān)于謂詞公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯誤的是__B_____ A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）

B．z是該謂詞公式的約束變元

C．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變元 8． 設(shè)S?A?B，下列各式中____B___________是正確的。

A、domS?B ； B、domS?A； C、ranS?A； D、domS ? ranS = S。9．設(shè)集合X??，則空關(guān)系?X不具備的性質(zhì)是____A________。

A、自反性； B、反自反性； C、對稱性； D、傳遞性。

10.集合A，R是A上的關(guān)系，如果R是等價關(guān)系，則R必須滿足的條件是__D___ A.R是自反的、對稱的 B.R是反自反的、對稱的、傳遞的 C.R是自反的、對稱的、不傳遞的 D.R是自反的，對稱的、傳遞的 11.集合A={a,b,c,d},B={1,2,3},則下列關(guān)系中__ACD______是函數(shù)

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} ????已知集合???????????? R?A,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},則頂點(diǎn)2的入度和出度分別是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.設(shè)完全圖Kn有n個結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)下面條件__C____滿足時，Kn中存在歐拉回路．

A．m為奇數(shù) B．n為偶數(shù) C．n為奇數(shù) D．m為偶數(shù) 14.下面敘述正確的是____B______ A.二部圖K3,3是歐拉圖 B.二部圖是平面圖

K3,3是哈密爾頓圖

C.二部圖 K3,32

D.二部圖K3,3是既不是歐拉圖也不哈密爾頓圖

15.已知某平面圖的頂點(diǎn)數(shù)是12，邊數(shù)是14，則該平面圖有__D___個面 A.3 B.2 C.5 D.4 16．設(shè)G是n個結(jié)點(diǎn)、m條邊和r個面的連通平面圖，則m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面幾種代數(shù)結(jié)構(gòu)中，不是群的是___D____ A. B. C. D.(這里Z，Q，R，N分別表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集、自然數(shù)集，+普通加法)

二、問答題

1.在程序設(shè)計過程中，有如下形式的判斷語句： if(a>=0)if(b>1)if(c<0)cout<

請將這段程序化簡，并說明化簡的理由。解：簡化的程序：

if(a>=0 && b>1 && c<0)cout<

設(shè)置命題變量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))經(jīng)過等值演算可得，A與下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①證明R是偏序關(guān)系。

②寫出偏序集（A，R）的極小元、極大元；最小元、最大元 ③寫出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根據(jù)整除性質(zhì)可知，R滿足自反性，反對稱性，傳遞性。所以R是A上的偏序關(guān)系。

②偏序集（A，R）的極小元：1，極大元：5, 6，7，8，9 最小元：1； 最大元：無

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m個男孩子，n個女孩排成一排，任何兩個女孩不相鄰，有多少種排法？

(n<=m)插空問題

(2)如果排成一個園環(huán)，又有多少種排法？

解：(1)考慮5個男孩，5個女孩的情況

男孩的安排方法： _B_B_B_B_B_ 排列總數(shù)P(5,5)女孩的安排方法：6個位置安排5個女孩，排列中數(shù) P(6,5)所以：總的排列方法數(shù)是 m!*p(m+1,n)

(2)考慮男孩的圓排列情況，結(jié)果是(m-1)!*p(m,n)

4.某商家有三種品牌的足球，每種品牌的足球庫存數(shù)量不少于10只，如果我想買5只足球，有多少種買法？如果每種品牌的足球最少買一只，有多少種買法？

解：①這是一個多重集的組合問題

類別數(shù)是k=3，選取的元素個數(shù)是 r=5 多重集組合數(shù)的計算公式是 N?所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由選取的球只有2個 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(r?k?1)!?C(k?r?1,r)

r!(k?1)!

5．某軟件公司將職工分為三種崗位。該公司65人，有些職工（例如項(xiàng)目管理人員、設(shè)計人員）可能從事不止一個崗位的工作。每個職工至少被分在一個崗位?，F(xiàn)在軟件設(shè)計崗位（崗位A）（包括需求分析、概要設(shè)計和詳細(xì)設(shè)計等工作）的人數(shù)是15人，代碼編寫崗位（崗位B）的人數(shù)是32人，軟件測試崗位（崗位C）的人數(shù)是28人，同時參加崗位A和崗位B的有12人, 同時參加崗位B和崗位C的有8人, 同時參加崗位A和崗位C組的有3人，問，三個崗位參加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 設(shè)S表示全班同學(xué)總?cè)藬?shù)，則 |S|=65 求：|A∩B∩C|=？

根據(jù)容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因?yàn)槊總€同學(xué)至少參加一個小組，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三個小組都參加的人數(shù)是13人

6.證明組合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

說明：也可以直接利用組合演算公式進(jìn)行演算 7.求1228的個位數(shù)是多少? 解：1228的個位數(shù)就是1228 mod 10的余數(shù)1228mod10?(12mod10)28mod10?24*7mod10?(27mod10)4mod10?8mod10?64

8.已知圖G有10條邊, 4個3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小于2, 問G至少有多少個頂點(diǎn)?

解：由握手定理∑d(v)=2m=20，度數(shù)為3的頂點(diǎn)有3個占去12度，還有8度由其余頂點(diǎn)占有，而由題意，其余頂點(diǎn)的度數(shù)可為0，1，當(dāng)均為1時所用頂點(diǎn)數(shù)最少，所以應(yīng)有8個頂點(diǎn)占有此8度，即G中至少有8+4=12個頂點(diǎn)。

9刑偵人員審一件盜竊案時，已經(jīng)掌握的線索如下：（1）甲或乙盜竊了電腦。

（2）若甲盜竊了電腦，則作案時間不能發(fā)生在午夜前。（3）若乙證詞正確，則在午夜時屋里燈光未滅。（4）若乙證詞不正確，則作案時間發(fā)生在午夜前。（5）午夜時屋里燈光滅了。

請通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細(xì)的推理步驟）解 設(shè)p： 甲盜竊了電腦，q： 乙盜竊了電腦，r： 作案時間發(fā)生在午夜前，s： 乙證詞正確，t：午夜時屋里燈光滅了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的時間T與數(shù)據(jù)規(guī)模n的遞推關(guān)系如下，求出T與n的顯示關(guān)系表達(dá)式

?T(n)?T(n?1)?n?1 ??T(1)?0

解：

??T(n)?T(n?1)?n?1 ??T(n?2)?n?2?n?1???T(n?3)?n?3?n?2?n?1 ?????T(n?k)?n?k???n?2?n?1??T(n?k)?kn-(1?2??k)??k(k?1)??T(n?k)?kn?2?令n-k=1，那么 k=n-1，所以：

n(n?1)n(n?1)n(n?1)? T(n)?T(1)??0???222?答：T與n的顯示關(guān)系是：T(n)?

11.解下列一階同余方程組

n(n?1)2x?1(mod 3)x?2(mod 4)x?3(mod 5)解：已知a1?1,a2?2,a3?3;m1?3,m2?4,m3?5 方程組的齊次通解是：x?k?Lcm(1,2,3)?6k 60k 根據(jù)中國剩余定理，特解是：

x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)M1?m2m3?20,M2?m1m3?15,M3?m1m2?12 ?1?1?1M1mod m1是下列同余方程的解

3)，解得：x=2，即M1?2 M1x?1(mod m1)即20x?1(mod?1?1同理可解得：M2?3，M3?3 ?1?1 7

x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)mod m?（1?20?2?2?15?3?3?12?3）mod 60?1?1?1所以：?(40?90?108)mod 60?238mod 6058

同余方程組的解是 x?x?x0?6k?58 60k

12.假設(shè)需要加密的明文數(shù)據(jù)是a=8,選取兩個素數(shù)p=7,q=19,使用RSA算法： ① 計算出密鑰參數(shù)

② 利用加密算法計算出密文c ③ 利用解密算法根據(jù)密文c反求出明文a 解：① 取 p=7,q=19;計算 n=p*q=7*19=133 計算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 選取較小的數(shù)w,使w與108互質(zhì), 5是最小的,于是w=5 計算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余數(shù)為1, 于是算出d=65 至此加密、解密參數(shù)計算完成：

公鑰w=5,n=133.私鑰d=65,n=133.② 加密

c?mwmodn?85mod133?((82mod133)*(83mod133))mod133

?(64*113)mod133?50③ 解密

a?cdmodn?5065mod133

a?A0?A6 其中，A0?50, Ai?(Ai?1)2

根據(jù)上述遞推公式可以計算出：A1?502mod133?106,A2?1062mod133?64

A3?642mod133?106，??, A6?1062mod133?64 a?A0?A6?(50*64)mod133?8

解密后的明文與原來的明文是相等的，所以算法正確。

13.設(shè)A={1，2，3，4，6，9，12，24},R定義為R?{(a,b)|a?b(mod 3)}，（1）證明R是一個等價關(guān)系；（2）寫出A的商集；

14.基于字典序的組合生成算法

問題說明：假設(shè)我們需要從5個元素中選取3個的所有組合，已知組合個數(shù)為 C（５，３）＝１０，按字典序，其具體組合為： 123,124,125,134,135,145,234,235,245,345 所謂按字典序生成組合，就是已知當(dāng)前的組合（例如135），求下一個組合（例如，145）。下面給出算法的函數(shù)頭：

//數(shù)組s[]:函數(shù)運(yùn)行前，保存當(dāng)前的組合，函數(shù)結(jié)束后，是新生成的下一個組合 //n,r:表示從n個元素中選取r個元素的組合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某單位要從A,B,C三人選派若干人出國考察, 需滿足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案? 9