本科離散數(shù)學(xué)復(fù)習(xí)題

本文格式為Word版，下載可任意編輯——本科離散數(shù)學(xué)復(fù)習(xí)題離散數(shù)學(xué)復(fù)習(xí)題

一、填空題。

1.集合A={?,1}，B={1,2}，則?(A)??(B)=___{（?，?），（?，1），（1，

?）}______.*

A與B的笛卡爾積A?B=____{（?，1），（?，2），（1,1），（1,2）}_____.2.設(shè)集合A={1,2,3}，B={a,b,c,d}，則A?B共有__12___個元素。A到B的關(guān)系

(包括空關(guān)系)共有__2^12___個，其中又有__4^3___個是A?B的函數(shù),有__4___個是A?B的內(nèi)射,有___4__個是A?B的雙射。

若#A=m,#B=n,A*B有mn個元素，A到B的關(guān)系共有2^mn個，A到B的函數(shù)有n^m個，有P（從上到下是m，n）個A到B的內(nèi)射，有n！個A到B的雙射。（課本75頁）

3.設(shè)A={a1,a2,a3,a4,a5,a6,a7,a8}.則由B15表示的A的子集是____{a5,a6,a7,a8}________.

A的一個子集{a2,a4,a5,}可表示為____B88________

P8B15=B00001111={a5,a6,a7,a8},{a2,a4,a5}=B01011000=B884.若{1,2,4,7}?A={1,2,4,7,8,10,11}且{1,2,4,7}?A={1,7},則A=_{1,7,8,10,11}____

5.集合A上的兩個關(guān)系?1={(1,2),(1,3),(2,1)(2,2),(4,1)},

?2={(1,3),(3,1)}，則

?1??2=__{(1,3)}__.?1??2.={(1,2),(1,3),(2,1),(2,2),(3,1),(4,1)}

?1?2=_{(1,1),(2,3),(4,3)}_.?2?1=_{(3,2)}_.?1c=____________.*

P43

6.集合A={1,2,3}上的關(guān)系?={(1,1),(1,2),(1,3),(3,3)}具有的性質(zhì)是_傳遞性_.

P52自反性：apb

對稱性：任何apb必有bpa

反對稱：每個apb和bpa必有a=b傳遞性：每當(dāng)apb和bpc必有apc

7.集合A={1,2,3,4}上具有自反性的關(guān)系有___15__個，

具有對稱性的關(guān)系有___44__個.

N個元素集合上有2^(n*(n+1)/2)個關(guān)系是對稱的、有2^n*3^(n(n+1)/2)個關(guān)系是反對稱

1

的、有3^(n(n-1)/2)個關(guān)系是非對稱的、有2^n(n-1)個關(guān)系是反自反、有2^(n(n-1)/2)個關(guān)系是既不自反也不反自反、有2^(n^2)-2*2^(n(n-1))個關(guān)系是自反和對稱的

8.集合A={a,b,c,d}，則A共有__15___中不同的分劃。A上共有__11___個不同的等價關(guān)系。若其中的一個分劃?A={{a},{b,c},coz8hjv}，

則與之對應(yīng)的等價關(guān)系是_{（a,a）,(b,b),(b,c),(c,b),(c,c),(d,d)}_.*

P19V,（最大下界的符號）>是一個含有元素1和0的格，對于L中的一個元素l，假使有元素l非使得lVl非=1，l（最大下界的符號）l非=0，則稱l非是l的補

12.設(shè)為任意的格,a,b,c,d?L,若a?b且b?c,則a?c=______c________.

b?c=_______b_______.a?c=_______a_______.a?b=_____b_________.13.Z是整數(shù)集,函數(shù)?定義為:Z?Z,且?(X)=|X|-2X,則函數(shù)?的類型是_雙射_

(內(nèi)射,滿射,雙射).

P75當(dāng)ai/=aj時，f(ai)/=f(aj)(也就是當(dāng)f(ai)=f(aj)時，有ai=aj)，則稱f為由A到B的內(nèi)射

若f(A)=B,則稱f為由A到B的滿射

若f既是內(nèi)射又是滿射，則稱f為A到B的雙射

14.設(shè)A={1,2,3,4,5},函數(shù)?:A?A,?(X)=6-X,則函數(shù)?是一個_____雙____射.15.含10條邊的圖的總度數(shù)是____20________.

每條邊貢獻(xiàn)兩個度數(shù)，所以10條邊貢獻(xiàn)20個度數(shù)16.含有8個頂點的完全圖共有___28___條邊.

P233具有n個節(jié)點和m條邊的圖稱為（n，m）圖，在一個完全的（n，m）

2

圖中，m=C（上2下n）=n（n-1）/2

17.含6個結(jié)點,9條邊的無向連通圖,要得到此圖的一棵生成樹,必需刪去_4_條邊.

P267在（n，m）樹中，m=n-1，須刪去的總數(shù)為9-（6-1）=418.畫不同構(gòu)且有6個結(jié)點的樹共有___6___個.

畫樹時，n=6，所以m=n-1=5，所以度數(shù)為10，分為：（1）111115（2）111124（3）111133（4）111223（5）112222

19.簡單圖G=共有10個結(jié)點,其中6個結(jié)點的度數(shù)為3，其余4個結(jié)點的度數(shù)都為2,則該圖共有__13__條邊.該圖的補圖共有__32__條邊.

度數(shù)和為邊數(shù)的兩倍，補圖的邊即為完全圖的邊（m=C（上2下n）=n（n-1）/2）減去該圖的邊

20.一棵樹有2個2度分支點,1個3度分支點,3個4度分支點,則此樹共有__7__片樹葉.

21.命題P:\小王學(xué)過高等數(shù)學(xué)\小王學(xué)過離散數(shù)學(xué)\則符合命題\小王學(xué)過高等數(shù)學(xué)但沒有學(xué)過離散數(shù)學(xué)\可表示為__p^?Q_________.命題?(P?Q)表示的復(fù)合命題含義是:___小王沒學(xué)過高等數(shù)學(xué)和離散數(shù)學(xué)。_______________.22.公式((?P?Q)?(?Q??P))?P可化簡為___________P^Q________________.

23.將公式P?(Q?P)化成與之等價的且只含?和?的公式,

則此公式為:____(?P^?Q)V(?P^Q)V(p^?Q)V(P^Q)______________.

24.令P,Q的賦值分別為1,0.則公式（(?P?Q)?(?Q??P)）?（P??Q）

的真值為____1______________.二、選擇題。

1.設(shè)集合A={a，{a}}，則以下錯誤的是(C).

A){a}??(A);B){a}??(A);C){{a}}??(A);

D){{a}}??(A);

2.集合A={1,2,3,4,5,6,7,8,9,10},A上的關(guān)系?={(x,y)|x+y=10，x,y?A},則關(guān)系

?具有的性質(zhì)是(D).

A)自反的;B)對稱的;C)傳遞的,對稱的;D)反自反的,對稱的;

3.設(shè)集合X={-1,1,2,3}與Y={1,2,3,4,5,9},?(x)=x2,是X?Y的一個函數(shù),則以下正確的是(A).

A)?是入射但不是滿射;B)?是滿射但不是入射;C)?是雙射;D)?既不是入射也不是滿射;

4.設(shè)I為整數(shù)集合.A={x|x2必定是有限格;B)在格中,?a,b?L,必有a?(a?b)=a;

C)格是有補格當(dāng)且僅當(dāng)有元素存在補元;

D)在有補分派格中,?a,b?L,必有a?b=a?b;

8.一個含n個結(jié)點,連通且有圈的簡單圖,至少有(A)條邊.A)n;B)n+1;C)n+2;D)2n-1;三、判斷題。

1.設(shè)A={?},B=?(?(A)),則:{?}?B且{?}?B.2.若A-B?B,則B?A.

(F)(F)(T)

3.集合A={a,b,c}上的關(guān)系?={(a,b),(a,c)}是不可傳遞的.

4.平面上直線間的平行關(guān)系是等價關(guān)系.（T）5.若A到B關(guān)系?和g都具有自反性,則?g必也具有自反性.(T)6.若??g是滿射,則?必是滿射.（內(nèi)射看前，滿射看后）(Ｆ)7.若?,g都是入射,則g??也是入射.(Ｔ)8.在有限分派格中,一個元素若有補元,則補元一定是唯一的.(Ｆ)9.K4有10個生成子圖.（１１）(Ｆ)10.三個(4,2)無向簡單圖中,至少有兩個同構(gòu).(Ｔ)11.凡陳述句都是命題.(Ｆ)12.命題公式(P?(P?Q))?Q是矛盾式.(Ｆ)13.命題\假使1+2=3，那么雪是黑的\是真命題.。（Ｆ）14.判定偏序集是否為格.（教材P150頁圖7-3、P174頁圖7-12）四、解答題。

1.設(shè)集合A={1,2,4,5},B={1,2,3,5,16,25},

A到B的關(guān)系?={(x,y)|x?A,y?B且y=x2},1)寫出?的所有元素;

2)?={(x,y)|(1,1),(4,16),(5,25)}

3)求出關(guān)系?的定義域及值域;定義域為{1,4,5},值域為{1，16，25}3)寫出關(guān)系?的關(guān)系矩陣M?;

4

1245110002000030000500001600102500014)判斷關(guān)系?是否為A?B的一個函數(shù),為什么?不是！A中的2并沒有像

2.設(shè)集合A={1,2,3,4},?是A上的一個關(guān)系,?的關(guān)系矩陣如下:

M?=

求:?的自反閉包r(?),對稱閉包s(?),傳遞閉包t(?).

自反閉包r(p)={(1,1),(2,2),(3,3),(4,4),(1,4),(2,3),(3,1),(4,3)}

對稱閉包s(p)={(1,1),(1,4),(4,1),(2,2),(2,3),(3,2),(3,1),(1,3),(4,3),(3,4),(4,4)}

3.設(shè)集合A={1,2,3,6,12,24,36,72},A上的整除關(guān)系?={(a,b)|a,b?A且a|b}.

①畫出偏序集的哈斯圖;

②對于A的子集B={6,24,36}