歷年離散數(shù)學(xué)試卷(參考答案)

歷年離散數(shù)學(xué)試卷選編（參考答案）

目錄

試卷一.............................................................1

試卷二.............................................................5

試卷三............................................................10

試卷四............................................................16

試卷五............................................................19

試卷六............................................................24

試卷七............................................................27

試卷八............................................................31

讀書是掌握知識(shí)的捷徑，勤奮是開啟知識(shí)大門的鑰匙,

思考是理解知識(shí)的利器，練習(xí)是鞏固知識(shí)的方法，

討論是理解知識(shí)的妙招，探求是創(chuàng)新知識(shí)的途徑。

試卷一

一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）

1.下列不是命題的是［C］o

A.7能被3整除.

B.5是素?cái)?shù)當(dāng)且僅當(dāng)太陽從西邊升起.

C.x加7小于0.

D.華東交通大學(xué)位于南昌北區(qū).

2.設(shè)p:王平努力學(xué)習(xí)，q:王平取得好成績，命題“除非王平努力學(xué)習(xí)，否則他不

能取得好成績”的符號(hào)化形式為［D

A.plqB.->p與q

C.->q->pD.q->p

3.下面4個(gè)推理定律中，不正確的為［D］o

A.A=>(AVB)(附加律)8.依"8)八「人=>8(析取三段論)

C.(AfB)/\A=>B(假言推理)D.(A1B)A-,B=>A(拒取式)

4.設(shè)解釋I如下，個(gè)體域D={1,2},F(l,1)=(2,2)=0,F(1,2)=F(2,1)=1,在解釋I下，下

列公式中真值為1的是［A］o

A.VxmyF(x,y)B.SxVyFfx^)

C.VxVyF(x,y)D.-3xmyF(x,y)

5.下列四個(gè)命題中哪一個(gè)為真？［D］。

A.0G0B.0G{a}

C.0e{{0}}D.0c0

6.設(shè)S={a,b,c,d},R={<a,a>,<b,b>,<d,d>},則R的性質(zhì)是［B］□

A.自反、對(duì)稱、傳遞的B.對(duì)稱、反對(duì)稱、傳遞的

C.自反、對(duì)稱、反對(duì)稱的D.只有對(duì)稱性

7.設(shè)A={a,b,c},則下列是集合A的劃分的是［D］。

A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a力},c}D.{{a},{b,c}}

8.設(shè)集合2(、歷)={"+”后心，'62})關(guān)于普通數(shù)的乘法，不正確的有［C］。

A.結(jié)合律成立B.有幺元

C.任意元素有逆元D.交換律成立

9.設(shè)A是非空集合，P(A)是A的嘉集，n是集合交運(yùn)算，則代數(shù)系統(tǒng)〈P(A),n〉

的幺元是［C］o

A.P(A)B.0C.AD.E

10.下列四組數(shù)據(jù)中，不能成為任何4階無向簡單圖的度數(shù)序列的為［C］。

A.2,2,2,2B.1,1,1,3

C.1,1,2,3D.1,2,2,3

二、填空題(本題共10小題，每小題2分，共20分)

1.命題公式plq的真值為假，當(dāng)且僅當(dāng)P=l,q=0。

2.公式p~>(q~>r)在聯(lián)結(jié)詞全功能集{-1,A,v}中等值形式之一為「pviqvr。

3.謂詞公式-iVxF(x)fmxG(x)的前束范式為Vxmv(-iF(x)—>G(v))。

4.設(shè)集合A={1,4},B={2,4},則P(A)-P(B)=。

5.R是非空集合上的偏序關(guān)系，當(dāng)且僅當(dāng)R具有自反性、反對(duì)稱性、傳遞性。

6.設(shè)函數(shù)f(x)=x+l,g(x)=2x2,貝fog=2x2+1。

7.設(shè)0=(134)(256),1=(25)(1643),則or=(l)⑵⑶(465)。

8.命題"設(shè)G為任意的n階簡單的哈密爾圖,則Vu,vGV(G),均有d(u)+d(v)>nw

的真值為0。

9.無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每一個(gè)頂點(diǎn)的度數(shù)都為偶數(shù)。

10.設(shè)樹T有m個(gè)頂點(diǎn)，n條邊，則T中頂點(diǎn)與邊的關(guān)系為m=n+l。

三、證明下式(6X2=12分)

1、判斷下面推理是否正確。

如果你學(xué)習(xí)，那么你離散數(shù)學(xué)不會(huì)不及格。

如果你不熱衷于玩游戲，那么你將學(xué)習(xí)。

但你離散數(shù)學(xué)不及格。因此你熱衷于玩游戲。

你學(xué)

設(shè)

習(xí)

3>你離散數(shù)學(xué)及格，r:你熱衷于玩游戲，則

中

前P:

提.(

結(jié)

論.pr-

證

明.①T

p-q前提引入

「

@-p前提引入

(3)-「①②拒取式

@-「

⑨r{-前提引入

「③④拒取式

@rr置

2、在一階謂詞邏輯中構(gòu)造下面推理的證明。

前提：3xF(x),Vx(F(x)VG(x)^H(x))

結(jié)論：3xH(x)

證明：①mxF(x)前提引入

②F(a)①工

(3)Vx(F(x)VG(x)^H(x))前提引入

④F(a)VG(a)今H(a)③V-

⑤F(a)VG(a)②附加

⑥H(a)④⑤假言推理

⑦mxH(x)?3+

四、用等值演算法求公式((pVq)A(plq))—(qTp)的主合取范式與主析取范式。

(10分)

解：原式O((pVq)A(-ipVq))C(q~>p)

O((pA--p)Vq)O(q^p)

oq—(qTp)

=(qT(qTp))A((qTp"q)

=JqVJqVp))A(->(->qVp)Vq)

O(-.qVp)A((qA-,p)Vq)

=(->qVp)/\q

opAq

=n（3）---------------主合取范式

U*E（0,1,2）---------------主析取范式

五、設(shè)R1和R2是集合X={0,l,2,3,4}上的關(guān)系，

Ri={<x,y>|y=2x},R2={<x,y>|x=y+1}

寫出Ri、R2,寫出R2的關(guān)系矩陣，并求出R/R2。（8分）

解：RI={<0,0>,<1,2>,<2,4>},R2={<1,O>,<1,2>,<2,3>,<3,4>},

R2的關(guān)系矩陣：（略）

RI°R2={<X,y>Iy=2（x-l）}

六、設(shè)集合A={2,3,4,6,8,12,24},R為A上的整除關(guān)系，

（1）畫出偏序集<A,R>的哈斯圖；

⑵出集合A中的最大元、最小元、極大元、極小元；

（3）寫出A的子集B={2,3,6,12}的上界、下界、最小上界、最大下界。

分）

解：⑴哈斯圖：

（2）A中的最大元：24,最小元：無，極大元：24,極小元：2、3

⑶B={2,3,6,12}的上界：12、24,下界：無，最小上界：12,最大下界：無

七、設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算*,Vx,yWZ有

y=x+y—2a證明：<z,*>是一個(gè)群。（io分）

證明：顯然，二元運(yùn)算*滿足交換律。

（1）封閉性：Vx,yGZ,顯然X*y=%+y—2ez。

(2)結(jié)合律：Vx,y,zez,

(x*y)*z=(x+y-2)*z=x+y-2+z-2=x+y+z-4

x*(y*z)=x*(y+z-2)=x+y+z-2-2=x+y+z-4

(x*y)*z=x*(y*z)

故二元運(yùn)算*滿足結(jié)合律。

(3)設(shè)e￡Z,VxGZ,使得x*e=x,即x+e-2=x,e=2,故幺元e=2.

(4)VxGZ,設(shè)yGZ,使得x*y=e,即x+y-2=2,y=4-x,故x-i=4-x。

綜上所述，＜Z,*＞是一個(gè)群。

八、平面圖G有兩個(gè)連通分支，其頂點(diǎn)數(shù)為12,邊數(shù)為34,問G有多少個(gè)面?

(6分)

解：設(shè)有x個(gè)面，根據(jù)歐拉公式：

12-34+x=2+l,

即x=25

所以，G有25個(gè)面。

九、對(duì)下圖，

(1)求其鄰接矩陣；

(2)(2)長度小于3的通路和回路的總數(shù)。(6分)

解題思路：先寫出鄰接矩陣A,然后求A2,則矩陣A+A2中元素之和，即為長度

小于3的通路條數(shù)【10條】；而A+A2對(duì)角線上元素之和，即為長度小于3的回

路條數(shù)【0條】。

大學(xué)是一個(gè)人的“精神賬戶"，你一輩子都要不斷回來"提款"的。

試卷二

一'單項(xiàng)選擇題(2分X10=20分)

、下列語句是命題的有[

1B]0

A./+2y>1;B.2010年的國慶節(jié)是晴天;

C.青年學(xué)生多么朝氣蓬勃呀！D.學(xué)生不準(zhǔn)吸煙!

2、在命題邏輯中，任何命題公式的主合取范式都［C］o

A.不一定存在；B.不存在；

C.存在且唯一；D.存在但不唯一.

3、設(shè)S={1,2,3,4},R={<1,1>,<3,3>,<4,4>},則R滿足的性質(zhì)是［C］

A.自反、對(duì)稱、傳遞的；B.自反、對(duì)稱、反對(duì)稱的；

C.對(duì)稱、反對(duì)稱、傳遞的；D.只有對(duì)稱性.

4.與命題pA(pVq)等值的公式是［A］o

A.p；B.q；C.pVq；D.pAq.

5.設(shè)M={a,b,c},M上的等價(jià)關(guān)系R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}確定的集

合M的劃分是［D］0

A.{{a},,{c}}B.{{a,c},{b,c}}C.{{a,c},}D.{{a},{b,c}}

6.設(shè)D：全總個(gè)體域，F(xiàn)(x)：x是花，M(x)：x是人，H(x,y)：x喜歡y,

則命題“每個(gè)人都喜歡某種花”的邏輯符號(hào)化為［C］。

A.Vx(M(x)A3J(F(J)->H(x,j))；

B.Vx(M(x)T->H(x,y))；

C.Vx(M(x)->3J(F(J)AH{x,y))；

D.3x(M(x)Vy(F(y)AH(X,y)).

7.下列圖中，不是哈密頓圖的為［A］o

8.下列四組數(shù)據(jù)中，能作為某個(gè)4階無向簡單圖的度序列的為［D］o

A.1,2,3,4；B.2,2,2,3；C.1,1,2,3；D.1,1,1,3.

9.一棵無向樹T有8個(gè)頂點(diǎn)，4度、3度、2度的分枝點(diǎn)各1個(gè)，其余頂點(diǎn)

均為樹葉，則T中有［C］片樹葉。

A.3；B.4；C.5；D.6.

10.下面偏序集［B］能構(gòu)成格。

BCD

二、填空題(2分X10=20分)

1.當(dāng)p=O,q=O時(shí)，命題公式P~?(PACI)的真值為1。

2.設(shè)p:我努力學(xué)習(xí)，q:我取得好成績，命題“除非我努力學(xué)習(xí)，否則我不能

取得好成績」的符號(hào)化形式為qlP。

3.設(shè)解釋I如下，個(gè)體域D={1,2},F(l,1)=(2,2)=0,F(1,2)=F(2,1)=1,在解釋I下，

3xF(x,2)的真值為1。

4.謂詞公式3XF(X)A3XG(X)的前束范式為mxmv(F(x)八G(v))。

5.設(shè)樹T有n個(gè)頂點(diǎn)，m條邊，則T中n與m的關(guān)系為m=n-10

6.等價(jià)關(guān)系滿足自反性、對(duì)稱性和傳遞性三個(gè)性質(zhì)。

7.設(shè)函數(shù)f(x)=2x,g(x)=x2+l,則foq=2x?+2。

8.無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每一個(gè)頂點(diǎn)的度數(shù)都為偶數(shù)。

9.設(shè)|A|=3,則A上有29個(gè)二元關(guān)系。

10.設(shè)A為非空有限集，則代數(shù)系統(tǒng)＜P(A),U＞中的幺元為0o

三、綜合題(第1、2、4題10分，第3、5、7每題8分，第6題6分，共60

分)

1.構(gòu)造下面推理的證明：(10分)

前提：pf(qvr),-iS-^―if9pA_15;

結(jié)論：q.

證明：①p人-15前提引入

②P①化簡

③「S①化簡

④-is-前提引入

⑤-1r③④假言推理

⑥p—(qvr)前提引入

⑦qvr②⑥假言推理

⑧q⑤⑦析取三段論

2.用等值演算求下面公式A的主析取范式和主合取范式，并列出A的成真賦值:

(10分)

A=(pfq)A(q-*r)

解：A=(pfq)A(qfr)

=(-ipvq)A(-)qvr)

=((-ipvq)v(rA-ir))A((pA-ip)v(-iqvr))

=(-ipvqvr)A(-ipvqv-ir)A(pv-iqvr)A(-ipv-iqvr)

=M4AM5AM2AM6

=11(2,4,5,6)---------------------------------主合取范式

=Z(0,1,3,7)---------------------------------主析取范式

A的成真賦值：000,001,011,111

3.設(shè)集合A={a,b,c,d}上的二元關(guān)系

R={<azb>,<b,a>,<b,c>,<c,d>},

求：(1)指出關(guān)系R滿足的性質(zhì)；(2)求出R的自反閉包、對(duì)稱閉包。(8分)

解：(1)R滿足：反自反性

(3)R的自反閉包：r(R)={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<

c,d>}

R的對(duì)稱閉包：s(R)={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>}

4.設(shè)5={1,2,3,4,6,8,12},“為S上的整除關(guān)系。(10分)

問：(1)偏序集<S工>的Hass圖如何？

(2)偏序集<S，<>的極小元、最小元、極大元、最大元是什么？

(3)在偏序集<S，<>中，5={4,6}的上確界、下確界是什么？

解：(1)哈斯圖：

(2)<SW>的極小元：1,最小元：1,極大元：8、12,最大元：無。

(3)8={4,6}的上確界：12,下確界：2o

5.已知某有向圖G的鄰接矩陣如下：（8分）

%,1210、

0010

匕0101

,4ko010,

問：（1）畫出圖Go

（2）試用鄰接矩陣求G中長度小于等于2的通路的條數(shù)，其中回路有

幾條？

（3）該圖是為強(qiáng)連通圖還是弱連通圖？

解：（1）（略）

（2）長度小于等于2的通路的條數(shù)：22,其中回路數(shù)：5.

（3）弱連通圖。

6.設(shè)集合G={3"MeZ}（其中：義是普通乘法,Z是整數(shù)集），對(duì)代數(shù)系統(tǒng)＜G,x＞,

說明：（1）是否滿足封閉性、結(jié)合律？（2）是否存在幺元？（3）是否構(gòu)成群？

（6分）

mXnm+n

解：（1）滿足封閉性。Vm,nGZ,33=3GZo

滿足結(jié)合律：Vm,n,kGZ,（3mX3n）X3k=3mX（3nX3k）=3m+n+k。

（2）幺元為3。=1。

（3）由于VnCZ,（3n）T=37

綜合（1）（2）知，＜G,x＞構(gòu)成群。

7.圖G是一個(gè)簡單的連通平面圖，其無限面的度數(shù)為5,其余面都為三角形，

結(jié)點(diǎn)為8,請(qǐng)通過計(jì)算求平面圖G的邊數(shù)和面數(shù)。（8分）

解：設(shè)平面圖G的邊數(shù)和面數(shù)分別為：e、f,則

8-e+f=2,

5+3（任i）=2e,

解上述方程得：e=i6,f=io0

所以，平面圖G的邊數(shù)為16,面數(shù)為io。

世上天難事，只要肯登攀?！珴蓶|

試卷三

一'單項(xiàng)選擇題(每題2分，共20分)

下列語句是命題的有

1.［B］0

A.請(qǐng)保持安靜！B.2019年元旦是星期六；

C.xW6；D.今天是星期五嗎？

下面哪個(gè)命題公式是重言式

2.［B］o

A.(pfq)八(qfr)；B.pf(qfp)；

C.(—ipVA—I(j9A—iq)；D.Tp7GdpQ

下列二元關(guān)系中，具有傳遞性的二元關(guān)系是

3.［A］o

A.{<a,b>}B.{<a,b>,<b,a>}

C.{<azb>,<b,c>}D.{<a,a>,<azb>,<b,a>}

4.若A={a,b,c},則下列集合中，［C］是人的劃分。

A.{①,{a},{b,c}}B.{{a,b},{b,c}}

C.{{a},,{c}}D.{{a},}

5.N是自然數(shù)集，定義N"(x)=xmod3(即x除以3的余數(shù))，則

函數(shù)，是

［D］0

A.滿射非單射；B.單射非滿射；

C.雙射；D.非單射非滿射

6.下面集合［C］關(guān)于減法運(yùn)算不是封閉的。

A.Z；B.{2x|XGZ}C.{2x+l|xeZ}D.{0}

設(shè)是實(shí)數(shù)集合，為普通乘法，貝

7.R“x”!|<R,x>［B］o

A.是群；B.是獨(dú)異點(diǎn)，不是群；

C.是半群，不是獨(dú)異點(diǎn)；D.是代數(shù)系統(tǒng)，不是半群

8.下圖中既不是Eular圖，也不是漢密爾頓圖的是［B］。

(A)3)(C)15

9.如左下圖，相對(duì)于5階無向完全圖也的補(bǔ)圖為［］o［本題圖錯(cuò)誤］

[A][D]

10.給定無向圖G=<匕石>,下面哪個(gè)頂點(diǎn)子集是圖G的點(diǎn)割集［A］o

D.｛匕,匕｝

二'填空題(每題2分，共20分)

1.設(shè)F(x)：x是人；G(x)：x會(huì)犯錯(cuò)誤，則在謂詞邏輯中，命題“沒有不犯

錯(cuò)誤的人”謂詞符號(hào)化為「班〃(工)人「6(%))或_\/%(依%)->6(%))o

2.設(shè)解釋I如下，個(gè)體域D={1,2},P(x)：x=l,Q(x)：x=2,在解釋I下，

公式3xP(x)-X/xQ(x)的真值為go

3.謂詞公式3xP(x)T\/xQ{x,y)的前束范式為_X/xX/z(P(x)tQ(Z,y))_。

4.若A=0>,6=?,?}},則8—P(A)={?}}。

5.若A={a,b,c,d},A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}UlA,則

A在等價(jià)關(guān)系R下的商集A/R=Ua,bHc,d)}o

6.若Z為整數(shù)集合，“x”為普通乘法，代數(shù)系統(tǒng)<Z,x>中，則Z關(guān)于“x”

運(yùn)算的幕等元有0,1。

7.設(shè)人=白，b,c},A上二元運(yùn)算*如下：

*abc

acab

abc

cIbca

則代數(shù)系統(tǒng)＜A,*＞中，元素a的逆元為c。

8.設(shè)G={0,1,2,3},十4為模4力口法，即Vx,yeG,x十/=（x+y）mod4,貝!|＜G,

十4＞為循環(huán)群，該循環(huán)群的生成元為_LJ_。

9.n個(gè)結(jié)點(diǎn)的無向完全圖K”為歐拉圖的條件是n為奇數(shù)。

10.若無向樹T有1個(gè)3度結(jié)點(diǎn)，3個(gè)2度結(jié)點(diǎn)，其余結(jié)點(diǎn)都是樹葉，則該

樹有3片樹葉。

三、綜合題（共60分）

1.在自然推理系統(tǒng)中，構(gòu)造下面推理的證明。（6分）

如果王菲是理科生，那么她一定學(xué)過高等數(shù)學(xué)；如果她不是文科生，

她一定是理科生；她沒學(xué)過高等數(shù)學(xué)，所以她是文科生。

設(shè)P：王菲是理科生，q：王菲學(xué)過高等數(shù)學(xué)，r：王菲是文科生

前提：p-q，-1r^p,-＞q

結(jié)論：r

①

②前提引入

③前提引入

④①②拒取式

⑤前提引入

⑥③④拒取式

⑤置換

2.在命題邏輯中，構(gòu)造下面推理的證明：（8分）

前提：r）,qr（p/\7）,tf—r

結(jié)論：qfT

證明：①q附加前提

②qr（pMT）前提引入

(3)pA―iS①②假言推理

@p③化簡

⑤pf(-1<7Vr)前提引入

⑥—vr④⑤假言推理

⑦r①⑥析取三段論

⑧―前提引入

⑨T⑦⑧拒取式

3.求公式-9)v(。->〃)△r)的主析取范式、主合取范式，及該公式的成

假

賦值。(8分)

解：原式o-i(可vq)▽(—"「)△一)

=(p/\—>4)vr

o(pvr)A(—vr)

=((〃vr)vA—>q)A(〃A-ip)v(—vr))

<z>(pv^vr)A(pv—iqvr)A(pv—\qvr)v(~pv—\qvr)

=M()AM2AM2AM6

oE[(0,2,6)------------------------------主合取范式

02(1,3,4,5,7)------------------------------主析取范式

成假賦值：000,010,110

4.設(shè)集合A={a,b,c},R是A上的二元關(guān)系，已知R的關(guān)系矩陣為(8分)

'100'

M=011

011

(1)并畫出R的關(guān)系圖；

(2)求出IV的集合表達(dá)式；

(3)說明R具有哪些性質(zhì)。

解：(1)(略)

(2)R2={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}；

⑶自反性，對(duì)稱性，傳遞性

5.設(shè)5={1,2,3,6,12,18,36},設(shè)“W”為S上的整除關(guān)系。(8分)

問：(1)畫出偏序集〈S,的哈斯圖。

(2)在偏序集〈S,中，B={2,3,6}的極大元、極小元分別是什么？

(3)在偏序集＜S,W＞中，C={6,12,18}的最小上界、最大下界分別

是什么？

解：(1)哈斯圖：

(2)B={2,3,6}的極大元：6,極小元：2、3。

(3)C={6,12,18}的最小上界:36,最大下界：6。

6.設(shè)＜G,*＞是群。若在G上定義運(yùn)算?，使得對(duì)于Vx,yeG,有：x?y=y*xo

證明：〈G,?〉是群。(8分)

證明：(1)滿足封閉性。Vx,yeG,由于＜G,*＞是群,滿足封閉性，有:x?y=y*xeG。

(2)滿足結(jié)合律。由于＜G,*＞是群，滿足結(jié)合律，貝!!Vx,yfzeG,

(x?y)?z=(y*x)?z=z*(y*x)=z*y*x,

x?(y?z)=x?(z*y)=(z*y)*xy=z*y*x.

(3)設(shè)e是＜G,*＞的幺元，則VxeG,

x^e=e*x=x,e＞x=x*e=x

即e也是〈G,?〉的幺元。

（4）VxeG,設(shè)x在＜G,*＞中的逆元是y,則

x.y=y*x=e,y?x=x*y=e

即y也是〈G,?〉中x的逆元。

綜上所述，〈G,?〉是群。

7.已知有向圖G的鄰接矩陣如下：（8分）

010口匕

0011%

A=

010°匕

100山

問：（1）畫出圖Go

（2）試通過鄰接矩陣A求圖G中長度等于2的通路總數(shù)。

（3）試求圖G的可達(dá)性矩陣。

⑷該圖是否為強(qiáng)連通圖?

解：（1）（略）

（2）13條

（3）（略）

（4）是強(qiáng)連通圖

8.設(shè)圖G為八個(gè)頂點(diǎn)m條邊的連通平面圖，且每個(gè)面的次數(shù)至少為4,

證明：n?^2n-4o（6分）

證明：設(shè)棉數(shù)為f,根據(jù)歐拉公式和平面圖的握手定理：

n-m+f=2,

4代2叫

解之得：

人生像一截木頭，或者選擇慢慢腐朽，或者選擇熊熊燃燒。

試卷四

一'單項(xiàng)選擇題（每小題2分，共20分）:

1.下列選項(xiàng)中與人1^=人等價(jià)的是

A.AAB=AB.A—B=0C.AUB=BD.BcA

2.下列語句是命題的有（C）o

A.明年元旦會(huì)是晴天嗎？B.x+y>°；

C.孫>°當(dāng)且僅當(dāng)x和y都大于0；D.我正在說謊。

3.設(shè)5={1，，3},s上關(guān)系R的關(guān)系圖為

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

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

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

4.如圖，給出格L,則e的補(bǔ)元是［B］0

5.公式A=h（P（x）-Q（x））的解釋［為:個(gè)體域D={2},P（X）：X>3,Q（X）：X=4

則A的真值為（A）o

A.1；B.0；C.可滿足式；D.無法判定。

6.在下述公式中（C）為矛盾式

A.（尸入Q）f（PvQ）；B.-fQ》（Q-P））；

C.TPfQMQ；D.PfQQ）。

7.無向圖的關(guān)聯(lián)矩陣中，每列的元素之和為一Bo

A.邊數(shù)的2倍B.2C.該圖的頂點(diǎn)總數(shù)D.對(duì)應(yīng)頂點(diǎn)的度數(shù)

8.5階無向完全圖(％)不是以下哪種圖？—Co

A.歐拉圖B.簡單圖C.二部圖D.哈密頓圖

9.下面哪一種圖不是樹？C

A.無回路的連通圖B.有n個(gè)結(jié)點(diǎn)，n-l條邊的連通圖；

C.每對(duì)結(jié)點(diǎn)間都有初級(jí)通路的圖；D.連通但刪去一條邊則不連通的

圖。

10.5階無向完全圖心的邊數(shù)為(B)0

A.5B.10C.15D.20

填空題(每小題2分，共20分)

1.設(shè)P：我生病，Q：我去上課，命題“雖然我生病，但我還是去上課了”符

號(hào)化為PAQ。

2.R為實(shí)數(shù)集合，若，和g都是R-R的函數(shù)，且/(x)=x+l,g(x)=2x,則fog

(2)=-5—o

3.設(shè)集合A={a,b},B={a,c},則A?(B-A)={a,b,c}—。(十為對(duì)稱差)

4.若關(guān)系R={<1,2>,<2,1>},則其傳遞閉包t(R)為。

5.設(shè)A={a,b,c,d},A上的等價(jià)關(guān)系R={<a,c>,<c,a>}U以,則商集

A/R=Ha,c},,aioxv1z}o

6.公式*F(x,y)人一iVvG(v)的前束范式是孔加(F(x,z)人一iG(v))。

7.設(shè)M(x):x是人，F(xiàn)(x):x吃飯。在一階邏輯中，“沒有不吃飯的人”符號(hào)化形

式為Vx(M(x)-F(x))。

8.完全二部圖4,3是平面圖，它的平面嵌入共有—3_個(gè)面。

9.一個(gè)無向圖有4個(gè)結(jié)點(diǎn)，4條邊，其中的3個(gè)頂點(diǎn)度數(shù)分別為1,2,3,則

第4個(gè)結(jié)點(diǎn)度數(shù)一定是，

10.設(shè)$={1,2,3),S上定義的二元運(yùn)算*如表所示，S中關(guān)于*運(yùn)算的零元

是1。

*123

1111

2123

3132

2.證明等值式：Q-(PA(Q-P))OPV「Q,并求該命題公式的成真賦值。

證明：（略）

3.一棵樹T中，有3個(gè)2度結(jié)點(diǎn)，一個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)都是樹葉。

（1）T中有幾個(gè)結(jié)點(diǎn)；

（2）畫出具有上述度數(shù)的所有非同構(gòu)的無向圖。

解：（1）設(shè)有x個(gè)結(jié)點(diǎn)，則

3x2+3+（x-4）=2（x-l）,

解之得：x=7.

⑵（略）

4.在命題邏輯中符號(hào)化以下文字，并證明其推理是正確的：

“如果廠方拒絕給工人增加工資并且工廠不更換廠長，那么罷工就不會(huì)停止。

因此，如果罷工停止，則要么廠方給工人增加了工資，要么更換了廠長。”

5.設(shè)集合A={1,2,3,5,6,7,15,35},R為整除關(guān)系。

（1）畫出偏序集＜A,R＞的哈斯圖；

（2）寫出A的最大元，最小元；

（3）寫出A的子集B={1,3,5}的上界，下界。

解：（1）哈斯圖：

（2）最大元：無,最小元：1

（3）B={1,3,5}的上界:15,下界：1

’1000、

6.設(shè)有向圖G的鄰接矩陣為：1011

1001

、1000,

（1）畫出該圖;

（2）求該圖中長度為2的通路總數(shù)。

（3）該圖是為強(qiáng)連通圖還是單向連通圖？

（4）判斷該圖是否為歐拉圖？說明理由。

解：（1）（略）

（2）8；（3）單向連通圖；（4）不是。

7.設(shè)集合S=R—{-l}（R為實(shí)數(shù)集），a*b=a+b+ab。

（1）證明<S,*>是群；

（2）在S中解方程：x*4=5o

（略）

逆境能打敗弱者而造就強(qiáng)者。——尼克松

試卷五

一'單項(xiàng)選擇題（每題2分，共20分）

下列語句是命題的有

1.［B］0

A.請(qǐng)保持安靜！B.2011年元旦是星期六；

C.x2+y^0；D.今天是星期五嗎？

下面哪個(gè)命題公式是矛盾式

2.［D］o

A.（pfq）八（qfr）；B.pf（qfp）；

C.（—ipx/q）A—1（〃A—;D.—i（p\/q）Ap。

下列二元關(guān)系中，不具有傳遞性的二元關(guān)系是

3.［C］0

A.{<a,b>}B.{<a,a>,<a,b>,<b,a>,<b,b>}

C.{<a,b>,<b,c>}D.{<a,b>,<a,a>}

4.若人=國力通},則下列集合中，［A］不是A的劃分。

A.{①,{a},{b,c}}B.{{a},{b,c}}

C.{{a},,{c}}D.{{a,b},{c}}

是自然數(shù)集，定義廳則函數(shù)，是［

5.Nf:NfN（x）=x,C］o

A.滿射非單射；B.單射非滿射；

C.雙射；D.非單射非滿射

6.下面集合［C］關(guān)于加法運(yùn)算不是封閉的。

A.Z(整數(shù)集合)；B.{2x|XGZ}C.{2X+1|XGZ}D.{0}

7.設(shè)R是實(shí)數(shù)集合，“+”為普通乘法，則<R,+>［B］o

A.是群；B.是獨(dú)異點(diǎn)，不是群；

C.是半群，不是獨(dú)異點(diǎn)；D.是代數(shù)系統(tǒng)，不是半群

8.下列四組數(shù)據(jù)中，不能成為任何圖的度數(shù)序列的為［C］o

A.1,1,1,3B.2,2,3,3

C.1,2,2,2D.1,2,3,4

9.無向圖的關(guān)聯(lián)矩陣中，每列的元素之和為［B］。

二'填空題(每題2分，共20分)

1.設(shè)Hx)：x是人；G(x)：x會(huì)犯錯(cuò)誤，則在謂詞邏輯中，命題”所有的人

都會(huì)犯錯(cuò)誤”謂詞符號(hào)化為o

2.設(shè)解釋I如下，個(gè)體域D={1,2},P(x)：x=l,Q(x)：x=2,在解釋I下，

公式

VxP(x)->3x(2(x)的真值為o

3.謂詞公式3xP(x,y)AV%2(x)的前束范式為*Vz(P(x,y)AQ(Z))_。

4.若4=中,8={。,?}},則B—A=,

5.若A={a,b,c},A上的等價(jià)關(guān)系R={<a,b>,<b,a>}UlA,則A在等價(jià)關(guān)系R

下的商集A/R=Ha,b},{cH

6.若Z為整數(shù)集合，+為普通加法，代數(shù)系統(tǒng)<Z,+>中，則Z關(guān)于+的塞

等元有0。

7.設(shè)A={a,b,c},A上二元運(yùn)算*如下:

則代數(shù)系統(tǒng)＜A,*＞的零元為b

8.設(shè)G={0,1,2,3},十4為模4加法,§PVx,yeG,x?4y=（x+y）mod4,則＜G,

十廣為循環(huán)群。該循環(huán)群中，元素2的階為一2_o

9.n個(gè)結(jié)點(diǎn)的無向完全圖K?的邊數(shù)為若3___________。

10.若無向樹T有1個(gè)3度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，其余結(jié)點(diǎn)均為樹葉，則該

樹有3片樹葉。

三、綜合題（共60分）

1.在自然推理系統(tǒng)中，構(gòu)造下面推理的證明。（6分）

如果今天天晴，那么我將去爬山；今天天晴，所以我將去爬山。

設(shè)P：今天天晴，q：我將去爬山，則

前提：pfq,p

結(jié)論:q

證明：①Pfq前提引入

②p前提引入

③q①②假言推理

2.在命題邏輯中，構(gòu)造下面推理的證明：（8分）

前提：pf-qvr）,qTp,rfs

結(jié)論：qTs

證明：①q附加前提引入

②qfp前提引入

自姓①②假言推理

④p->Jqvr)前提引入

⑤"r③④假言推理

⑥r(nóng)①⑤析取三段論

⑦，->s前提引入

⑧s⑥⑦假言推理

3.求公式->4)vr的主析取范式、主合取范式，及該公式的成假賦值。(8

分)

解：原式O-<「pvq)vr

=(p/\—1〃)\/廠

=(pvr)A(-iqvr)

=((pVr)VA—1鄉(xiāng))A(j9A—p)v(—vr))

^(pvqvr)/\(pv—iqvr)A(pv—\qvr)A(~pv—vr)

=MOAM2AM2AM6

=n(0,2,6)-----------------------------主合取范式

=E(1,3,4,5,7)----------------------------主析取范式

成假賦值：000,010,110

4.設(shè)集合A={a,b,c},R是A上的二元關(guān)系，已知R的關(guān)系矩陣為(8分)

100

M=001

011

(1)并畫出R的關(guān)系圖；

⑵求出R2的集合表達(dá)式；

(3)說明R具有哪些性質(zhì)。

解：⑴(略)

(2)R2={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}

⑶滿足：對(duì)稱性

5.設(shè)$={1,2,3,4,6,9),設(shè)"<”為S上的整除關(guān)系。(8分)

問：(1)畫出偏序集<S,的哈斯圖。

(2)在偏序集＜S,4＞中，B={2,3,6}的最大元、最小元分別是什么？

(3)在偏序集〈S,《＞中，C={1,2,3}的上界、下界分別是什么？

解：(1)哈斯圖:

4

2

1

(2)B={2,3,6}的最大元：6,最小元：無;

(3)C={1,2,3}的上界：6、9,下界：lo

6.設(shè)＜G,+＞是群。G為整數(shù)集合，+為普通加法運(yùn)算，證明：〈G,+〉是群。(8

分)

(略)

7.已知有向圖G的鄰接矩陣如下：(8分)

'01"％

A=110v2

01ojv3

問：⑴畫出圖Go

(2)試通過鄰接矩陣A求圖G中長度等于2的通路總數(shù)。

(3)試求圖G的可達(dá)性矩陣。

⑷該圖是否為強(qiáng)連通圖？

解：(1)(略)

'120'

(2)A2=121

110

長度為2的通路數(shù)：9

-111

(3)P=111

111

(4)強(qiáng)連通圖

8.圖G是一頂點(diǎn)數(shù)為6的簡單的連通的平面圖，有2個(gè)面的次數(shù)為4,其余

面的次數(shù)都為3,求平面圖G的邊數(shù)和面數(shù)。(6分)

解：設(shè)G的邊數(shù)為e,面數(shù)為f,則根據(jù)歐拉公式和握手定理，有：

6-e+f=2,

4x2+3(f-2)=2e

解上述方程式得：e=10,f=6,即圖G的邊數(shù)為10,面數(shù)為6。

能夠快樂地學(xué)習(xí)和工作，這是精神上優(yōu)秀的征兆。

試卷六

一、選擇題(每題2分，共20分)

1.下列句子為簡單命題的是[D]0

A.禁止吸煙！B.王紅既聰明又美麗。

C.我正在說謊。D.小王和小李是好朋友。

2.設(shè)D：全總個(gè)體域，F(xiàn)(x)：x是優(yōu)點(diǎn)，M(x)：x是人，H(x,y)：x有y,則命

題“每個(gè)人都有一些優(yōu)點(diǎn)。”的邏輯符號(hào)化為[C]o

A.Vx(M(x)A3y(F(y)->H(x,y))

B.Vx(M(x)t寺(尸(y)->H(x,y))

C.Vx(M(x)3y(F(y)AH(X,y))

D.3x(M(x)TVy(尸(y)AH(X,y))

3.下面命題公式是矛盾式的為[C]0

A.〈p/\q)7PB.「pvq

C.Tpfq)八qD.-q)

4.已知某班有35人，其中10人學(xué)習(xí)日語，20人學(xué)習(xí)英語，5人既學(xué)日語又學(xué)

英語，那么既不學(xué)日語也不學(xué)英語的人數(shù)是［B］。

A.5B.10C.15D.20

5.Z是整數(shù)集合，定義fZ"(x)=f,則函數(shù)￡是［C］。

A.滿射非單射B.單射非滿射

C.雙射