華東交通大學歷年離散數(shù)學試卷選編(參考答案)

1、歷年離散數(shù)學試卷選編（參考答案）目錄15101619242731試卷 試卷一 試卷三 試卷四 試卷五 式卷八 試卷七 試卷八讀書是掌握知識的捷徑，勤奮是開啟知識大門的鑰匙, 思考是理解知識的利器，練習是鞏固知識的方法， 討論是理解知識的妙招，探求是創(chuàng)新知識的途徑。試卷一一、單項選擇題（本大題共10小題，每小題2分，共20分）1 .下列不是命題的是C 。A. 7能被3整除.B. 5是素數(shù)當且僅當太陽從西邊升起.C. x力口 7小于0.D.華東交通大學位于南昌北區(qū).2 .設p:王平努力學習，q:王平取得好成績，命題 除非王平努力學習，否則他不 能取得好成績”的符號化形式為D 。A. p-qB. -

2、p一 qCq一 pD. q一 p3 .下面4個推理定律中，不正確的為D 。A. A=>(AV B)附加律)B. (AV B)A -A=>B 所取三段論)C. (A一 B八A=>B假言推理) D. (A一 B八B=>A拒取式)4 .設解釋 I 如下，個體域 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 .下列四個命題中哪一個為真？ D 。A. 0C0B.0 aC.0 C 0D.6 .設 S=a,b,

3、c,d R=<a,a>,<b,b>,<d,d>則 R 的性質(zhì)是B 。A.自反、對稱、傳遞的B.對稱、反對稱、傳遞的C.自反、對稱、反對稱的D.只有對稱性7 .設人=口處,0則下列是集合A的劃分的是D 。A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c8 .設集合Q("2) =a *b'2a,b" Q)關于普通數(shù)的乘法，不正確的有C 。A.結合律成立B.有幺元C.任意元素有逆元D.交換律成立9 .設A是非空集合，P(A) A的募集，n是集合交運算，則代數(shù)系統(tǒng)P(A),n 的幺元是C 。A. P(A) B.小 C.

4、A D. E10 .下列四組數(shù)據(jù)中，不能成為任何 4階無向簡單圖的度數(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的真值為假，當且僅當 _p=1,q=0一2 .公式p一(q 一啦聯(lián)結詞全功能集，八，v中等值形式之一為zpxZqvro3 .謂詞公式 FxF(x) xG(x,勺前束范式為 -xmyrF(x戶G(y).4 .設集合 A = 1, 4, B = 2, 4,則 P (A) - P (B) = 1,1,4。5 . R是非空集合上的偏序關系，當且僅當 R具有自反性、反對稱性

5、、傳遞性。6 .設函數(shù) f(x)=x + 1,g(x)=或 則 f o g =2X + 1。7 .設(7=(134)(25$) p =(25)(1643)貝Ur(1)(465)。8 .命題設G為任意的n階簡單的哈密爾圖，則Vu,vC V(G),均有d(u)+d(v) > n" 的真值為_0_09 .無向連通圖G是歐拉圖，當且僅當G中每一個頂點的度數(shù)都為偶數(shù)。10 .設樹T有m個頂點，n條邊，則T中頂點與邊的關系為 m=n+1。三、證明下式(6X2=12分)1、判斷下面推理是否正確。如果你學習，那么你離散數(shù)學不會不及格。如果你不熱衷于玩游戲，那么你將學習。但你離散數(shù)學不及格。因此

6、你熱衷于玩游戲。設p:你學習，q:你離散數(shù)學及格，r:你熱衷于玩游戲，則前提：p-*q,I p,q結論：r證明：p-*q前提引入q前提引入p拒取式ip前提引入(r)拒取式r置換2、在一階謂詞邏輯中構造下面推理的證明。前提：xF(x), x(F(x)V G(x) - H(x)結論：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)主析取范式五、設Ri和2是集合X= 0,1 , 2,3,41的關系，Ri=<x , y>| y = 2x &=<x , y>| x= y + 1寫出Ri、R2 ,寫出R2的關系矩陣，并求出Ri欠2。(8分)解：Ri=<0,0>,<1,2>,<2,4>, R,=<1,0>,<1,

8、2>,<2,3>,<3,4>,R2的關系矩陣：(略)R1 R=<x , y>| y = 2(x-1) 六、設集合A=2,3,4,6,8,12,24, R為A上的整除關系，(1)畫出偏序集<A, R>哈斯圖；(2)出集合A中的最大元、最小元、極大元、極小元；(3)寫出A的子集B=2,3,6,12»勺上界、下界、最小上界、最大下界。(8分)解：(1)哈斯圖：A中的最大元：24,最小元：無，極大元：24,極小元：2、3B=2,3,6,12勺上界：12、24,下界：無,最小上界：12,最大下界：無七、設Z為整數(shù)集合，在Z上定義二元運算*,

9、 Vx,yCZ有x* y = x + y - 2。證明：<z, *>是一個群。(1。分)證明：顯然，二元運算*滿足交換律。(1)封閉性：vx,yez,顯然 x* y = x + y2ez。(2)結合律：-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)故二元運算*滿足結合律。(3)設 eCZ, Vx Z,使得 x*e=x,即 x+e-2=x, e=2 故幺元 e=2.(4) Vx 乙設 yCZ,使得 x*y=e,即 x+y-2=2, y=4-x,故

10、 x-1=4-x。綜上所述，<Z, *>是一個群。八、平面圖G有兩個連通分支，其頂點數(shù)為12,邊數(shù)為34,問G有多少個面?(6分)解：設有x個面，根據(jù)歐拉公式：12-34+x=2+1,即 x=25所以，G有25個面。九、對下圖，(1)求其鄰接矩陣；(2)(2)長度小于3的通路和回路的總數(shù)。(6分)V2v3v5解題思路：先寫出鄰接矩陣 A,然后求A2,則矩陣A+A2中元素之和，即為長度 小于3的通路條數(shù)【10條】；而A+A2對角線上元素之和，即為長度小于 3的回路條數(shù)【0條】。大學是一個人的“精神賬戶"，你一輩子都要不斷回來"提款"的。> X、八-

11、試卷一一、單項選擇題(2分X 10=20分)1、下列語句是命題的有B 。A. x2+2y>1 ;B. 2010年的國慶節(jié)是晴天;C.青年學生多么朝氣蓬勃呀！ D.學生不準吸煙！2中在命題邏輯中，任何命題公式的主合取范式都A.不一定存在；B.不存在；C.存在且唯一 ；D.存在但不唯一.3、設 S=1,2,3,4 R=<1,1>,<3,3>,<4,4>則 R滿足的性質(zhì)是C A.自反、對稱、傳遞的； B.自反、對稱、反對稱的；C.對稱、反對稱、傳遞的； D.只有對稱性.4 .與命題p A(pVq)等值的公式是A 。A. p；B. q；C. pV q；D. p

12、A q.5 .設 M=a,b,c, M 上的等價關系 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 .設D:全總個體域，F(xiàn) (x): x是花，M(x) : x是人, 則命題“每個人都喜歡某種花”的邏輯符號化為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ù)中，能作為某個 4階無向簡單圖的度序列的為D 。A. 1,2,3,4; B. 2,2,2,3 C. 1,1,2,3D. 1,1,1,3.9. 一棵無向樹T有8個頂點，4度、3度、2度的分枝點各1個，其余頂點 均為樹葉，則T中有C 片樹葉。A. 3;B. 4;C. 5;D. 6.10.下面偏序集B 能構成格ABCD二、填空題(2分X 10=20分)1 .當p=0,q=0時，命題公式p一 (pA q)的真值為1。2 .設p:我努力學習，q:我取得好成績，命題“除非我努力學習，否則我不能 取得好成績。”的符號化形式為 qz±p o3 .設解釋 I

14、如下，個體域 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 .設樹T有n個頂點，m條邊，則T中n與m的關系為m=n-1。6 .等價關系滿足自反性、對稱性和傳涕性 三個性質(zhì)。7 .設函數(shù) f(x)=2x, g(x)= x2+1,貝U f o g = 2x2+_2_ 08 .無向連通圖G是歐拉圖，當且僅當G中每一個頂點的度數(shù)都為 偶數(shù)。9 .設|A|=3 ,則A上有29個二元關系。10 .設A為非空有限集，則代數(shù)系統(tǒng)P(A),U中的幺元

15、為名 o三、綜合題(第1、2、4題10分，第3、5、7每題8分，第6題6分，共60 分)前提：p-(qvr),A F 結論：q.證明：p -sp-s一A 一r一r p-(qvr)q rq1 .構造下面推理的證明：(10分) p -s；前提引入化簡化簡前提引入假言推理前提引入假言推理析取三段論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 .設集合A=a, b, c, d上的二元關系R=<a , b > ,< b , a > ,< b, c > , < c , d >求：(1)指出關系R滿足的性質(zhì)；(2)求出R的自反閉包、對稱閉包。(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 的對稱閉包：s(R)= <a , b > ,< b , a > ,< b, c > , <c,b>,< c , d >,<d,c>4 .設5=1 , 2,3,4, 6,8,12為 S 上的整除關系。(10 分)問：(1)偏序集S ,仝的Hass圖如何？(2)偏序集S，令的極小元、最小元、極大元、最大元是什么 ？(3)在偏序集S，令中，B=4,6的上確界、下確界是什么？解：(1)哈斯圖：(2) S , '的極小元：1,最小元：1,極大元：8、

18、12,最大元：無(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中長度小于等于2的通路的條數(shù)，其中回路有 幾條？（3）該圖是為強連通圖還是弱連通圖？解：（1）（略）（2）長度小于等于2的通路的條數(shù)：22,其中回路數(shù)：5.（3）弱連通圖。6 .設集合G=3nnwZ（其中：丸是普通乘法，Z是整數(shù)集），對代數(shù)系統(tǒng)G,說明：（1）是否滿足封閉性、結合律？ （ 2）是否存在幺元？ （ 3）是否構成群？（6 分）解：（1）滿足封閉性。

19、Vm,nZ, 3mM 3n=3m+nC 乙滿足結合律：/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構成群。7.圖G是一個簡單的連通平面圖，其無限面的度數(shù)為5,其余面都為三角形，結點為8 ,請通過計算求平面圖 G的邊數(shù)和面數(shù)。（8分）解：設平面圖G的邊數(shù)和面數(shù)分別為：e、f,則8-e+f=2,5+3（f-1）=2e, 解上述方程得：e=16,f=10 。所以，平面圖G的邊數(shù)為16,面數(shù)為10。世上無難事，只要肯登攀。毛澤東試卷三單項選擇題（每題2分，共2

20、0分）1,下列語句是命題的有B 。A.請保持安靜！C. x<6;2 .下面哪個命題公式是重言式 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 .下列二元關系中，具有傳遞性的二元關系是 A 5. N是自然數(shù)集，定義f :NtN, f （x） = xmod3 （即x除以3的余數(shù)），則函數(shù)£是D A.滿射非單射；B,單射非滿射；C,雙射；D,非單射非滿射6 .下面集合C 關于減法運算不是封閉的。A. Z;B, 2x x ZC, 2x+1 x Z D. 07 .設R是實數(shù)集合，“父”為普通乘法，則<R, X> B 0A.是群；B.是獨異點，不是群；C,是半群，不是獨異點；D,是代數(shù)系統(tǒng)，不是半群8.下圖中既不是Eular圖，也不是漢密爾頓圖的是B BC)(D9 .如左下

22、圖，相對于5階無向完全圖K的補圖為。本題圖錯誤兇BK皿10.給定無向圖G=<V，E>,下面哪個頂點子集是圖 G的點割集A A. I）；B.L）； C. I' D. J5、填空題(每題2分，共20分)1 .設F(x): x是人；G(x): x會犯錯誤，則在謂詞邏輯中，命題“沒有不犯 錯誤的人”謂詞符號化為mx(M(x)aG(x)更Vx(M(x)t G(x)。2 .設解釋I如下，個體域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上的等價關系 R=<a,b>, <b,a>, <c,d>, <d,c>U Ia,則 A在等價關系R下的商集A/R = _a,b,c.d_6 .若Z為整數(shù)集合，“x”為普通乘法，代數(shù)系統(tǒng) <乙”中，則Z關于“父” 運算的幕等元有 _QL 。7 .設A=a, b, c , A上二元運算*如下：o則代數(shù)系統(tǒng)A, *中,8 .設 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個結點的無向完全圖Kn為歐拉圖的條件是n為奇數(shù)10 .若無向樹T有1個3度結點，3個2度結點，其余結點都是樹葉，則該 樹有 3 片樹葉。三、綜合題（共60分）1 .在自然推理系統(tǒng)中，構造下面推理的證明。（6分）如果王菲是理科生，那么她一定學過高等數(shù)學；如果她不是文科生, 她一定是理科生；她沒學過高等數(shù)學，所以她是文科生。設p：王菲是理科生，q：王菲學過高等數(shù)學，r：王菲是文科生前提：p-q,r-p,q結論：r證明：p-q飛-pF-pCr)r前提引入 前提引入 拒取式 前提引入 拒取式 置換2 .在命題邏輯中，構造下面推理的證明：（8分）前

25、提：p ，q r）, q （p -s）, t 一r結論：q- 't證明：q q (p s)前提引入附加前提p - sp p - (-q r)-q rr t - -r-t假言推理化簡前提引入假言推理析取三段論前提引入拒取式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 .設集合A=a, b, c , R是A上的二元關系，已知R的關系矩陣為 (8分)1 0 0M = 0 1 10 1k(1)并畫出R的關系圖；(2)求出R2的集合表達式；(3)說明R具有哪些性質(zhì)。解：(1)(略)(2)=<1,1>,<2,2>,<3,3>,<2,3>,<3,2吊(3)自反性，對稱性，傳遞性5.設5=1, 2, 3, 6, 12, 18, 36,設 為 S 上的整除關系。(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.設G, *是群。若在G上定義運算,使得對于Vx, y=G,有：x產(chǎn)y*x 證明：G, 是群。(8分)證明：(1)滿足封閉性。Vx,yWG,由于G,*是群，滿足封閉性，有：x*y=y*xEG。(2)滿足結合律。由于G, *是群，滿足結合律，則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) 設e是G, *的幺元，貝U VxG,x*e=e*x=x, e *x=x*e =x即e也是G, 的幺元(4) vxeG,設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中長度等于2的通路總數(shù) (3)試求圖G的可達性矩陣。(4)該圖是否為強連通圖?解：(1)(略)(2) 13

29、條(略)(4)是強連通圖8 .設圖G為n個頂點m條邊的連通平面圖，且每個面的次數(shù)至少為4,證明：m0 2n-4。(6 分)證明：設棉數(shù)為f,根據(jù)歐拉公式和平面圖的握手定理：n-m+f=2,4f 2m,解之得：m0 2n-4。人生像一截木頭，或者選擇慢慢腐朽，或者選擇熊熊燃燒。試卷四、單項選擇題（每小題2分，共20分）:1.卜列選項中與AU B=A等價的是（_D_）_。A. AH B=AB, A B =C.AU B=B D BA2.卜列語句是命題的有（3.4.5.A.明年元旦會是晴天嗎?C. xy >0當且僅當x和y都大于0;設S = 1，2,3 , S上關系R的關系圖為D.我正在說謊。則

30、R具有（D ）性質(zhì)。A.自反性、對稱性、傳遞性;C.反自反性、反對稱性、傳遞性;如圖，給出格L則e的補元是B 0A.B.C.D.a；f；b；公式A = （P（X）T Q（x）的解釋則A的真值為（A )0A. 1; B. 0;C.可滿足式;6.在下述公式中（B.反自反性、反對稱性;D.自反性bda為：個體域 D=2, P(x): x>3, Q(x): x=4D.無法判定。）為矛盾式A (P Q) >(P Q).B (P- Q卜(P > Q) (Q > P).口?C -(P，Q) Q .D. " ("Q)。7. 無向圖的關聯(lián)矩陣中，每列的元素之和為B 。

31、A.邊數(shù)的2倍 B. 2C.該圖的頂點總數(shù) D.對應頂點的度數(shù)8. 5階無向完全圖(Ks)不是以下哪種圖？ C。A.歐拉圖 B,簡單圖 C.二部圖 D.哈密頓圖9. 下面哪一種圖不是樹？CA.無回路的連通圖B.有n個結點，n 1條邊的連通圖；C.每對結點間都有初級通路的圖；D.連通但刪去一條邊則不連通的圖。10. 5階無向完全圖Ks的邊數(shù)為(B )。A. 5 B .10 C .15 D .20填空題(每小題2分，共20分)1 .設P：我生病，Q：我去上課， 命題“雖然我生病，但我還是去上課了”符 號化為fq。2 . R為實數(shù)集合，若f和g都是R一R的函數(shù)，且f(x)=x+1, g(x)=2x,

32、則fog (2)=5 o3 .設集合 A= a, b, B=a, c則 A© (B A) =a, b,c (© 為對稱差)4 .若關系 R=<1,2>, <2,1>則其傳遞閉包 t(R)為 /<1,2>, <2,1>,<1,1><2,2>_5 .設 A = a, b, c, d A上的等價關系 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、設M(x): x是人，F(xiàn)(x): x吃飯。在一階邏輯中，“沒有不吃飯的人”符號化形式為 與 x(M(x) -F(x)。8,完全二部圖K2,3是平面圖，它的平面嵌入共有 3_個面。9 . 一個無向圖有4個結點，4條邊，其中的3個頂點度數(shù)分別為1, 2, 3,則 第4個結點度數(shù)一定是_2_010 .設S =1,2, 3 , S上定義的二元運算*如表所示，S中關于好運算的零元 是 1 0*1231112123313212 .證明等值式：Q一(PA (Q-P) u P VQ,并求該命題公式的成真賦值。證明：(略)3 . 一棵樹T中，有3個2度結點,一個3度結點,其余結點都是樹葉(1) T中有幾個結點；

34、(2)畫出具有上述度數(shù)的所有非同構的無向圖。解：(1)設有x個結點，則3 2+3+(x-4)=2(x-1),解之得： x=7.(2)(略)4 .在命題邏輯中符號化以下文字，并證明其推理是正確的：“如果廠方拒絕給工人增加工資并且工廠不更換廠長，那么罷工就不會停止因此，如果罷工停止，則要么廠方給工人增加了工資，要么更換了廠長5 .設集合A= 1, 2, 3, 5, 6,7,15,35 R為整除關系(1)畫出偏序集A, R勺哈斯圖；(2)寫出A的最大元，最小元；(3)寫出A的子集B = 1,3,5勺上界，下界。解：(1)哈斯圖：(2)最大元：無，最小元：1(3) B = 1,3,5勺上界：15,下界

35、：110 0 06.設有向圖G的鄰接矩陣為:10 1110 0 11 0 0 0(1)畫出該圖;(2)求該圖中長度為2的通路總數(shù)。(3)該圖是為強連通圖還是單向連通圖？(4)判斷該圖是否為歐拉圖？說明理由。解：(1)(略)(2) 8 ;(3)單向連通圖；(4)不是。7.設集合 S = R- _ 1(R為實數(shù)集)，a*b=a + b + abo(1)證明<S, *址群；(2)在S中解方程：x*4=5。(略)逆境能打敗弱者而造就強者。-尼克松試卷五單項選擇題(每題2分，共20分)1,下列語句是命題的有B 。A.請保持安靜！C. x2+y< 0;2.下面哪個命題公式是矛盾式DA. (p-

36、> q)八(qT r)；1 . pvq)L(pLq);3 .下列二元關系中，不具有傳遞性的二元關系是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 關于加法運算不是封閉的。A. Z(整數(shù)集合)；B. 2x|xeZC. 2x+1|xeZD. 07.設R是實數(shù)集合，“+”為普通乘法，則<R, +> B 。A.是群；B.是獨異點，不是群；C,是半群，不是獨異點；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 .無向圖的關聯(lián)矩陣中，每列的元素之和為B 。A.

38、邊數(shù)的2倍 B. 2 C.頂點數(shù) D,頂點的度數(shù)10 .在如下各圖中，B 是歐拉圖。二、填空題(每題2分，共20分)1 .設F(x): x是人；G(x): x會犯錯誤，則在謂詞邏輯中，命題”所有的人都會犯錯誤”謂詞符號化為。2 .設解釋I如下，個體域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上的等價關系R=<a,b>, <b,a>U Ia

39、,則A在等價關系R 下的商集 A/R= a,b,cA 6 .若Z為整數(shù)集合，+為普通加法，代數(shù)系統(tǒng) <乙+>中，則Z關于+的幕 等元有一0 。7 .設A=a, b, c , A上二元運算*如下:*a b cabcabcbbbcba則代數(shù)系統(tǒng)A, *的零元為b 。8 .設 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個結點的無向完全圖 Kn的邊數(shù)為。10 .若無向樹T有1個3度結點，2個2度結點，其余結點均為樹葉，則該 樹有 3 片樹葉。三、綜

40、合題（共60分）1 .在自然推理系統(tǒng)中，構造下面推理的證明。（6分）如果今天天晴，那么我將去爬山；今天天晴，所以我將去爬山。設p：今天天晴，q：我將去爬山，則前提：p-q, p結論：q證明：p-*q前提引入p前提引入q假言推理2 .在命題邏輯中，構造下面推理的證明：（8分）前提：p （-q r）, q- p, r - s結論：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 .設集合A=a, b, c , R是A上的二元關系，已知R的關系矩陣為1 0 0M = 0 0 1：。1 1 _(1)并畫出R的關系圖；(2)求出R2的集合表達式；(3)說明R具有哪些性質(zhì)。解：(1)(略)(2)R2=<1,1>,<2,2>,<3,3>,<2,3>

42、,<3,2>(3)滿足：對稱性 5.設5=1, 2, 3, 4, 6, 9,設為S上的整除關系。(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 .設G, 十址群。G為整數(shù)集合， 分)(略)7 .已知后向圖G的鄰接矩陣如下一0 1 11vlA= 1 1 0v2-0 1 0_v3問：(1)畫出圖Go(2)試通過鄰接矩陣A求(3)試

43、求圖G的可達性矩F(4)該圖是否為強連通圖？解：(1)(略)一1 2 0 ，一、2(2) A = 1 2 11 1 0 _696,最小元：無；9,下界：1。+為普通加法運算，證明：G, +是群。(8:(8 分)圖G中長度等于2的通路總數(shù)。車。長度為2的通路數(shù)：91 1 1(3) P = 1 1 111 1 一(4)強連通圖8.圖G是一頂點數(shù)為6的簡單的連通的平面圖，有 2個面的次數(shù)為4,其余面的次數(shù)都為3,求平面圖G的邊數(shù)和面數(shù)。(6分)解：設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。能夠快樂地學習和工作，這是精神上優(yōu)秀的征兆。試卷六一、選擇題(每題2分，共20分)1 .下列句子為簡單命題的是D 。A.禁止吸煙！B.王紅既聰明又美麗。C.我正在說謊。D.小王和小李是好朋友。2 .設D:全總個體域，F(xiàn)(x): x是優(yōu)點，M(x) : x是人，H(x,y): x有y ,則命 題“每個人都有一些優(yōu)點?！钡倪壿嫹柣癁镃 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人學習日語，20人學習英語，5人既學日語又學 英語，那么既不學日語也不學英語的人數(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 .設Q是有理數(shù)集合, A.封閉性C.存在幺元* ”為普通乘法，則代數(shù)系統(tǒng)<Q, *>不滿足的是B.可結合性D. Q中每個元素都存在逆元7 . <Z6,出&

46、gt;為循環(huán)群，其中Z6=0,1,2,3,4,5, ©為模6加法，該群中元素2的階為C。A. 1B. 2C. 3D.8 .下列四組數(shù)據(jù)中，不能成為無向簡單圖的度數(shù)序列的是AA. 2,3,3,4B. 3,3,3,3C. 0,1,2,1D. 1,2,2,19 . 4階無向完全圖(K4)是以下哪種圖？ B 。A.歐拉圖 B .平面圖 C .多重圖 D .10 .圖G如右圖所示，則G的補圖為C 。二、填空題(每題2分，共20分)1 .公式三xP(x) -Q(x,y)的前束范式為mx(P(x) -Q(z,y)。2 .設解釋I如下，個體域D=a, b, P(x) : x=a, Q(x): x=b

47、。在解釋I下，公式Vx(P(x) vQ(x)的直俏為 1。3 .設集合 A= a,b,c, B=b,c則 A B = a。4 .設集合 A=a,b,c,d,e A上的等價關系 R= <a, b>,<b, a>,<d, e>,<e, d> U Ia, 則商集 A/R= a,b,c,d,e。5 .給定人=1,2,3,4±的二元關系 R=<1,2>,<2,1>,<2,3>,<4,4弓R的對稱閉包 s(R= <1,2>,<2,1>,<2,3>,<3,2>,

48、<4,4>。6 .若半群<G,。>含有 幺元 ，則稱半群<6, 口 >為獨異點。7 .若Z為整數(shù)集合,*為普通乘法，代數(shù)系統(tǒng)<Z,*>中，Z關于*的零元為 0。8 .無向連通圖G是歐拉圖當且僅當所有點的度數(shù)均為偶數(shù)。9 .設一個無向連通圖G有10個頂點15條邊，則圖G的任意一棵生成樹的總邊 數(shù)為9條。10 .連通的簡單平面圖G有6個頂點，有5個面，則圖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)中，構造下面推理的證明。前提：如果今天天氣好，那么我去逛街或者去圖書館看書；如果圖書館關門， 那么我就沒去圖書館看書；今天天氣好并且圖書館關門。結論：所以我去逛街了。設p：今天天氣好。q：我去逛街。r：我去圖書館看書。s：圖書館關 門。正確符號化前提和結論并證明推理的有效性。前提：p > (q ?r),s一 r,p ?s結論：q證明：p?s前提引入p化簡s化簡尸(q ?r)

50、前提引入q?r假言推理STrr前提引入r假言推理q析取三段論3 .設 A=1,2,3,4,有一個 A上的劃分 S= 1, 2, 3, 4, 求：(1)寫出由劃分S確定的等價關系R的集合表達式。(2)證明關系R是等價關系。(3)寫出R2的關系矩陣。解：(1) R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>(2)說明滿足等價關系的條件：自反性、對稱性、傳遞性(略)4、設集合 A=1 , 2,3問：(1)寫出集合A的募集P(A)。(2)畫出偏序集P(A)三的哈斯圖。其中，工為P(A)上的包含關系。(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 .設集合G =3n |nw Z(其中：乂是普通乘法，Z是整數(shù)集)，問集合G 和乘法運算煞能否構成交換群？并進行驗證。(略)6 .已知有向圖G的鄰接矩陣如下：0 10 0vl0 10 1v2 A =2 0 0 1 v3-0 0 0 1 _v4問：(1)畫出圖Go(2)通過鄰接矩陣A求圖G中長度為2的通路總數(shù)。(3)該圖是否為強連通圖？說明理由。解：(1)(略)(2) 9 條(3)不是強連通圖人心就

52、像容器，裝的學習多了，空虛就少了試卷七一、選擇題(每題2分，共20分)1 .下列句子是命題的是D 。A.禁止吸煙！B.你帶了衣服嗎?C. 2x+38。D.小紅是大學生。2,對于公式Vx(F(x, y)T 3yH (x, y) aG(x, z),下列說法正確的是C .x是約束變元.Vx的轄域是F(x, y)B 。.矛盾式A. y是自由變元BC. z是自由變元D3 .命題公式(pT 4)八4的類型是A.重言式BC.非永真的可滿足式D .等價式4 . A= a, b, c上的二元關系如下所示，具有傳遞性的是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 運算為二元運算(滿足封閉性)。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, +>中，+是普通加法，以下選項B 不是群。A. G為有理數(shù)集合B . G為自然數(shù)集合C. G為整數(shù)集合D . G為實數(shù)集合8 .無環(huán)有向圖的關聯(lián)矩陣中，每行中 1的個數(shù)是C oA.邊數(shù)的2倍B.相關頂點的度C.相關頂點的出度D .相關頂點的入度9 . 6階無向完全圖的邊數(shù)為A 。A. 15 B .30 C .0 D .1010.有向圖的度數(shù)序列為(6,5,4,4,3),入度序列為(2,3,1,4,2),則以下選項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)二、填空題