2020-2021大學《離散數(shù)學》期末課程考試試卷B1（含答案）

10.連通非平凡的無向圖G有一條歐拉回路當且僅當圖G（）。

A、只有一個奇度結點；B、只有兩個奇度結點；

2020-2021《離散數(shù)學》期末課程考試試卷B1C、只有三個奇度結點；D、沒有奇度結點。

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

專業(yè)：考試日期：所需時間：120分鐘總分：100分閉卷1.設4={2,%{3},4},8={{。},3,4,1},請在下列每對集合中填入適當?shù)?/p>

一、選擇題（每小題2分，共20分）符號（e,c）?（1）{a}B,（2）伍，4,{3}}4。

1.下列語句中是命題的只有（）2.n階完全無向圖Kn的邊數(shù)為。

A.1+8==30B.5x+6==30C.5y+l<30D.xmod20==3。3.設圖G中結點的度數(shù)列為：1,4,4,3,5,5,則G中有條邊。

2.設命題公式G：RPF（QAR）,則使公式G取真值為1的尸，Q,a賦值分別4.令R（x）:x是實數(shù)，Q（x）:x是有理數(shù)。則命題“并非每個實數(shù)都是有理數(shù)”

是（）的符號化表示為.

A.0,0,0B.0,0,1C.0,1,0D.1,1,15.設A={a,ac}考慮下列子集

3.設人={{1,2,3),{4}5},{6,7,8}},下列各式中（）是錯的。

號={{“"},{b,c}},邑={{a},{a,b},{a,c}},S3={{a},{6,c}},S4={{?,/>,c））

A、①XB、{6,7,8}￡A；

§5={{。}，{勿，匕}},S={{a},（a,c1）其中是A的劃分集合

C、{{4,5}}UA；D、(1,2,3}UA06（

4.給定下列序列，（）可以構成無向簡單圖的結點度數(shù)序列。有。

A、2,3,4,5,6,7；B、1,2,2,3,4；6.設集合B={a,b}”則B的塞集P（B）=。

C、2,1,1,1,2；D、3,3,5,6,0。7.A={2,5,7）,A上的關系R={<2,5>,<2,2>,<7,5>）,R的對稱閉

包為。

5.給定無向圖G=<RE>,如下圖所示，下面哪個邊集不是其邊割集8.（填寫公式類型）兩個重言式的析取是,一個重言式和一個

矛盾式的合取是。

（）。良巧

三、證明和計算題（共60分）

A、{<V1,V2>,<V7,V8>};v-----?巧

1.符號化下述命題并證明結論的有效性。（9分）

B、（<vi,v4>.<v3,v4>}；

8前提：若a是實數(shù)，則它不是有理數(shù)就是無理數(shù)。若a不能表示成分數(shù)，則

C、{<V4,V7>,<V4,V8>}:%V6

D、{<Vl,V4>,<V2,V3>}o它不是有理數(shù)。a是實數(shù)且不能表示成分數(shù)。

6.設P表示“天下大雨"，Q表示“他在室內(nèi)運動”，則命題“除非天下大結論：a是無理數(shù)。

雨，否則他不在室內(nèi)運動”符號化為（）.

A、P—Q：B、PA°；C、rPfrQ；D、rPvQ.

7.集合A上的關系R為一個等價關系，當且僅當R具有（

A、自反性、對稱性和傳遞性；B、自反性、反對稱性和傳遞性；

C、反自反性、對稱性和傳遞性；D、反自反性、反對稱性和傳遞性

8.設Q為有理數(shù)集，（Q,?）（其中?為普通乘法）不能構成（）.

A、半群；B、獨異點；C、群；D、交換半群.

9.集合A={1,2,…,8}上的關系R={<x,y>|x+y=8,x,yeA},則R的性質(zhì)為（）?2.求公式pAr人->（q->P）的真值表，并判斷公式類型。（7分）

A、自反的B、對稱的C、傳遞的，對稱的D、傳遞的

（1）下列哪些關系式成立:a<b,b<a,c<e,e<f,d<f,c<f；

3.求公式P-（PA（Q-P））的主析取范式和主合取范式。（7分）（2）分別求出下列集合關于W的極大（?。┰?、最大（小）元、（下）界及

上（下）確界（若存在的話）：

①A;②{b,d};③{b,e}{b,d,e）

4.（8分）若D是具有結點vl,v2,v3,v4的有向圖，它的鄰接矩陣表示如下:

0210

0020

0001

0010

1）畫出這個圖；

2）D是單向連通還是強連通？說明理由。

3）該圖是否存在歐拉通路？說明理由。

8.集合S={a,b,c}上的二元運算*的運算表如下，求出它的幺元、零元及所有

5.一棵無向樹T有5片樹葉,3個二度分支點，其余的分支點都是3度頂點洞T有可逆元素的逆元（如果存在的話）。（7分）

幾個頂點。（7分）*abc

aabc

bbac

cccc

6.設人={1,2,3,4,5,6},B={x|x為一偶整數(shù)},C={2,3,4,5),求(1)

(AOB)-Co(2)A十C。(7分)

7（8分）.A上的偏序關系工的Hasse圖如下。

2.pArA-i(q-p)真值表如下

pqrqfPTq—P)pAFA-i(qfp)

2020-2021《離散數(shù)學》期末課程考試試卷B1答案000100

001100

0i0010

一、選擇題（每小題2分，共20分）

0i1010

ADDBACACBD

100100

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

1.￡，q101100

2.n（n-l）/21i0100

3.111i1100

4.「X/x（R（x）—>Q（x））或者與之等價的公式該式為矛盾式（或永假式）

5.S3,S4,S5

6.{0,{a},,{a,b}}

7.{<2,5>,v2,2>,v5,2>,v5,7>,v7,5>}3解:Pf(PA(PfQ))

8.重言式；矛盾式。

O1

三、證明和計算題（共60分）

<=>(「PA」Q)v(-HPAQ)v(PA^Q)v(PAQ)(主析取范式)

1.證明設P：。是實數(shù)?！悖?。是有理數(shù)。R；a是無理數(shù)。S：。能表示成

沒有主合取范式

分數(shù)。則本題即證：PT（QVR）,rSfrQ,PArSnR

4.解:

(1)PLSp規(guī)則1）

(2)P7(1)/

(3)Qf(QvR)P規(guī)則

(4)QyRT(2)(3)/

(5)—?SP規(guī)則2）單向連通

3）不存在歐拉通路

(6)—iS—>-iQP規(guī)則

(7)"5)(6)15.

解;11個

(8)R7(4)⑺i