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

第1章

一.填空題

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

3.4.5.6.7.全體小項(xiàng)的析取式必為_(kāi)___________________式。

8.P,Q為兩個(gè)命題，則德摩根律可表示為7.全體小項(xiàng)的析取式必為_(kāi)________式。

9.P,Q為兩個(gè)命題，則吸收律可表示為_(kāi)___________________。

10.設(shè)P：我有錢(qián)，Q：我去看電影。命題“雖然我有錢(qián)，但是我不去看電影”符號(hào)化為_(kāi)____ _______________。

11.設(shè)P：我生病，Q：我去學(xué)校。命題“如果我生病，那么我不去學(xué)校”符號(hào)化為_(kāi)________ ___________。

12.13.14./ 36

15.設(shè)P、Q為兩個(gè)命題，交換律可表示為_(kāi)___________________。

16.17.命題“如果你不看電影，那么我也不看電影”（P：你看電影，Q：我看電影）的符號(hào)化 為_(kāi)___________________。

18.19.20.21.P：你努力，Q：你失敗。命題“除非你努力，否則你將失敗”的翻譯為_(kāi)______________ _____。

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

25.全體小項(xiàng)的析取式為_(kāi)___________________。

26.命題“如果你不看電影，那么我也不看電影”（P：你看電影，Q：我看電影）的符號(hào)化 為_(kāi)___________________。

27.28.設(shè)P：它占據(jù)空間，Q：它有質(zhì)量，R：它不斷運(yùn)動(dòng)，S：它叫做物質(zhì)。命題“占據(jù)空間的，有質(zhì)量的而且不斷運(yùn)動(dòng)的叫做物質(zhì)”的符號(hào)化為_(kāi)___________________。

29./ 36 30.二.選擇題

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

A.2

B.3

C.4

D.1

4.判斷下列語(yǔ)句哪個(gè)是命題（）。

A.你喜歡唱歌嗎？

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

C.前進(jìn)！

D.給我一杯水吧！

5.6.7.8.永真式的否定是（）

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

9.下面哪一個(gè)是假命題（）。

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

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

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

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

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

A.p→q

B.q→p

C.p→┐q

D.┐p→q

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

A.p→q

B.q→p

C.┐q→p

D.┐p→q

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

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：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）。

A.p∧┐q

B．p∨┐q C.p∧q

D．p→┐q

15.一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫(xiě)法是唯一的（）。

Ａ．析取范式

B．合取范式

Ｃ．主析取范式

D．以上答案都不對(duì)

16.令p：今天下雨了，q：我上學(xué)，則命題“因?yàn)榻裉煜掠炅耍晕也簧蠈W(xué)了”可符號(hào)化

為（）。

A．p→┐q

B．p∨┐q C．p∧q

D．p∧┐q

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

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

D.A,A 18./ 36

19.20.21.22.23.24.25.下列語(yǔ)句哪個(gè)是命題（）。

A.9+5≤12

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

D 我正在說(shuō)謊。/ 36

26.27.28.n個(gè)命題變?cè)僧a(chǎn)生（）個(gè)互不等價(jià)的大項(xiàng)。

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.下列語(yǔ)句哪個(gè)不是命題（）。

A.雪是黑的。

B.天氣多好啊！

C.今天下雨。

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

三.判斷題

1.“我正在說(shuō)謊。”是一個(gè)命題。

（）

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

3.“她昨天做了一頓或兩頓飯。”是個(gè)原子命題。（）

4.命題公式是沒(méi)有真假值的，僅當(dāng)在一個(gè)公式中命題變?cè)么_定的命題代入時(shí)，才得到一 個(gè)命題。（）

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

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

7.一般來(lái)說(shuō)，n個(gè)命題變?cè)M成的命題公式共有2n中真值情況。（）

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

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

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

12.全體小項(xiàng)的析取式永為假。（）

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

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

15.由n個(gè)命題變?cè)M成不等值的命題公式的個(gè)數(shù)為2n。（）

四.計(jì)算題

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.約束變?cè)獡Q名時(shí)，一定要更改為作用域中沒(méi)有出現(xiàn)的變?cè)Q。（）

3.4.簡(jiǎn)單命題函數(shù)由一個(gè)謂詞和一些客體變?cè)M成。（）

5.單獨(dú)一個(gè)謂詞，不是完整的命題。（）

6.任意一個(gè)謂詞公式均和一個(gè)前束范式等價(jià)。（）

7.8.9.10.11.12.13./ 36

14.15.四.計(jì)算題 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表示三個(gè)集合，圖中陰影部分的集合表達(dá)式為_(kāi)___________________。/ 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>}畫(huà)出R的關(guān)系圖_ ________________。

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

則 R=_______________________。

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

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

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

9.偏序集〈Ρ（{a,b}），?〉的哈斯圖為_(kāi)_______________。

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

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

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

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

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

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

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

16.若R是集合A上的等價(jià)關(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的對(duì)稱閉包是__ _______________。

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個(gè)元素，則A的冪集有___________個(gè)元素。

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

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上的等價(jià)關(guān)系R=IA∪{(b,c),(c,b),(a,d),(d,a)}，則對(duì) 應(yīng)于R的A的劃分是_______________。

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

二.選擇題

1.設(shè)A={1,2,3}，則A上有（）個(gè)二元關(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.自反、對(duì)稱、傳遞的 B.自反、對(duì)稱、反對(duì)稱的C.對(duì)稱、反對(duì)稱、傳遞的 D.只有對(duì)稱性

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)反對(duì)稱性

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

A)rs(R)=sr(R)

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

D)rtr(R)=tr(R)

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

A）等價(jià)關(guān)系

B)偏序關(guān)系

C)同余關(guān)系

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

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

A)m

B)m!

C)2m

D)2m-1

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

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．自反性、對(duì)稱性、傳遞性；

B．反自反性、反對(duì)稱性；

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

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對(duì)稱的，則R°S是對(duì)稱的；

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

D、若R,S反對(duì)稱的，則R°S是反對(duì)稱的

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)系，則下列說(shuō)法正確的是（）。

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

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

C．若R，S 是對(duì)稱的，則R°S是對(duì)稱的；

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

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

A.R是自反的B.R是傳遞的C.R是對(duì)稱的 D.R是反對(duì)稱的

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上的等價(jià)關(guān)系R={,,,}∪IA，則對(duì)應(yīng)于R的A的劃 分是（）。

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

B．{{a,b},{c},jdb3l39rxn9} C．{{a},{b},{c},jdb3l39rxn9}

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

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

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

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)對(duì)稱性

(D)反對(duì)稱性

28.設(shè)A, B為集合，當(dāng)（）時(shí)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)對(duì)稱性

(D)以上答案都不對(duì) / 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)以上都不對(duì)。

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的祖母}的表達(dá)式為（）

(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)系矩陣所對(duì)應(yīng)的關(guān)系具有反自反性的是（）

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

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

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

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

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

三.判斷題

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

2.恒等關(guān)系既是等價(jià)關(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上的等價(jià)關(guān)系確定了A的一個(gè)劃分。（）

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

（）

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

（）

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

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

11.設(shè)R是實(shí)數(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是對(duì)稱的，則R-1也是對(duì)稱的。

15.空集是唯一的。

（）

16.全集不是唯一的。

（）

17.對(duì)于一個(gè)給定的集合，其劃分是唯一的。

（）

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

（）

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

（）

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

（）

四.計(jì)算題

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

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

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

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

（2）求R的自反閉包和對(duì)稱閉包。

3.在實(shí)數(shù)平面上，畫(huà)出關(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＝{,,,}，寫(xiě)出它的關(guān)系矩陣和關(guān) 系圖，并用矩陣運(yùn)算方法求出R的傳遞閉包。

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

(1)求dom R；

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

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

（1）畫(huà)出R的哈斯圖；

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

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

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

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

10.下圖是偏序集的哈斯圖，（1）寫(xiě)出集合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)系。畫(huà)出A上的偏序集合圖(哈斯圖)，并指出A中的極大元和極小元，最大元和最小元。

五.證明題

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

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

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

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

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

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

第4章

一.填空題

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

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

2.設(shè)X，U，V，Y都是實(shí)數(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í)數(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,如果對(duì)X中的任意兩個(gè)不同的x1和x2，它們的象y1和y2也不同，我們說(shuō)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有（）個(gè)不同的雙射函 數(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)（）時(shí)，f=g。

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

B、domg?domf且f?g；

C、f與g的表達(dá)式相同；

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.對(duì)于下面函數(shù)f的描述，那條不對(duì)（）

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

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

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

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

A.f是單射

B.f是滿射

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

三.判斷題

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

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

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

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

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

四.計(jì)算題

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

3.設(shè)A={1,2,3,4},B={x,y,z,w},決定下列(1)--(5)的每個(gè)關(guān)系R是不是從A到B的一個(gè)函數(shù)。如果是一個(gè)函數(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>}, 計(jì)算f °g，g °f。

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

五.證明題

1.令g οf 是一個(gè)復(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分）在某次研討會(huì)的休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音分別作出下述判斷： 甲說(shuō)：王教授不是蘇州人，是上海人。乙說(shuō)：王教授不是上海人，是蘇州人。丙說(shuō)：王教授既不是上海人，也不是杭州人。

王教授聽(tīng)后說(shuō)：你們3人中有一個(gè)全說(shuō)對(duì)了，有一人全說(shuō)錯(cuò)了，還有一個(gè)人對(duì)錯(cuò)各一半。試判斷王教授是哪里人？

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

王教授只可能是其中一個(gè)城市的人或者3個(gè)城市都不是。所以，丙至少說(shuō)對(duì)了一半。因此，可得甲或乙必有一人全錯(cuò)了。又因?yàn)椋艏兹e(cuò)了，則有?Q∧P，因此，乙全對(duì)。同理，乙全錯(cuò)則甲全對(duì)。所以丙必是一對(duì)一錯(cuò)。故王教授的話符號(hào)化為：

((?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的且具有自反性、對(duì)稱性和傳遞性的最小關(guān)系。

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

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

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

四、（15分）集合A＝{a，b，c，d，e}上的二元關(guān)系R為R＝{，，，，，，，，，，，，，}，(1)寫(xiě)出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)系矩陣可知，對(duì)角線上所有元素全為1，故R是自反的；rij＋rji≤1，故R是反對(duì)稱的；可計(jì)算對(duì)應(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。于是可證，對(duì)任意的a∈G，有aG＝G。又因?yàn)檫\(yùn)算*滿足交換律，所以aG＝G＝Ga。令e∈G使得a*e＝a。對(duì)任意的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)算*的幺元。對(duì)任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由運(yùn)算*滿足交換律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每個(gè)元素都存在逆元。故G是一群。

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

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

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

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

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

2若存在兩個(gè)不相鄰結(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）矛盾。所以，對(duì)于G中任意兩個(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)畫(huà)出R的關(guān)系圖。(2)寫(xiě)出R的關(guān)系矩陣。

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

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

經(jīng)過(guò)計(jì)算可得

101110110??0? 0??0??(3)對(duì)于R的關(guān)系矩陣，由于對(duì)角線上不全為1，R不是自反的；由于對(duì)角線上存在非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)對(duì)任意的x，y，x1，y1∈R，若f()＝f()，則＝，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y(tǒng)1，故f是單射。

(2)對(duì)任意的∈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分）給定群，若對(duì)G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，3試證是Abel群。

證明 對(duì)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個(gè)結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。

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

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

（2）試給出|V|＝n，|E|＝(n－1)(n－2)的簡(jiǎn)單無(wú)向圖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______是錯(cuò)的。

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.下列語(yǔ)句中，不是命題的是____A_________ A.我說(shuō)的這句話是真話； B.理發(fā)師說(shuō)“我說(shuō)的這句話是真話”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以這些煤不會(huì)燃燒；

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佩某些老師”符號(hào)化為_(kāi)__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),下面的描述中錯(cuò)誤的是__B_____ A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）

B．z是該謂詞公式的約束變?cè)?/p>

C．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變?cè)?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、對(duì)稱性； D、傳遞性。

10.集合A，R是A上的關(guān)系，如果R是等價(jià)關(guān)系，則R必須滿足的條件是__D___ A.R是自反的、對(duì)稱的 B.R是反自反的、對(duì)稱的、傳遞的 C.R是自反的、對(duì)稱的、不傳遞的 D.R是自反的，對(duì)稱的、傳遞的 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個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)下面條件__C____滿足時(shí)，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___個(gè)面 A.3 B.2 C.5 D.4 16．設(shè)G是n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面的連通平面圖，則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ù)集，+普通加法)

二、問(wèn)答題

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

請(qǐng)將這段程序化簡(jiǎn)，并說(shuō)明化簡(jiǎn)的理由。解：簡(jiǎn)化的程序：

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)過(guò)等值演算可得，A與下面的公式是等值的 P∧q∧r→s

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

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

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

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

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

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

(n<=m)插空問(wèn)題

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

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

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

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

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

解：①這是一個(gè)多重集的組合問(wèn)題

類(lèi)別數(shù)是k=3，選取的元素個(gè)數(shù)是 r=5 多重集組合數(shù)的計(jì)算公式是 N?所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由選取的球只有2個(gè) 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è)計(jì)人員）可能從事不止一個(gè)崗位的工作。每個(gè)職工至少被分在一個(gè)崗位。現(xiàn)在軟件設(shè)計(jì)崗位（崗位A）（包括需求分析、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)等工作）的人數(shù)是15人，代碼編寫(xiě)崗位（崗位B）的人數(shù)是32人，軟件測(cè)試崗位（崗位C）的人數(shù)是28人，同時(shí)參加崗位A和崗位B的有12人, 同時(shí)參加崗位B和崗位C的有8人, 同時(shí)參加崗位A和崗位C組的有3人，問(wèn)，三個(gè)崗位參加的有多少人？

解： 已知 |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)槊總€(gè)同學(xué)至少參加一個(gè)小組，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三個(gè)小組都參加的人數(shù)是13人

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

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

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

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

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

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

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

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

10.插入排序算法的時(shí)間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ù)中國(guó)剩余定理，特解是：

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,選取兩個(gè)素?cái)?shù)p=7,q=19,使用RSA算法： ① 計(jì)算出密鑰參數(shù)

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

公鑰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ù)上述遞推公式可以計(jì)算出：A1?502mod133?106,A2?1062mod133?64

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

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

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

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

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

//數(shù)組s[]:函數(shù)運(yùn)行前，保存當(dāng)前的組合，函數(shù)結(jié)束后，是新生成的下一個(gè)組合 //n,r:表示從n個(gè)元素中選取r個(gè)元素的組合 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三人選派若干人出國(guó)考察, 需滿足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問(wèn)有幾種可能的選派方案? 9

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

一、單項(xiàng)選擇題（每小題3分，本題共15分）

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

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

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

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

3．設(shè)無(wú)向圖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．若無(wú)向樹(shù)T有5個(gè)結(jié)點(diǎn)，則T的邊數(shù)為

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

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

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

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

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

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

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

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

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

錯(cuò)誤． 因?yàn)锳中元素2沒(méi)有B中元素與之對(duì)應(yīng)，故f不是A到B的函數(shù)．

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

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

五．計(jì)算題（每小題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}}，試計(jì)算

（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)}，對(duì)應(yīng)邊的權(quán)值依次為1、2、3、1、4及5，試

（1）畫(huà)出G的圖形；（2）寫(xiě)出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹(shù)及其權(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）最小的生成樹(shù)如圖二中的粗線所示：權(quán)為：1+1+3=5

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

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

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

又因?yàn)镾自反，所以x R x，即< x, x >?S．

即< x, x>?R∩S

故R∩S自反．

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

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

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

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

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

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

B.p∧┐q

C.p→┐q

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

D.條件式

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

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

B.F(x)∧G(x)

C.?xF(x)

D.?xG(x)5.設(shè)F(x)表示x是火車(chē)，G(x)表示y是汽車(chē)，H(x，y)表示x比y快，命題“某些汽車(chē)比所有火車(chē)慢”的符號(hào)化公式是（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.對(duì)稱性 D.以上答案都不對(duì)

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

C.既是自由變?cè)质羌s束變?cè)?D.既不是自由變?cè)植皇羌s束變?cè)?/p>

8.設(shè)X、Y是兩個(gè)集合且|X|＝n，|Y|＝m，則從X到Y(jié)可產(chǎn)生(A)個(gè)二元關(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，那么明天是陰天”可符號(hào)化為 p->q，其真值是 1。

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

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

4.設(shè)S(x)∶x是大學(xué)生；K(x)∶x是運(yùn)動(dòng)員。則“有些運(yùn)動(dòng)員不是大學(xué)生”的符號(hào)化為。

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

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

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

，z的轄域是。

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

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

(p∨q)。