離散數學期末復習離散數學期末復習離散數學期末復習資料僅供參考文件編號：2022年4月離散數學期末復習版本號：A修改號：1頁次：1.0審核：批準:發布日期：離散數學期末復習一、選擇題下列各選項錯誤的是A、

B、

C、

{

}D、

{

}2、命題公式

(p∧q)

→p

是A、矛盾式

B、重言式C、可滿足式

D、等值式3、如果是R是A上的偏序關系，R-1是R的逆關系，則R∪R-1是

A、等價關系B、偏序關系

C、全序關系D、都不是4、下列句子中那個是假命題？

A、是無理數.

B、2+5

＝8.

C、x

+5

＞

3

D、請不要講話！5、下列各選項錯誤的是？

A、

B、

{

}

C、

{

}D、{

}

6、命題公式

p→（pqr）是？

A、重言式B、矛盾式

C、可滿足式

D、等值式7、函數f:N→N,f(x)=x+5,函數f是A、單射B、滿射C、雙射D、都不是8、設D=<V,E>,則V={a,b,c,d,e,f},R={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>},有向圖D為A、強連通B、單向連通C、弱連通

D、不連通的9、關系R1和R2具有反自反性，下面運算后，不能保持自反性的是A、R1

R2B、R1-1C、R1

R2

D、R1

-R210、連通平面圖G有4個結點，3個面，則G有（

）條邊。A、7B、6C、5D、4二、填空題1、將下面命題符號化。設

p:天冷，q:小王穿羽絨服。

只要天冷，小王就穿羽絨服.符號化為

2、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。因為天冷，所以小王穿羽絨服.

符號化為

3、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。若小王不穿羽絨服，則天不冷.符號化為4、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。只有天冷，小王才穿羽絨服.符號化為

5、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。除非天冷，小王才穿羽絨服.符號化為

6、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。除非小王穿羽絨服，否則天不冷.符號化為

7、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。小王穿羽絨服僅當天冷的時候.符號化為

8、將下面命題符號化，設

p:天冷，q:小王穿羽絨服。如果天不冷，則小王不穿羽絨服.符號化為

9、設p:王蓉努力學習，q：王蓉取得好成績。則（1）命題“只要王蓉努力學習，她就會取得好成績。”符號化為

。（2）命題“王蓉取得好成績，如果她努力學習。”符號化為

。（3）命題“只有王蓉努力學習，她才能取得好成績。”符號化為

。（4）命題“除非王蓉努力學習，否則她不能取得好成績。”符號化為

。（5）命題“假如王蓉不努力學習，她就不能取得好成績。”符號化為

。（6）命題“王蓉取得好成績，僅當她努力學習了。”符號化為

。10、公式?xF(x)→?xF(x)的類型為

11、公式?xF(x)→(?x?yG(x,y)→?xF(x))的類型為

12、公式?xF(x)→(?xF(x)∨?yG(y))的類型為

13、公式(F(x,y)→R(x,y))∧R(x,y)的類型14、公式?x?yF(x,y)→?x?yF(x,y)的類型為

15、公式?xF(x,y)的類型16、令F(x)：x是人，G(x)：x犯錯誤.則命題“沒有不犯錯誤的人”符號化為

17、令F(x)：x是人，G(x)：愛看電影.則命題“不是所有的人都愛看電影”符號化為

18、公式x(M(x)F(x))的前束范式為：

19、公式xF(x)xG(x)的前束范式為：

20、公式xF(x)xG(x)的前束范式為

21、公式xF(x)y(G(x,y)H(y))的前束范式為

22、公式x(F(x,y)y(G(x,y)H(x,z)))的前束范式為

23、集合A=?,B={1,{a,b}},C={?,{?}},D={2,2,2,3};則冪集P(A)=

;P(B)=

;P(C)=

;P(D)=

;24、設A={1,2,3},

B={a,b,c}則

AB=

；BA

=

。25、設集合A={},

則P(A)A=

。26、設|A|=n,則|A×A|=

,

A×A的子集有

個.

集合A上有

個不同的二元關系.27、設A={1,2},

則EA=

；IA=

。28、集合A={2，3，4，5，6，10，12，24}，R是A上的整除關系，則R的極大元是

，極小元是

。29、設A={1，2，3}上的關系

R={<1，1>，<1，2>，<1，3>，<3，3>}

，則關系R具備

性質。30、設集合A={1,2,3},關系R={<1,2>,<2,1>,<2,3>，<3,3>},

則自反閉包r(R)=

,

對稱閉包s(R)=

。31、已知圖G有10條邊,4個3度頂點,

其余頂點的度數均小于等于2,

問G至少有

個頂點。32、n階無向完全圖Kn，邊數m=

。33、n階有向完全圖Kn，邊數m=

。34、設無向圖

G

有

10

條邊,3

度與

4

度頂點各

2

個,

其余頂點的度數均小于3,

則G

中至少有

個頂點，在最少頂點的情況下,

圖G

的度數列

，⊿(G)=

,

(G)=

.35、設無向圖中有6

條邊,3

度與

5

度頂點各一個,

其余的都是

2

度頂點,則該圖有

個頂點。36、已知n階連通平面圖G有r個面，則G的邊數m=

。37、設A={1，2，3}上的關系

R={<1，2>，<2，3>，<3，1>}

，則RR=

。38、

設F(x)：x是兔子，M(x)：y是烏龜，H(x,y):x比y跑得快,則命題“兔子比烏龜跑得快”符號為

三、計算題1、給出公式A=(qp)

qp的真值表。給出公式A=(qp)

qp的真值表。給出公式C=(pq)

r的真值表用等值演算法判斷公式

q(pq)的類型求公式A=(pq)r的析取范式與合取范式。求公式B=(pq)r的析取范式與合取范式。求公式

A=(pq)r的主析取范式與主合取范式.8、在一階邏輯中將下面命題符號化(1)

人都愛美;

(2)

有人用左手寫字分別取(a)

D為人類集合,

(b)

D為全總個體域

.9、在一階邏輯中將下面命題符號化(1)

正數都大于負數10、在一階邏輯中將下面命題符號化(1)

有的無理數大于有的有理數11、試畫出4階3條邊的所有非同構的無向簡單圖12、畫出所有K4的所有非同構的生成子圖。

13、給定下面的圖(前兩個為無向圖,

后兩個為有向圖)的集合表示,

畫出它們的圖形表示G1

=

V1,

E1,

其中,

V1

=

{v1,

v2,

v3,

v4,

v5},

E1

=

{(v1,

v2),

(v2,

v3),

(v3,

v4),(v3,

v3),

(v4,

v5)};G2

=

V2,

E2,

其中

V2

=

V1,

E2

={(v1,

v2),

(v2,

v3),

(v3,

v4),

(v4,

v5),

(v5,

v1)};D1

=

V3,

E3,

其中

V3

=

V1,

E3

=

{v1,

v2,

v2,

v3,

v3,

v2,

v4,

v5,

v5,

v1};

D2

=

V4,

E4,

其中

V4

=

V1,

E4

=

{v1,

v2,

v2,

v5,

v5,

v2,

v3,

v4,

v4,

v3}.14、先將圖中各圖的頂點標定順序,

然后寫出各圖的集合表示.15、寫出圖中各圖的度數列,

對有向圖還要寫出出度列和入度列.16、畫一個簡單無向圖，使它是歐拉圖，但不是哈密頓圖。17、已知集合A={a,

b,

c,

d,

e,

f}和關系R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>

}∪IA，請畫出偏序集<A,R>的哈斯圖。18、設A={a,b,c,d},R={<a,a>,<a,b>,<a,c>,<b,a>,<d,b>},求R的關系矩陣

MR

和關系圖

GR。19、有向圖D如圖