第一篇：離散數(shù)學(xué)結(jié)構(gòu)試題集4

第1章

一.填空題

1.2.公式P→(Q→R)在聯(lián)結(jié)詞全功能集{﹁,∨}中等值形式為___________________。

3.4.5.6.7.全體小項的析取式必為____________________式。

8.P,Q為兩個命題，則德摩根律可表示為7.全體小項的析取式必為_________式。

9.P,Q為兩個命題，則吸收律可表示為____________________。

10.設(shè)P：我有錢，Q：我去看電影。命題“雖然我有錢，但是我不去看電影”符號化為_____ _______________。

11.設(shè)P：我生病，Q：我去學(xué)校。命題“如果我生病，那么我不去學(xué)?！狈柣癁開________ ___________。

12.13.14./ 36

15.設(shè)P、Q為兩個命題，交換律可表示為____________________。

16.17.命題“如果你不看電影，那么我也不看電影”（P：你看電影，Q：我看電影）的符號化 為____________________。

18.19.20.21.P：你努力，Q：你失敗。命題“除非你努力，否則你將失敗”的翻譯為_______________ _____。

22.23.24.一個重言式和一個矛盾式的合取是____________________。

25.全體小項的析取式為____________________。

26.命題“如果你不看電影，那么我也不看電影”（P：你看電影，Q：我看電影）的符號化 為____________________。

27.28.設(shè)P：它占據(jù)空間，Q：它有質(zhì)量，R：它不斷運動，S：它叫做物質(zhì)。命題“占據(jù)空間的，有質(zhì)量的而且不斷運動的叫做物質(zhì)”的符號化為____________________。

29./ 36 30.二.選擇題

1.2.3.在除﹁之外的四大聯(lián)結(jié)詞中，滿足結(jié)合律的有幾個（）。

A.2

B.3

C.4

D.1

4.判斷下列語句哪個是命題（）。

A.你喜歡唱歌嗎？

B.若7+8＞18，則三角形有4條邊。

C.前進！

D.給我一杯水吧！

5.6.7.8.永真式的否定是（）

A.永真式 B.永假式 C.可滿足式 D.A--D均有可能 / 36

9.下面哪一個是假命題（）。

A.如果2是偶數(shù)，那么一個公式的析取范式唯一。

B.如果2是偶數(shù)，那么一個公式的析取范式不唯一。

C.如果2是奇數(shù)，那么一個公式的析取范式唯一。

D.如果2是奇數(shù)，那么一個公式的析取范式不唯一。

10.設(shè)p:天下大雨，q:小王乘公共汽車上班，命題“只有天下大雨，小王才乘公共汽車上班 ”的符號化形式為（）。

A.p→q

B.q→p

C.p→┐q

D.┐p→q

11.設(shè)p:小李努力學(xué)習(xí)，q:小李取得好成績，命題“除非小李努力學(xué)習(xí)，否則他不能取得好 成績”的符號化形式為（）。

A.p→q

B.q→p

C.┐q→p

D.┐p→q

12.下面4個推理定律中，不正確的為（）。

A.A=>(A∨B)(附加律)

B.(A∨B)∧┐A=>B(析取三段論)

C.(A→B)∧A=>B(假言推理)

D.(A→B)∧┐B=>A(拒取式)

13.使命題公式p→(p∧q)為假的賦值是（）。

A.10

B.01

C.00

D.11

14.令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）。

A.p∧┐q

B．p∨┐q C.p∧q

D．p→┐q

15.一個公式在等價意義下，下面哪個寫法是唯一的（）。

Ａ．析取范式

B．合取范式

Ｃ．主析取范式

D．以上答案都不對

16.令p：今天下雨了，q：我上學(xué)，則命題“因為今天下雨了，所以我不上學(xué)了”可符號化

為（）。

A．p→┐q

B．p∨┐q C．p∧q

D．p∧┐q

17.下列各組公式中哪組互為對偶（）。(P為原子命題，A為復(fù)合命題)A.P,P

B.P, ┐P C.A,(A*)*

D.A,A 18./ 36

19.20.21.22.23.24.25.下列語句哪個是命題（）。

A.9+5≤12

B.x+3=5 C.我用的計算機CPU主頻是1G嗎？

D 我正在說謊。/ 36

26.27.28.n個命題變元可產(chǎn)生（）個互不等價的大項。

A.n

B.n2

C.2n

D.2n

29.下列各命題中真值為真的命題有（）。

A.2+2=4當(dāng)且僅當(dāng)3是奇數(shù)

B.2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)

C.2+2≠4當(dāng)且僅當(dāng)3是奇數(shù)

D.2+2≠5當(dāng)且僅當(dāng)3不是奇數(shù)

30.下列語句哪個不是命題（）。

A.雪是黑的。

B.天氣多好啊！

C.今天下雨。

D 我學(xué)英語，或者我學(xué)日語。

三.判斷題

1.“我正在說謊?！笔且粋€命題。

（）

2.一個命題標(biāo)識符如表示確定的命題，就稱為命題常量。（）

3.“她昨天做了一頓或兩頓飯?！笔莻€原子命題。（）

4.命題公式是沒有真假值的，僅當(dāng)在一個公式中命題變元用確定的命題代入時，才得到一 個命題。（）

5.如果A和B是合式公式，那么(A→ B)是合式公式。（）

6.原子謂詞公式是合式公式。（）

7.一般來說，n個命題變元組成的命題公式共有2n中真值情況。（）

8.任何兩個重言式的合取或析取，仍然是一個重言式。（）/ 36 9.重言式和矛盾式的析取是重言式。（）

10.在真值表中，一個公式的真值為F的指派所對應(yīng)的大項的析取，即為此公式的主析取范式。（）

11.從假的命題出發(fā)，能證明任何命題。（）

12.全體小項的析取式永為假。（）

13.連接詞↑和↓是可交換的，也是可結(jié)合的。（）

14.P→Q =〉P→P∧Q。（）

15.由n個命題變元組成不等值的命題公式的個數(shù)為2n。（）

四.計算題

1.2.3.4.5.6.7.8.9./ 36

10.11.12.13.14.15.五.證明題 / 36 1.2.3.第2章

一.填空題

1.2.3.4.5.6.7./ 36 8.9.10.11.12.13.14.15.16.17./ 36 18.19.20.21.22.23.24.25.二.選擇題 / 36 1.2.3.4./ 36

5.6.7.8.9./ 36

10.11.12.13./ 36 14.15.16.17.18./ 36

19.20.21.22.23.24./ 36

25.26.27.28.29./ 36 30.三.判斷題

1.“如果1+2=3，則4+5=9?！笔钦婷}。（）

2.約束變元換名時，一定要更改為作用域中沒有出現(xiàn)的變元名稱。（）

3.4.簡單命題函數(shù)由一個謂詞和一些客體變元組成。（）

5.單獨一個謂詞，不是完整的命題。（）

6.任意一個謂詞公式均和一個前束范式等價。（）

7.8.9.10.11.12.13./ 36

14.15.四.計算題 1.2.3.4.5.6.7.8.9./ 36

10.五.證明題 1.2.3.4.第3章

一.填空題

1.設(shè)A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},則A∪B=_________________。

2.A，B，C表示三個集合，圖中陰影部分的集合表達式為____________________。/ 36

3.設(shè)A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},則A°B=_______________。

4.設(shè)A={1，2，3，4}，A上二元關(guān)系R={<1，2>，<2，1>，<2，3>，<3，4>}畫出R的關(guān)系圖_ ________________。

5.設(shè)A={a，b，c，d}，其上偏序關(guān)系R的哈斯圖為

則 R=_______________________。

6.設(shè)A={1，2，3}，則A上既不是對稱的又不是反對稱的關(guān)系為R=____________________。

7.設(shè)A={1，2，3}，則A上既是對稱的又是反對稱的關(guān)系為R=_____________________。

8.設(shè)|A|=3，則A上有________________個二元關(guān)系。

9.偏序集〈Ρ（{a,b}），?〉的哈斯圖為________________。

10.集合A={2，3，6，12，24，36}上偏序關(guān)系R的Hass圖為 / 36

則集合B={2，3，6，12}的上界是_________________。

11.對集合X和Y，設(shè)|X|=m，|Y|=n，則從X到Y(jié)的函數(shù)有__________________個。

12.關(guān)系R的自反閉包r(R)＝________________。

13.關(guān)系R的對稱閉包s(R)＝_________________。

14.關(guān)系R的傳遞閉包t(R)＝_____________________。

15.若R是集合A上的偏序關(guān)系，則R滿足___________________。

16.若R是集合A上的等價關(guān)系，則R滿足____________________。

17.若R是集合A上的相容關(guān)系，則R滿足__________________。

18.集合A={2，3，6，12，24，36}上偏序關(guān)系R的Hass圖為

則集合B={2，3，6，12}的上確界是_____________。/ 36 19.設(shè)A，B是兩集合，其中A={a，b，c}，B={a，b}，則A-B=_______________。

20.設(shè)R={,,}，則ran(R)=______________。

21.設(shè)R={,,}，則dom(R)=________________。

22.設(shè)R={,,}，則FLD(R)=_________________。

23.設(shè)A={a，b}，B＝｛1，2，3｝，則A×B=__________________。

24.設(shè)R是A={1，2，3，4}上的二元關(guān)系,R={<1,1>,<1,2>,<2,3>,<3,4>},則R的對稱閉包是__ _______________。

25.設(shè)R是A={1，2，3，4}上的二元關(guān)系,R={<1,1>,<1,2>,<2,3>,<3,4>},則R的自反閉包是__ ________________。

26.設(shè)R是A={1，2，3，4}上的二元關(guān)系,R={<1,1>,<1,2>,<2,3>,<3,4>},則R的傳遞閉包是__ __________________。

27.集合A={2，3，6，12，24，36}上偏序關(guān)系R的Hass圖為

則集合B={2，3，6，12}的下確界是__________________。

28.設(shè)A,B是集合，|A|=3，|B|=4，|A∩B|=2，那么|A∪B|=_____________。

29.集合A有n個元素，則A的冪集有___________個元素。

30.一個集合的非平凡子集包括___________和全集。

31.集合A={2，3，6，12，24，36}上偏序關(guān)系R的Hass圖為 / 36

則集合B={2，3，6，12}的下界是_______________。

32.集合A={?,a}，則A的冪集P(A)=____________。

33.設(shè)A,B為集合，則命題A-B=?<=>A=B的真值為（填“真”或“假”或“不可判別”）____ ____。

34.設(shè)A={a,b,c,d}，A上的等價關(guān)系R=IA∪{(b,c),(c,b),(a,d),(d,a)}，則對 應(yīng)于R的A的劃分是_______________。

35.給定集合A＝{1,2,3,4,5},R是A上的等價關(guān)系，且此關(guān)系R能產(chǎn)生劃分{{1,2},{3,4,5}}, 則R=_________________。

二.選擇題

1.設(shè)A={1,2,3}，則A上有（）個二元關(guān)系。

A.23

B.32

C.2^{2^3}

D.2 ^{3^2}

2.設(shè)X，Y，Z是集合，下列結(jié)論不正確的是（）。

A．若X?Y,則X∩Y=X

B．(X-Y)-Z=X-(Y∩Z)C．X⊕X=?

D．X-Y=X∩(~Y)

3.設(shè)S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，則R的性質(zhì)是（）。

A.自反、對稱、傳遞的 B.自反、對稱、反對稱的C.對稱、反對稱、傳遞的 D.只有對稱性

4.設(shè)R和S是P上的關(guān)系，P是所有人的集合，R={|x,y∈P∧x是y的父親}，S={|x, y∈P∧x是y的母親} 則S-1 °R表示關(guān)系（）。

A、{|x,y∈P∧x是y的丈夫} B、{|x,y∈P∧x是y的孫子或?qū)O女} C、? / 36 D、{|x,y∈P∧x是y的祖父或祖母}

5.若X是Y的子集，則一定有（）。

A.X不屬于Y

B.X∈Y

C.X真包含于Y

D.X∩Y=X

6.下列式子中正確的是（）。

A．?=0

B． ?∈?

C．?∈{a，b}

D．?∈{?}

7.下面那條不是偏序關(guān)系的性質(zhì)：（）

A).自反性

B)相容性

C)傳遞性

D)反對稱性

8.關(guān)于閉包運算，下面那條性質(zhì)不對（）

A)rs(R)=sr(R)

B)rt(R)=tr(R)C)st(R)=ts(R)

D)rtr(R)=tr(R)

9.劃分必然誘導(dǎo)一個（）

A）等價關(guān)系

B)偏序關(guān)系

C)同余關(guān)系

D)同態(tài)關(guān)系

10.設(shè)某集合有m個元素，則可以構(gòu)成（）個子集。

A)m

B)m!

C)2m

D)2m-1

11.A, B為兩個集合，如果A?B，則下面那個是錯誤的。（）

A)A∩B≠?

B)~B?~A

C)(B-A)∪A=B

D)(B-A)∪A=A

12.設(shè)S={1,2,3}，S上關(guān)系R的關(guān)系圖為

則R具有（）性質(zhì)。

A．自反性、對稱性、傳遞性；

B．反自反性、反對稱性；

C．反自反性、反對稱性、傳遞性；

D．自反性。

13.設(shè)A={?，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“?”的哈斯圖為（/ 36）

14.集合A={1，2，3，4}上的偏序關(guān)系圖為

則它的哈斯圖為（）。/ 36

15.集合A={1，2，3，4}上的偏序關(guān)系為）。

16.設(shè)R，S是集合A上的關(guān)系，則下列（A、R,S自反的，則R°S是自反的；

B、若R,S對稱的，則R°S是對稱的；

C、若R,S傳遞的，則R°S是傳遞的；

D、若R,S反對稱的，則R°S是反對稱的

17.設(shè)X為集合，|X|=n，在X上有（A、n2；

B、2n；

C、2^{2^n}；2。

18.下圖描述的偏序集中，子集{b,e,f}的上界為（/ 36，則它的Hass圖為（）斷言是正確的。）種不同的關(guān)系。

D、2^{n^）。}

A、b,c ；

B、a,b ；

C、b；

D、a,b,c。

19.設(shè)R，S是集合A上的關(guān)系，則下列說法正確的是（）。

A．若R，S 是自反的，則R°S是自反的；

B．若R，S 是反自反的，則R°S是反自反的；

C．若R，S 是對稱的，則R°S是對稱的；

D．若R，S 是傳遞的，則R°S是傳遞的。

20.設(shè)R是集合A上的二元關(guān)系，IA是A上的恒等關(guān)系，IA?R下面四 個命題為真的是（）。

A.R是自反的B.R是傳遞的C.R是對稱的 D.R是反對稱的

21.已知A,B是集合│A│=15，│B│=10，│A∪B│=20，則│A∩B│=（）

A．10

B．5

C．20

D．13

22.設(shè)X，Y，Z是集合，下列結(jié)論不正確的是（）。

A．若X?Y,則X∩Y=X

B．(X-Y)-Z=X-(Y∩Z)C．X ⊕X=?

D．X-Y=X∩(~Y)

23.設(shè)A={a,b,c,d}，A上的等價關(guān)系R={,,,}∪IA，則對應(yīng)于R的A的劃 分是（）。

A．{{a},{b,c},k68dsei}

B．{{a,b},{c},8rwenhs} C．{{a},,{c},h6ohy8o}

D．{{a,b},{c,d}}

24.設(shè)R是集合A上的二元關(guān)系，IA是A上的恒等關(guān)系，IA?R下面四 個命題為真的是（）A.R是自反的B.R是傳遞的C.R是對稱的 D.R是反對稱的

25.集合A={1，2，3，4}，則對 A 的元素進行劃分正確的是（）

A.{,{1,2},{3,4}}

B.{{1,2,3},{3,4}} C.{{1},{3,4}}

D.{{1,2,3,4}}

26.設(shè)集合A={2,{a},3,4}，B = {{a},3,4,1}，E為全集，則下列命題正確的是（）。

(A){2}∈A

(B){a}?A

(C)??{{a}}?B?E

(D){{a},1,3,4}?B

27.設(shè)集合A={1,2,3},A上的關(guān)系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備（）.(A)自反性

(B)傳遞性

(C)對稱性

(D)反對稱性

28.設(shè)A, B為集合，當(dāng)（）時A－B＝B.(A)A＝B(B)A?B(C)B?A(D)A＝B＝?.29.設(shè)集合A = {1,2,3,4}, A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)}, 則R具有（）。

(A)自反性

(B)傳遞性

(C)對稱性

(D)以上答案都不對 / 36

30.下列關(guān)于集合的表示中正確的為（）。

(A){a}∈{a,b,c}(B){a}?{a,b,c}(C)?∈{a,b,c}

(D){a,b}∈{a,b,c}

31.設(shè)R和S是集合A上的關(guān)系，若R和S是傳遞的，則（）

(A)R∩S是傳遞的；

(B)R∪S是傳遞的；

(C)R°S是傳遞的；

(D)以上都不對。

32.設(shè)集合X為人的全體，在X上定義關(guān)系R、S為R={| a，b∈X∧a是b的父親}，S={|a，b∈X∧a是b的母親|，那么關(guān)系{| a，b∈X∧a是b的祖母}的表達式為（）

(A)R°S

(B)R-1 °S

(C)S°R

(D)R°S-1

33.下列命題正確的是

（）(A){1,2}?{{1,2},{1,2,3},1}

(B){1,2}?{1,{1,2},{1,2,3},2}(C){1,2}?{{1},{2},{1,2}}

(D){1,2}∈{1,2,{2},{1,2,3}}

34.下列關(guān)系矩陣所對應(yīng)的關(guān)系具有反自反性的是（）

35.設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)于R1 &opl us;R2的說法正確的是（）

(A)一定是相容關(guān)系；

(B)一定不是相容關(guān)系；

(C)可能是也可能不是相容關(guān)系；

(D)一定是等價關(guān)系。

三.判斷題

1.設(shè)集合A={ a,b,c,d,e,f}，那么S1= {?, {a,b},{c,d},{f}}是集合A的一個覆蓋。（）

2.恒等關(guān)系既是等價關(guān)系又是偏序關(guān)系。

（）/ 36 3.設(shè)F,R都是二元關(guān)系,則(F°R)-1=F-1 °R-1。

（）

4.設(shè)A,B,C是三集合，已知A∪B＝A∪C，則一定有B＝C。

（）

5.設(shè)集合A={ a,b,c,d,e,f}，那么S1= { {a,b},{c,d,e},{e,f } }是集合A的劃分。（）

6.集合A上的等價關(guān)系確定了A的一個劃分。（）

7.集合A上的偏序關(guān)系的三個性質(zhì)是反自反性、對稱性和傳遞性。

（）

8.三種重要的二元關(guān)系是等價關(guān)系、偏序關(guān)系和函數(shù)關(guān)系，它們的共同特點是都具有自反 性。

（）

9.R的自反傳遞閉包也一定滿足自反關(guān)系，傳遞關(guān)系。（）

10.偏序集合中，鏈上的任何兩個元素都是有關(guān)系的。（）

11.設(shè)R是實數(shù)集，R上的關(guān)系f={||x-y|<2,x,y∈R}，R是相容關(guān)系。（）

12.空集是任何集合的真子集。（）

13.設(shè)集合A、B、C為任意集合，若A×B = A×C，則B = C。

（）

14.若集合A上的關(guān)系R是對稱的，則R-1也是對稱的。

15.空集是唯一的。

（）

16.全集不是唯一的。

（）

17.對于一個給定的集合，其劃分是唯一的。

（）

18.設(shè)R為X上的二元關(guān)系，則R是對稱的<=>R=Rc。

（）

19.設(shè)R為X上的二元關(guān)系，則R是反對稱的<=>R∩Rc?IX。

（）

20.設(shè)R為X上的二元關(guān)系，則R是傳遞的<=>(R°R)?R。

（）

四.計算題

1.設(shè)S={1,2,3,4,6,8,12,24}，“≤”為S上整除關(guān)系，問：

（1）偏序集的Hass圖如何？

（2）偏序集的極小元、最小元、極大元、最大元是什么?

2.A={a，b，c，d}，R={,,},R是集合A上的二元關(guān)系。/ 36（1）畫出的R的關(guān)系圖；

（2）求R的自反閉包和對稱閉包。

3.在實數(shù)平面上，畫出關(guān)系R={|x-y+2>0∧x-y-2<0}，并判定關(guān)系的特殊性質(zhì)。

4.R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}，(1)求 R1-1

(2)求R2 °R1

5.設(shè)集合A＝{a,b,c,d}上的關(guān)系R＝{,,,}，寫出它的關(guān)系矩陣和關(guān) 系圖，并用矩陣運算方法求出R的傳遞閉包。

6.設(shè)R是自然數(shù)集合N上的關(guān)系，且xRy<=>x+2y=10。

(1)求dom R；

(2)說明R具有的性質(zhì)(自反、反自反、對稱、反對稱、傳遞)。

7.設(shè)為一個偏序集，其中A={1，2，3，4，6，9，24，54},R是A上的整除關(guān)系。

（1）畫出R的哈斯圖；

（2）求A的極大元和極小元；

（3）求B={4,6}的上確界和下確界

8.集合S={1，2，3，4，5}，找出S上的等價關(guān)系，此關(guān)系能產(chǎn)生劃分{{1，2}，{3}，{4，5 }}，并畫出關(guān)系圖。

9.集合上的關(guān)系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>},寫出關(guān)系矩陣，畫出關(guān)系圖并討論R的性質(zhì)。

10.下圖是偏序集的哈斯圖，（1）寫出集合A,R;（2）求A的極大元和極小元；

（3）求B={e,f}的上確界和下確界。

11.設(shè)A={1,3,5,7}，定義A上的二元關(guān)系R:∈R <=> a

/ 36

12.A={a,b,c,}, R1={,,,},R2={,,}, 求：(1)R1-

1(2)R2 °R1

13.R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>} 求：(1)R1-1

(2)R1·R2

(3)R12

14.設(shè)A是正整數(shù)m=20的因子的集合，并設(shè)≤為整除關(guān)系。畫出A上的偏序集合圖(哈斯圖)，并指出A中的極大元和極小元，最大元和最小元。

五.證明題

1.令I(lǐng)是整數(shù)集合，I上關(guān)系R定義為：R＝{|x-y可被3整除}，求證R是自反、對稱和傳 遞的。

2.設(shè)A、B、C是任意集合，證明：A-(B∪C)=(A-B)∩(A-C)

3.如果集合A上的關(guān)系R和S是反自反的、對稱的和傳遞的，證明：是A上的等價關(guān)系。

4.集合A的任一劃分S誘導(dǎo)了A的一個等價關(guān)系R。

5.A, B為兩個任意集合，求證：A－(A∩B)=(A∪B)－B.6.試證明實數(shù)集R上的小于等于關(guān)系“≤” 是偏序關(guān)系。

7.設(shè)R,S為二元關(guān)系, 試證明(R°S)c =S c °Rc.8.設(shè)A、B、C為任意三個集合，證明A×(B∪C)=(A×B)∪(A×C)。

第4章

一.填空題

1.設(shè)f是集合X到集合Y的一個關(guān)系，如果對?x∈X，有唯一的y∈Y使得∈f，則稱關(guān)系

f為X到Y(jié)的__________。

2.設(shè)X，U，V，Y都是實數(shù)集，f1:X->U，且f1(x)=ex； f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3

(v)=cosv。那么f3°f2 °f1的 定義域是__________ ____。

3.設(shè)X，U，V，Y都是實數(shù)集，f1:X->U，且f1(x)=ex；

/ 36 f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3

(v)=cosv。那么f3°f2 °f1(x)=______________。

4.F={,,}______（“是”或者“不是”）函數(shù)。

5.F={,}_______（“是 ”或者“不是”）函數(shù)。

6.設(shè)f，g是自然數(shù)集N上的函數(shù)，?x∈N，f(x)=x+1，g(x)=2x，則f°g(x)＝_______。

7.設(shè)函數(shù)f:X→Y,如果對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f是

______函數(shù)。

8.設(shè)函數(shù)f:A→B, 則f 的逆關(guān)系是函數(shù)當(dāng)且僅當(dāng)f 是________（“入射”或“滿射”或“ 雙射”）。

9.若函數(shù)f:A→B存在逆函數(shù)f-1,則 f-1 °f =_________。

10.若函數(shù)f:A→B存在逆函數(shù)f-1,則f° f-1=_________。

11.如果IA=_______，則稱IA：A→A為集合X上的恒等函數(shù)。

12.函數(shù)f:I->I,f(j)=j(mod3)______（“是”或者“不是”）入射函數(shù)。

13.函數(shù)射函數(shù)。

_____（“是”或者“不是”）滿14.函數(shù)f:I->I,f(j)=j(mod3)_______(“是”或者“不是”)雙射函數(shù)。

15.函數(shù)f:I->N,f(i)=|2i|+1_______（“是”或者“不是”）入射函數(shù)。

16.函數(shù)________（“是”或者“不是”）滿射函數(shù)。

17.函數(shù)f:I->I,f(j)=j(mod3)______（“是”或者“不是”）雙射函數(shù)。

/ 36 18.函數(shù)f:R->R,f(r)=2r-15_____（“是”或者“不是”）入射函數(shù)。

19.函數(shù)f:I->I,f(j)=j(mod3)_______（“是”或者“不是”）滿射函數(shù)。

20.函數(shù)f:I->I,f(j)=j(mod3)_______（“是”或者“不是”）雙射函數(shù)。

二.選擇題

1.設(shè)集合A，B是有窮集合，且|A|=m，|B|=n，則從A到B有（）個不同的雙射函 數(shù)。

A、n ；

B、m ；

C、n!；

D、m!。

2.下列命題正確的有（）。

A、若g,f是滿射，則g°f是滿射；

B、若g°f是滿射，則g,f都是滿射；

C、若g°f是單射，則g,f都是單射；

D、若g°f是雙射，則f是雙射。

3.設(shè)f，g是函數(shù)，當(dāng)（）時，f=g。

A、?x∈domf 都有f(x)=g(x)；

B、domg?domf且f?g；

C、f與g的表達式相同；

D、domg=domf,rangef=rangef

4.N是自然數(shù)集，定義f:N->N,f(x)=(x)mod3（即x除以3的余數(shù)），則f是（。

A、滿射不是單射；B、單射不是滿射；C、雙射；D、不是單射也不是滿射。

5.下列關(guān)系中能構(gòu)成函數(shù)的是（）。

A、{|(x,y∈N)∧(x+y<10)}；B、{|(x,y∈R)∧(y=x2)}；

C、{|(x,y∈R)∧(y2 =x)}； D、{|(x,y∈I)∧(x≡y mod3)}

6.下面函數(shù)（）是單射而非滿射。

A、f：R->R，f(x)=-x2 +2x-1； B、f:Z+->R，f(x)=ln x；

C、f:R->Z，f(x)=[x],[x]表示不大于x的最大整數(shù)；

D、f:R->R，f(x)=2x+1。

7.若函數(shù)g和f的復(fù)合函數(shù)g°f 是雙射，則（）一定是正確的。

A、g是入射；B、f是入射；C、g是雙射；D、f是滿射。

8.X={a，b，c，d，e}，Y={1，2，3，4}，f從X到Y(jié)的映射，其中f(a)=2, f(b)=4, f(c)=1, f(d)=3,f(e)=4,則f是（）。

A雙射

B 滿射

C 單射

D 以上都不是

9.對于下面函數(shù)f的描述，那條不對（）

A)f(x)的像必然唯一存在B)如果f存在逆函數(shù)，則必是滿射的

/ 36）C)如果f是入射的，則必存在逆函數(shù)

D)如果f是雙射的，則必是入射的

10.設(shè)函數(shù)f：N→N（N 為自然數(shù)集），f(n)=n+1，下面四個命題為真的是（）。

A.f是單射

B.f是滿射

C.f是雙射的D.f非單射非滿射

三.判斷題

1.若X和Y的元素個數(shù)相同，即|X|=|Y|，則f : X->Y是入射的當(dāng)且僅當(dāng)它是一個滿射。（）

2.設(shè)f : X->Y是滿射，即對任意的y∈Y，必存在x∈X，使得f(x)= y成立。（）

3.一個函數(shù)必然是一個關(guān)系。（）

4.一個關(guān)系就是一個函數(shù)。（）

5.函數(shù)f : X->Y就是從集合X到集合Y的一個映射。（）

四.計算題

1.設(shè)R是實數(shù)集合，σ,τ,φ是R上的三個映射，σ(x)= x+3, τ(x)= 2x, φ(x)＝ x/4 ,試求復(fù)合映射σ?τ，σ?σ, σ?φ, φ?τ，σ?φ?τ.2.下面有三個關(guān)系圖，判斷它們是函數(shù)否？如果不是，請說明原因。

3.設(shè)A={1,2,3,4},B={x,y,z,w},決定下列(1)--(5)的每個關(guān)系R是不是從A到B的一個函數(shù)。如果是一個函數(shù),找出其定義域和值域,并確定它是不是入射的或滿射的。

(1){<1,x>,<2,x>,<3,z>,<4,y>};(2){<1,z>,<2,x>,<3,y>,<4,z>,<2,w>};(3){<1,z>,<2,w>,<3,x>,<4,y>};(4){<1,w>,<2,w>,<4,x>}(5){<1,y>,<2,y>,<3,y>,<4,y>}。

/ 36

4.設(shè)集合A={1,2,3}, f、g是集合A到A的函數(shù)，f={<1,2>,<2,3>,<3,1>}，g={<1,2>,<2,1>, <3,3>}, 計算f °g，g °f。

5.設(shè)集合A={1,2,3},B={a,b}, f:A->B, 且f={<1,a>,<2,b>,<3,b>}，試判斷f是不是一個函 數(shù)?如果是函數(shù)，是否存在逆函數(shù)？

五.證明題

1.令g οf 是一個復(fù)合函數(shù)。若g 和 f 是滿射，則g οf是滿射的。

2.設(shè)f °g是復(fù)合函數(shù)，證明：如果f °g是滿射的，那么f是滿射的。

3.設(shè)f °g是復(fù)合函數(shù)，證明：如果f °g是入射的，那么g是入射的。

/ 36

第二篇：離散數(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個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因為，若甲全錯了，則有?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，進而有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)。證明：因為

∈(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)，運算*滿足交換律和結(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。又因為運算*滿足交換律，所以aG＝G＝Ga。令e∈G使得a*e＝a。對任意的b∈G，令c*a＝b，則b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由運算*滿足交換律得e*b＝b，所以e是關(guān)于運算*的幺元。對任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由運算*滿足交換律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每個元素都存在逆元。故G是一群。

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

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

設(shè)G中結(jié)點為v1、v2、…、vn。由連通性，必存在與v1相鄰的結(jié)點，不妨設(shè)它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結(jié)點，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結(jié)點相鄰，得新邊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é)點u、v使得d(u)＋d(v)＜m，則有2n＝

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

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

一、（10分）使用將命題公式化為主范式的方法，證明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。證明：因為(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。

因為a*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é)點的連通圖G中，至少有n－1條邊。

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

設(shè)G中結(jié)點為v1、v2、…、vn。由連通性，必存在與v1相鄰的結(jié)點，不妨設(shè)它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結(jié)點，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結(jié)點相鄰，得新邊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，命題“所有演員都欽佩某些老師”符號化為___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)},則頂點2的入度和出度分別是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.設(shè)完全圖Kn有n個結(jié)點(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.已知某平面圖的頂點數(shù)是12，邊數(shù)是14，則該平面圖有__D___個面 A.3 B.2 C.5 D.4 16．設(shè)G是n個結(jié)點、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ù)集，+普通加法)

二、問答題

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人，有些職工（例如項目管理人員、設(shè)計人員）可能從事不止一個崗位的工作。每個職工至少被分在一個崗位?，F(xiàn)在軟件設(shè)計崗位（崗位A）（包括需求分析、概要設(shè)計和詳細設(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| 因為每個同學(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)

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

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

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

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

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

請通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細的推理步驟）解 設(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)系表達式

?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ù)運行前，保存當(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

第四篇：離散數(shù)學(xué)10年7月份試題

一、單項選擇題（每小題3分，本題共15分）

1．若集合A={1，{2}，{1，2}}，則下列表述正確的是(B)．

A．2?AB．{1}?AC．1?AD．2 ? A

2．已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為

(D)．A．6B．4C．3D．5

3．設(shè)無向圖G的鄰接矩陣為則G的邊數(shù)為(B)．, A．1B．7C．6D．14 ?0?1??1??1

??11111? 0011??0000??1001?1010??

4．設(shè)集合A={a}，則A的冪集為(C)． A．{{a}}B．{a，{a}}C．{?，{a}}D．{?，a} 5．下列公式中(B)為永真式． A．?A??B ? ?A??BB．?A??B ? ?(A?B)C．?A??B ? A?BD．?A??B ? ?(A?B)

二、填空題（每小題3分，本題共15分）

6．命題公式P??P的真值是假（或F，或0）．7．若無向樹T有5個結(jié)點，則T的邊數(shù)為

8．設(shè)正則m叉樹的樹葉數(shù)為t，分支數(shù)為i，則(m-1)it

9．設(shè)集合A={1，2}上的關(guān)系R＝{<1, 1>,<1, 2>}，則在R中僅需加一個元素，就可使新得到的關(guān)系為對稱的．10．(?x)(A(x)→B(x，z)∨C(y))中的自由變元有z，y．

三、邏輯公式翻譯（每小題6分，本題共12分）

11．將語句“今天上課．”翻譯成命題公式．

設(shè)P：今天上課，則命題公式為：P．

12．將語句“他去操場鍛煉，僅當(dāng)他有時間．”翻譯成命題公式．

設(shè) P：他去操場鍛煉，Q：他有時間，則命題公式為：P ?Q．

四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．

13．設(shè)集合A={1，2}，B={3，4}，從A到B的關(guān)系為f={<1, 3>}，則f是A到B的函數(shù)．

錯誤． 因為A中元素2沒有B中元素與之對應(yīng)，故f不是A到B的函數(shù)．

14．設(shè)G是一個有4個結(jié)點10條邊的連通圖，則G為平面圖．

錯誤．不滿足“設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．

五．計算題（每小題12分，本題共36分）

15．試求出（P∨Q）→（R∨Q）的析取范式．

（P∨Q）→（R∨Q）? ┐(P∨Q)∨（R∨Q）

?(┐P∧┐Q)∨（R∨Q）

?(┐P∧┐Q)∨R∨Q（析取范式）

16．設(shè)A={{1}, 1, 2}，B={ 1, {2}}，試計算

（1）A∩B（2）A∪B（3）A ?（A∩B）．

（1）A∩B={1}（2）A∪B={1, 2, {1}, {2}}（3）A?（A∩B）={{1}, 1, 2}

17．圖G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，對應(yīng)邊的權(quán)值依次為1、2、3、1、4及5，試

（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值． 3（1）G的圖形表示如圖一所示：ad

?0?1??1??1101111011?1 5 1??1 5?1 ?b c1 0?b c 圖二 a 3d（2）鄰接矩陣：圖一

（3）最小的生成樹如圖二中的粗線所示：權(quán)為：1+1+3=5

六、證明題（本題共8分）

18．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．

證明：設(shè)?x?A，因為R自反，所以x R x，即< x, x>?R；

又因為S自反，所以x R x，即< x, x >?S．

即< x, x>?R∩S

故R∩S自反．

第五篇：離散數(shù)學(xué)單元測試試題1

臨沂大學(xué)2015—2016學(xué)第1學(xué)期

離散數(shù)學(xué)單元測試試題一

(適用于2014級計算機科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程專業(yè)本科學(xué)生)

一、選擇題(共10題，每題3分，共30分)1.下列語句中為命題的是（D)。A.這朵花是誰的？ B.這朵花真美麗?。.這朵花是你的嗎？ D.這朵花是他的。

2.若p：他聰明；q：他用功；則“他雖聰明，但不用功”，可符號化為(B)。A.p∨q

B.p∧┐q

C.p→┐q

D.p∨┐q 3.命題公式p∨q→q的公式類型為（D)。A.矛盾式 B.非重言可滿足式 C.重言式

D.條件式

4.若F(x)：x是有理數(shù)，G(x)：x能被2整除，則“有的有理數(shù)能被2整除”，可符號化為（A)。

A.?x(F(x)∧G(x))

B.F(x)∧G(x)

C.?xF(x)

D.?xG(x)5.設(shè)F(x)表示x是火車，G(x)表示y是汽車，H(x，y)表示x比y快，命題“某些汽車比所有火車慢”的符號化公式是（B)。

A.?y(G(y)→?x(F(x)∧H(x,y)))B.?y(G(y)∧?x(F(x)→H(x,y)))C.?x?y(G(y)→(F(x)∧H(x,y)))D.?y(G(y)→(?x)(F(x)→H(x,y)))6．設(shè)集合A={1,2,3},A上的關(guān)系R={<1,2>,<1,3>,<3,3>},則R具有(D)。A.自反性 B.傳遞性 C.對稱性 D.以上答案都不對

######7.謂詞公式?x(P(x)∨?yR(y))→Q(x)中的 x是(C)。A.自由變元 B.約束變元

C.既是自由變元又是約束變元 D.既不是自由變元又不是約束變元

8.設(shè)X、Y是兩個集合且|X|＝n，|Y|＝m，則從X到Y(jié)可產(chǎn)生(A)個二元關(guān)系。A.n ? m B.mn

C.2n m D.nm 9.下列關(guān)于集合的表示中正確的為(C)。A.{a}?{a,b,c} B.{a}?{a,b,c}

C.??{a,b,c} D.{a,b}?{a,b,c} 10．設(shè)集合A={1,2,3,4,5},下列哪些是集合A的劃分(D)。A.{{1,2},{3,5}}

B.{{1,2,3,4},5} C.{ ?,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}}

二、填空題(共10空，每空3分，共30分)1.設(shè)p：2＋2＝5，q：明天是陰天，則命題“只要2＋2＝5，那么明天是陰天”可符號化為 p->q，其真值是 1。

2.設(shè)p:你陪伴我，q:你代我叫車子，r:我出去，則“如果你不陪伴我或不代我叫車子,我就不出去。”的符號化形式為 ?p/?q->r。

3.設(shè)p: 天下雨，q: 天刮風(fēng)，r: 我去書店，則“如果天不下雨并且不刮風(fēng)，我就去書店”的符號化形式為。

4.設(shè)S(x)∶x是大學(xué)生；K(x)∶x是運動員。則“有些運動員不是大學(xué)生”的符號化為。

5.設(shè)P(x)：x非常聰明；Q(x):x非常能干；a：小李；則“小李非常聰明且能干”的符號化形式為。

6.設(shè)F(x): x是人，G(x): x用右手寫字，則“有的人并不用右手寫字”的符號化形式為。

7.設(shè)S(x)：x是學(xué)生；L(x)：x喜歡英語。則“有些學(xué)生喜歡英語”的符號化為：。8.在公式?x(P(z)→Q(x,z))∧?zR(x,z)中，?x的轄域是

，z的轄域是。

三、計算與證明(共2題，每題20分，共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。

2.在命題邏輯自然推理系統(tǒng)中，構(gòu)造下面推理的證明。前提： p∨q, q→r, p→s, ┐s，結(jié)論：r ∧

(p∨q)。