中國石油大學(xué)大學(xué)離散數(shù)學(xué)》期末復(fù)習(xí)題及答案

1、離 散 數(shù) 學(xué) 期 末 復(fù) 習(xí) 題填空題（每空2分，共20 分）1集合A上的偏序關(guān)系的三個(gè)性質(zhì)是 、和。2、 一個(gè)集合的幕集是指 。3、集合 A=b,c，B=a,b,c,d,e，貝U A?B=。4、集合 A=1,2,3,4 , B=1,3,5,7,9，貝U A?B=。5、 若A是2元集合,則2A有個(gè)元素。6、 集合 A=1,2,3 , A上的二元運(yùn)算定義為：a* b = a和b兩者的最大值，則2*3=。7、設(shè) A=a, b,c,d ,貝Z A I =。8、 對實(shí)數(shù)的普通加法和乘法， 是加法的幕等元， 是乘法的幕等元。9、設(shè)a,b,c是阿貝爾群G,+的元素，貝U -（a+b+c）=。10、 一個(gè)

2、圖的哈密爾頓路是 。11、 不能再分解的命題稱為 ，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為。12、命題是。13、 如果 p表示王強(qiáng)是一名大學(xué)生，則p表示。14、 與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做 。15、 量詞分兩種： 禾廿。16、設(shè)A、B為集合，如果集合 A的元素都是集合 B的元素，則稱 A是B的。17、 集合上的三種特殊元是 、及。18、設(shè)A=a, b,貝U PA）的四個(gè)元素分別是：,。19、 代數(shù)系統(tǒng)是指由 及其上的 或組成的系統(tǒng)。20、 設(shè)<L,* 1,*2>是代數(shù)系統(tǒng)，其中是*1,*2二元運(yùn)算符，如果*1,*2都滿，則稱足、，并且*1和*2滿足<L,*1,*2> 是格。21、

3、集合 A=a,b,c,d，B=b ，貝U A B= 。22、設(shè) A=1,2,貝Z A I =。23、 在有向圖中，結(jié)點(diǎn) v的出度deg+(v)表示，入度deg-(v)表示以。24、 一個(gè)圖的歐拉回路是 。25、 不含回路的連通圖是 。26、 不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為 。27、推理理論中的四個(gè)推理規(guī)則是、二、判斷題(每題2分，共20 分)1、空集是唯一的。2、對任意的集合 A, A包含Ao3、恒等關(guān)系不是對稱的，也不是反對稱的。4、集合1,2,3,3和1,2,2,3是同一集合。5、圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊數(shù)稱為點(diǎn) v的度數(shù)，記作deg(v)o6、在實(shí)數(shù)集上，普通加法和普通乘法不是可結(jié)合運(yùn)算。

4、7、對于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。8、 設(shè)(A,*)是代數(shù)系統(tǒng)，a A，如果a*a= a,則稱a為(A, *)的等幕元。9、 設(shè)f: AtB, g: BtC。若f, g都是雙射，則gf不是雙射。10、無向圖的鄰接矩陣是對稱陣。11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱為函數(shù)，是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、<0,1,2,3,4,MAX,MIN> 是格。15、樹一定是連通圖。16、單位元不是可逆的。17、一個(gè)命題可賦予一個(gè)值，稱為真值。18、復(fù)合命題是由連結(jié)詞、標(biāo)點(diǎn)符號和原子命題復(fù)合構(gòu)成的命題。19、任何兩個(gè)

5、重言式的合取或析取不是一個(gè)重言式。20、 設(shè)f: At B, g： BC。若f, g都是滿射，則g?f不是滿射。21、集合 1,2,3,3和1,2,3 是同一集合。22、零元是不可逆的。23、一般的，把與 n 個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。24、“我正在說謊?！辈皇敲}。25、 用A表示“是個(gè)大學(xué)生”，c表示“張三”，則 A(c):張三是個(gè)大學(xué)生。26、設(shè) F = <3,3>,<6,2>，貝U F-1 = <6,3>,<2,6>。27、歐拉圖是有歐拉回路的圖。28、 設(shè)f: At b , g： Btc。若f, g都是單射，則 g?f也是單射。三

6、、計(jì)算題(每題 10 分，共 40分)1、設(shè) A=c,d, B=0,1,2，則計(jì)算 A X B, B X A。2、A = a,b,c , B = 1,2，計(jì)算 A X B。3、A = a,b,c ，計(jì)算 AX A。4、符號化命題“如果 2 大于 3，則 2 大于 4?！?。5、符號化命題“并不是所有的兔子都比所有的烏龜跑得快”。6、符號化命題“ 2 是素?cái)?shù)且是偶數(shù)”。7、設(shè) A=a,b,c,d ， R 是 A 的二元關(guān)系，定義為： R=<a,a>,<a,b>,<b,a>,<c,b>, <c,a>,<d,c>,<d,b&

7、gt;, <d,a> ，寫出 A 上二元關(guān)系 R 的關(guān)系矩陣。8、 設(shè) A=1,2,3,4 , R 是 A 的二元關(guān)系，定義為：R=<1,1>,<1,2>,<2,1>,<3,2>, <3,1>,<4,3>,<4,2>, <4,1>，寫出A上二元關(guān)系R的關(guān)系矩陣。9、設(shè)有向圖 G 如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。V412、求命題公式(pAn q)的真值表。13、設(shè) <2x+y, 5>=<10, x - 3y>，求 x, y。14、R1、R2 是從1,2, 3

8、, 4, 5到2, 4, 6的關(guān)系，若 R1 = <1,2>, <3, 4>, <5, 6> , R2=<1,4>,<2, 6>，計(jì)算 domR1， ranR1， fldR1， domR2， ranR2， fldR2。15、例：設(shè) A=1,2, 3, 4, 5，B=3, 4, 5, C=1,2, 3，A 到 B 的關(guān)系 R=<x, y>|x+y=6，B到 C 的關(guān)系 S=<y, z>| y- z=2，求 R?S。16、集合 A=a, b, c , B=1,2, 3, 4, 5 , R 是 A 上的關(guān)系，S是 A

9、 到 B 的關(guān)系。R=<a, a>, <a, c>, <b, b>, <c, b>, <c, c> , S=<a, 1>, <a, 4>, <b, 2>, <c, 4>, <c, 5>，求 R?S, S ?R17、A = 1,2, 3, 4, 5, 6 , D是整除關(guān)系，畫出哈斯圖并求出最小元、最大元、極小元和極 大元。18、設(shè)集合A=a,b,c , A上的關(guān)系R=<a,a>, <a,b>, <b,c>,求R的自反、對稱、傳遞閉包。19、求

10、下圖中頂點(diǎn) v0與v5之間的最短路徑。V17V320、分別用三種不同的遍歷方式寫出對下圖中二叉樹點(diǎn)的訪問次序。四、證明題(每題10分，共20分)1、 若R和S都是非空集A上的等價(jià)關(guān)系，證明 R S是A上的等價(jià)關(guān)系。2、證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。3、 PtQ, n Q R, n R, n S P n S4、在群<G,*>中，除單位元 e夕卜，不可能有別的幕等元。5、 設(shè)R和S是二元關(guān)系，證明：(R S=R-1S-16、證明：(Q A S)t R)A (St (PV R) = (S A (Pt Q)t R.7、 設(shè)I是整數(shù)集合，k是正整數(shù)，I上的關(guān)系R=&

11、lt;x, y>|x, y I，且x y可被k整除, 證明R是等價(jià)關(guān)系。8、 證明(ptq)tr)(n qA p) V r)9、證明(PV Q) A (Pt R) A (Q t S) SV R10、證明 Pt n Q, Q Vn R, RAn S n P11、證(？x)(P(x)V Q(x) n (?x)P(x) t( x)Q(x)12、 證明定理：設(shè)<G, ? > 是群，對于任意a, b G,貝y方程a?x=b與y?a=b，在群內(nèi)有唯一解。離散數(shù)學(xué)復(fù)習(xí)題參考答案一、填空題(每空1分，共20分)1、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是自反性、反對稱性和傳遞性 2、一個(gè)集合的幕集是指

12、該集合所有子集的集合。3、集合 A=b,c ，B=a,b,c,d,e，貝U A?B=a,b,c,d,e。4、集合 A=1,2,3,4 , B=1,3,5,7,9，貝U A?B=1,3。5、 若A是2元集合，則2A有_4_個(gè)元素。6、 集合 A=1,2,3 , A上的二元運(yùn)算定義為：a* b = a和b兩者的最大值，則 2*3=7、設(shè) A=a, b,c,d,貝A I = 4_。8、 對實(shí)數(shù)的普通加法和乘法，是加法的幕等元，匚是乘法的幕等元。9、設(shè) a,b,c是阿貝爾群 G,+ 的元素，貝U -(a+b+c)=(-a)+( -b)+( -c)。10、一個(gè)圖的哈密爾頓路是一條通過圖中所有結(jié)點(diǎn)一次且恰

13、好一次的路。11、不能再分解的命題稱為原子命題，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為復(fù)合命 12、命題是能夠表達(dá)判斷(分辯其真假)的陳述語句。13、 如果p表示王強(qiáng)是一名大學(xué)生，則p表示王強(qiáng)不是一名大學(xué)生。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。15、量詞分兩種：全稱量詞和存在量詞。16、 設(shè)A、B為集合，如果集合 A的元素都是集合 B的元素，則稱 A是B的子集。17、集合上的三種特殊元是單位元、零元及可逆元。18、 設(shè)A=a, b,貝U p(A)的四個(gè)元素分別是：空集， a , b, a, b。19、代數(shù)系統(tǒng)是指由集合及其上的一元或二元運(yùn)算符組成的系統(tǒng)。20、 設(shè)L,*1,*2是代數(shù)系統(tǒng)，其中是*

14、1,*2二元運(yùn)算符，如果*1,*2都滿足交換律、結(jié)合律，并 且*1和*2滿足吸收律，則稱L,*1,*2是格。21、集合 A=a,b,c,d , B=b ，貝U A B= a, c,d 。22、 設(shè) A=1,2,貝UI A I = 2_。23、 在有向圖中，結(jié)點(diǎn) v的出度deg+(v)表示以v為起點(diǎn)的邊的條數(shù)，入度deg-(v)表示以v 為終點(diǎn)的邊的條數(shù)。24、一個(gè)圖的歐拉回路是一條通過圖中所有邊一次且恰好一次的回路。25、不含回路的連通圖是樹。26、不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)。27、 推理理論中的四個(gè)推理規(guī)則是全稱指定規(guī)則（US規(guī)則）、全稱推廣規(guī)則 （UG規(guī)則）、存 在指定規(guī)則 （E

15、S規(guī)則）、存在推廣規(guī)則 （EG規(guī)則）。二、判斷題（每題2分，共20分）1、V"。2、“。3、X <。4、/5、V。6、X。7、V。> 8、V。9、Xo 10、Vo11、xo 12、V。13、X。14、'。15、。16、Xo17、V。18V。19、Xo20、Xo 21、V。22、/23、Xo 24、V。25、V。26、X。 27、V。28、Vo1空集是唯一的。2、對任意的集合 A，A包含A。3、恒等關(guān)系不是對稱的，也不是反對稱的。4、集合1,2,3,3和1,2,2,3是同一集合。5、圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊數(shù)稱為點(diǎn) v的度數(shù)，記作deg（v）。6、在實(shí)數(shù)集上，普通加

16、法和普通乘法不是可結(jié)合運(yùn)算。7、對于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。8、 設(shè)（A,*）是代數(shù)系統(tǒng)，a A，如果a*a= a,則稱a為（A, *）的等幕元。9、 設(shè)f: AtB, g: BtC。若f, g都是雙射，則gf不是雙射。10、無向圖的鄰接矩陣是對稱陣。11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱為函數(shù)，是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、<0,1,2,3,4,MAX,MIN> 是格。15、樹一定是連通圖。16、單位元不是可逆的。17、一個(gè)命題可賦予一個(gè)值，稱為真值。18、復(fù)合命題是由連結(jié)詞、標(biāo)點(diǎn)符號和原子命題復(fù)

17、合構(gòu)成的命題。19、任何兩個(gè)重言式的合取或析取不是一個(gè)重言式。20、 設(shè)f: At b , g： Btc。若f, g都是滿射，則g?f不是滿射。21、集合 1,2,3,3和1,2,3 是同一集合。22、零元是不可逆的。23、一般的，把與 n 個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。24、“我正在說謊?！辈皇敲}。25、 用A表示“是個(gè)大學(xué)生”，c表示“張三”，則 A(c):張三是個(gè)大學(xué)生。26、設(shè) F = <3,3>,<6,2>，貝U F-1 = <6,3>,<2,6>。27、歐拉圖是有歐拉回路的圖。28、 設(shè)f: At B, g： B宀C。若f, g都

18、是單射，則 g?f也是單射。三、計(jì)算題(每題 10 分，共 40分)1、設(shè) A=c,d, B=0,1,2，貝U A X B=<c,0>,<c,1>,<c,2>,<d,0>,<d,1>,<d,2>, B X A=<0,c>,<0,d>,<1,c>,<1,d>,<2,c>,<2,d>。2、A = a,b,c， B = 1,2 ， AXB = a,b,c X1,2 = <a,1>,<b,1>,<c,1>,<a,2&g

19、t;,<b,2>,<c,2>。3、A = a,b,c ， AXA = a,b,c Xa,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。”。設(shè) L(x,y): x 大于 y， a: 2， b: 3， c: 4，則命題符號化為 L(a,b)tL(a,c)。5、符號化命題“并不是所有的兔子都比所有的烏龜跑得快”。設(shè)F(x): x是兔子。G(x)

20、: x是烏龜。H(x,y): x比y跑得快。該命題符號化為：？ x? y(F(x)A G(y)t H(x,y)。6、符號化命題“ 2 是素?cái)?shù)且是偶數(shù)”。設(shè) F(x)： x 是素?cái)?shù)。G(x) ： x 是偶數(shù)。a： 2，則命題符號化為 F(a)A G(a)。7、設(shè) A=a,b,c,d ， R 是 A 的二元關(guān)系，定義為： R=<a,a>,<a,b>,<b,a>,<c,b>, <c,a>,<d,c>,<d,b>, <d,a> ，寫出 A 上二元關(guān)系 R 的關(guān)系矩陣。解： R 的關(guān)系矩陣為：11001000

21、110011108、設(shè) A=1,2,3,4 , R 是 A 的二元關(guān)系，定義為： R=<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>, <4,1>，寫出A上二元關(guān)系R的關(guān)系矩陣。解：R的關(guān)系矩陣為:110 010 0 0110 01110入度和度數(shù)。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(v

22、4)= 2, deg+(v4)= 1, deg-(v4)= 1;10、設(shè)有向圖G如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。答：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;01011010A(G)門01011010deg(v5)= 1, deg+(v5)= 0, deg-(v5)= 1;12、求命題公式(p A n q)的真值表。pqn qpAn qn (pA

23、 n q)0010；101001101101100113、設(shè) <2x+y, 5>=<10, x - 3y>，求 x, y。解：由定理列出如下方程組：2x y 10x 3y 5求解得x=5， y=0 o14、R1、R2 是從1,2, 3, 4, 5到2, 4, 6的關(guān)系，若 R1 = <1,2>, <3, 4>, <5, 6> , R2=<1,4>, <2, 6>，計(jì)算 domR1, ranR1, fldR1 , domR2, ranR2, fldR2。解：domR1=1,3, 5 , ranR1=2, 4, 6

24、 , fldR1=dom R1 U ran R1=1,2, 3, 4, 5, 6;domR2=1,2 , ranR2=4, 6 , fldR2=dom R2 U ran R2=1,2, 4, 6。15、例：設(shè) A=1,2, 3, 4, 5 , B=3, 4, 5, C=1,2, 3, A 到 B 的關(guān)系 R=<x, y>|x+y=6, B到 C 的關(guān)系 S=<y, z>|y - z=2，求 R?S。解：R=<1,5>, <2, 4>, <3, 3>, S=<3, 1>, <4, 2>, <5, 3>

25、,從而 R?S=<1,3>, <2, 2>, <3, 1> 或者因 <1,5> R, <5, 3> S,所以 <1,3> R?S;因 <2, 4> R, <4, 2> S,所以 <2, 2> R?S;因 <3, 3> R, <3, 1> S,所以 <3, 1> R?S;從而 R?S=<1,3>, <2, 2>, <3, 1>16、集合 A=a, b, c , B=1,2, 3, 4, 5 , R 是 A 上的關(guān)系，S

26、是 A 到 B 的關(guān)系。R=<a, a>, <a, c>, <b, b>, <c, b>, <c, c> , S=<a, 1>, <a, 4>, <b, 2>, <c, 4>, <c, 5>，求 R?S, S-?R-R?S=<a, 1>, <a, 4>, <a, 5>, <b, 2>, <c, 2>, <c, 4>, <c, 5>1(R?S) =<1, a>, <4, a&g

27、t;, <5, a>, <2, b>, <2, c>, <4, c>, <5, c>-1R =<a, a>, <c, a>, <b, b>, <b, c>, <c, c>,_1S =<1, a>, <4, a>, <2, b>, <4, c>, <5, c>1=<1, a>, <2, b>, <2, c>, <4, a>, <4, c>, <5, a&

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

29、;,<c,b>t(R)=<a,a>,<a,b>,<b,c>,<a,c>19、求下圖中頂點(diǎn) v0與v5之間的最短路徑。Vi7v3解：如下圖所示 V0與v5之間的最短路徑為：v0, v1, v2, v4 , v3, v5最短路徑值為 1+2+1+3+2=9V720、分別用三種不同的遍歷方式寫出對下圖中二叉樹點(diǎn)的訪問次序。先根遍歷：ABDEHCFIJGK 中根遍歷：DBHEAIFJCGK 后根遍歷：DHEBIJFKGCA四、證明題（每題10分，共20分）1、若R和S都是非空集A上的等價(jià)關(guān)系，證明 R S是A上的等價(jià)關(guān)系。 證明： a A，因

30、為R和S都是A上的等價(jià)關(guān)系，所以xRx且xSx。故x R S X。從而R S 是自反的。a,b A, aR Sb,即aRb且aSb因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以 bRa且bSat故 b R S a。從而R S是對稱的。a,b,c A, a R S b且b R S c,即aRb, aSb, bRc且bSc。因?yàn)?R和S都是A上的等價(jià) 關(guān)系，所以aRc且aSc故a R S c從而R S是傳遞的。故R S是A上的等價(jià)關(guān)系。2、證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。設(shè)：H(x) : x是人。M(x) : x是要死的。s：蘇格拉底。本題要證明：(x)(H(x)tM(x) A H(s

31、) M(s) 證明：(x)(H(x) t M(x)P H(s)t M(s)US H(s)P M(s)、3、Pt Q ,q QR,n R,n S Pn S證明：(1) n R前提n Q R前提 n Q(1),(2)(4)Pt Q前提 n P(3),(4)n S P前提 n S(5),(6)4、在群 <G,*> 中,除單位元e 外,不可能有別的幕等兀。因?yàn)?e?e=e,所以 e是幕等元。設(shè) a G 且 a?a=a,則有 a=e?a=(a -1 ?a)?a=a - 1?(a?a)=a-1 ?a=e, 即 a=e。5、設(shè)R和S是二元關(guān)系，證明：(R S)-1=R-1S1證明:V -廠 &#

32、39;(9) RAn R由(6)和 (8)，矛盾Q) e=(ytx)e(RfS)= (O- Q e &八3 心申=©J) W) = (x,y) e A-1 nW所以込ciet】2ns-】.6、證明：(Q A S) T R) A (S T (R)Y= (S A (P Q) R.證明：左邊：(QA S) T R) A (S T (PR)y=(n (Q AS)V R)A (n S(PV R)=(n QVn SVR)A (n SPV R)=(n QVn SVR)A (n SPV R)右邊：(SA (P t Q) T=n (S A (n PQ)V R=(n SVPAn Q) VR=(n QVn SR)A (n SPV R)所以(Q A S) t R) A (S t R) =/(S A (P t Q) t R.7、 設(shè)I是整數(shù)集合，k是正整數(shù)，I上的關(guān)系R=<x, y>|x, y I，且x y可被k整除, 證明R是等價(jià)關(guān)系。證明： 對任意的x A，有x x=0可被k整除。所以<x, x> R,即R具有自反性。 對任意的x, y A , <x, y> R,即卩x y可被k整除，設(shè)x y=km，則y x= km, 顯然y x可被k整除。所以<y, x> R,即R具有對