《離散數(shù)學(xué)》期末復(fù)習(xí)題答案

1、離散數(shù)學(xué)期末復(fù)習(xí)題參考答案一、填空題(每空 1 分，共 20分)1、集合 A 上的偏序關(guān)系的三個(gè)性質(zhì)是自反性、反對(duì)稱(chēng)性和傳遞性。2、一個(gè)集合的冪集是指該集合所有子集的集合。3、集合 A=b,c ， B=a,b,c,d,e ，則 A ?B=a,b,c,d,e 。4、集合 A=1,2,3,4 ， B=1,3,5,7,9 ，則 A?B=1,3 。5、若 A 是 2 元集合 , 則 2A 有 4 個(gè)元素。6、集合 A=1,2,3 ，A 上的二元運(yùn)算定義為： a* b = a 和b兩者的最大值，則 2*3= 3 。7、設(shè) A=a, b,c,d, 則A= 4 。8、對(duì)實(shí)數(shù)的普通加法和乘法，0 是加法的冪等

2、元， 1 是乘法的冪等元。9、設(shè) a,b,c 是阿貝爾群 的元素，則 -(a+b+c)=(-a)+( -b)+( -c) 。10、一個(gè)圖的哈密爾頓路是一條通過(guò)圖中所有結(jié)點(diǎn)一次且恰好一次的路。11、不能再分解的命題稱(chēng)為原子命題，至少包含一個(gè)聯(lián)結(jié)詞的命題稱(chēng)為復(fù)合命題。12、命題是能夠表達(dá)判斷(分辯其真假)的陳述語(yǔ)句。13、如果 p 表示王強(qiáng)是一名大學(xué)生，則 p表示王強(qiáng)不是一名大學(xué)生。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。15、量詞分兩種：全稱(chēng)量詞和存在量詞。16、設(shè) A 、 B 為集合，如果集合 A 的元素都是集合 B 的元素，則稱(chēng) A 是 B 的子集。17、集合上的三種特殊元是單位元、零元及

3、可逆元。18、設(shè) A=a, b ，則 (A) 的四個(gè)元素分別是：空集， a ，b ，a, b 。19、代數(shù)系統(tǒng)是指由集合及其上的一元或二元運(yùn)算符組成的系統(tǒng)。20、設(shè) 是代數(shù)系統(tǒng)，其中是 *1,*2 二元運(yùn)算符，如果 * 1,* 2都滿(mǎn)足交換律、結(jié)合律， 并且* 1和*2滿(mǎn)足吸收律，則稱(chēng) 是格。21、集合 A=a,b,c,d ，B=b ，則 A B= a, c,d 。22、設(shè) A=1, 2, 則A= 2 。23、在有向圖中，結(jié)點(diǎn) v 的出度 deg+(v) 表示以 v 為起點(diǎn)的邊的條數(shù)，入度 deg-(v)表示以 v 為終點(diǎn)的邊的條數(shù)。24、一個(gè)圖的歐拉回路定義為一條通過(guò)圖中所有邊一次且恰好一次

4、的回路。25、不含回路的連通圖是樹(shù)。26、不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱(chēng)為孤立結(jié)點(diǎn)。27、推理理論中的四個(gè)推理規(guī)則是全稱(chēng)指定規(guī)則(US 規(guī)則)、全稱(chēng)推廣規(guī)則 (UG 規(guī)則 )、存在指定規(guī)則 (ES 規(guī)則) 、存在推廣規(guī)則 (EG 規(guī)則 )。二、判斷題(每題 2 分，共 20分)1、空集是唯一的。 2、對(duì)任意的集合 A， A 包含 A。 3、恒等關(guān)系不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)的。4、集合 1,2,3,3 和 1,2,2,3 是同一集合。 5、圖 G 中，與頂點(diǎn) v 關(guān)聯(lián)的邊數(shù)稱(chēng)為點(diǎn) v 的度數(shù)，記作 deg（v）。 6、在實(shí)數(shù)集上，普通加法和普通乘法不是可結(jié)合運(yùn)算。7、對(duì)于任何一命題公式，都存在與其等

5、價(jià)的析取范式和合取范式。8、設(shè)（ A,* ）是代數(shù)系統(tǒng)， a A，如果 a*a a，則稱(chēng) a為（ A ， * ）的等冪元。 9、設(shè) f： A B， g： BC。若 f，g 都是雙射，則 gf 不是雙射。 10、無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)陣。 11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱(chēng)為函數(shù)，是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、 是格。 15、樹(shù)一定是連通圖。 16、單位元不是可逆的。 17、一個(gè)命題可賦予一個(gè)值，稱(chēng)為真值 。18、復(fù)合命題是由連結(jié)詞、標(biāo)點(diǎn)符號(hào)和原子命題復(fù)合構(gòu)成的命題。19、任何兩個(gè)重言式的合取或析取不是一個(gè)重言式。20、設(shè) f：AB，

6、g：BC。若 f， g都是滿(mǎn)射，則 g?f 不是滿(mǎn)射。 21、集合 1,2,3,3 和 1,2,3 是同一集合。 22、零元是不可逆的 。23、一般的，把與 n 個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞 。24、“我正在說(shuō)謊?！辈皇敲}。 25、用 A 表示“是個(gè)大學(xué)生”， c 表示“張三”，則 A（c） ：張三是個(gè)大學(xué)生。 26、設(shè) F , ，則 F-1 , 。27、歐拉圖是有歐拉回路的圖。 28、設(shè) f：AB， g：BC。若 f， g都是單射，則 g?f 也是單射。 三、計(jì)算題（每題 10 分，共 40 分）1、設(shè) A=c,d, B=0,1,2 ，則 A B=, ，B A= , 。2、A = a,b

7、,c ，B = 1,2 ，AB = a,b,c 1,2 = , 。3、A = a,b,c ，AA = a,b,c a,b,c = , 。4、符號(hào)化命題“如果 2 大于 3，則 2 大于 4?！?。設(shè) L(x,y) ：x 大于 y， a：2， b： 3， c： 4，則命題符號(hào)化為 L(a,b) L(a,c) 。5、符號(hào)化命題“并不是所有的兔子都比所有的烏龜跑得快”。設(shè) F(x) ：x 是兔子。 G(x) ：x 是烏龜。 H(x,y) ：x比 y 跑得快。該命題符號(hào)化為： ? x? y(F(x) G(y) H(x,y) 。6、符號(hào)化命題“ 2 是素?cái)?shù)且是偶數(shù)”。設(shè) F(x) ：x 是素?cái)?shù)。 G(x)

8、：x 是偶數(shù)。 a： 2，則命題符號(hào)化為 F(a)G(a)。7、設(shè) A=a,b,c,d ，R 是 A 的二元關(guān)系， 定義為：R=, , ，寫(xiě)出 A 上二元關(guān)系 R 的關(guān)系矩陣。解：R 的關(guān)系矩陣為：11001000110011108、設(shè) A=1,2,3,4 ，R是A的二元關(guān)系，定義為：R=, ,9、設(shè)有向圖G 如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。deg(v1) 3， deg+(v1) 1， deg-(v1) 2； deg(v2) deg+(v4) deg-(v2) 0； deg(v3)3， deg(v4)2，deg+(v3) 2，deg+(v4) 1，deg-(v3)1；deg-(v4)

9、1；求它的鄰接矩陣。入度和度數(shù)。答：deg+(v1) 2， deg+(v2) 2， deg+(v3) 2，deg(v1)3，deg(v2)3，deg(v3)5，deg(v4) deg+(v4) deg-(v4) 0； deg(v5) 1， deg+(v5) 0， deg-(v5) 1；deg-(v1)1；deg-(v2)1；deg-(v3)3；01011010A(G)0101101012、求命題公式 (p q)的真值表。qpq (p q) ，寫(xiě)出A 上二元關(guān)系 R 的關(guān)系矩陣。解：R 的關(guān)系矩陣為：11001000110011100010101001101101100113、設(shè) = ，求 x，

10、y。 解：由定理列出如下方程組：2x y 10x 3y 5求解得 x=5 ， y=0 。14、R1、R2是從1, 2, 3, 4, 5 到2, 4, 6 的關(guān)系，若R1, , ，R2=, ，計(jì)算 domR1，ranR1，fldR1 ，domR2，ranR2，fldR2 。解： domR1=1, 3, 5 ， ranR1=2, 4, 6 ，fldR1=dom R1 ran R1=1, 2, 3, 4, 5, 6 ； domR2=1, 2 ， ranR2=4, 6 ，fldR2=dom R2 ran R2=1, 2, 4, 6 。15、設(shè) A=1, 2, 3, 4, 5 ，B=3, 4, 5, C

11、=1, 2, 3 ，A到 B的關(guān)系 R=|x+y=6 ，B到C 的關(guān)系 S=|y z=2 ，求 R?S。解：R=, , , S=, , ，從而 R?S=, , 或者因 R ， S，所以 R?S；因R， S，所以 R?S；因 R， S，所以 R?S；從而 R?S=, , 16、集合 A=a, b, c ，B=1, 2, 3, 4, 5 ，R是A上的關(guān)系，S是 A到B 的關(guān)系。R=, , , , ， S=, , , , ，求 R?S， S1?R1 R?S=, , , , , , (R?S)-1=, , , , , , 1R 1=, , , , ，1S1=, , , , S1?R 1=, , , ,

12、 , , 。17、A1, 2, 3, 4, 5, 6 ，D 是整除關(guān)系，畫(huà)出哈斯圖并求出最小元、最大元、極小元和極 大元。解：1 是 A 的最小元，沒(méi)有最大元， 1 是極小元， 4、 5、 6 都是 A 的極大元。18、設(shè)集合 A=a,b,c ，A 上的關(guān)系 R=, , ，求 R 的自反、 對(duì)稱(chēng)、 傳遞閉包。 r(R)=,s(R)=, t(R)=,19、求下圖中頂點(diǎn) v0 與 v5 之間的最短路徑。v5v0, v1, v2, v4 , v3, v520、分別用三種不同的遍歷方式寫(xiě)出對(duì)下圖中二叉樹(shù)點(diǎn)的訪問(wèn)次序。中根遍歷：DBHEAIFJCGK后根遍歷： DHEBIJFKGCA四、證明題(每題 1

13、0 分，共 20 分)1、若 R和 S都是非空集 A 上的等價(jià)關(guān)系，證明 R S是 A 上的等價(jià)關(guān)系。證明： aA，因?yàn)?R和S都是A上的等價(jià)關(guān)系，所以 xRx且xSx。故 x R S x。從而 R S 是自反的。a,b A ，aR Sb，即 aRb且aSb。因?yàn)?R和S都是 A上的等價(jià)關(guān)系，所以 bRa且bSa。 故 b R S a。從而 R S 是對(duì)稱(chēng)的。a,b,cA，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、證明蘇格拉底

14、論證：凡人要死。蘇格拉底是人，蘇格拉底要死。設(shè)： H(x) ：x是人。M(x) ：x是要死的。s：蘇格拉底。本題要證明： ( x)(H(x) M(x) H(s) M(s) 證明：US( x)(H(x) M(x) P H(s) M(s) H(s)P M(s)、3、P Q， QR， R， S PS證明：(1)R前提(2)Q R前提(3)Q（1），（2）(4)PQ前提(5)P（3），（4）(6)S P前提(7)S（5），（6）4、在群 中，除單位元e 外，不可能有別的冪等元。因?yàn)?e?e=e，所以e 是冪等元。設(shè)aG且a?a=a，則有a=e?a=(a 1 ?a)?a=a 1?(a?a)=a1 ?a=

15、e，即 a=e。6、證明： (Q S) R)(S (P R) = (S(PQ) R.證明：左邊： (QS)R) (S(P R)=( (QS)R)( S(PR)=( QSR)( SPR)=( QSR)( SPR)右邊： (S(PQ) R= (S( PQ) R= ( S(P Q)R= ( QSR)( SPR)所以 (Q S) R)(S (P R) = (S (PQ) R.7、設(shè) I 是整數(shù)集合， k 是正整數(shù)， I 上的關(guān)系 R |x, y I，且 xy 可被 k 整除 ， 證明 R 是等價(jià)關(guān)系。證明： (1) 對(duì)任意的 x A，有 x x=0 可被 k 整除。所以 R，即 R 具有自反性。(2)

16、 對(duì)任意的 x，y A， R，即 xy可被 k 整除，設(shè) x y=km ，則 y x= km， 顯然 yx可被 k整除。所以 R，即 R具有對(duì)稱(chēng)性。(3)設(shè)x，y，z A ，若 R， R，即xy可被 k整除， y z可被 k整除， 設(shè)x y=km ， y z=kn ，則 x z=k(m+n) ，即 xz可被 k整除。所以 R，即 R具 有傳遞性。綜上所述， R 具有自反性、對(duì)稱(chēng)性和傳遞性，故 R 是等價(jià)關(guān)系。8、證明：(p q)r) (qp)r)p (q r)? r(q p)證明： (pq) r)( p q) r)/蘊(yùn)涵等值式(pq) r/蘊(yùn)涵等值式(p ( q) r/德摩根律( q p) r

17、)/交換律p(qr)? r(q p)(1)(P)反證法附加前提(2)P由(1)(3)PQ已知前提(4)Q由(2)和(3)(5)QR已知前提(6)R由(4)和(5)(7)RS已知前提(8)R由 (7)(9)RR由(6)和(8)，矛盾(1) (? x)P(x)前提引入(2) ( x) P(x)由(1)(3) P(c)由(2) ES(4) ( ? x)(P(x) Q(x)前提引入(5) P(c) Q(c)由(4) US(6) Q(c)由(3)和(5)(7) ( x)Q(x)由(6) EG (? x)P(x) ( x)Q(x)CP 規(guī)則：要證 S RC ，也就是證明 (S R) C? p (qr)? p (qr)? r( q p)? r(q p)? r (q p)9、證明 (PQ) (P R)/蘊(yùn)涵等值式/蘊(yùn)涵等值式/結(jié)合律與交換律/蘊(yùn)涵等值式/蘊(yùn)涵等值式 (Q S) SR(1)PQ已知前提(2)PQ由(1)(3)QS已知前提(4)PS由(2) 和 (3)(5)SP由(4)(6)PR已知前提(7)SR由(5) 和 (6)(8)SR由(