中國石油大學大學《離散數(shù)學》期末復習題及答案

千里之行，始于足下。第2頁/共2頁精品文檔推薦中國石油大學大學《離散數(shù)學》期末復習題及答案《離散數(shù)學》期末復習題

一、填空題（每空2分，共20分）

1、集合A上的偏序關系的三個性質(zhì)是、

和。

2、一具集合的冪集是指。

3、集合A={b,c}，B={a,b,c,d,e}，則A?B=。

4、集合A={1,2,3,4}，B={1,3,5,7,9}，則A?B=。

5、若A是2元集合,則2A有個元素。

6、集合A={1,2,3｝，A上的二元運算定義為：a*b=a和b兩者的最大值，則

2*3=。

7、設A={a,b,c,d},則∣A∣=。

8、對實數(shù)的一般加法和乘法，是加法的冪等元，

是乘法的冪等元。

9、設a,b,c是阿貝爾群的元素，則-(a+b+c)=。

10、一具圖的哈密爾頓路是。

11、別能再分解的命題稱為，至少包含一具聯(lián)結詞的命題稱

為。

12、命題是。

13、假如p表示王強是一名大學生，則┐p表示。

14、與一具個體相關聯(lián)的謂詞叫做。

15、量詞分兩種：和。

16、設A、B為集合，假如集合A的元素基本上集合B的元素，則稱A是B

的。

17、集合上的三種特別元是、

及。

18、設A={a,b}，則ρ(A)的四個元素分不

是：，，，。

19、代數(shù)系統(tǒng)是指由及其上的或

組成的系統(tǒng)。

20、設是代數(shù)系統(tǒng)，其中是*1,*2二元運算符，假如*1,*2都滿

腳、，同時*1和*2滿腳，則稱是格。

21、集合A={a,b,c,d}，B=，則A\B=。

22、設A={1,2},則∣A∣=。

23、在有向圖中，結點v的出度deg+(v)表示，入度deg-(v)表示

以。

24、一具圖的歐拉回路是。

25、別含回路的連通圖是。

26、別與任何結點相鄰接的結點稱為。

27、推理理論中的四個推理規(guī)則

是、、、。

二、推斷題（每題2分，共20分）

1、空集是唯一的。

2、對任意的集合A，A包含A。

3、恒等關系別是對稱的，也別是反對稱的。

4、集合{1,2,3,3}和{1,2,2,3}是同一集合。

5、圖G中，與頂點v關聯(lián)的邊數(shù)稱為點v的度數(shù)，記作deg(v)。

6、在實數(shù)集上，一般加法和一般乘法別是可結合運算。

7、關于任何一命題公式，都存在與其等價的析取范式和合取范式。

8、設（A,*）是代數(shù)系統(tǒng)，a∈A，假如a*a＝a，則稱a為（A，*）的等冪元。

9、設f：A→B，g：B→C。若f，g基本上雙射，則gf別是雙射。

10、無向圖的鄰接矩陣是對稱陣。

11、一具集合別能夠是另一具集合的元素。

12、映射也能夠稱為函數(shù)，是一種特別的二元關系。

13、群中每個元素的逆元都別是惟一的。

14、是格。

15、樹一定是連通圖。

16、單位元別是可逆的。

17、一具命題可給予一具值，稱為真值。

18、復合命題是由連結詞、標點符號和原子命題復合構成的命題。

19、任何兩個重言式的合取或析取別是一具重言式。

20、設f：A→B，g：B→C。若f，g基本上滿射，則g?f別是滿射。

21、集合{1,2,3,3}和{1,2,3}是同一集合。

22、零元是別可逆的。

23、普通的，把與n個個體相關聯(lián)的謂詞叫做一元謂詞。

24、“我正在講謊?！眲e是命題。

25、用A表示“是個大學生”，c表示“張三”，則A(c)：張三是個大學生。

26、設F＝{,}，則F-1＝{,}。

27、歐拉圖是有歐拉回路的圖。

28、設f：A→B，g：B→C。若f，g基本上單射，則g?f也是單射。

三、計算題（每題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、符號化命題“假如2大于3，則2大于4?！薄?/p>

5、符號化命題“并別是所有的兔子都比所有的烏龜跑得快”。

6、符號化命題“2是素數(shù)且是偶數(shù)”。

7、設A={a,b,c,d}，R是A的二元關系，定義為：R={,,,,,,,}，寫出A上二元關系R的關系矩陣。

8、設A={1,2,3,4}，R是A的二元關系，定義為：R={,,,,,,,}，寫出A上二元關系R的關系矩陣。

9、設有向圖G如下所示，求各個結點的出度、入度和度數(shù)。

10、設有向圖G如下所示，求各個結點的出度、入度和度數(shù)。

11、設無向圖G如下所示，求它的鄰接矩陣。

12、求命題公式┐(p∧┐q)的真值表。

13、設=，求x，y。

14、R1、R2是從{1,2,3,4,5}到{2,4,6}的關系，若R1＝{,,}，R2={,}，計算domR1，ranR1，fldR1，domR2，ranR2，fldR2。

15、例：設A={1,2,3,4,5}，B={3,4,5},C={1,2,3}，A到B的關系R={|x+y=6}，B到C的關系S={|y－z=2}，求R?S。

16、集合A={a,b,c}，B={1,2,3,4,5}，R是A上的關系，S是A到B的關系。R={,,,,}，S={,,,,}，求R?S，S–1?R–1

17、A＝{1,2,3,4,5,6}，D是整除關系，畫出哈斯圖并求出最小元、最大元、極小元和極大元。

18、設集合A={a,b,c}，A上的關系R={,,}，求R的自反、對稱、傳遞閉包。

19、求下圖中頂點v0與v5之間的最短路徑。

20、分不用三種別同的遍歷方式寫出對下圖中二叉樹點的拜訪次序。

四、證明題（每題10分，共20分）

1、若R和S基本上非空集A上的等價關系，證明R?S是A上的等價關系。

2、證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。

3、P→Q，┐Q∨R，┐R，┐S∨P?┐S

4、在群中，除單位元e外，不會有不的冪等元。

5、設R和S是二元關系，證明：(R?S)-1=R-1?S-1

6、證明：((Q∧S)→R)∧(S→(P∨R))=(S∧(P→Q))→R.

7、設I是整數(shù)集合，k是正整數(shù)，I上的關系R＝{|x,y∈I，且x－y可被k整除}，

證明R是等價關系。

8、證明((p→q)→r)?((┐q∧p)∨r)

9、證明(P∨Q)∧(P→R)∧(Q→S)?S∨R

10、證明P→┐Q，Q∨┐R，R∧┐S?┐P

11、證(?x)(P(x)∨Q(x))?┐(?x)P(x)→(?x)Q(x)

12、證明定理：設是群，關于任意a,b∈G，則方程a?x=b與y?a=b，在群內(nèi)有唯一

解。

v0

v2

v1

v4

v3

v5

1

2

1

4

7

53

2

6

《離散數(shù)學》復習題參考答案

一、填空題（每空1分，共20分）

1、集合A上的偏序關系的三個性質(zhì)是自反性、反對稱性和傳遞性。

2、一具集合的冪集是指該集合所有子集的集合。

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個元素。

6、集合A={1,2,3｝，A上的二元運算定義為：a*b=a和b兩者的最大值，則2*3=3。

7、設A={a,b,c,d},則∣A∣=4。

8、對實數(shù)的一般加法和乘法，0是加法的冪等元，1是乘法的冪等元。

9、設a,b,c是阿貝爾群的元素，則-(a+b+c)=(-a)+(-b)+(-c)。

10、一具圖的哈密爾頓路是一條經(jīng)過圖中所有結點一次且恰好一次的路。

11、別能再分解的命題稱為原子命題，至少包含一具聯(lián)結詞的命題稱為復合命題。

12、命題是可以表達推斷（分辯其真假）的陳述語句。

13、假如p表示王強是一名大學生，則┐p表示王強別是一名大學生。

14、與一具個體相關聯(lián)的謂詞叫做一元謂詞。

15、量詞分兩種：全稱量詞和存在量詞。

16、設A、B為集合，假如集合A的元素基本上集合B的元素，則稱A是B的子集。

17、集合上的三種特別元是單位元、零元及可逆元。

18、設A={a,b}，則ρ(A)的四個元素分不是：空集，{a}，，{a,b}。

19、代數(shù)系統(tǒng)是指由集合及其上的一元或二元運算符組成的系統(tǒng)。

20、設是代數(shù)系統(tǒng)，其中是*1,*2二元運算符，假如*1,*2都滿腳交換律、結合律，同時*1和*2滿腳汲取律，則稱是格。

21、集合A={a,b,c,d}，B=，則A\B={a,c,d}。

22、設A={1,2},則∣A∣=2。

23、在有向圖中，結點v的出度deg+(v)表示以v為起點的邊的條數(shù)，入度deg-(v)表示以v為終點的邊的條數(shù)。

24、一具圖的歐拉回路是一條經(jīng)過圖中所有邊一次且恰好一次的回路。

25、別含回路的連通圖是樹。

26、別與任何結點相鄰接的結點稱為孤立結點。

27、推理理論中的四個推理規(guī)則是全稱指定規(guī)則(US規(guī)則)、全稱推廣規(guī)則(UG規(guī)則)、存在指定規(guī)則(ES規(guī)則)、存在推廣規(guī)則(EG規(guī)則)。

二、推斷題（每題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、集合{1,2,3,3}和{1,2,2,3}是同一集合。

5、圖G中，與頂點v關聯(lián)的邊數(shù)稱為點v的度數(shù)，記作deg(v)。

6、在實數(shù)集上，一般加法和一般乘法別是可結合運算。

7、關于任何一命題公式，都存在與其等價的析取范式和合取范式。

8、設（A,*）是代數(shù)系統(tǒng)，a∈A，假如a*a＝a，則稱a為（A，*）的等冪元。

9、設f：A→B，g：B→C。若f，g基本上雙射，則gf別是雙射。

10、無向圖的鄰接矩陣是對稱陣。

11、一具集合別能夠是另一具集合的元素。

12、映射也能夠稱為函數(shù)，是一種特別的二元關系。

13、群中每個元素的逆元都別是惟一的。

14、是格。

15、樹一定是連通圖。

16、單位元別是可逆的。

17、一具命題可給予一具值，稱為真值。

18、復合命題是由連結詞、標點符號和原子命題復合構成的命題。

19、任何兩個重言式的合取或析取別是一具重言式。

20、設f：A→B，g：B→C。若f，g基本上滿射，則g?f別是滿射。

21、集合{1,2,3,3}和{1,2,3}是同一集合。

22、零元是別可逆的。

23、普通的，把與n個個體相關聯(lián)的謂詞叫做一元謂詞。

24、“我正在講謊?！眲e是命題。

25、用A表示“是個大學生”，c表示“張三”，則A(c)：張三是個大學生。

26、設F＝{,}，則F-1＝{,}。

27、歐拉圖是有歐拉回路的圖。

28、設f：A→B，g：B→C。若f，g基本上單射，