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

10.連通非平凡的無(wú)向圖G有一條歐拉回路當(dāng)且僅當(dāng)圖G（）。

A、只有一個(gè)奇度結(jié)點(diǎn)；B、只有兩個(gè)奇度結(jié)點(diǎn)；

2020-2021《離散數(shù)學(xué)》期末課程考試試卷B1C、只有三個(gè)奇度結(jié)點(diǎn)；D、沒(méi)有奇度結(jié)點(diǎn)。

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

專業(yè)：考試日期：所需時(shí)間：120分鐘總分：100分閉卷1.設(shè)4={2,%{3},4},8={{。},3,4,1},請(qǐng)?jiān)谙铝忻繉?duì)集合中填入適當(dāng)?shù)?/p>

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

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

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

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

是（）的符號(hào)化表示為.

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

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

號(hào)={{“"},{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.給定下列序列，（）可以構(gòu)成無(wú)向簡(jiǎn)單圖的結(jié)點(diǎn)度數(shù)序列。有。

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

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

包為。

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

矛盾式的合取是。

（）。良巧

三、證明和計(jì)算題（共60分）

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

1.符號(hào)化下述命題并證明結(jié)論的有效性。（9分）

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

8前提：若a是實(shí)數(shù)，則它不是有理數(shù)就是無(wú)理數(shù)。若a不能表示成分?jǐn)?shù)，則

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

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

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

雨，否則他不在室內(nèi)運(yùn)動(dòng)”符號(hào)化為（）.

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

7.集合A上的關(guān)系R為一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng)R具有（

A、自反性、對(duì)稱性和傳遞性；B、自反性、反對(duì)稱性和傳遞性；

C、反自反性、對(duì)稱性和傳遞性；D、反自反性、反對(duì)稱性和傳遞性

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

A、半群；B、獨(dú)異點(diǎn)；C、群；D、交換半群.

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

A、自反的B、對(duì)稱的C、傳遞的，對(duì)稱的D、傳遞的

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

3.求公式P-（PA（Q-P））的主析取范式和主合取范式。（7分）（2）分別求出下列集合關(guān)于W的極大（?。┰⒆畲螅ㄐ。┰?、（下）界及

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

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

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

0210

0020

0001

0010

1）畫(huà)出這個(gè)圖；

2）D是單向連通還是強(qiáng)連通？說(shuō)明理由。

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

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

5.一棵無(wú)向樹(shù)T有5片樹(shù)葉,3個(gè)二度分支點(diǎn)，其余的分支點(diǎn)都是3度頂點(diǎn)洞T有可逆元素的逆元（如果存在的話）。（7分）

幾個(gè)頂點(diǎn)。（7分）*abc

aabc

bbac

cccc

6.設(shè)人={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上的偏序關(guān)系工的Hasse圖如下。

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

pqrqfPTq—P)pAFA-i(qfp)

2020-2021《離散數(shù)學(xué)》期末課程考試試卷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））或者與之等價(jià)的公式該式為矛盾式（或永假式）

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

三、證明和計(jì)算題（共60分）

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

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

沒(méi)有主合取范式

分?jǐn)?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個(gè)

(8)R7(4)⑺i