1、-?離散數學?期末復習題一、 填空題每空2分，共20分1、集合A上的偏序關系的三個性質是、和。2、一個集合的冪集是指。3、集合A=b,c，B=a,b,c,d,e，則AB=。4、集合A=1,2,3,4，B=1,3,5,7,9，則AB=。5、假設A是2元集合, 則 2A 有個元素。6、集合 A=1,2,3，A上的二元運算定義為：a* b = a和b兩者的最大值，則2*3=。7、設A=a, b,c,d , 則A=。8、對實數的普通加法和乘法， 是加法的冪等元， 是乘法的冪等元。9、設a,b,c是阿貝爾群<G,+>的元素，則-(a+b+c)=。10、一個圖的哈密爾頓路是。11、不能再分解的

2、命題稱為，至少包含一個聯結詞的命題稱為。12、命題是。13、如果p表示王強是一名大學生，則p表示。14、與一個個體相關聯的謂詞叫做。15、量詞分兩種：和。16、設A、B為集合，如果集合A的元素都是集合B的元素，則稱A是B的。17、集合上的三種特殊元是、及。18、設A=a, b，則(A) 的四個元素分別是：，。19、代數系統是指由及其上的或組成的系統。20、設<L,*1,*2>是代數系統，其中是*1,*2二元運算符，如果*1,*2都滿足、，并且*1和*2滿足，則稱<L,*1,*2>是格。21、集合A=a,b,c,d，B=b ，則A B=。22、設A=1, 2, 則A=。2

3、3、在有向圖中，結點v的出度deg+(v)表示，入度deg-(v)表示以。24、一個圖的歐拉回路是。25、不含回路的連通圖是。26、不與任何結點相鄰接的結點稱為。27、推理理論中的四個推理規則是、。二、判斷題每題2分，共20分1、空集是唯一的。2、對任意的集合A，A包含A。3、恒等關系不是對稱的，也不是反對稱的。4、集合1,2,3,3和1,2,2,3是同一集合。5、圖G中，與頂點v關聯的邊數稱為點v的度數，記作deg(v)。6、在實數集上，普通加法和普通乘法不是可結合運算。7、對于任何一命題公式，都存在與其等價的析取式和合取式。8、設A,*是代數系統，aA，如果a*aa，則稱a為A，*的等冪元

4、。9、設f：AB， g：BC。假設f，g都是雙射，則gf不是雙射。10、無向圖的鄰接矩陣是對稱陣。11、一個集合不可以是另一個集合的元素。12、映射也可以稱為函數，是一種特殊的二元關系。13、群中每個元素的逆元都不是惟一的。14、<0,1,2,3,4,MA*,MIN>是格。15、樹一定是連通圖。16、單位元不是可逆的。17、一個命題可賦予一個值，稱為真值。18、復合命題是由連結詞、標點符號和原子命題復合構成的命題。19、任何兩個重言式的合取或析取不是一個重言式。20、設f：AB， g：BC。假設f，g都是滿射，則gf不是滿射。21、集合1,2,3,3和1,2,3是同一集合。22、零

5、元是不可逆的。23、一般的，把與n個個體相關聯的謂詞叫做一元謂詞。24、“我正在說謊。不是命題。25、用A表示“是個大學生，c表示“三，則A(c)：三是個大學生。26、設F<3,3>,<6,2>，則 F-1 <6,3>,<2,6>。27、歐拉圖是有歐拉回路的圖。28、設f：AB， g：BC。假設f，g都是單射，則gf也是單射。三、計算題每題10分，共40分1、設A=c,d, B=0,1,2，則計算A×B，B×A。2、A = a,b,c，B = 1,2，計算A×B。3、A = a,b,c，計算A×A。4、符號

6、化命題“如果2大于3，則2大于4。5、符號化命題“并不是所有的兔子都比所有的烏龜跑得快。6、符號化命題“2是素數且是偶數。7、設A=a,b,c,d，R是A的二元關系，定義為：R=<a,a>,<a,b>,<b,a>,<c,b>,<c,a>,<d,c>,<d,b>,<d,a>，寫出A上二元關系R的關系矩陣。8、設A=1,2,3,4，R是A的二元關系，定義為：R=<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,

7、<4,2>,<4,1>，寫出A上二元關系R的關系矩陣。9、設有向圖G如下所示，求各個結點的出度、入度和度數。10、設有向圖G如下所示，求各個結點的出度、入度和度數。11、設無向圖G如下所示，求它的鄰接矩陣。12、求命題公式(pq)的真值表。13、設<2*+y, 5>=<10, *3y>，求*，y。14、R1、R2是從1, 2, 3, 4, 5到2, 4, 6的關系，假設R1<1, 2>, <3, 4>, <5, 6>，R2=<1, 4>, <2, 6>，計算domR1，ranR1，fld

8、R1，domR2，ranR2，fldR2。15、例：設A=1, 2, 3, 4, 5，B=3, 4, 5, C=1, 2, 3，A到B的關系R=<*, y>|*+y=6，B到C的關系S=<y, z>|yz=2，求RS。16、集合A=a, b, c，B=1, 2, 3, 4, 5，R是A上的關系，S是A到B的關系。R=<a, a>, <a, c>, <b, b>, <c, b>, <c, c>，S=<a, 1>, <a, 4>, <b, 2>, <c, 4>, &l

9、t;c, 5>，求RS，S1R117、A1, 2, 3, 4, 5, 6，D是整除關系，畫出哈斯圖并求出最小元、最大元、極小元和極大元。18、設集合A=a,b,c，A上的關系R=<a,a>, <a,b>, <b,c>，求R的自反、對稱、傳遞閉包。19、求以下圖中頂點v0與v5之間的最短路徑。20、分別用三種不同的遍歷方式寫出對以下圖中二叉樹點的次序。四、證明題每題10分，共20分1、假設R和S都是非空集A上的等價關系，證明RS是A上的等價關系。2、證明格拉底論證：凡人要死。格拉底是人，格拉底要死。3、PQ，QR，R，SPÞS4、在群<G

10、,*>中，除單位元 e 外，不可能有別的冪等元。5、設R和S是二元關系，證明：(RS)-1=R-1S-16、證明：(QS)R)(S(PR) = (S(PQ)R.7、設I是整數集合，k是正整數，I上的關系R<*, y>|*, y I，且*y可被k整除，證明R是等價關系。8、證明(pq)r)Û (qp)r)9、證明(PQ) (PR) (QS)ÞSR10、證明PQ，QR，RSÞP11、證 (*)(P(*)Q(*) Þ(*)P(*) ($*)Q(*)12、證明定理：設<G, >是群，對于任意a, bG，則方程a*=b與ya=b，在群

11、有唯一解。?離散數學?復習題參考答案一、填空題每空1分，共20分1、集合A上的偏序關系的三個性質是自反性、反對稱性和傳遞性。2、一個集合的冪集是指該集合所有子集的集合。3、集合A=b,c，B=a,b,c,d,e，則AB=a,b,c,d,e。4、集合A=1,2,3,4，B=1,3,5,7,9，則AB=1,3。5、假設A是2元集合, 則 2A 有 4 個元素。6、集合 A=1,2,3，A上的二元運算定義為：a* b = a和b兩者的最大值，則2*3= 3 。7、設A=a, b,c,d, 則A= 4 。8、對實數的普通加法和乘法， 0 是加法的冪等元， 1 是乘法的冪等元。9、設a,b,c是阿貝爾群

12、<G,+>的元素，則-(a+b+c)=(-a)+( -b)+( -c)。10、一個圖的哈密爾頓路是一條通過圖中所有結點一次且恰好一次的路。11、不能再分解的命題稱為原子命題，至少包含一個聯結詞的命題稱為復合命題。12、命題是能夠表達判斷分辯其真假的述語句。13、如果p表示王強是一名大學生，則p表示王強不是一名大學生。14、與一個個體相關聯的謂詞叫做一元謂詞。15、量詞分兩種：全稱量詞和存在量詞。16、設A、B為集合，如果集合A的元素都是集合B的元素，則稱A是B的子集。17、集合上的三種特殊元是單位元、零元及可逆元。18、設A=a, b，則 (A) 的四個元素分別是：空集，a，b，a

13、, b。19、代數系統是指由集合及其上的一元或二元運算符組成的系統。20、設<L,*1,*2>是代數系統，其中是*1,*2二元運算符，如果*1,*2都滿足交換律、結合律，并且*1和*2滿足吸收律，則稱<L,*1,*2>是格。21、集合A=a,b,c,d，B=b ，則A B= a, c,d 。22、設A=1, 2, 則A= 2 。23、在有向圖中，結點v的出度deg+(v)表示以v為起點的邊的條數，入度deg-(v)表示以v為終點的邊的條數。24、一個圖的歐拉回路是一條通過圖中所有邊一次且恰好一次的回路。25、不含回路的連通圖是樹。26、不與任何結點相鄰接的結點稱為孤立結

14、點。27、推理理論中的四個推理規則是全稱指定規則 (US規則)、全稱推廣規則 (UG規則)、存在指定規則 (ES規則) 、存在推廣規則 (EG規則)。二、判斷題每題2分，共20分1、。2、。3、×。4、。5、。6、×。7、。8、。9、×。10、。11、×。12、。13、×。14、。15、。16、×。17、。18、。19、×。20、×。21、。22、。23、×。24、。25、。26、×。27、。28、。1、空集是唯一的。2、對任意的集合A，A包含A。3、恒等關系不是對稱的，也不是反對稱的。4、集合

15、1,2,3,3和1,2,2,3是同一集合。5、圖G中，與頂點v關聯的邊數稱為點v的度數，記作deg(v)。6、在實數集上，普通加法和普通乘法不是可結合運算。7、對于任何一命題公式，都存在與其等價的析取式和合取式。8、設A,*是代數系統，aA，如果a*aa，則稱a為A，*的等冪元。9、設f：AB， g：BC。假設f，g都是雙射，則gf不是雙射。10、無向圖的鄰接矩陣是對稱陣。11、一個集合不可以是另一個集合的元素。12、映射也可以稱為函數，是一種特殊的二元關系。13、群中每個元素的逆元都不是惟一的。14、<0,1,2,3,4,MA*,MIN>是格。15、樹一定是連通圖。16、單位元不

16、是可逆的。17、一個命題可賦予一個值，稱為真值。18、復合命題是由連結詞、標點符號和原子命題復合構成的命題。19、任何兩個重言式的合取或析取不是一個重言式。20、設f：AB， g：BC。假設f，g都是滿射，則gf不是滿射。21、集合1,2,3,3和1,2,3是同一集合。22、零元是不可逆的。23、一般的，把與n個個體相關聯的謂詞叫做一元謂詞。24、“我正在說謊。不是命題。25、用A表示“是個大學生，c表示“三，則A(c)：三是個大學生。26、設F<3,3>,<6,2>，則 F-1 <6,3>,<2,6>。27、歐拉圖是有歐拉回路的圖。28、設f：

17、AB， g：BC。假設f，g都是單射，則gf也是單射。三、計算題每題10分，共40分1、設A=c,d, B=0,1,2，則A×B=<c,0>,<c,1>,<c,2>,<d,0>,<d,1>,<d,2>，B×A= <0,c>,<0,d>,<1,c>,<1,d>,<2,c>,<2,d>。2、A = a,b,c，B = 1,2，A×B = a,b,c ×1,2 = <a,1>,<b,1>,<

18、;c,1>,<a,2>,<b,2>,<c,2>。3、A = a,b,c，A×A = a,b,c ×a,b,c = <a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a,>,<c,b>,<c,c>。4、符號化命題“如果2大于3，則2大于4。設 L(*,y)：*大于y， a：2， b：3， c：4，則命題符號化為L(a,b)L(a,c)。5、符號化命題“并不是所有的兔子都比所有的烏龜跑得快。設F(*)：

19、*是兔子。G(*)：*是烏龜。H(*,y)：*比y跑得快。該命題符號化為：¬*y(F(*)G(y)H(*,y)。6、符號化命題“2是素數且是偶數。設 F(*)：*是素數。 G(*)：*是偶數。 a： 2，則命題符號化為F(a)G(a)。7、設A=a,b,c,d，R是A的二元關系，定義為：R=<a,a>,<a,b>,<b,a>,<c,b>,<c,a>,<d,c>,<d,b>,<d,a>，寫出A上二元關系R的關系矩陣。解：R的關系矩陣為：8、設A=1,2,3,4，R是A的二元關系，定義為：R=

20、<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>，寫出A上二元關系R的關系矩陣。解：R的關系矩陣為：9、設有向圖G如下所示，求各個結點的出度、入度和度數。. z-deg(v1)3，deg+(v1)1，deg-(v1)2；deg(v2)deg+(v4)deg-(v2)0；deg(v3)3，deg+(v3)2，deg-(v3)1；deg(v4)2，deg+(v4)1，deg-(v4)1；. z-10、設有向圖G如下所示，求各個結點的出度、入度和度數。. z-

21、答：deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)deg+(v4)deg-(v4)0；deg(v5)1，deg+(v5)0，deg-(v5)1；. z-11、設無向圖G如下所示，求它的鄰接矩陣。. z-. z-12、求命題公式(pq)的真值表。pqqpq (pq)0010101001101101100113、設<2*+y, 5>=<10, *3y>，求*，y。解：由定理列出如下方程組：求解得*=5，y=0。14、R1、R2是從1,

22、 2, 3, 4, 5到2, 4, 6的關系，假設R1<1, 2>, <3, 4>, <5, 6>，R2=<1, 4>, <2, 6>，計算domR1，ranR1，fldR1，domR2，ranR2，fldR2。解：domR1=1, 3, 5，ranR1=2, 4, 6，fldR1=dom R1ran R1=1, 2, 3, 4, 5, 6；domR2=1, 2，ranR2=4, 6，fldR2=dom R2ran R2=1, 2, 4, 6。15、例：設A=1, 2, 3, 4, 5，B=3, 4, 5, C=1, 2, 3，A到B

23、的關系R=<*, y>|*+y=6，B到C的關系S=<y, z>|yz=2，求RS。解：R=<1, 5>, <2, 4>, <3, 3>, S=<3, 1>, <4, 2>, <5, 3>，從而RS=<1, 3>, <2, 2>, <3, 1>或者因<1, 5>R，<5, 3>S，所以<1, 3> RS；因<2, 4>R，<4, 2>S，所以<2, 2> RS；因<3, 3>R，&

24、lt;3, 1>S，所以<3, 1> RS；從而RS=<1, 3>, <2, 2>, <3, 1>16、集合A=a, b, c，B=1, 2, 3, 4, 5，R是A上的關系，S是A到B的關系。R=<a, a>, <a, c>, <b, b>, <c, b>, <c, c>，S=<a, 1>, <a, 4>, <b, 2>, <c, 4>, <c, 5>，求RS，S1R1RS=<a, 1>, <a, 4&

25、gt;, <a, 5>, <b, 2>, <c, 2>, <c, 4>, <c, 5>(RS)-1=<1, a>, <4, a>, <5, a>, <2, b>, <2, c>, <4, c>, <5, c>R1=<a, a>, <c, a>, <b, b>, <b, c>, <c, c>，S1=<1, a>, <4, a>, <2, b>, <4,

26、c>, <5, c>S1R1=<1, a>, <2, b>, <2, c>, <4, a>, <4, c>, <5, a>, <5, c>。17、A1, 2, 3, 4, 5, 6，D是整除關系，畫出哈斯圖并求出最小元、最大元、極小元和極大元。解：1是A的最小元，沒有最大元，1是極小元，4、5、6都是A的極大元。18、設集合A=a,b,c，A上的關系R=<a,a>, <a,b>, <b,c>，求R的自反、對稱、傳遞閉包。r(R)=<a,a>,&l

27、t;a,b>,<b,c>,<b,b>,<c,c>s(R)=<a,a>,<a,b>,<b,a>,<b,c>,<c,b>t(R)=<a,a>,<a,b>,<b,c>,<a,c>19、求以下圖中頂點v0與v5之間的最短路徑。解：如以下圖所示v0與v5之間的最短路徑為：v0, v1, v2, v4 , v3, v5最短路徑值為1+2+1+3+2=9 20、分別用三種不同的遍歷方式寫出對以下圖中二叉樹點的次序。先根遍歷：ABDEHCFIJGK 中根遍歷：D

28、BHEAIFJCGK 后根遍歷：DHEBIJFKGCA四、證明題每題10分，共20分1、假設R和S都是非空集A上的等價關系，證明RS是A上的等價關系。證明：aA，因為R和S都是A上的等價關系，所以*R*且*S*。故* RS *。從而RS是自反的。a,bA，aRSb，即aRb且aSb。因為R和S都是A上的等價關系，所以bRa且bSa。故b RS a。從而RS是對稱的。a,b,cA，a RS b且b RS c，即aRb，aSb，bRc且bSc。因為R和S都是A上的等價關系，所以aRc且aSc。故a RS c。從而RS是傳遞的。故RS是A上的等價關系。2、證明格拉底論證：凡人要死。格拉底是人，格拉底

29、要死。設： H(*)：*是人。M(*)：*是要死的。s：格拉底。此題要證明：("*)(H(*)M(*)H(s)ÞM(s)證明： ("*)(H(*)M(*)P H(s)M(s)US H(s)P M(s)、3、PQ，QR，R，SPÞS證明：(1) R 前提(2) QR 前提(3) Q 1，2(4) PQ 前提(5) P 3，4(6) SP 前提(7) S 5，64、在群<G,*>中，除單位元 e 外，不可能有別的冪等元。因為ee=e，所以e是冪等元。設aÎG且aa=a，則有a=ea=(a 1a)a=a 1(aa)=a1a=e，即a=e。

30、5、設R和S是二元關系，證明：(RS)-1=R-1S-1證明： .所以 .6、證明：(QS)R)(S(PR) = (S(PQ)R.證明：左邊：(QS)R)(S(PR)=(QS)R)(S(PR)=(QSR)(SPR)=(QSR)(SPR)右邊：(S(PQ)R= (S(PQ)R= (S(PQ)R= (QSR)(SPR)所以 (QS) R)(S (PR) = (S(PQ)R.7、設I是整數集合，k是正整數，I上的關系R<*, y>|*, y I，且*y可被k整除，證明R是等價關系。證明：(1) 對任意的* A，有*=0可被k整除。所以<*, *> R，即R具有自反性。(2) 對任意的*，y A，<*, y> R，即*y可被k整除，設*y=km，則y*=km，顯然y*可被k整除。所以<