離散數(shù)學(xué)習(xí)題整合

1、CH01復(fù)習(xí)題§1.2 1. 命題判斷（每空1分，共4分）1.11.3 P32-A 小李和小王是同班同學(xué) B 小豬不是鮮花 C 3-2n<0 D 若2+2=4，則太陽(yáng)從西方升起。上述語(yǔ)句中， 是簡(jiǎn)單命題， 不是命題， 是符合命題且真值為假， 是符合命題且真值為真。 （參考答案：ACDB）2. 命題符號(hào)化（每空2分，共4分）習(xí)題1.5(7)(3) P32-p：天下大雨，q：他乘公共汽車去上班，命題“除非天下大雨，否則他不乘公共汽車去上班”可符號(hào)化為 。（參考答案：qp 必要條件為后件）r：天很冷，s：老李來(lái)了，命題“雖然天很冷，老李還是來(lái)了” 可符號(hào)化為 。（參考答案rs）3.

2、五個(gè)真值表（每空2分，共4分）習(xí)題1.6(2)(4) P32-設(shè)p的真值為0，r的真值為1，q、s都是命題，則命題公式（的真值為 ，命題公式的真值為 。（參考答案：0,1）4. 用符號(hào)p、q填空。（每空1分，共4分）基本概念設(shè)p：x>0（其中x是整數(shù)） ，q：太陽(yáng)從西方升起，則 是命題， 是命題變項(xiàng)， 是命題常項(xiàng)， 不是命題。（參考答案：q，p，q，p）5. 命題符號(hào)化，相容或與排斥或設(shè)r：現(xiàn)在小李在圖書館，s：現(xiàn)在小李在學(xué)生宿舍，則“現(xiàn)在小李在圖書館或?qū)W生宿舍”可符號(hào)化為 。（參考答案：B）A rs B (r¬s)(¬rs) C rs D (r¬s)或(&

3、#172;rs)§1.2 命題公式及分類已知：A是含三個(gè)命題變項(xiàng)的命題公式，且A(001)=0，A(100)=1，則A是 。（D）A 矛盾是 B 可滿足式 C 重言式 D 非重言式的可滿足式§1.3 等值演算用等值演算法證明等值式：(pq)rp(qr). (演算的每一步都要寫依據(jù))§1.4 范式6. （每項(xiàng)1分，共4分）已知命題公式A(p,q)的真值表PqA(p,q)000011100111求A的永主析取范式、主合取范式、成真賦值和成假賦值。（參考答案：m1m3，M0M2，01、11，00、10）7. （2分）命題公式B(p,q,r)=(¬pr¬

4、;q)的主析取范式是 。（參考答案：C） A m2 B M6 C m1 D M5 E 命題公式B(p,q,r)=(¬p¬qr)的主析取范式是 。（參考答案：A） A m0m1m2m3m4m5m7 B M6 C m1 D M1 §1.5 全功能集（2分） 不是聯(lián)結(jié)詞全功能集。（參考答案：D） A B ¬, C ¬, D , 是聯(lián)結(jié)詞全功能集。（參考答案：A） A , B , C D §1.6 組合電路（習(xí)題1.16）有一盞燈由三個(gè)開關(guān)控制，要求按任何一個(gè)開關(guān)都能使燈由黒變亮或由亮變黑，試設(shè)計(jì)這樣的一個(gè)電路。（解題基本步驟：狀態(tài)設(shè)置、設(shè)計(jì)

5、真值表、寫主析取范式、化簡(jiǎn)、繪制電路. 答案不唯一）§1.7 推理理論(習(xí)題1.19(1)用直接證明法或歸謬法證明下面的推理.前提：¬(p¬q)， ¬qr，¬r. 結(jié)論：¬p.證明： (習(xí)題1.19(3)用直附加前提法證明下面的推理.前提：Pq. 結(jié)論：P(pq).證明：（例題1.28）公安人員審查一件盜竊案，已知事實(shí)如下：（1） 李或王盜竊了錄音機(jī)；（2） 若李盜竊了錄音機(jī)，則作案時(shí)間不能發(fā)生在午夜前；（3） 若王的證詞正確，則午夜時(shí)屋里燈光未滅；（4） 若王的證詞不正確，則作案時(shí)間發(fā)生在午夜前；（5） 午夜時(shí)屋里燈光滅了.試問(wèn)盜竊

6、錄音機(jī)的是李還是王，并證明你的結(jié)論。參考答案：王盜竊了錄音機(jī).設(shè) p：李盜竊了錄音機(jī)；q：王盜竊了錄音機(jī)；r：作案時(shí)間發(fā)生在午夜前；s：王的證詞正確；t：午夜時(shí)屋里燈光滅了.前提：pq，p¬r，st，¬sr，¬t. 結(jié)論：q.證明：CH02復(fù)習(xí)題§2.1例2.1（3）1 將命題“若李一的成績(jī)比王二高，王二的成績(jī)比吳三高，那么李一的成績(jī)比吳三高”用0元謂詞符號(hào)化。解：設(shè)H(x,y)：x的成績(jī)比y高，a：李一，b：王二，c: 吳三則命題可符號(hào)化為 H(a,b) H(b,c) H(a,c)§2.1例2.4（4）2 在一階邏輯中將命題“素?cái)?shù)不全是奇數(shù)”

7、符號(hào)化。解：設(shè)F(x)：x是素?cái)?shù)，G(x)：x是奇數(shù)則命題可符號(hào)化為 x(F(x)G(x)或 x(F(x)G(x)§2.23 （每空1分，共4分）給定解釋I，對(duì)一階邏輯合式公式中每個(gè) 出現(xiàn)的 指定 中的一個(gè)元素，稱作在 下的賦值。 （自由 個(gè)體變項(xiàng) 個(gè)體域 解釋I）§2.24 下面的一階邏輯合式公式 不是閉式。(D 有自由出現(xiàn)) A x(F(x)G(X) B y(F(x,y)G(x) C xF(x)yG(y) D xF(x,y)yG(y)§2.25 下面各種敘述， 不正確。(C 例2.8（5）) 也可改造成正誤判斷題 A 在給定的解釋和賦值下，任何一階邏輯合式公式

8、都是命題 P45- B 閉公式的真值與賦值無(wú)關(guān)，只需要給定解釋 C 非閉式的公式的真值只與賦值有關(guān) D 可滿足式可能是邏輯有效式§2.36 在四個(gè)合式公式"x$y(F(x)®(G(y)ÙH(x,y) 、"x(F(x)®$y(G(y)ÙH(x,y)、"xØ(F(x)ÙG(x)、 Ø$x(F(x)ÙG(x) 中共有 個(gè)是前束范式。（參考答案：A）A 2 B 3 C 1 D 0（*參考答案：B）7 已知F(x)=Ø$x(M(x)ÙF(x)，G1(x)="

9、;xØ(M(x) Ù F(x)，G2(x)="x(ØM(x)ÚØF(x)，G3(x)="x(M(x)®ØF(x) ，則在G1(x)、G2(x)和G3(x)中，有 個(gè)是F(x)的前束范式。 A 0 B 3 C 2 D 1例2.11（3）8 求公式 xF(x)G(x) 的前束范式。解：xF(x)G(x)xF(x)xG(x) (蘊(yùn)涵等值式)xF(x)xG(x) (量詞否定等值式)xF(x)G(x) ) (量詞分配等值式)解法2：xF(x)G(x)xF(x)yG(y) (換名規(guī)則)x(F(x)yG(y) (量詞擴(kuò)

10、TH2.2(2)xyF(x)G(y) ) (量詞擴(kuò)TH2.2(2)解法3：xF(x,)G(x)F(y)G(x) )§2.4例2.17設(shè)個(gè)體域D=a,b，消去公式 x(F(x)yG(y) 中的量詞。離散CH03復(fù)習(xí)題判斷（1分/每小題）若集合A=1，1,2，3，則2A （×）若集合B=2，a，b，則a，bB （×）單選（2分/每小題）下面的集合算式 不正確。（A=C）A A-(BC)=A-B)(A-C) B A-B=AB C A=A D ABA-B=已知B= a，b，c ，則|P(A)|= . （P(A)= ，c，a，b，B，A）A |，c，a，b，B| B 2 C

11、 3 D 8填空（2分/每小題）若|P(A)| = 128，則|A|= . (|P(A)|=27,7)設(shè)A=1,3,3，則|A|= . (A=1,3，2)計(jì)算（8分/每小題）某班有48個(gè)學(xué)生， 第一次作業(yè)優(yōu)秀7人，第二次作業(yè)優(yōu)秀6人，兩次作業(yè)都沒得優(yōu)秀的41人，求兩次作業(yè)都得優(yōu)秀的人數(shù)。（求解過(guò)程參見例3.12，參考答案：6）解：用A、B分別表示第一次和第二次作業(yè)優(yōu)秀的人數(shù)集合，E為某班全體學(xué)生的集合 則：|E|=48，|A|=7，|B|=6，|AB|=41|AB| = |E|-(|A|+|B|)+|AB|AB| = 41-48+(7+6) = 6已知A=a，b，c，d，B=c，d，計(jì)算AB、

12、AB、A-B、AB。（P74-3.13(1)）畫圖畫（AB）（C-B）的文氏圖。（3.15（3）ABC證明：（AB）（C-B）=（AC）- B證：左式=（AB）（CB ） （3.27 /差交運(yùn)算轉(zhuǎn)換 ）= (AC) B （3.8/分配律）= (AC)-B （3.27 /差交運(yùn)算轉(zhuǎn)換 ）離散CH04復(fù)習(xí)題判斷（1分/每小題）§4.11. A是任意集合，則A×A的任何子集稱作A上的二元關(guān)系。 （）2. 若集合B=2，a，b，則a，bB （×）單選（2分/每小題）§4.13. A是任意集合，<x，x>|xA稱作 關(guān)系。（恒等關(guān)系蘊(yùn)含其是A上的B）A

13、 空 B恒等 C 全域 D A上的4. 設(shè)A=a，b，c， R=<a，a>，<a，b >，< b，b>，<b，c>，<c，a>，<c，b>，則 是R的關(guān)系矩陣。（參見P80-，參考答案：（A）A B C D 設(shè)S=1,2,3,4，R是S上的關(guān)系，其關(guān)系矩陣是，R的關(guān)系圖中有 個(gè)環(huán)。AA 1 B 3 C 6 D 7填空（2分/每小題）§4.16. A、B是任意兩個(gè)集合，若|A|=m，|B|=n，則|P(A×B)|= 。 （）7. 設(shè)A是任意集合， |A|=n，則A上有 個(gè)不同的二元關(guān)系。 (,|A

14、5;A|=n2)§4.58. R是集合A上的等價(jià)關(guān)系，如果有序?qū)?lt;a,b>R，則記作 。（ab）9.若R是集合A上的偏序關(guān)系，則可將此偏序關(guān)系簡(jiǎn)記作；有序?qū)?lt;x,y>，可記作 。（ab）計(jì)算（8分/每小題）§4.210. 已知關(guān)系R=<2,2>，<2,2,2>，求RR、R2、R2. (同例4.7 理解定義4.9)解：RR=<2，2,2>R2 = <2,2> 限制R2 = ran（R2）= ran<2,2> = 2 像集11. 已知A=a，b，c，d，R1和R2是A上的關(guān)系，且R1=<a

15、，a>，<a，b>，<b，d>，R2=<a，d>，<b，c>，<b，d>，<c，b>。求R2R1。解：<a，a>R1 <a，d>R2 ，<a，d>R2R1 <a，b>R1 <b，c>R2 ，<a，c>R2R1 <a，b>R1 <b，d>R2 ，<a，d>R2R1故 R2R1=<a，d>，<a，c>證明題綜合：§1等值公式和等值運(yùn)算+§3集合運(yùn)算+§4關(guān)系性質(zhì)

16、的定義12. 設(shè)集合A上的兩個(gè)關(guān)系R1和R2都是對(duì)稱的，證明R1R2仍是對(duì)稱的。證明： 參見主教材P87-13. 試證任何集合A的冪集P(A) 上的包含關(guān)系R是偏序關(guān)系證明：xP(A)，都有xx，<x，x>R R是自反的<x,y>R xyxy xy xy （集合包含關(guān)系的定義） yx <y,x>R (包含關(guān)系的定義) R是反對(duì)稱的x、t、yP(A),若<x,t>R<t,y>R 則 xtty (關(guān)系R的定義) xy （集合運(yùn)算律） <x,y>R （關(guān)系R的定義）R是傳遞的14. 已知R的關(guān)系圖如下圖所示，畫R的自反閉包r（R

17、）、對(duì)稱閉包s（R）、傳遞閉包t(R).1235415. 畫<1,2,3,4,5,6,7,8，R整除>的哈斯圖。16. 判斷函數(shù)f：NN， 是否是滿射、單射、雙射，為什么?012.0123.解：作f的對(duì)應(yīng)關(guān)系圖如右，由圖可知1無(wú)原像，故f非滿射，也非雙射。但f是單射。離散CH05 選擇一個(gè)最合適的答案       e0e1e2v3v4v5v6e3v0v1v2e4e5e61.下圖中的邊（和邊的交替）序列：e0 e1 e2 e3 e4e5 稱為 。（A） A 簡(jiǎn)單通路 B 初級(jí)通路 C 通路 D 復(fù)雜通路 v0v1v

18、2v3v4v5v62. 下面有向圖中的頂點(diǎn)序列：V0 V1 V2 V3 V4 V2 V5 稱為 。（C）A 路徑 B 初級(jí)通路 C簡(jiǎn)單通路 D 復(fù)雜通路3. 能構(gòu)成圖的度數(shù)序列。（C）A （3，3，2，1） B （2，3，2） C （1） D（3，3，3）填空：4. 設(shè)G（V,E）是n階有向簡(jiǎn)單圖，若u，vV，都有 ，則稱G是n階有向完全圖。（<u，v>E < v，u >E）5. G（V,E）是n階有向完全圖，通常記為 。(Kn）v1v2v3e4e1e2e36. 在下面的有向圖中，從v2到v2的長(zhǎng)度為2的初級(jí)回路是 。v2e4v1e1v2v0v1v3v2e0e1e3e2

19、7.在下面的無(wú)向圖中，頂點(diǎn) 是割點(diǎn)，邊 是橋。（V2）（e3）8. 設(shè)G是有向圖或無(wú)向圖，稱p（G）是圖G的 。（連通分支個(gè)數(shù)）簡(jiǎn)答（6分/每小題）§5.29. 下面三個(gè)無(wú)向圖，它們之間哪些同構(gòu)，哪些不同構(gòu)。若不同構(gòu)，為什么？若同構(gòu)，請(qǐng)建立頂點(diǎn)之間的雙射。 圖G1 圖G2 圖G3答：圖G1與圖G2不同構(gòu)，因?yàn)閳DG1與G2存在度不相同的頂點(diǎn)。 2分同理G2G3. 2分G1 G3. 2分因?yàn)?2 c b 1 4 3 d a建立頂點(diǎn)之間的如下對(duì)應(yīng)關(guān)系f：1a，2b，3c，4d，f是雙射，并且兩圖的邊也一一對(duì)應(yīng)。10.無(wú)向圖的（點(diǎn)）著色：P132-例5.511. 圖 強(qiáng)連通，圖 單向連通，圖

20、 弱連通，圖 非連通。D2D3D4D1 參考答案：D2 、D3 、D4 、D1）12.應(yīng)用題 P133-例5.6離散CH06 選擇一個(gè)最合適的答案1. 下面三種說(shuō)法，其中不正確的有 個(gè)。(C 還有必要條件) Hall定理是二部圖G(V1, V2,E)存在完備匹配的充要條件 無(wú)論是有向圖還是無(wú)向圖，都有判斷其是否存在歐拉通路和歐拉回路的充要條件 目前只有判斷哈密頓圖的充分條件A 0 B 3 C 1 D 2 2. 下面四種說(shuō)法，其中正確的有 個(gè)。（A） 存在既是歐拉圖又是哈密頓圖的無(wú)向圖 存在是歐拉圖不是哈密頓圖的無(wú)向圖存在不是歐拉圖卻是哈密頓圖的無(wú)向圖 存在既不是歐拉圖又不是哈密頓圖的無(wú)向圖A

21、4 B 3 C 2 D 1填空§6.13. 用G(V1 ,V2,E)表示二部圖G，| V1|=n，| V2|=m，記號(hào)表示圖G為 。（完全二部圖）§6.44. 若圖G畫在平面上使得除頂點(diǎn)處外沒有 出現(xiàn)，則稱G為平面圖。（邊交叉）5. 下面的平面圖共有 個(gè)面，其中無(wú)限面R0的次數(shù)deg（R0）= 。（3，8） 平面圖6-1 6. 非連通的平面圖6-2的外部面是R0，deg（R0）= 。（9）R1R0R2非連通平面圖6-2應(yīng)用題：7. P151-習(xí)題6.5 （二部圖的應(yīng)用）8. P151-習(xí)題6.15 （哈密頓圖的應(yīng)用）9. P152-習(xí)題6.18 （歐拉通路或歐拉回路的應(yīng)用）10. *P152-習(xí)題6.23 （平面圖在作色中的應(yīng)用）離散CH07復(fù)習(xí)題§7.11. P165-12設(shè)n階連通無(wú)向圖G(V,E)有m條邊，G的生成樹有 條邊，余樹有 條邊。（n-1，m-n+1）2. P167-例7.5（2）畫出4個(gè)頂點(diǎn)非同構(gòu)無(wú)向樹。（2種）3. P173-習(xí)題7.16（3）畫出4個(gè)頂點(diǎn)非同構(gòu)的根