離散數(shù)學(xué)作業(yè)

1、離散數(shù)學(xué)標(biāo)準(zhǔn)化作業(yè)紙 專業(yè)班級(jí) 學(xué)號(hào) 姓名 第一章 命題邏輯的基本概念一、判斷下列語(yǔ)句是否是命題，若是命題是復(fù)合命題則請(qǐng)將其符號(hào)化（1）中國(guó)有四大發(fā)明。（2）2是有理數(shù)。（3）“請(qǐng)進(jìn)！”（4）劉紅和魏新是同學(xué)。（5）a+b（6）你去圖書館嗎？（7）如果買不到飛機(jī)票，我哪兒也不去。（8）侈而惰者貧，而力而儉者富。（韓非：韓非子·顯學(xué)）（9）火星上有生命。（10）這朵玫瑰花多美麗?。《?、將下列命題符號(hào)化，其中p:2<1,q:3<2（1）只要2<1，就有3<2。（2）如果2<1，則3³2。（3）只有2<1，才有3³2。（4）除非2&l

2、t;1，才有3³2。（5）除非2<1，否則3³2。（6）2<1僅當(dāng)3<2。三、將下列命題符號(hào)化(1)小麗只能從筐里拿一個(gè)蘋果或一個(gè)梨。(2)王棟生于1992年或1993年。四、設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p(qr) （2）（pr）(qs) （3）（pqr）(pqr) (4)（rs）(pq) 五判斷下面一段論述是否為真：“是無理數(shù)。并且，如果3是無理數(shù)，則也是無理數(shù)。另外6能被2整除，6才能被4整除?！绷⒂谜嬷当砼袛嘞铝泄降念愋停?1) p(pq)(pq) (2) (pr) (pq)(2)(pq) (qr) (p

3、r)第二章 命題邏輯等值演算一、用等值演算法判斷下列公式的類型，對(duì)不是重言式的可滿足式，再用真值表法求出成真賦值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)二、用等值演算法證明下面等值式(1)(pq)(pr)(p(qr)(2)(pq)(pq)(pq) (pq)三、用等值演算求下列公式的主析取范式與主合取范式，并求成真賦值(1)(pq)(qp)(2)(pq)qr(3)(p(qr)(pqr)四、用真值表法求下列公式的主析取范式,再用主析取范式求主合取范式 (1) (pq)r (2)p(pqr)第三章 命題邏輯的推理理論一、 填空1.數(shù)理邏輯的的主要任務(wù)是 。推理是指 ， 前

4、提是 ，結(jié)論是 。2.推理正確是指： 3.命題公式A1，A,2，¼，A,k推B的推理正確當(dāng)且僅當(dāng) 二、先把下列命題符號(hào)化，再寫出前提、結(jié)論、推理的形式結(jié)構(gòu)，然后用3種方法證明（真值表法、等值演算法、主析取范式法）證明下列推理是正確的。若a是奇數(shù)，則a不能被2整除。若a是偶數(shù)，則a能被2整除。因此，若a是偶數(shù)，則a不是奇數(shù)。設(shè)p: a是奇數(shù),q: a能被2整除,r: a是偶數(shù)三、 在自然推理系統(tǒng)下用直接法或用附加前提法或用歸謬法構(gòu)造下列推理的證明 - 5 -(1)前提：pq,(qr),r結(jié)論：p (2)前提：qp,qs,st,tr結(jié)論：pq（3）前提：p(qr),sp,q （4）前提：

5、pq,rq,rs結(jié)論：sr 結(jié)論：p 離散數(shù)學(xué)標(biāo)準(zhǔn)化作業(yè)紙 專業(yè)班級(jí) 學(xué)號(hào) 姓名 四、 在自然推理系統(tǒng)下構(gòu)造下列推理的證明如果我學(xué)習(xí)，那么我數(shù)學(xué)不會(huì)不及格。如果不熱衷于玩游戲，那么我將學(xué)習(xí)。但我數(shù)學(xué)不及格。因此我熱衷于玩游戲。第四章 一階邏輯的基本概念一、將下列命題用0元謂詞符號(hào)化.(1) 小王學(xué)過英語(yǔ)和法語(yǔ)。(2)除非李建是東北人，否則他一定怕冷。(3)2大于3僅當(dāng)2大于4。(4)3不是偶數(shù)。(5)2或3是素?cái)?shù)。二、在一階邏輯中將下面將下面命題符號(hào)化,并分別討論個(gè)體域限制為(a),(b)條件時(shí)命題的真值:(1) 對(duì)于任意x,均有(2) 存在x,使得x+5=9.其中(a)個(gè)體域?yàn)樽匀粩?shù)集合.

6、(b)個(gè)體域?yàn)閷?shí)數(shù)集合.三、在一階邏輯中將下列命題符號(hào)化:(1) 沒有不能表示成分?jǐn)?shù)的有理數(shù)。(2) 在北京賣菜的人不全是外地人。(3)烏鴉都是黑的。(4)有的人天天鍛煉身體。四、給定解釋I如下: (a) 個(gè)體域D為實(shí)數(shù)集合R. (b) D中特定元素=0. (c) 特定函數(shù)(x,y)=x-y,x,y (d) 特定謂詞(x,y):x=y, (x,y):x<y,x,y. 說明下列公式在I下的含義,并指出各公式的真值:(1)(2)(3) (4) 五、給定下列各公式一個(gè)成真的解釋，一個(gè)成假的解釋。(1) "x(F(x)G(x) (2) $x(F(x) G(x) H(x)六、判斷下列公式

7、的類型(1) F(x,y)(G(x,y)F(x,y)(2) "x$y F(x,y)$x"y F(x,y)第五章 一階邏輯的等值演算與推理一、 設(shè)個(gè)體域D=a,b,c,消去下列各式的量詞(1) "x $y(F(x) G(y)(2) "x $y(F(x) G(y)(3) "x F(x) $y G(y)二、求下列公式的前束范式（1）"x F(x) "y G(x,y)（2）"x(F(x,y) $y G(x,y,z)三、設(shè)個(gè)體域D=1,2,3,4，F(xiàn)(x):x是2的倍數(shù)，G(x):x是奇數(shù)。將命題"x (F(x)

8、Ø G(y)中的量詞消去，并討論命題的真值。四、在自然推理系統(tǒng)下用直接法或用附加前提法或用歸謬法構(gòu)造下列推理的證明 - 25 -q 1.全稱量詞消去規(guī)則(UI)q 2.全稱量詞引入規(guī)則(UG) q 3. 存在量詞引入規(guī)則(EG) q 4. 存在量詞消去規(guī)則(EI) （1）前提："x (F(x) G(x), "x F(x) 結(jié)論："x G(x) (2) 前提："x(F(x)G(x)結(jié)論："xF(x)"x G(x)(3) 前提："x(F(x)G(x)，$x G(x)結(jié)論：$x F(x)五、 在自然推理系統(tǒng)下構(gòu)造下列推理

9、的證明沒有白色的烏鴉，北京鴨都是白色的。因此，北京鴨都不是烏鴉。第六章 集合論一、單項(xiàng)選擇題1若集合A=a，b，B= a，b， a，b ，則（ ） AAÌB，且AÎB BAÎB，但AËB CAÌB，但AÏB DAËB，且AÏB2若集合A2，a， a ，4，則下列表述正確的是( )Aa， a ÎA B a ÍA C2ÎA DÎA3若集合A a，a，1，2，則下列表述正確的是( ) Aa，aÎA B2ÍACaÍA DÆÎA4若集合

10、A=a，b， 1，2 ，B= 1，2，則（ ） AB Ì A，且BÎA BBÎ A，但BËA CB Ì A，但BÏA DBË A，且BÏA 5設(shè)集合A = 1, a ，則P(A) = ( ) A1, a B,1, a C,1, a, 1, a D1, a, 1, a 6若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為（ ） A1024 B10 C100 D1二、1設(shè)集合A有n個(gè)元素，那么A的冪集合P(A)的元素個(gè)數(shù)為 2設(shè)集合Aa，b，那么集合A的冪集是 三、（1）B、C為任意的三個(gè)集合，如果AB=AC，判斷結(jié)論B=

11、C 是否成立？并說明理由（2）B、C為任意的三個(gè)集合，如果AB=AC，判斷結(jié)論B=C 是否成立？并說明理由四、 1設(shè)集合Aa, b, c，B=b, d, e，求（1）BÇA； （2）AÈB； （3）AB； （4）BÅA2設(shè)A=a, b, 1, 2，B= a, b, 1, 1，試計(jì)算（1）（A-B） （2）（AB） （3）（AB）-（AB）五證明集合等式：AÈ (BÇC)=(AÈB) Ç (AÈC)六、某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。

12、已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。第七章 二元關(guān)系（1）一、單項(xiàng)選擇題1集合A=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系R=<x，y>|x+y=10且x, yA，則R的性質(zhì)為（ ） A自反的 B對(duì)稱的 C傳遞且對(duì)稱的 D反自反且傳遞的2設(shè)集合A = 1，2，3，4，5，6 上的二元關(guān)系R =a , bêa , bA , 且a +b = 8，則R具有的性質(zhì)為（ ）A自反的 B對(duì)稱的C對(duì)稱和傳遞的 D反自反和傳遞的3如果R1和R2是A上的自反關(guān)系，則R1R2，R1R2，R1-R2中自反關(guān)系有（ ）個(gè) A0 B2 C1 D34設(shè)集合A=1 ,

13、2 , 3 , 4上的二元關(guān)系R = 1 , 1，2 , 2，2 , 3，4 , 4，S = 1 , 1，2 , 2，2 , 3，3 , 2，4 , 4，則S是R的（ ）閉包A自反 B傳遞 C對(duì)稱 D以上都不對(duì)二、填空題1設(shè)集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元關(guān)系，則R的有序?qū)蠟?2設(shè)集合A=0, 1, 2，B=0, 2, 4,R是A到B的二元關(guān)系，則R的關(guān)系矩陣MR 3設(shè)集合A=a,b,c，A上的二元關(guān)系R=<a, b>,<c. a>，S=<a, a>,<a, b>,<c, c>則(R

14、3;S)1=4設(shè)集合A=a,b,c，A上的二元關(guān)系R=<a, b>, <b, a>, <b, c>, <c, d>，則二元關(guān)系R具有的性質(zhì)是三、設(shè)A=a，b，構(gòu)成集合（A）×A。四、(1)列出集合A=2,3,4上的恒等關(guān)系I A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.(2)設(shè)A=a,b,c,d，為A上的關(guān)系，其中= 求。adbc圖1五、設(shè)集合Aa, b, c, d上的二元關(guān)系R的關(guān)系圖如圖1所示（1）寫出R的表達(dá)式； （2）寫出R的關(guān)系矩陣； （3）求出R2 六、設(shè)集合A=1，2，3，4，R=<x, y>|x, y

15、ÎA；|x-y|=1或x-y=0，試（1）寫出R的集合表示； （2）畫出R的關(guān)系圖；（3）說明R滿足自反性，不滿足傳遞性第七章 二元關(guān)系（2）一、選擇題1. 下列說法正確的是( )ABCD2. 若A=（x，y）| （y4）/（x+2）=1和B=（x，y）| y=3x2，則AB為（ ）A(x，y)| (y3)/(x1)=1B(x，y)| x=4，y=10C(x，y)| y=x+2D3. 設(shè)A為有限集，元素個(gè)數(shù)為n個(gè)，P(A)為A的冪集，則P(A)的元素個(gè)數(shù)及的元素個(gè)數(shù)為( ) A B 及 C 及 D以上全不對(duì)4. 設(shè)A是非空集合，則A上的空關(guān)系不具有( )A反自反性 B自反性 C對(duì)稱性

16、 D傳遞性5設(shè)，R是A上相等關(guān)系“=”，由R產(chǎn)生等價(jià)類有( ) A10個(gè) B50個(gè) C100個(gè) D1個(gè)6.集合A的一個(gè)劃分，確定A的元素間的關(guān)系為( ). A全序關(guān)系B等價(jià)關(guān)系C偏序關(guān)系D擬序關(guān)系7集合A=1，2，3上的下列關(guān)系矩陣中符合等價(jià)關(guān)系條件的是（）ABCD8.給定A=1、2、3上的關(guān)系R=<1, 1>, <2, 2>, <1, 3>, <3, 1>, <2, 3>則( )A R是自反的且傳遞B R不反自反且不對(duì)稱C R是反對(duì)稱且不對(duì)稱D R不自反且傳遞9A=1、2、3，則A上不同等價(jià)關(guān)系有( ) A. 5 B.10 C. 1

17、5 D.8二、設(shè)A=1，2，3，4,R=<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>是A上的等價(jià)關(guān)系嗎？如果是,給出給出每個(gè)元素的等價(jià)類；如果不是,請(qǐng)說明理由。三、設(shè)集合A=1，2，3，6，8，12，24，36，R為A上整除關(guān)系，畫出R的哈斯圖，并指出B=2，6，8的極大元，極小元、最大元，最小元、及上確界和下確界。四、設(shè)A=1，2，3，4，在AA上定義二元關(guān)系R， <u,v>,<x,y>AA ，u,v> R <x,y>u + y = x + v.(1)

18、證明R 是AA上的等價(jià)關(guān)系.(2)確定由R 引起的對(duì)AA的劃分.第八章 函數(shù)一、選擇題1設(shè)A=a, b，B=1, 2，R1，R2，R3是A到B的二元關(guān)系，且R1=<a，2>, <b，2>，R2=<a，1>, <a，2>, <b，1>，R3=<a，1>, <b，2>，則（ ）不是從A到B的函數(shù) AR1和R2 BR2 CR3 DR1和R32.設(shè)A=a，b，c，B=1，2，作f：AB，則不同的函數(shù)個(gè)數(shù)為( )A 6 B.5 C. 9 D.83.下列函數(shù)中為雙射的是( ). AB CD4.設(shè)Z是整數(shù)集，E=,-4,-2

19、,0,2,4，f：ZE，f（x）=2x，則f是( )A僅是滿射B僅是單射 C是雙射D無逆函數(shù)二、判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的? (1) f:NN, f(x)=x2+2 (2) f:NN,f(x)=(x)mod 3, x除以3的余數(shù) (3) f:NN,f(x)= (4) f:N0,1,f(x)= (5) f:N-0R,f(x)=lgx (6) f:RR,f(x)=x2-2x-15 三、設(shè)X=a,b,c,d,Y=1,2,3,f=<a,1>,<b,2>,<c,3>,判斷以下命題的真假: (1)f是從X到Y(jié)的二元關(guān)系,但不是從X到Y(jié)的函數(shù);

20、 (2)f是從X到Y(jié)的函數(shù),但不是滿射,也不是單射的; (3)f是從X到Y(jié)的滿射,但不是單射; (4)f是從X到Y(jié)的雙射.四、設(shè)A=1,2，B=a,b,c,寫出所有A到B的函數(shù)，并說明所具有的性質(zhì)。五、已知集合A和B且|A|=n，|B|=m，求A到B的二元關(guān)系數(shù)是多少？A到B的函數(shù)數(shù)是多少？ 六、設(shè)N是自然數(shù)集合，定義 N 上的二元關(guān)系R：R=(x,y): x ÎN, y ÎN, x+y 是偶數(shù)(1) 證明R是等價(jià)關(guān)系。 (2) 求 關(guān)系R的等價(jià)類。第十四、十五章 一、單項(xiàng)選擇題1一個(gè)無向圖有4個(gè)結(jié)點(diǎn)，其中3個(gè)的度數(shù)為2，3，3，則第4個(gè)結(jié)點(diǎn)的度數(shù)不可能是（ ）A.0 B.

21、 1 C. 2 D. 42無向完全圖有 (    )條邊A. n          B. n2    C.  n(n-1)      D. n(n-1)/23整數(shù)列（1，3，3，5，4）（ ）A可以簡(jiǎn)單圖化 B. 不可圖化 C. 可圖化，不可簡(jiǎn)單圖化4若答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是( ). A. (1,2,2,3,4,5)

22、 B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6).5設(shè)簡(jiǎn)單圖G所有結(jié)點(diǎn)的度之和為12，則G一定有( ). A3條邊 B4條邊 C5條邊 D6條邊6設(shè)無向圖中有6條邊，有一個(gè)3度頂點(diǎn)和一個(gè)5度頂點(diǎn)，其余頂點(diǎn)度為2，則該圖的頂點(diǎn)數(shù)是（）A3 B4 C5 D67下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）A B C D8.設(shè)G為完全二部圖K2,3，下面命題中為真的是( )A.G為歐拉圖 B.G為哈密爾頓圖C.G為平面圖 D.G為正則圖二、填空1簡(jiǎn)單無向圖有21條邊,3個(gè)4度結(jié)點(diǎn),其余均為3度結(jié)點(diǎn),則G有_個(gè)結(jié)點(diǎn).2無向圖G=<V,E>,V

23、=a,b,c,d,E=(a,b),(a,c),(a,d),(b,c),則它的鄰接矩陣為 ，該圖的補(bǔ)圖有 條邊。3.設(shè)K6是有6個(gè)點(diǎn)的完全圖，則K6共有_條邊。4. .已知n階無向簡(jiǎn)單圖G有m條邊，則G的補(bǔ)圖G有_條邊。圖25. 若一條路中，所有邊均不相同，則此路稱作_；若一條路中所有的結(jié)點(diǎn)均不相同，則稱此路為_。ah hb fh hc eh hd 圖16圖G如圖1所示，那么圖G的割點(diǎn)是 。7如圖2所示G的鄰接矩陣A=_ 8.下圖的點(diǎn)連通度等于 ，邊連通度等于_。9.已知n階無向圖G中有m條邊，各頂點(diǎn)的度數(shù)均為3。又已知2n-3=m，則m= .三、（1）已知無向圖G有12條邊，1度頂點(diǎn)有2個(gè)，2

24、度、3度、5度頂點(diǎn)各1個(gè)，其余頂點(diǎn)度數(shù)均為4，求4度頂點(diǎn)的個(gè)數(shù)。（2）假設(shè)在圖G(有向圖或無向圖)中，有10條邊，4個(gè)3度的結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)不大于2。問G中至少有幾個(gè)結(jié)點(diǎn)？四、判斷下圖是否歐拉圖，若是，找出一個(gè)歐拉回路。五設(shè)簡(jiǎn)單無向圖G有n個(gè)結(jié)點(diǎn),n+1條邊，證明G中至少有一上結(jié)點(diǎn)的度3。六、畫出彼德森圖，K5，K3,3，并判斷他們是否是歐拉圖，是否是哈密頓圖。第十六、十七章一、選擇題1一顆二叉樹后序遍歷的結(jié)果是bdeca，中序遍歷的結(jié)果是badce，則 根結(jié)點(diǎn)的右子樹有（ ）結(jié)點(diǎn)。A1 B2 C3 D42設(shè)G是連通平面圖，G中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是（  &

25、#160;  ）A2 B3 C4 D53.下列編碼是前綴碼的是(    ).A.1,11,101  B.1,001,0011 C. 1,01,001,000  D.0,00,0004.下圖所示的二叉樹中序遍歷的結(jié)果是（     ）Aabcde Bedcba Cbdeca Dbadce5.關(guān)于無向樹的描述,不正確的是( ).A. 無向樹是連通圖、沒有回路,每個(gè)邊都是橋；B. 無向樹是連通圖、邊數(shù)比頂點(diǎn)數(shù)少,任意兩個(gè)頂點(diǎn)的路徑是惟一的；C. 無向樹是連通圖、沒有回路,每個(gè)頂點(diǎn)都是

26、割點(diǎn)；D. 無向樹是連通圖、沒有回路，每條邊都是割邊。6.關(guān)于含有n片樹葉的最優(yōu)二叉樹描述,不正確的是( ).A. 含有n片樹葉的最優(yōu)二叉樹每個(gè)分支點(diǎn)都有兩個(gè)孩子；B. 含有n片樹葉的最優(yōu)二叉樹分支點(diǎn)的個(gè)數(shù)是n-1；C.W(T)等于個(gè)分支點(diǎn)的權(quán)重（構(gòu)造最優(yōu)二叉樹時(shí)產(chǎn)生）之和；D. 在權(quán)重一定的前提下，含有n片樹葉的最優(yōu)二叉樹是惟一的。7.彼得森圖是 ( )。A. 平面圖 B. 二部圖 C. Euler圖 D. 以上都不是二、1.一棵二叉樹先序遍歷得ABDECF，中序遍歷得DBEACF,則后序遍歷的結(jié)果是_。2.一無向圖存在生成樹的充分必要條件是 。3.最優(yōu)二叉樹有n片樹葉，則它有 分支點(diǎn)。三、1.(1)在一棵有2個(gè)2度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)都是樹葉的無向樹中應(yīng)該有幾片樹葉？(2)畫出兩棵非同構(gòu)的滿足上述條件的無向樹。2. 畫一棵帶權(quán)為2，2，2，3，3，4，5，8的最優(yōu)二叉樹T，并計(jì)算它的權(quán)W（T）。3. 求下2圖的最