




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、歷年離散數(shù)學(xué)試卷選編(參考答案)目錄15101619242731試卷 試卷一 試卷三 試卷四 試卷五 式卷八 試卷七 試卷八讀書是掌握知識(shí)的捷徑,勤奮是開啟知識(shí)大門的鑰匙, 思考是理解知識(shí)的利器,練習(xí)是鞏固知識(shí)的方法, 討論是理解知識(shí)的妙招,探求是創(chuàng)新知識(shí)的途徑。試卷一一、單項(xiàng)選擇題(本大題共10小題,每小題2分,共20分)1 .下列不是命題的是C 。A. 7能被3整除.B. 5是素?cái)?shù)當(dāng)且僅當(dāng)太陽(yáng)從西邊升起.C. x力口 7小于0.D.華東交通大學(xué)位于南昌北區(qū).2 .設(shè)p:王平努力學(xué)習(xí),q:王平取得好成績(jī),命題 除非王平努力學(xué)習(xí),否則他不 能取得好成績(jī)”的符號(hào)化形式為D 。A. p-qB. -
2、p一 qCq一 pD. q一 p3 .下面4個(gè)推理定律中,不正確的為D 。A. A=>(AV B)附加律)B. (AV B)A -A=>B 所取三段論)C. (A一 B八A=>B假言推理) D. (A一 B八B=>A拒取式)4 .設(shè)解釋 I 如下,個(gè)體域 D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)q 1 在解釋 I 下,下 列公式中真值為1的是A 。A.-x yF(x,y)B.xyF(x,y)C. x-yF(x,y)D. - x yF(x,y)5 .下列四個(gè)命題中哪一個(gè)為真? D 。A. 0C0B.0 aC.0 C 0D.6 .設(shè) S=a,b,
3、c,d R=<a,a>,<b,b>,<d,d>則 R 的性質(zhì)是B 。A.自反、對(duì)稱、傳遞的B.對(duì)稱、反對(duì)稱、傳遞的C.自反、對(duì)稱、反對(duì)稱的D.只有對(duì)稱性7 .設(shè)人=口處,0則下列是集合A的劃分的是D 。A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c8 .設(shè)集合Q("2) =a *b'2a,b" Q)關(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 。A. P(A) B.小 C.
4、A D. E10 .下列四組數(shù)據(jù)中,不能成為任何 4階無(wú)向簡(jiǎn)單圖的度數(shù)序列的為C 。A. 2,2,2,2B. 1,1,1,3C. 1,1,2,3D. 1,2,2,3二、填空題(本題共10小題,每小題2分,共20分)1 .命題公式p-q的真值為假,當(dāng)且僅當(dāng) _p=1,q=0一2 .公式p一(q 一啦聯(lián)結(jié)詞全功能集,八,v中等值形式之一為zpxZqvro3 .謂詞公式 FxF(x) xG(x,勺前束范式為 -xmyrF(x戶G(y).4 .設(shè)集合 A = 1, 4, B = 2, 4,則 P (A) - P (B) = 1,1,4。5 . R是非空集合上的偏序關(guān)系,當(dāng)且僅當(dāng) R具有自反性、反對(duì)稱性
5、、傳遞性。6 .設(shè)函數(shù) f(x)=x + 1,g(x)=或 則 f o g =2X + 1。7 .設(shè)(7=(134)(25$) p =(25)(1643)貝Ur(1)(465)。8 .命題設(shè)G為任意的n階簡(jiǎn)單的哈密爾圖,則Vu,vC V(G),均有d(u)+d(v) > n" 的真值為_0_09 .無(wú)向連通圖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+1。三、證明下式(6X2=12分)1、判斷下面推理是否正確。如果你學(xué)習(xí),那么你離散數(shù)學(xué)不會(huì)不及格。如果你不熱衷于玩游戲,那么你將學(xué)習(xí)。但你離散數(shù)學(xué)不及格。因此
6、你熱衷于玩游戲。設(shè)p:你學(xué)習(xí),q:你離散數(shù)學(xué)及格,r:你熱衷于玩游戲,則前提:p-*q,I p,q結(jié)論:r證明:p-*q前提引入q前提引入p拒取式ip前提引入(r)拒取式r置換2、在一階謂詞邏輯中構(gòu)造下面推理的證明。前提:xF(x), x(F(x)V G(x) - H(x)結(jié)論:xH(x)證明:WF(x)前提引入F(a)三 Vx(F(x)V G(x) -H(x)前提引入F(a)V G(a) 一Ha)V-F(a)V G(a)附加H(a)假言推理WH(x)三十四、用等值演算法求公式(pV q)A (p-q)?(q p)的主合取范式與主析取范式。(10 分)解:原式 u(pV q)A (pV q)?
7、(qp)u(pAp) Vq)?(qp)u q?(q p)u (q(q-p)八(q-p) 一)U (qVLqVp) A(qVp) V q)u(qVp)A(qAp) V q)(一q V p)A q二 pA q(3) 主合取范式(0,1,2)主析取范式五、設(shè)Ri和2是集合X= 0,1 , 2,3,41的關(guān)系,Ri=<x , y>| y = 2x &=<x , y>| x= y + 1寫出Ri、R2 ,寫出R2的關(guān)系矩陣,并求出Ri欠2。(8分)解:Ri=<0,0>,<1,2>,<2,4>, R,=<1,0>,<1,
8、2>,<2,3>,<3,4>,R2的關(guān)系矩陣:(略)R1 R=<x , y>| y = 2(x-1) 六、設(shè)集合A=2,3,4,6,8,12,24, R為A上的整除關(guān)系,(1)畫出偏序集<A, R>哈斯圖;(2)出集合A中的最大元、最小元、極大元、極小元;(3)寫出A的子集B=2,3,6,12»勺上界、下界、最小上界、最大下界。(8分)解:(1)哈斯圖:A中的最大元:24,最小元:無(wú),極大元:24,極小元:2、3B=2,3,6,12勺上界:12、24,下界:無(wú),最小上界:12,最大下界:無(wú)七、設(shè)Z為整數(shù)集合,在Z上定義二元運(yùn)算*,
9、 Vx,yCZ有x* y = x + y - 2。證明:<z, *>是一個(gè)群。(1。分)證明:顯然,二元運(yùn)算*滿足交換律。(1)封閉性:vx,yez,顯然 x* y = x + y2ez。(2)結(jié)合律:-x,y,zC乙(x*y)*z=(x+y-2)*z=x+y-2+z-2=x+y+z-4x*(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è) eCZ, Vx Z,使得 x*e=x,即 x+e-2=x, e=2 故幺元 e=2.(4) Vx 乙設(shè) yCZ,使得 x*y=e,即 x+y-2=2, y=4-x,故
10、 x-1=4-x。綜上所述,<Z, *>是一個(gè)群。八、平面圖G有兩個(gè)連通分支,其頂點(diǎn)數(shù)為12,邊數(shù)為34,問G有多少個(gè)面?(6分)解:設(shè)有x個(gè)面,根據(jù)歐拉公式:12-34+x=2+1,即 x=25所以,G有25個(gè)面。九、對(duì)下圖,(1)求其鄰接矩陣;(2)(2)長(zhǎng)度小于3的通路和回路的總數(shù)。(6分)V2v3v5解題思路:先寫出鄰接矩陣 A,然后求A2,則矩陣A+A2中元素之和,即為長(zhǎng)度 小于3的通路條數(shù)【10條】;而A+A2對(duì)角線上元素之和,即為長(zhǎng)度小于 3的回路條數(shù)【0條】。大學(xué)是一個(gè)人的“精神賬戶",你一輩子都要不斷回來(lái)"提款"的。> X、八-
11、試卷一一、單項(xiàng)選擇題(2分X 10=20分)1、下列語(yǔ)句是命題的有B 。A. x2+2y>1 ;B. 2010年的國(guó)慶節(jié)是晴天;C.青年學(xué)生多么朝氣蓬勃呀! D.學(xué)生不準(zhǔn)吸煙!2中在命題邏輯中,任何命題公式的主合取范式都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 .與命題p A(pVq)等值的公式是A 。A. p;B. q;C. pV q;D. p
12、A q.5 .設(shè) M=a,b,c, M 上的等價(jià)關(guān)系 R=<a,a>,<b,b>,<c,c>,<b,c>,<c,b>t的集合M的劃分是D 。A.a,b,cB.a,c,b,c C.a,c,b D.a,b,c H(x,y): x 喜歡 y。6 .設(shè)D:全總個(gè)體域,F(xiàn) (x): x是花,M(x) : x是人, 則命題“每個(gè)人都喜歡某種花”的邏輯符號(hào)化為CA. Vx(M(x)八三y(F(y)T H(x,y);B. -x(M(x)T 三y(F(y)T H (x, y);C. Vx(M(x)t 3y(F(y)AH(x,y);D. x(M(x) y
13、(F(y) H(x,y).8.下列四組數(shù)據(jù)中,能作為某個(gè) 4階無(wú)向簡(jiǎn)單圖的度序列的為D 。A. 1,2,3,4; B. 2,2,2,3 C. 1,1,2,3D. 1,1,1,3.9. 一棵無(wú)向樹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)成格ABCD二、填空題(2分X 10=20分)1 .當(dāng)p=0,q=0時(shí),命題公式p一 (pA q)的真值為1。2 .設(shè)p:我努力學(xué)習(xí),q:我取得好成績(jī),命題“除非我努力學(xué)習(xí),否則我不能 取得好成績(jī)。”的符號(hào)化形式為 qz±p o3 .設(shè)解釋 I
14、如下,個(gè)體域 D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1ft解釋 I 下, 5xF(x,2)的真侑為1。4 .謂詞公式 3xF(x)A次G(x)的前束范式為三xmy( F(x)A G(y)。5 .設(shè)樹T有n個(gè)頂點(diǎn),m條邊,則T中n與m的關(guān)系為m=n-1。6 .等價(jià)關(guān)系滿足自反性、對(duì)稱性和傳涕性 三個(gè)性質(zhì)。7 .設(shè)函數(shù) f(x)=2x, g(x)= x2+1,貝U f o g = 2x2+_2_ 08 .無(wú)向連通圖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中的幺元
15、為名 o三、綜合題(第1、2、4題10分,第3、5、7每題8分,第6題6分,共60 分)前提:p-(qvr),A F 結(jié)論:q.證明:p -sp-s一A 一r一r p-(qvr)q rq1 .構(gòu)造下面推理的證明:(10分) p -s;前提引入化簡(jiǎn)化簡(jiǎn)前提引入假言推理前提引入假言推理析取三段論2 .用等值演算求下面公式 A的主析取范式和主合取范式,并列出A的成真賦值:(10 分)A=(p-q) (qr)解:A=(p-q) A(qr)=(P q) Tq r)三 (P q) (r r) (p _p) (_q r)三(p q r) (-p q -r) (p -q r) (p -q r)t M4 M5
16、M 2 M6二:(2,4,5,6)比合取范式=% (0,1,3,7)主析取范式A 的成真賦值:000, 001, 011,1113 .設(shè)集合A=a, b, c, d上的二元關(guān)系R=<a , b > ,< 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 &g
17、t; ,< 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,令中,B=4,6的上確界、下確界是什么?解:(1)哈斯圖:(2) S , '的極小元:1,最小元:1,極大元:8、
18、12,最大元:無(wú)(3) B=4,6的上確界:12,下確界:25 .已知某有向圖G的鄰接矩陣如下:(8分)v1 '1 2 1 0、A 芋 0010 v3 0 1 0 1 v4 k0010 j問:(1)畫出圖Go(2)試用鄰接矩陣求G中長(zhǎng)度小于等于2的通路的條數(shù),其中回路有 幾條?(3)該圖是為強(qiáng)連通圖還是弱連通圖?解:(1)(略)(2)長(zhǎng)度小于等于2的通路的條數(shù):22,其中回路數(shù):5.(3)弱連通圖。6 .設(shè)集合G=3nnwZ(其中:丸是普通乘法,Z是整數(shù)集),對(duì)代數(shù)系統(tǒng)G,說明:(1)是否滿足封閉性、結(jié)合律? ( 2)是否存在幺元? ( 3)是否構(gòu)成群?(6 分)解:(1)滿足封閉性。
19、Vm,nZ, 3mM 3n=3m+nC 乙滿足結(jié)合律:/m,n,kC Z, (3嗎 3n) x 3k=3mx (3nM 3k )=3m+n+k。(2)幺元為30=1。(3)由于 V nZ, (3n) -1=3-n,綜合(1) (2)知,G,M構(gòu)成群。7.圖G是一個(gè)簡(jiǎn)單的連通平面圖,其無(wú)限面的度數(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(f-1)=2e, 解上述方程得:e=16,f=10 。所以,平面圖G的邊數(shù)為16,面數(shù)為10。世上無(wú)難事,只要肯登攀。毛澤東試卷三單項(xiàng)選擇題(每題2分,共2
20、0分)1,下列語(yǔ)句是命題的有B 。A.請(qǐng)保持安靜!C. x<6;2 .下面哪個(gè)命題公式是重言式 A (P-> q)n(qT r);C. (p vq) L(p Aq);B. 2019年元旦是星期六;D.今天是星期五嗎?B 。B P-* (q-* p);D. _|( p v q) a p oA. <a,b>C. <a,b>, <b,c>4.若A=a,b,c則下列集合中,A. :',a,b,cC. a,b,cB. <a,b>, <b,a>D. <a,a>, <a,b>, <b,a> C
21、 是人的劃分。B. a,b,b,cD. a,b3 .下列二元關(guān)系中,具有傳遞性的二元關(guān)系是 A 5. N是自然數(shù)集,定義f :NtN, f (x) = xmod3 (即x除以3的余數(shù)),則函數(shù)£是D A.滿射非單射;B,單射非滿射;C,雙射;D,非單射非滿射6 .下面集合C 關(guān)于減法運(yùn)算不是封閉的。A. Z;B, 2x x ZC, 2x+1 x Z D. 07 .設(shè)R是實(shí)數(shù)集合,“父”為普通乘法,則<R, X> B 0A.是群;B.是獨(dú)異點(diǎn),不是群;C,是半群,不是獨(dú)異點(diǎn);D,是代數(shù)系統(tǒng),不是半群8.下圖中既不是Eular圖,也不是漢密爾頓圖的是B BC)(D9 .如左下
22、圖,相對(duì)于5階無(wú)向完全圖K的補(bǔ)圖為。本題圖錯(cuò)誤兇BK皿10.給定無(wú)向圖G=<V,E>,下面哪個(gè)頂點(diǎn)子集是圖 G的點(diǎn)割集A A. I);B.L); C. I' D. J5、填空題(每題2分,共20分)1 .設(shè)F(x): x是人;G(x): x會(huì)犯錯(cuò)誤,則在謂詞邏輯中,命題“沒有不犯 錯(cuò)誤的人”謂詞符號(hào)化為mx(M(x)aG(x)更Vx(M(x)t G(x)。2 .設(shè)解釋I如下,個(gè)體域D=1, 2, P(x) : x=1, Q(x): x=2,在解釋I下, 公式三xP(x)t VxQ(x)的真值為003 .謂詞公式 *P(x)t VxQ(x, y)的前束范式為 _ VxVz(P
23、(x)t Q(z,y)。4 .若人=中=現(xiàn)代,則BP(A) =粵。5 .若 A=a,b,c,d A上的等價(jià)關(guān)系 R=<a,b>, <b,a>, <c,d>, <d,c>U Ia,則 A在等價(jià)關(guān)系R下的商集A/R = _a,b,c.d_6 .若Z為整數(shù)集合,“x”為普通乘法,代數(shù)系統(tǒng) <乙”中,則Z關(guān)于“父” 運(yùn)算的幕等元有 _QL 。7 .設(shè)A=a, b, c , A上二元運(yùn)算*如下:o則代數(shù)系統(tǒng)A, *中,8 .設(shè) G=0,1,2,3,出4為模 4 加法,即 Vx,y三G, x©4y = (x+y) mod 4,貝U<G
24、,4 為循環(huán)群,該循環(huán)群的生成元為1, 3 Q9 . n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn為歐拉圖的條件是n為奇數(shù)10 .若無(wú)向樹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,r-p,q結(jié)論:r證明:p-q飛-pF-pCr)r前提引入 前提引入 拒取式 前提引入 拒取式 置換2 .在命題邏輯中,構(gòu)造下面推理的證明:(8分)前
25、提:p ,q r), q (p -s), t 一r結(jié)論:q- 't證明:q q (p s)前提引入附加前提p - sp p - (-q r)-q rr t - -r-t假言推理化簡(jiǎn)前提引入假言推理析取三段論前提引入拒取式3 .求公式 飛pT q) v(q-»)八)的主析取范式、主合取范式,及該公式的成 假賦值。(8分)解:原式二一(p q) (q r) r)=(p q) r=(p r) (一q r)= (p r) (q -q) (p -p) Cq r):二(p q r) (p q r) (p _q r) (_p -q r) 二 M0?M2?M2?M6(0,2,6)比合取范式=
26、% (1,3,4,5,7)-主析取范式成假賦值:000,010,1104 .設(shè)集合A=a, b, c , R是A上的二元關(guān)系,已知R的關(guān)系矩陣為 (8分)1 0 0M = 0 1 10 1k(1)并畫出R的關(guān)系圖;(2)求出R2的集合表達(dá)式;(3)說明R具有哪些性質(zhì)。解:(1)(略)(2)=<1,1>,<2,2>,<3,3>,<2,3>,<3,2吊(3)自反性,對(duì)稱性,傳遞性5.設(shè)5=1, 2, 3, 6, 12, 18, 36,設(shè) 為 S 上的整除關(guān)系。(8 分) 問:(1)畫出偏序集S, 0的哈斯圖。(2)在偏序集$, W中,B=2,
27、3, 6的極大元、極小元分別是什么? (3)在偏序集$, W中,C=6, 12, 18的最小上界、最大下界分別是什么?解:(1)哈斯圖:(2) B=2, 3, 6的極大元:6,極小元:2、3。C=6, 12, 18的最小上界:36,最大下界:66.設(shè)G, *是群。若在G上定義運(yùn)算,使得對(duì)于Vx, y=G,有:x產(chǎn)y*x 證明:G, 是群。(8分)證明:(1)滿足封閉性。Vx,yWG,由于G,*是群,滿足封閉性,有:x*y=y*xEG。(2)滿足結(jié)合律。由于G, *是群,滿足結(jié)合律,則Vx, y, zG,(x。) z= (y * x) =z* (y * x) =z*y * x,x . (y *z
28、) =x , (z * y) =(z*y )* x) =z*y * x.(3) 設(shè)e是G, *的幺元,貝U VxG,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分)0 1 0 1vl0 0 1 1 v2A =0 1 0 0 v3_1 0 0 11v4問:(1)畫出圖Go(2)試通過鄰接矩陣A求圖G中長(zhǎng)度等于2的通路總數(shù) (3)試求圖G的可達(dá)性矩陣。(4)該圖是否為強(qiáng)連通圖?解:(1)(略)(2) 13
29、條(略)(4)是強(qiáng)連通圖8 .設(shè)圖G為n個(gè)頂點(diǎn)m條邊的連通平面圖,且每個(gè)面的次數(shù)至少為4,證明:m0 2n-4。(6 分)證明:設(shè)棉數(shù)為f,根據(jù)歐拉公式和平面圖的握手定理:n-m+f=2,4f 2m,解之得:m0 2n-4。人生像一截木頭,或者選擇慢慢腐朽,或者選擇熊熊燃燒。試卷四、單項(xiàng)選擇題(每小題2分,共20分):1.卜列選項(xiàng)中與AU B=A等價(jià)的是(_D_)_。A. AH B=AB, A B =C.AU B=B D BA2.卜列語(yǔ)句是命題的有(3.4.5.A.明年元旦會(huì)是晴天嗎?C. xy >0當(dāng)且僅當(dāng)x和y都大于0;設(shè)S = 1,2,3 , S上關(guān)系R的關(guān)系圖為D.我正在說謊。則
30、R具有(D )性質(zhì)。A.自反性、對(duì)稱性、傳遞性;C.反自反性、反對(duì)稱性、傳遞性;如圖,給出格L則e的補(bǔ)元是B 0A.B.C.D.a;f;b;公式A = (P(X)T Q(x)的解釋則A的真值為(A )0A. 1; B. 0;C.可滿足式;6.在下述公式中(B.反自反性、反對(duì)稱性;D.自反性bda為:個(gè)體域 D=2, P(x): x>3, Q(x): x=4D.無(wú)法判定。)為矛盾式A (P Q) >(P Q).B (P- Q卜(P > Q) (Q > P).口?C -(P,Q) Q .D. " ("Q)。7. 無(wú)向圖的關(guān)聯(lián)矩陣中,每列的元素之和為B 。
31、A.邊數(shù)的2倍 B. 2C.該圖的頂點(diǎn)總數(shù) D.對(duì)應(yīng)頂點(diǎn)的度數(shù)8. 5階無(wú)向完全圖(Ks)不是以下哪種圖? C。A.歐拉圖 B,簡(jiǎn)單圖 C.二部圖 D.哈密頓圖9. 下面哪一種圖不是樹?CA.無(wú)回路的連通圖B.有n個(gè)結(jié)點(diǎn),n 1條邊的連通圖;C.每對(duì)結(jié)點(diǎn)間都有初級(jí)通路的圖;D.連通但刪去一條邊則不連通的圖。10. 5階無(wú)向完全圖Ks的邊數(shù)為(B )。A. 5 B .10 C .15 D .20填空題(每小題2分,共20分)1 .設(shè)P:我生病,Q:我去上課, 命題“雖然我生病,但我還是去上課了”符 號(hào)化為fq。2 . R為實(shí)數(shù)集合,若f和g都是R一R的函數(shù),且f(x)=x+1, g(x)=2x,
32、則fog (2)=5 o3 .設(shè)集合 A= a, b, B=a, c則 A© (B A) =a, b,c (© 為對(duì)稱差)4 .若關(guān)系 R=<1,2>, <2,1>則其傳遞閉包 t(R)為 /<1,2>, <2,1>,<1,1><2,2>_5 .設(shè) A = a, b, c, d A上的等價(jià)關(guān)系 R= <a, c>, <c, a> Ia,則商集A/R= _/a.c.b.d_6 .公式三x F(x, y)"厚yG(y)的前束范式是 :x三y (F(x, zbG(y)。7 .
33、設(shè)M(x): x是人,F(xiàn)(x): x吃飯。在一階邏輯中,“沒有不吃飯的人”符號(hào)化形式為 與 x(M(x) -F(x)。8,完全二部圖K2,3是平面圖,它的平面嵌入共有 3_個(gè)面。9 . 一個(gè)無(wú)向圖有4個(gè)結(jié)點(diǎn),4條邊,其中的3個(gè)頂點(diǎn)度數(shù)分別為1, 2, 3,則 第4個(gè)結(jié)點(diǎn)度數(shù)一定是_2_010 .設(shè)S =1,2, 3 , S上定義的二元運(yùn)算*如表所示,S中關(guān)于好運(yùn)算的零元 是 1 0*1231112123313212 .證明等值式:Q一(PA (Q-P) u P VQ,并求該命題公式的成真賦值。證明:(略)3 . 一棵樹T中,有3個(gè)2度結(jié)點(diǎn),一個(gè)3度結(jié)點(diǎn),其余結(jié)點(diǎn)都是樹葉(1) T中有幾個(gè)結(jié)點(diǎn);
34、(2)畫出具有上述度數(shù)的所有非同構(gòu)的無(wú)向圖。解:(1)設(shè)有x個(gè)結(jié)點(diǎn),則3 2+3+(x-4)=2(x-1),解之得: x=7.(2)(略)4 .在命題邏輯中符號(hào)化以下文字,并證明其推理是正確的:“如果廠方拒絕給工人增加工資并且工廠不更換廠長(zhǎng),那么罷工就不會(huì)停止因此,如果罷工停止,則要么廠方給工人增加了工資,要么更換了廠長(zhǎng)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)最大元:無(wú),最小元:1(3) B = 1,3,5勺上界:15,下界
35、:110 0 06.設(shè)有向圖G的鄰接矩陣為:10 1110 0 11 0 0 0(1)畫出該圖;(2)求該圖中長(zhǎng)度為2的通路總數(shù)。(3)該圖是為強(qiáng)連通圖還是單向連通圖?(4)判斷該圖是否為歐拉圖?說明理由。解:(1)(略)(2) 8 ;(3)單向連通圖;(4)不是。7.設(shè)集合 S = R- _ 1(R為實(shí)數(shù)集),a*b=a + b + abo(1)證明<S, *址群;(2)在S中解方程:x*4=5。(略)逆境能打敗弱者而造就強(qiáng)者。-尼克松試卷五單項(xiàng)選擇題(每題2分,共20分)1,下列語(yǔ)句是命題的有B 。A.請(qǐng)保持安靜!C. x2+y< 0;2.下面哪個(gè)命題公式是矛盾式DA. (p-
36、> q)八(qT r);1 . pvq)L(pLq);3 .下列二元關(guān)系中,不具有傳遞性的二元關(guān)系是A. <a,b>C. <a,b>, <b,c>4 .若A=a,b,c1則下列集合中,A. :',a,b,cC. a,b,c5. N是自然數(shù)集,定義f :NtA.滿射非單射;B. 2011年元旦是星期六;D.今天是星期五嗎?。B. p-* (q-* p);D. _,(p v q) a p 0C oB. <a,a>, <a,b>, <b,a>, <b,b>D. <a,b>, <a,a&
37、gt;A 不是A的劃分。B. a,b,cD. a,b,cN, f(x) = x ,則函數(shù) £是C 0B,單射非滿射;C.雙射;D.非單射非滿射6.下面集合C 關(guān)于加法運(yùn)算不是封閉的。A. Z(整數(shù)集合);B. 2x|xeZC. 2x+1|xeZD. 07.設(shè)R是實(shí)數(shù)集合,“+”為普通乘法,則<R, +> B 。A.是群;B.是獨(dú)異點(diǎn),不是群;C,是半群,不是獨(dú)異點(diǎn);D,是代數(shù)系統(tǒng),不是半群8,下列四組數(shù)據(jù)中,不能成為任何圖的度數(shù)序列的為C 。A. 1,1,1,3B. 2,2,3,3C. 1,2,2,2D. 1,2,3,49 .無(wú)向圖的關(guān)聯(lián)矩陣中,每列的元素之和為B 。A.
38、邊數(shù)的2倍 B. 2 C.頂點(diǎn)數(shù) D,頂點(diǎn)的度數(shù)10 .在如下各圖中,B 是歐拉圖。二、填空題(每題2分,共20分)1 .設(shè)F(x): x是人;G(x): x會(huì)犯錯(cuò)誤,則在謂詞邏輯中,命題”所有的人都會(huì)犯錯(cuò)誤”謂詞符號(hào)化為。2 .設(shè)解釋I如下,個(gè)體域D=1, 2, P(x) : x=1, Q(x): x=2,在解釋I下, 公式VxP(x)T三xQ(x)的真值為。3 .謂詞公式三xP(x, y)八VxQ(x)的前束范式為 三xz(P(x, y)八Q(z)一。4 .若 A=S,B=現(xiàn)代,則 BA =。5 .若A=a,b,c A上的等價(jià)關(guān)系R=<a,b>, <b,a>U Ia
39、,則A在等價(jià)關(guān)系R 下的商集 A/R= a,b,cA 6 .若Z為整數(shù)集合,+為普通加法,代數(shù)系統(tǒng) <乙+>中,則Z關(guān)于+的幕 等元有一0 。7 .設(shè)A=a, b, c , A上二元運(yùn)算*如下:*a b cabcabcbbbcba則代數(shù)系統(tǒng)A, *的零元為b 。8 .設(shè) G=0,1,2,3, 中4為模 4 加法,即Vx,ywG, x©4y = (x+y) mod 4,貝UG , ©4為循環(huán)群。該循環(huán)群中,元素2的階為 2 o9 . n個(gè)結(jié)點(diǎn)的無(wú)向完全圖 Kn的邊數(shù)為。10 .若無(wú)向樹T有1個(gè)3度結(jié)點(diǎn),2個(gè)2度結(jié)點(diǎn),其余結(jié)點(diǎn)均為樹葉,則該 樹有 3 片樹葉。三、綜
40、合題(共60分)1 .在自然推理系統(tǒng)中,構(gòu)造下面推理的證明。(6分)如果今天天晴,那么我將去爬山;今天天晴,所以我將去爬山。設(shè)p:今天天晴,q:我將去爬山,則前提:p-q, p結(jié)論:q證明:p-*q前提引入p前提引入q假言推理2 .在命題邏輯中,構(gòu)造下面推理的證明:(8分)前提:p (-q r), q- p, r - s結(jié)論:q- s證明:q附加前提引入qT p前提引入p假言推理pT (飛”前提引入-q rrr , ss假言推理析取三段論前提引入假言推理3 .求公式(pT q)Mr的主析取范式、主合取范式,及該公式的成假賦值。(8分)解:原式u -(-p q) r=(p q) r=(p r)
41、(q r)二 (p r) (q -q) (p -p) (-q r):二(p q r) (p q r) (p -q r) (_p _q r)= M0?M2?M2?M6:二:(0,2,6)-主合取范式:=' (1,3,4,5,7)注析取范式成假賦值:000,010,110(8分)4 .設(shè)集合A=a, b, c , R是A上的二元關(guān)系,已知R的關(guān)系矩陣為1 0 0M = 0 0 1:。1 1 _(1)并畫出R的關(guān)系圖;(2)求出R2的集合表達(dá)式;(3)說明R具有哪些性質(zhì)。解:(1)(略)(2)R2=<1,1>,<2,2>,<3,3>,<2,3>
42、,<3,2>(3)滿足:對(duì)稱性 5.設(shè)5=1, 2, 3, 4, 6, 9,設(shè)為S上的整除關(guān)系。(8分)問:(1)畫出偏序集<S, 0>的哈斯圖(2)在偏序集$, &中,B=2, 3, 6的最大元、最小元分別是什么?(3)在偏序集$, W中,C=1, 2, 3的上界、下界分別是什么?解:(1)哈斯圖:11(2) B=2, 3, 6的最大元:(3) C=1, 2, 3的上界:6、6 .設(shè)G, 十址群。G為整數(shù)集合, 分)(略)7 .已知后向圖G的鄰接矩陣如下一0 1 11vlA= 1 1 0v2-0 1 0_v3問:(1)畫出圖Go(2)試通過鄰接矩陣A求(3)試
43、求圖G的可達(dá)性矩F(4)該圖是否為強(qiáng)連通圖?解:(1)(略)一1 2 0 ,一、2(2) A = 1 2 11 1 0 _696,最小元:無(wú);9,下界:1。+為普通加法運(yùn)算,證明:G, +是群。(8:(8 分)圖G中長(zhǎng)度等于2的通路總數(shù)。車。長(zhǎng)度為2的通路數(shù):91 1 1(3) P = 1 1 111 1 一(4)強(qiáng)連通圖8.圖G是一頂點(diǎn)數(shù)為6的簡(jiǎn)單的連通的平面圖,有 2個(gè)面的次數(shù)為4,其余面的次數(shù)都為3,求平面圖G的邊數(shù)和面數(shù)。(6分)解:設(shè)G的邊數(shù)為e,面數(shù)為f,則根據(jù)歐拉公式和握手定理,有:6-e+f=2, 4 2+3 (f-2) =2e解上述方程式得:e=10, f=6,即圖G的邊數(shù)為
44、10,面數(shù)為6。能夠快樂地學(xué)習(xí)和工作,這是精神上優(yōu)秀的征兆。試卷六一、選擇題(每題2分,共20分)1 .下列句子為簡(jiǎn)單命題的是D 。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 oA. -x(M(x) y(F(y) > H(x, y)B. -x(M(x) > y(F(y) > H (x, y)C. -x(M (x) , y(F(y) H(x, y)D. x(M(x) > -y(F(y) H (x,
45、y)3 .下面命題公式是矛盾式的為C 。A. (p")vpb.pqC. 一(p,q) q(p q) (p 一 q)4.已知某班有35人,其中10人學(xué)習(xí)日語(yǔ),20人學(xué)習(xí)英語(yǔ),5人既學(xué)日語(yǔ)又學(xué) 英語(yǔ),那么既不學(xué)日語(yǔ)也不學(xué)英語(yǔ)的人數(shù)是 B 。A. 5 B .10 C . 15 D . 20 5. Z是整數(shù)集合,定義f :Zt Z, f (x) = -x,則函數(shù)f是CA.滿射非單射B.單射非滿射C.雙射D.非單射非滿射6 .設(shè)Q是有理數(shù)集合, A.封閉性C.存在幺元* ”為普通乘法,則代數(shù)系統(tǒng)<Q, *>不滿足的是B.可結(jié)合性D. Q中每個(gè)元素都存在逆元7 . <Z6,出&
46、gt;為循環(huán)群,其中Z6=0,1,2,3,4,5, ©為模6加法,該群中元素2的階為C。A. 1B. 2C. 3D.8 .下列四組數(shù)據(jù)中,不能成為無(wú)向簡(jiǎn)單圖的度數(shù)序列的是AA. 2,3,3,4B. 3,3,3,3C. 0,1,2,1D. 1,2,2,19 . 4階無(wú)向完全圖(K4)是以下哪種圖? B 。A.歐拉圖 B .平面圖 C .多重圖 D .10 .圖G如右圖所示,則G的補(bǔ)圖為C 。二、填空題(每題2分,共20分)1 .公式三xP(x) -Q(x,y)的前束范式為mx(P(x) -Q(z,y)。2 .設(shè)解釋I如下,個(gè)體域D=a, b, P(x) : x=a, Q(x): x=b
47、。在解釋I下,公式Vx(P(x) vQ(x)的直俏為 1。3 .設(shè)集合 A= a,b,c, B=b,c則 A B = a。4 .設(shè)集合 A=a,b,c,d,e A上的等價(jià)關(guān)系 R= <a, b>,<b, a>,<d, e>,<e, d> U Ia, 則商集 A/R= a,b,c,d,e。5 .給定人=1,2,3,4±的二元關(guān)系 R=<1,2>,<2,1>,<2,3>,<4,4弓R的對(duì)稱閉包 s(R= <1,2>,<2,1>,<2,3>,<3,2>,
48、<4,4>。6 .若半群<G,。>含有 幺元 ,則稱半群<6, 口 >為獨(dú)異點(diǎn)。7 .若Z為整數(shù)集合,*為普通乘法,代數(shù)系統(tǒng)<Z,*>中,Z關(guān)于*的零元為 0。8 .無(wú)向連通圖G是歐拉圖當(dāng)且僅當(dāng)所有點(diǎn)的度數(shù)均為偶數(shù)。9 .設(shè)一個(gè)無(wú)向連通圖G有10個(gè)頂點(diǎn)15條邊,則圖G的任意一棵生成樹的總邊 數(shù)為9條。10 .連通的簡(jiǎn)單平面圖G有6個(gè)頂點(diǎn),有5個(gè)面,則圖G有 9 條邊。三、綜合題(每題10分,共60分)1 .求命題公式(r -* p)八q的主析取范式、主合取范式及該公式的成真賦值。解:原式:=(r p) q=(q r) (p q)u(qr) (p
49、p) (pq)(r r)u(Pq r) p q r)(pqr) (pq -r)= m7?m3?m6(3,6,7 ) 主析取范式二口(0,1,2,4,5 ) 主合取范式成真賦值:011,110,1112 .在自然推理系統(tǒng)中,構(gòu)造下面推理的證明。前提:如果今天天氣好,那么我去逛街或者去圖書館看書;如果圖書館關(guān)門, 那么我就沒去圖書館看書;今天天氣好并且圖書館關(guān)門。結(jié)論:所以我去逛街了。設(shè)p:今天天氣好。q:我去逛街。r:我去圖書館看書。s:圖書館關(guān) 門。正確符號(hào)化前提和結(jié)論并證明推理的有效性。前提:p > (q ?r),s一 r,p ?s結(jié)論:q證明:p?s前提引入p化簡(jiǎn)s化簡(jiǎn)尸(q ?r)
50、前提引入q?r假言推理STrr前提引入r假言推理q析取三段論3 .設(shè) A=1,2,3,4,有一個(gè) A上的劃分 S= 1, 2, 3, 4, 求:(1)寫出由劃分S確定的等價(jià)關(guān)系R的集合表達(dá)式。(2)證明關(guān)系R是等價(jià)關(guān)系。(3)寫出R2的關(guān)系矩陣。解:(1) R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>(2)說明滿足等價(jià)關(guān)系的條件:自反性、對(duì)稱性、傳遞性(略)4、設(shè)集合 A=1 , 2,3問:(1)寫出集合A的募集P(A)。(2)畫出偏序集P(A)三的哈斯圖。其中,工為P(A)上的包含關(guān)系。(3
51、)在偏序集P(A)£中,B= 1 , 2, 1,2 的最大元和下確界是什么?解:(1) P(A)丑?,1,2,3,1,2,1,3,2,3,1,2,3(略)(3)最大元:1,2,下確界:?。5 .設(shè)集合G =3n |nw Z(其中:乂是普通乘法,Z是整數(shù)集),問集合G 和乘法運(yùn)算煞能否構(gòu)成交換群?并進(jìn)行驗(yàn)證。(略)6 .已知有向圖G的鄰接矩陣如下:0 10 0vl0 10 1v2 A =2 0 0 1 v3-0 0 0 1 _v4問:(1)畫出圖Go(2)通過鄰接矩陣A求圖G中長(zhǎng)度為2的通路總數(shù)。(3)該圖是否為強(qiáng)連通圖?說明理由。解:(1)(略)(2) 9 條(3)不是強(qiáng)連通圖人心就
52、像容器,裝的學(xué)習(xí)多了,空虛就少了試卷七一、選擇題(每題2分,共20分)1 .下列句子是命題的是D 。A.禁止吸煙!B.你帶了衣服嗎?C. 2x+38。D.小紅是大學(xué)生。2,對(duì)于公式Vx(F(x, y)T 3yH (x, y) aG(x, z),下列說法正確的是C .x是約束變?cè)?Vx的轄域是F(x, y)B 。.矛盾式A. y是自由變?cè)狟C. z是自由變?cè)狣3 .命題公式(pT 4)八4的類型是A.重言式BC.非永真的可滿足式D .等價(jià)式4 . A= a, b, c上的二元關(guān)系如下所示,具有傳遞性的是A 。A. <a,a>B. <b,c>,<a,b>C. &
53、lt;a,b>,<b,a> D . <b,a>, <a,c>, <c,b>5 .集合 1, 0, 1上的A 運(yùn)算為二元運(yùn)算(滿足封閉性)。A.乘法B.除法C.加法D.減法6 . P(S足非空有限集合S的募集,則代數(shù)系統(tǒng)<P(S> U>中的零元是B 。A. P(S) B . S C . D . 7 .代數(shù)系統(tǒng)<G, +>中,+是普通加法,以下選項(xiàng)B 不是群。A. G為有理數(shù)集合B . G為自然數(shù)集合C. G為整數(shù)集合D . G為實(shí)數(shù)集合8 .無(wú)環(huán)有向圖的關(guān)聯(lián)矩陣中,每行中 1的個(gè)數(shù)是C oA.邊數(shù)的2倍B.相關(guān)頂點(diǎn)的度C.相關(guān)頂點(diǎn)的出度D .相關(guān)頂點(diǎn)的入度9 . 6階無(wú)向完全圖的邊數(shù)為A 。A. 15 B .30 C .0 D .1010.有向圖的度數(shù)序列為(6,5,4,4,3),入度序列為(2,3,1,4,2),則以下選項(xiàng)C 是正確的出度序列。A. (2,3,1,4,2)B. (6,5,4,4,3)C. (4,1,3,1,1)D. (3,3,3,0,2)二、填空題
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 《課間活動(dòng)》(教案)2024-2025學(xué)年數(shù)學(xué)二年級(jí)上冊(cè)
- 2025年美容院會(huì)員協(xié)議模板
- 學(xué)習(xí)2025年雷鋒精神六十二周年主題活動(dòng)方案 合計(jì)3份
- 2025年青海省安全員A證考試題庫(kù)
- 《游山西村》歷年中考古詩(shī)欣賞試題匯編(截至2024年)
- 全國(guó)河大音像版初中信息技術(shù)七年級(jí)下冊(cè)第一章第二節(jié)《文字素材的采集》教學(xué)設(shè)計(jì)
- 歷史-云南省師范大學(xué)附屬中學(xué)2025屆高三下學(xué)期開學(xué)考試試題和答案
- 2025年??谑袉握新殬I(yè)適應(yīng)性測(cè)試題庫(kù)附答案
- 2025年度兒童游樂場(chǎng)主題包裝與品牌推廣合作協(xié)議書
- 2025年度個(gè)人公司資金走賬專項(xiàng)管理合同協(xié)議
- 腸內(nèi)營(yíng)養(yǎng)考評(píng)標(biāo)準(zhǔn)終
- Mysql 8.0 OCP 1Z0-908 CN-total認(rèn)證備考題庫(kù)(含答案)
- 三年級(jí)下冊(cè)音樂教學(xué)計(jì)劃含教學(xué)進(jìn)度安排活動(dòng)設(shè)計(jì)word表格版
- STEM教學(xué)設(shè)計(jì)與實(shí)施PPT完整全套教學(xué)課件
- 門窗加工制作合同
- 項(xiàng)目邊坡護(hù)坡工程施工組織設(shè)計(jì)
- 2023年全國(guó)各省高考詩(shī)歌鑒賞真題匯總及解析
- 四年級(jí)上冊(cè)音樂《楊柳青》課件PPT
- 安徽省廬陽(yáng)區(qū)小升初語(yǔ)文試卷含答案
- 全國(guó)2017年4月自考00043經(jīng)濟(jì)法概論(財(cái)經(jīng)類)試題及答案
- 蘇教版六年級(jí)數(shù)學(xué)下冊(cè)《解決問題的策略2》優(yōu)質(zhì)教案
評(píng)論
0/150
提交評(píng)論