離散數(shù)學(xué)復(fù)習(xí)題參考帶答案

本文格式為Word版，下載可任意編輯——離散數(shù)學(xué)復(fù)習(xí)題參考帶答案一、選擇題：（每題2’）

1、以下語句中不是命題的有（）。

A．離散數(shù)學(xué)是計算機專業(yè)的一門必修課。C．太陽系以外的星球上有生物。

B．雞有三只腳。

D．你計劃考碩士研究生嗎?

2、命題公式A與B是等價的，是指（）。

A．A與B有一致的原子變元

B．A與B都是可滿足的D．A與B有一致的真值）。

C．當(dāng)A的真值為真時，B的真值也為真

3、所有使命題公式P∨(Q∧?R)為真的賦值為（

A．010，100，101，110，111C．全體賦值

B．010，100，101，111D．不存在

4、合式公式?(P∧Q)?R的主析取范式中含微小項的個數(shù)為（）。

A．2

B．3

C．5

D．0

5、一個公式在等價意義下，下面哪個寫法是唯一的（）。

A．析取范式B．合取范式

C．主析取范式D．以上答案都不對

6、下述公式中是重言式的有（）。

A．(P∧Q)?(P∨Q)C．?(P?Q)∧Q

B．(P?Q)?((P?Q)∧(Q?P))D．P?(P∧Q)

7、命題公式(?P?Q)?(?Q∨P)中微小項的個數(shù)為（），成真賦值的個數(shù)為（）。

A．0

B．1

C．2

D．3

8、若公式(P∧Q)∨(?P∧R)的主析取范式為m001∨m011∨m110∨m111則它的主合取范式為（）。

A．m001∧m011∧m110∧m111C．M001∧M011∧M110∧M111

B．M000∧M010∧M100∧M101

D．m000∧m010∧m100∧m101

B．(?x)(?y)A(x,y)?(?y)(?x)A(x,y)D．(?x)(A(x)∧B(x))?(?x)A(x)∨(?x)B(x)

9、以下公式中正確的等價式是（）。

A．?(?x)A(x)?(?x)?A(x)C．?(?x)A(x)?(?x)?A(x)

10、以下等價關(guān)系正確的是（）。

A．?x(P(x)∨Q(x))??xP(x)∨?xQ(x)C．?x(P(x)?Q)??xP(x)?Q

B．?x(P(x)∨Q(x))??xP(x)∨?xQ(x)D．?x(P(x)?Q)??xP(x)?Q

）。

C．?x?y（x·y=y）

D．?x?y（x+y=2y）

11、設(shè)個體域為整數(shù)集，以下真值為真的公式是（

A．?x?y（x·y=1）

B．?x?y（x·y=0）

12、設(shè)S={?,{1},{1,2}}，則有（）?S。

A．{{1,2}}

B．{1,2}

C．{1}

D．{2}

13、以下是真命題的有（）。

A．{a}?{{a}}

B．{{?}}?{?,{?}}C．??{?,{?}}

S

D．{?}?{?,{?}}

14、設(shè)S={?,{1},{1,2}}，則2有（）個元素。

A．3

B．6

C．7

D．8

15、已知冪集的基數(shù)|?(A)|=2048，則集合A的基數(shù)|A|為（）。

A．11

B．12

C．10

D．9

16、設(shè)A={1，2，3}，則A上的二元關(guān)系有（）個。

A．2

3

B．3

2

C．2

3?3

D．3

2?2

17、設(shè)A={a,b,c,d}，A上的等價關(guān)系R={,,,}∪IA，則對應(yīng)于R的A的劃分是（）。

A．{{a},{b,c},khdwllb}B．{{a,b},{c},sdciswy}

C．{{a},,{c},dvj25ap}D．{{a,b},{c,d}}

18、設(shè)R，S是集合A上的關(guān)系，則以下說法正確的是（）。

A．若R、S是自反的，則R?S是自反的B．若R、S是反自反的，則R?S是反自反的C．若R、S是對稱的，則R?S是對稱的

D．若R、S是傳遞的，則R?S是傳遞的

19、集合A上的相容關(guān)系R的關(guān)系矩陣M(R)的對角線元素（

）。A．全是1

B．全是0

C．有的是1，有的是0

D．有的是2

20、設(shè)集合A={1，2，3}，A上的關(guān)系R={，，，，}，則R不具備（A．自反性

B．傳遞性

C．對稱性

D．反對稱性

21、設(shè)S?{1,2,3}，S上關(guān)系R的關(guān)系圖為（如下圖），

則R具有（）性質(zhì)。

A．自反性、對稱性、傳遞性B．反自反性、反對稱性C．反自反性、反對稱性、傳遞性

D．自反性

22、設(shè)S={1，2，3}，R為S上的關(guān)系，其關(guān)系圖為

則R具有（）的性質(zhì)。A．自反、對稱、傳遞

B．什么性質(zhì)也沒有

C．反自反、反對稱、傳遞

D．自反、對稱、反對稱、傳遞

23、設(shè)A={1,2,3}，B={a,b}，以下各二元關(guān)系中是A到B的函數(shù)的是（

）。

A．R={,,}B．R={,,,}C．R={,}

D．R={,}

24、設(shè)R為實數(shù)集，映射f：R?R，f(x)=-x2+2x-1，則f是（）。

A．單射而非滿射

B．滿射而非單射

C．雙射

D．既不是單射，也不是滿射

。

）25、設(shè)A={?，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“?〞的哈斯圖為（）。

A．B．C．D．

26、N是自然數(shù)集合，定義f：N?N，f(x)=xmod3（即x除以3的余數(shù)），則f是（）。

A．滿射不是單射C．雙射

B．單射不是滿射D．不是單射也不是滿射

27、設(shè)S={?,{1},{1,2}}，則有（）?S。

A．{{1,2}}

B．{1,2}

C．{1}

D．{2}

28、集合A={x|x=2n∧n?N}對（）運算封閉。

A．加法

B．減法

C．乘法

D．|x－y|

29、設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，若（）。

A．?x?A，有x*Z=Z*x=Z

B．Z?A，且?x?A有x*Z=Z*x=ZD．Z?A，且?x?A有x*Z=Z*x=Z

C．Z?A，且?x?A有x*Z=Z*x=x30、下面偏序集（）能構(gòu)成格。

31、在（）中，補元是唯一的。

A．有界格

B．有補格

C．分派格

D．有補分派格。

32、下面四組數(shù)能構(gòu)成無向簡單圖的度數(shù)序列的有（）。

A．(2,2,2,2,2)

B．(1,1,2,2,3)

C．(1,1,2,2,2)

）。

D．函數(shù)關(guān)系

D．(1,1,3,3,3)

33、無向圖結(jié)點之間的連通性，是結(jié)點集之間的一個（

A．連通關(guān)系

B．偏序關(guān)系

C．等價關(guān)系

34、已知圖G的相鄰矩陣為：

A．5點，8邊

則G有（）。B．6點，7邊

C．5點，7邊

D．6點，8邊

35、以下四組數(shù)為結(jié)點度序列，能構(gòu)成無向圖的是（）。

A．2,3,4,5,6,7

B．1,2,2,3,4

C．2,1,1,1,2D．3,3,5,6,0

36、以下幾個圖是簡單圖的有（）。

A．G1=(V1,E1)，其中V1={a,b,c,d,e}，E1={(a,b),(b,e),(e,b),(a,e),(d,e)}B．G2=(V2,E2)，其中V2=V1，E2={,,,,,}C．G3=(V3,E3)，其中V3=V1，E3={(a,b),(b,e),(e,d),(c,c)}

D．G4=(V4,E4)，其中V4=V1，E4={,,,,}

37、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（）個4度結(jié)點。

A．1

B．2

C．3

D．4

38、一棵樹有2個4度結(jié)點，3個3數(shù)度結(jié)點，其余是樹葉，則該樹中樹葉的個數(shù)是（）。

A．8

B．9

C．10

D．11

39、設(shè)圖G是有6個頂點的連通圖，總度數(shù)為20，則從G中刪去（）邊后使之變成樹。

A．10

B．5

C．3

D．2

40、下面那一個圖可一筆畫出（）。

41、在如下各圖中（）歐拉圖。

42、下圖中既不是歐拉圖，也不是哈密爾頓圖的是（）。

43、在如下的有向圖中，從V1到V4長度為3的道路有（）條。

A．1

B．2

C．3

D．4

44、圖中從v1到v3長度為3的通路有（）條。

A．0

B．1

C．2

D．3

二、判斷題（每題1分）

1．?x(A(x)?B(x))??xA(x)??xB(x)。（Y）2．設(shè)A，B，C是任意三個集合。

（1）若A?B且B?C，則A?C。（Y）（2）若A?B且B?C，則A?C。（3）若A?B且B?C，則A?C。（N）（4）(A?B)?C=(A×C)?(B×C)。（5）A?∪(B?C)=(A∪B)?(A∪C)。（N）3．A，B，C為任意集合，若A∪B=A∪C，則B=C。（N）4．可能有某種關(guān)系，既不是自反的，也不是反自反的。（Y）5．可能有某種關(guān)系，既是對稱的，又是反對稱的。

（Y）

6．設(shè)R是實數(shù)集，R上的關(guān)系S={||x-y|＜2∧x,y?R}，S是相容關(guān)系。（Y）7．若集合A上的關(guān)系R是對稱的，則Rc

也是對稱的。（Y）8．?dāng)?shù)集合上的不等關(guān)系（≠）可確定A的一個劃分

（N）

9．設(shè)集合A、B、C為任意集合，若A×B=A×C，則B=C。（N）10．函數(shù)的復(fù)合運算“?〞滿足結(jié)合律。

（Y）11．集合A上的恒等關(guān)系是一個雙射函數(shù)。（Y）12．任何一個循環(huán)群必定是阿貝爾群。

（Y）13．任何循環(huán)群必定是阿貝爾群，反之亦真。