第一篇：離散數學
第一章
數學語言與證明方法
例1 設E={ x | x是北京某大學學生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走讀生}, C= { x | x是數學系學生}，D= { x | x是喜歡聽音樂的學生}.試描述下列各集合中學生的特征:
(A?D)? ~ C={ x | x是北京人或喜歡聽音樂,但不是數學系學生} ~ A?B={ x | x是外地走讀生}(A-B)? D={ x | x是北京住校生, 并且喜歡聽音樂} ~ D ? ~ B={ x | x是不喜歡聽音樂的住校生} 例3 證明:(1)A?B=B?A(交換律)證 ?x
x?A?B
? x?A?x?B
(并的定義)
?x?B?x?A
(邏輯演算的交換律)
?x?B?A
(并的定義)(2)A?(B?C)=(A?B)?(A?C)(分配律)證 ?x
x?A?(B?C)
? x?A?(x?B? x?C)
(并,交的定義)
?(x?A?x?B)?(x?A?x?C)
(邏輯演算的分配律)
?x?(A?B)?(A?C)
(并,交的定義)(3)A?E=E(零律)證 ?x
x?A?E
? x?A?x?E
(并的定義)
? x?A?1
(全集E的定義)
?1
(邏輯演算的零律)
?x?E
(全集E的定義)(4)A?E=A(同一律)證 ?x
x?A?E
? x?A?x?E
(交的定義)
? x?A?1
(全集E的定義)
? x?A
(邏輯演算的同一律)例4 證明 A?(A?B)=A（吸收律）證 利用例3證明的4條等式證明
A?(A?B)
=(A?E)?(A?B)
(同一律)
= A?(E?B)
(分配律)
= A?(B?E)
(交換律)
= A?E
(零律)
= A
(同一律)例5 證明(A-B)-C=(A-C)-(B-C)證
(A-C)-(B-C)
=(A ? ~C)? ~(B ? ~C)
(補交轉換律)
=(A ? ~C)?(~B ? ~~C)
(德摩根律)
=(A ? ~C)?(~B ? C)
(雙重否定律)
=(A ? ~C ? ~B)?(A ? ~C ? C)
(分配律)
=(A ? ~C ? ~B)?(A ? ?)
(矛盾律)
= A ? ~C ? ~B
(零律,同一律)
=(A ? ~B)? ~C
(交換律,結合律)
=(A – B)– C
(補交轉換律)例6 證明(A?B)?(A?C)=(B?C)(A?C))?((A?C)A 例7 設A,B為任意集合, 證明:(1)A?A?B 證 ?x x?A ? x?A?x?B
(附加律)
? x?A?B
(2)A?B?A
證 ?x x?A?B ? x?A?x?B
? x?A
(化簡律)(3)A-B?A
證 ?x x?A-B ? x?A?x?B
? x?A
(化簡律)(4)若A?B, 則P(A)?P(B)證 ?x x?P(A)? x?A
? x?B
(已知A?B)
? x?P(B)例8 證明 A?B=A?B-A?B.證
A?B=(A?~B)?(~A?B)
=(A?~A)?(A?B)?(~B?~A)?(~B?B)
=(A?B)?(~B?~A)
=(A?B)?~(A?B)
=A?B-A?B 例3 若A-B=A, 則A?B=?
證 用歸謬法, 假設A?B??, 則存在x,使得
x?A?B ? x?A?x?B ? x?A-B?x?B
(A-B=A)
? x?A?x?B?x?B ? x?B?x?B，矛盾 例4 證明
是無理數
證
假設
是有理數, 存在正整數n,m, 使得
=m/n,不妨設m/n為既約分數.于是m=n, m2=2n2, m2是偶數, 從而m是偶數.設m=2k, 得(2k)2=2n2, n2=2k2, 這又得到n也 是偶數, 與m/n為既約分數矛盾.例6 對于每個正整數n, 存在n個連續的正合數.證
令x=(n+1)!
則 x+2, x+3,…, x+n+1是n個連續的正合數:
i | x+i，i=2,3,…,n+1 例7 判斷下述命題是真是假:
若A?B=A?C, 則B=C.解
反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有
A?B=A?C = {a,b} 但B?C, 故命題為假.例8 證明:對所有n?1, 1+2+ … +n=n(n+1)/2 證
歸納基礎.當n=1時, 1=1?(1+1)/2, 結論成立.歸納步驟.假設對n?1結論成立, 則有
1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)
(歸納假設)
=(n+1)(n+2)/2 得證當n+1時結論也成立.例9 任何大于等于2的整數均可表成素數的乘積 證 歸納基礎.對于2, 結論顯然成立.歸納步驟.假設對所有的k(2?k?n)結論成立, 要證結論 對n+1也成立.若n+1是素數, 則結論成立;否則n+1=ab, 2?a,b 命題邏輯 例1 下列句子中那些是命題？ (1)北京是中華人民共和國的首都.(2)2 + 5 ＝8.(3)x + 5 ＞ 3.(4)你會開車嗎？ (5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請關上門！(8)我正在說謊話.(1),(2),(5)是命題,(3),(4),(6)~(8)都不是命題 例2 將下列命題符號化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學.解 (1)p∧q (2)p∧q (3)p∧?q(4)記 r:張輝是三好生, s:王麗是三好生，r∧s(5)簡單命題，記 t:張輝與王麗是同學 例3 將下列命題符號化(1)2或4是素數.(2)2或3是素數.(3)4或6是素數.(4)元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.解 (1)p∨r, 真值:1(2) p∨q, 真值: 1(3)r∨s,真值: 0(4)記t:元元拿一個蘋果,u:元元拿一個梨 (t∧?u)∨(?t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年 (v∧?w)∨(?v∧w)又可形式化為 v∨w 例4 設p:天冷, q:小王穿羽絨服，將下列命題符號化 (1)只要天冷，小王就穿羽絨服.p?q(2)因為天冷，所以小王穿羽絨服.p?q (3)若小王不穿羽絨服，則天不冷.?q??p 或 p?q(4)只有天冷，小王才穿羽絨服.q?p(5)除非天冷，小王才穿羽絨服.q?p(6)除非小王穿羽絨服，否則天不冷.p?q (7)如果天不冷，則小王不穿羽絨服.?p??q 或 q?p(8)小王穿羽絨服僅當天冷的時候.q?p 例5 求下列復合命題的真值 (1)2+2＝4 當且僅當 3+3＝6.(2)2+2＝4 當且僅當 3是偶數.0(3)2+2＝4 當且僅當 太陽從東方升起.(4)2+2＝5 當且僅當 美國位于非洲.(5)f(x)在x0處可導的充要條件是它在 x0處連續.0 例6 公式A=(? p1? ? p2? ? p3)?(p1? p2) 000是成真賦值，001是成假賦值 公式B=(p?q)?r 000是成假賦值，001是成真賦值 例3 證明 p?(q?r)?(p?q)?r 證 p?(q?r) ? ?p?(?q?r) （蘊涵等值式） ?(?p??q)?r （結合律） ? ?(p?q)?r （德摩根律） ?(p?q)?r （蘊涵等值式 例4 證明: p?(q?r) (p?q)?r 方法一 真值表法（見例2） 方法二 觀察法.容易看出000使左邊成真, 使右邊成假.方法三 先用等值演算化簡公式, 再觀察.例5 用等值演算法判斷下列公式的類型(1)q??(p?q)解 q??(p?q) ? q??(?p?q) （蘊涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交換律，結合律） ? p?0 （矛盾律） ? 0 （零律）該式為矛盾式.(2)(p?q)?(?q??p)解 (p?q)?(?q??p) ?(?p?q)?(q??p) （蘊涵等值式） ?(?p?q)?(?p?q) （交換律） ? 1 該式為重言式.(3)((p?q)?(p??q))?r) 解 ((p?q)?(p??q))?r) ?(p?(q??q))?r （分配律） ? p?1?r （排中律） ? p?r （同一律） 非重言式的可滿足式.如101是它的成真賦值,000是它的 成假賦值.例1 求?(p?q)??r 的析取范式與合取范式 解 ?(p?q)??r ? ?(?p?q)??r ?(p??q)??r 析取范式 ?(p??r)?(?q??r) 合取范式 注意: 公式的析取范式與合取范式不惟一.例1(續)求?(p?q)??r 的主析取范式與主合取范式 解(1)?(p?q)??r ?(p??q)??r p??q ?(p??q)?1 同一律 ?(p??q)?(?r?r) 排中律 ?(p??q??r)?(p??q?r) 分配律 ? m4?m5 ?r ?(?p?p)?(?q?q)??r 同一律, 排中律 ?(?p??q??r)?(?p?q??r)?(p??q??r)?(p?q??r) ? m0? m2? m4? m6 得 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6 可記作 ? ?(0,2,4,5,6)(2)?(p?q)??r ?(p??r)?(?q??r) p??r ? p?0??r 同一律 ? p?(q??q)??r 矛盾律 分配律 ?(p?q??r)?(p??q??r) 分配律 ? M1?M3 ?q??r ?(p??p)??q??r 同一律, 矛盾律 ?(p??q??r)?(?p??q??r) 分配律 ? M3?M7 得 ?(p?q)??r ? M1?M3?M7 可記作 ? ?(1,3,7)例2(1)求 A ?(?p?q)?(?p??q?r)?r的主析取范式 解 用快速求法 (1)?p?q ?(?p?q??r)?(?p?q?r)? m2? m3 ?p??q?r ? m1 r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1? m3? m5? m7 得 A? m1? m2? m3? m5? m7 ? ?(1,2,3,5,7)(2)求 B? ?p?(p?q??r)的主合取范式 解 ?p ?(?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1 得 B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7)例3 用主析取范式判斷公式的類型:(1)A? ?(p?q)?q (2)B? p?(p?q) (3)C?(p?q)?r 解(1)A ? ?(? p?q)?q ?(p??q)?q ? 0 矛盾式(2)B ? ? p?(p?q)? 1 ? m0?m1?m2?m3 重言式(3)C ? ?(p?q)?r ?(?p??q)?r ?(?p??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r) ? m0?m1?m3? m5?m7 非重言式的可滿足式 例4 用主析取范式判斷下面2組公式是否等值:(1)p與(?p?q)?(p?q)解 p ? p?(?q?q)?(p??q)?(p?q)? m2?m3 (?p?q)?(p?q)? ?(?p?q)?(p?q) ?(p??q)?(p?q)? m2?m3 故 p ?(?p?q)?(p?q)(2)(p?q)?r 與 p?(q?r)解(p?q)?r ?(p?q??r)?(p?q?r) ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5? m6?m7 p?(q?r)?(p?q)?(p? r) ?(p?q??r)?(p?q?r)?(p??q?r)?(p?q?r) ? m5? m6?m7 故 (p?q)?r p?(q?r)例5 某單位要從A,B,C三人中選派若干人出國考察, 需滿 足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案? 解 記p:派A去, q:派B去, r:派C去 (1)p?r，(2)q??r，(3)(p??q)?(?p?q)求下式的成真賦值 A=(p?r)?(q??r)?((p??q)?(?p?q))例6 求A=(?p??q?r)?(?p?q?r)?(p?q?r)的主合取范式 解 A ? m1?m3?m7 ? M0?M2?M4?M5?M6 例1 判斷下面推理是否正確:(1)若今天是1號, 則明天是5號.今天是1號.所以, 明天是5號.解 設 p: 今天是1號, q: 明天是5號 推理的形式結構為 (p?q)ùp?q 證明 用等值演算法 (p?q)ùp?q ? ?((?púq)ùp)úq ?((pù?q)ú?p)úq ? ?pú?qúq ? 1 得證推理正確 (2)若今天是1號, 則明天是5號.明天是5號.所以, 今天是1號.解 設p: 今天是1號, q: 明天是5號.推理的形式結構為 (p?q)ùq?p 證明 用主析取范式法 (p?q)ùq?p ?(?púq)ùq?p ? ?((?púq)ùq)úp ? ?qúp ?(?pù?q)ú(pù?q)ú(pù?q)ú(pùq) ? m0úm2úm3 01是成假賦值, 所以推理不正確.例2 在自然推理系統P中構造下面推理的證明: 前提: púq, q?r, p?s, ?s 結論: rù(púq)證明 ① p?s 前提引入 ② ? s 前提引入 ③ ? p ①②拒取式 ④ púq 前提引入 ⑤ q ③④析取三段論 ⑥ q?r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ rù(púq) ⑦④合取 推理正確, rù(púq)是有效結論 例3 構造推理的證明: 若明天是星期一或星期三, 我就有 課.若有課, 今天必需備課.我今天下午沒備課.所以, 明天 不是星期一和星期三.解 設 p:明天是星期一, q:明天是星期三，r:我有課，s:我備課 前提:(púq)?r, r?s, ?s 結論: ?pù?q 例4 構造下面推理的證明: 前提: ?púq, ?qúr, r?s 結論: p?s 證明 ① p 附加前提引入 ② ?púq 前提引入 ③ q ①②析取三段論 ④ ?qúr 前提引入 ⑤ r ③④析取三段論 ⑥ r?s 前提引入 ⑦ s ⑤⑥假言推理 推理正確, p?s是有效結論 例5 構造下面推理的證明 前提: ?(pùq)úr, r?s, ?s, p 結論: ?q 證明 用歸繆法 ① q 結論否定引入 ② r?s 前提引入 ③ ?s 前提引入 ④ ?r ②③拒取式 ⑤ ?(pùq)úr 前提引入 ⑥ ?(pùq) ④⑤析取三段論 ⑦ ?pú?q ⑥置換 ⑧ ?p ①⑦析取三段論 ⑨ p 前提引入 ⑩ ?pùp ⑧⑨合取 推理正確, ?q是有效結論 例6 用歸結證明法構造下面推理的證明: 前提:(p?q)?r, r?s, ?s 結論:(p?q)?(pùs)解 (p?q)?r ? ?(?púq)úr ?(pù?q)úr ?(púr)ù(?qúr) r?s ? ?rús ? (p?q)?(pùs)? ?(?púq)ú(pùs)?(pù?q)ú(pùs)? ? pù(?qús)推理可表成 前提: púr, ?qúr, ?rús, ?s 結論: pù(?qús) 第3章 一階邏輯 例1(1)4是偶數 4是個體常項, “是偶數”是謂詞常項, 符號化為: F(4)(2)小王和小李同歲 小王, 小李是個體常項, 同歲是謂詞常項.記a:小王，b: 小李, G(x,y): x與y同歲, 符號化為: G(a,b)(3)x< y x,y是命題變項, < 是謂詞常項, 符號化為: L(x,y)(4)x具有某種性質P x是命題變項, P是謂詞變項, 符號化為: P(x)例2 將下述命題用0元謂詞符號化, 并討論它們的真值:(1) 是無理數, 而 是有理數(2)如果2>3，則3<4 解 (1)設F(x): x是無理數, G(x): x是有理數 符號化為 真值為0(2)設 F(x,y): x>y, G(x,y): x 個體域分別取(a)人類集合,(b)全總個體域.解:(a)(1)設F(x): x愛美，符號化為 ?x F(x) (2)設G(x): x用左手寫字，符號化為 ?x G(x) (b)設M(x): x為人，F(x), G(x)同(a)中 (1)?x(M(x)?F(x)) (2)? x(M(x)?G(x))M(x)稱作特性謂詞 例4 將下列命題符號化, 并討論其真值:(1)對任意的x, 均有x2-3x+2=(x-1)(x-2)(2)存在x, 使得x+5=3 分別取(a)個體域D1=N,(b)個體域D2=R 解 記F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3(a)(1)?x F(x) 真值為1 (2)?x G(x) 真值為0(b)(1)?x F(x) 真值為1 (2)?x G(x) 真值為1 例5 將下面命題符號化:(1)兔子比烏龜跑得快 (2)有的兔子比所有的烏龜跑得快(3)并不是所有的兔子都比烏龜跑得快(4)不存在跑得一樣快的兔子和烏龜 解 用全總個體域，令F(x): x是兔子, G(y): y是烏龜，H(x,y): x比y跑得快，L(x,y): x和y跑得一樣快(1)?x?y(F(x)?G(y)?H(x,y))(2)?x(F(x)?(?y(G(y)?H(x,y)))(3)? ?x?y(F(x)?G(y)?H(x,y))(4)? ?x?y(F(x)?G(y)?L(x,y))例6 公式 ?x(F(x,y)??yG(x,y,z))?x的轄域:(F(x,y)??yG(x,y,z))，指導變元為x ?y的轄域:G(x,y,z)，指導變元為y x的兩次出現均為約束出現 y的第一次出現為自由出現, 第二次出現為約束出現 z為自由出現.例7 公式 ?x(F(x)??xG(x))?x的轄域:(F(x)??xG(x))，指導變元為x ?x的轄域:G(x)，指導變元為x x的兩次出現均為約束出現.但是, 第一次出現的x是?x中 的x, 第二次出現的x是?x中的x.例8 給定解釋I 如下: (a)個體域 D=N (b) (c) (d)謂詞 說明下列公式在 I 下的含義, 并討論其真值 (1)?xF(g(x,a),x)?x(2x=x) 假命題 (2)?x?y(F(f(x,a),y)?F(f(y,a),x))?x?y(x+2=y?y+2=x) 假命題(3)?x?y?zF(f(x,y),z) ?x?y?z(x+y=z) 真命題 (4)?xF(f(x,x),g(x,x)) ?x(2x=x2) 真命題(5)F(f(x,a), g(x,a))x+2=2x 不是命題 (6)?x(F(x,y)?F(f(x,a), f(y,a)))?x(x=y?x+2=y+2) 真命題 例8(1)~(4)都是閉式, 在I下全是命題.(5)和(6)不是閉式, 在I下(5)不是命題,(6)是命題 例9 判斷下列公式的類型:(1)?x(F(x)?G(x))取解釋I1, D1=R，:x是整數，:x是有理數, 取解釋I2, D2=R，:x是整數，:x是自然數, 非永真式的可滿足式(2)?(?xF(x))?(?xF(x)) 這是 ?p?p 的代換實例, ?p?p是重言式，永真式(3)?(?xF(x)??yG(y))? ?yG(y)這是?(p?q)?q的代換實例, ?(p?q)?q是矛盾式 矛盾式 例1 消去公式中既約束出現、又自由出現的個體變項 真命題 假命題 (1)?xF(x,y,z)? ?yG(x,y,z)? ?uF(u,y,z)? ?yG(x,y,z) 換名規則 ? ?uF(u,y,z)? ?vG(x,v,z) 換名規則 或者 ? ?xF(x,u,z)? ?yG(x,y,z) 代替規則 ? ?xF(x,u,z)? ?yG(v,y,z) 代替規則(2)?x(F(x,y)? ?yG(x,y,z))? ?x(F(x,y)? ?tG(x,t,z)) 換名規則 或者 ? ?x(F(x,t)? ?yG(x,y,z)) 代替規則 例2 設個體域D={a,b,c}, 消去下面公式中的量詞:(1)?x(F(x)?G(x))?(F(a)?G(a))?(F(b)?G(b))?(F(c)?G(c))(2)?x(F(x)??yG(y))? ?xF(x)??yG(y) 量詞轄域收縮 ?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))(3)?x?yF(x,y)? ?x(F(x,a)?F(x,b)?F(x,c))?(F(a,a)?F(a,b)?F(a,c))?(F(b,a)?F(b,b)?F(b,c)) ?(F(c,a)?F(c,b)?F(c,c))例3 給定解釋I:(a)D={2,3},(b) (c) :x是奇數，: x=2 ? y=2，: x=y.在I下求下列各式的真值:(1)?x(F(f(x))?G(x, f(x))) 解 (F(f(2))?G(2, f(2)))?(F(f(3))?G(3, f(3)))?(1?1)?(0?1)? 1(2)?x?yL(x,y)解 ?yL(2,y)??yL(3,y)?(L(2,2)?L(2,3))?(L(3,2)?L(3,3))?(1?0)?(0?1)? 0 例4 證明下列等值式: ? ?x(M(x)?F(x))? ?x(M(x)? ?F(x))證 左邊 ? ?x ?(M(x)?F(x)) 量詞否定等值式 ? ?x(?M(x)??F(x))? ?x(M(x)? ?F(x))例5 求公式的前束范式(1)?xF(x)???xG(x)解 ? ?xF(x)??x?G(x) 量詞否定等值式 ? ?x(F(x)??G(x)) 量詞分配等值式 解2 ? ?xF(x)???yG(y) 換名規則 ? ?xF(x)??y?G(y) 量詞否定等值式 ? ?x(F(x)??y?G(y)) 量詞轄域擴張 ? ?x?y(F(x)??G(y)) 量詞轄域擴張 第4章 關系 例1 <2,x+5>=<3y?4,y>，求 x, y.解 3y?4=2, x+5=y ? y=2, x= ?3 例2 A={0, 1}, B={a, b, c} A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} B?A ={ A = {?}, B = ? P(A)?A = {, <{?},?>} P(A)?B = ? 例3 (1)R={ ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2)C={ R={ |A|=n, |B|=m, |A×B|=nm, A×B 的子集有 個.所以從A到B有 元關系.|A|=n, A上有 不同的二元關系.例如 |A|=3, 則 A上有512個不同的二元關系.例 5A={a, b, c, d}, R={ ??1110??1000???0000???0100??例1 R={ domR = ranR = fldR = 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R?1 = R°S = S°R = 個不同的二 例3 設A = {a, b, c, d}, R = { ?0100??0100??01 ???1010??1010102???M?? M???0001??0001??00 ?????00000000???00?? 例1 A = {a, b, c}, R1, R2, R3 是 A上的關系, 其中 R1 = { 00??1?010????01??0??00??0010?101??000??000?R2自反, R3 反自反, R1既不自反也不反自反.例2 設A＝{a,b,c}, R1, R2, R3和R4都是A上的關系, 其中 R1＝{ R1＝{ R2＝{ R3＝{ 證明若 IA ?R，則 R 在 A 上自反.證 任取x，x?A ? 因此 R 在 A 上是自反的.例5 證明若 R=R?1 , 則 R 在A上對稱.證 任取 因此 R 在 A 上是對稱的.例6 證明若 R∩R?1?IA , 則 R 在 A 上反對稱.證 任取 ? 因此 R 在 A 上是反對稱的.例7 證明若 R°R?R , 則 R 在 A 上傳遞.證 任取 因此 R 在 A 上是傳遞的.例8 判斷下圖中關系的性質, 并說明理由 (1)不自反也不反自反；對稱, 不反對稱；不傳遞.(2)反自反, 不是自反；反對稱, 不是對稱；傳遞.(3)自反，不是反自反；反對稱，不是對稱；不傳遞.例1 設A={a,b,c,d}, R={ 例1 設 A={1, 2, …, 8}, 如下定義 A上的關系R： R={ ?x?A, 有x≡x(mod 3) ?x,y?A, 若x≡y(mod 3), 則有y≡x(mod 3) ?x,y,z?A, 若x≡y(mod 3), y≡z(mod 3), 則有 x≡z(mod 3)例2 令A={1, 2, …, 8}，A關于模 3 等價關系R 的商集為 A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A關于恒等關系和全域關系的商集為： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} } 例3 設A＝{a, b, c, d}, 給定? 1, ? 2, ? 3, ? 4, ? 5, ? 6如下： ? 1={{a, b, c},jdb3l39rxn9}，? 2={{a, b},{c},jdb3l39rxn9} ? 3={{a},{a, b, c, d}}，? 4={{a, b},{c}} ? 5={?,{a, b},{c, d}}，? 6={{a,{a}},{b, c, d}} 則? 1和? 2是A的劃分, 其他都不是A的劃分.例4 給出A＝{1,2,3}上所有的等價關系 求解思路：先做出A的所有劃分, 然后根據劃分寫出 對應的等價關系.A上的等價關系與劃 分之間的對應： ? 4對應于全域關系EA ? 5對應于恒等關系IA ? 1, ? 2和? 3分別對應于等價關系 R1, R2和R3.其中 R1={<2,3>,<3,2>}∪IA R2={<1,3>,<3,1>}∪IA R3={<1,2>,<2,1>}∪IA 例5 設A={1,2,3,4}，在A?A上定義二元關系 R： < A?A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>，<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>，<4,4>} 根據有序對 例6 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> 例7 已知偏序集 R={ 例8 設偏序集 例1 設A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , f7 }, 其中 f0={<1,a>,<2,a>,<3,a>} f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>} f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>} f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>} f7={<1,b>,<2,b>,<3,b>} 例2 判斷下面函數是否為單射, 滿射, 雙射的, 為什么?（1）f : R→R, f(x)= ?x2+2x?1（2）f : Z+→R, f(x)=lnx, Z+為正整數集（3）f : R→Z, f(x)=?x?（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+為正實數集.解(1)f : R→R, f(x)= ?x2+2x?1 在x=1取得極大值0.既不是單射也不是滿射的.(2)f : Z+→R, f(x)=lnx 單調上升, 是單射的.但不滿射, ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= ?x? 是滿射的, 但不是單射的, 例如 f(1.5)=f(1.2)=1.(4)f : R→R, f(x)=2x+1 是滿射、單射、雙射的, 因為它是單調函數并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x 有極小值f(1)=2.該函數既不是單射的也不是滿射的.例3 A=P({1,2,3}), B={0,1}{1,2,3} 解 A={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={ f0, f1, … , f7 }, 其中 f0={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>}，f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>}，f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}.令 f : A→B，f(?)=f0, f({1})=f1, f({2})=f2, f({3})=f3，f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4 A=[0,1] B=[1/4,1/2] 構造雙射 f : A→B解 令 f : [0,1]→[1/4,1/2] f(x)=(x+1)/4 例5 A=Z, B=N，構造雙射 f : A→B 將Z中元素以下列順序排列并與N中元素對應： Z：0?11 ?22?33 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N：0 1 2 4 5 6 … 則這種對應所表示的函數是： x?0?2xf:Z?N,f(x)????2x?1x?0例1 設 f : R→R, g : R→R ?x2x?3f(x)?? x?3??2 g(x)?x?2 求 f °g, g°f.如果 f 和 g 存在反函數, 求出它們的反函數.解 f?g:R?R?x2?2x?3f?g(x)??x?3?0g?f:R?R?(x?2)2g?f(x)????2x?1x?1 f : R→R不存在反函數；g : R→R的反函數是 g?1: R→R, g?1(x)=x?2 第6章 圖 例1 下述2組數能成為無向圖的度數列嗎?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇數個奇數.(2)能 例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數均小 于等于2, 問G至少有多少個頂點? 解 設G有n個頂點.由握手定理，4?3+2?(n-4)?2?10 解得 n?8 例3 已知5階有向圖的度數列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 證明不存在具有奇數個面且每個面都具有奇數條棱的 多面體.證 用反證法.假設存在這樣的多面體, 作無向圖G= 討論所有可能的情況.設有a個5度頂點和b個6度頂點(1)a=0, b=9; (2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)~(3)至少5個6度頂點,(4)和(5)至少6個5度頂點 方法二 假設b<5, 則a>9-5=4.由握手定理的推論, a ? 6 例6 畫出4階3條邊的所有非同構的無向簡單圖 解 總度數為6, 分配給4個頂點, 最大度為3, 且奇度頂點數 為偶數, 有下述3個度數列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,3 1,1,2,2 例7 畫出3個以1,1,1,2,2,3為度數列的非同構的無向簡單圖 0,2,2,2 例1 右圖有 個面 R1的邊界:a R2的邊界:bce R3的邊界:fg R0的邊界:abcdde, fg deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右邊2個圖是同一平面圖的平面嵌入.R1在(1)中是外部面, 在(2)中是內部面;R2在(1)中是內部面, 在(2)中是外部面.R3 R1 R3 R2(1) R2 R1(2) 說明:(1)一個平面圖可以有多個不同形式的平面嵌入, 它們都同構.(2)可以通過變換(測地投影法)把平面圖的任何一面作為外部面 例3 證明 K5 和 K3,3不是平面圖 證 K5 : n=5, m=10, l=3 K3,3 : n=6, m=9, l=4 不滿足定理6.15的條件 例 5證明下面2個圖均為非平面圖.與K3,3同胚也可收縮到K3,3 與K5同胚也可收縮到K5 例6 畫出所有非同構的6階11條邊的簡單連通非平面圖 解 在K5(5階10條邊)上加一個頂點和一條邊 在K3,3(6階9條邊)上加2條邊 例1 某中學有3個課外活動小組:數學組, 計算機組和生物組.有趙,錢,孫,李,周5名學生, 問分別在下述3種情況下, 能否選出3人各任一個組的組長?(1)趙, 錢為數學組成員, 趙,孫,李為計算機組成員, 孫,李,周為生物組成員.(2)趙為數學組成員, 錢,孫,李為計算機組成員, 錢,孫,李,周為生物組成員.(3)趙為數學組和計算機組成員, 錢,孫,李,周為生物組成員.解 數 計 生 數 計 生 趙 錢 孫 李 周 趙 錢 孫 李 周 (1(數 計 生 趙 錢 孫 李 周 (3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖: (a(b(c) (c)中存在哈密頓通路 例3 證明右圖不是哈密頓圖 證 假設存在一條哈密頓回路, a,f,g是2度頂點, 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點c出現3次, 矛盾.a b c f d e g 此外, 該圖滿足定理6.10的條件, 這表明此條件是必要、而不充分的.又, 該圖有哈密頓通路.例4 有7個人, A會講英語, B會講英語和漢語, C會講英語、意大利語和俄語, D會講日語和漢語, E會講德語和意大利語, F會講法語、日語和俄語, G會講法語和德語.問能否將他們沿圓桌安排就坐成一圈, 使得每個人都能與兩旁的人交談? 解 作無向圖, 每人是一個頂點, 2人之間有邊?他們有共同的語言.G F E D A B C ACEGFDBA是一條哈密頓回路,按此順序就坐即可. 離散數學試題（A卷答案） 一、（10分） （1）證明(P?Q)∧(Q?R)?(P?R)（2）求(P∨Q)?R的主析取范式與主合取范式，并寫出其相應的成真賦值和成假賦值。解：（1）因為((P?Q)∧(Q?R))?(P?R)??((?P∨Q)∧(?Q∨R))∨(?P∨R)?(P∧?Q)∨(Q∧?R)∨?P∨R ?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R))?(P∧?Q)∨(Q∨?P∨R)?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R)?T 所以，(P?Q)∧(Q?R)?(P?R)。 （2）(P∨Q)?R??(P∨Q)∨R?(?P∧?Q)∨R ?(?P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R)?M2∧M4∧M6 ?m0∨m1∨m3∨m5 所以，其相應的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。 二、（10分）分別找出使公式?x(P(x)??y(Q(y)∧R(x，y)))為真的解釋和為假的解釋。 解：設論域為{1，2}。 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((F∧F)∨(F∧F)))∧(T?((F∧F)∨(F∧F)))?(T?F)∧(T?F)?F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((T∧T)∨(T∧T)))∧(T?((T∧T)∨(T∧T)))?(T?T)∧(T?T)?T 三、（10分） 在謂詞邏輯中構造下面推理的證明：每個喜歡步行的人都不喜歡做汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。 解 論域：所有人的集合。A(x)：x喜歡步行；B(x)：x喜歡坐汽車；C(x)：x喜歡騎自行車；則推理化形式為： ?x(A(x)??B(x))，?x(B(x)∨C(x))，??xC(x)?x?A(x)下面給出證明：(1)??xC(x) P(2)?x?C(x) T(1)，E(3)?C(c) T(2)，ES(4)?x(B(x)∨C(x)) P(5)B(c)∨C(c) T(4)，US(6)B(c) T(3)(5)，I(7)?x(A(x)??B(x)) P(8)A(c)??B(c) T(7)，US(9)?A(c) T(6)(8)，I(10)?x?A(x) T(9)，EG 四、（10分） 下列論斷是否正確？為什么？(1)若A∪B＝A∪C，則B＝C。(2)若A∩B＝A∩C，則B＝C。(3)若A?B＝A?C，則B＝C。 解(1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，則A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，則A∩B＝A∩C，但B＝C不成立。(3)成立。因為若A?B＝A?C，對任意的x∈B，當x∈A時，有x∈A∩B?x?A?B?x?A?C＝(A∪C)－(A∩C)?x∈A∩C?x∈C，所以B?C；當x?A時，有x?A∩B，而x∈B?x∈A∪B，所以x∈A∪B－A∩B＝A?B?x∈A?C，但x? A，于是x∈C，所以B?C。 同理可證，C ?B。 因此，當A?B＝A?C時，必有B＝C。 五、（10分）若R是集合A上的自反和傳遞關系，則對任意的正整數n，R＝R。 證明 當n＝1時，結論顯然成立。設n＝k時，Rk＝R。當n＝k＋1時，Rk+1＝Rk*R＝R*R。下面由R是自反和傳遞的推導出R*R＝R即可。 由傳遞性得R*R?R。另一方面，對任意的 由數學歸納法知，對任意的正整數n，Rn＝R。 n 六、（15分）設函數f：R×R?R×R，f定義為：f( (1)證明f是單射。(2)證明f是滿射。(3)求逆函數f。 (4)求復合函數f－1?f和f?f。 證明(1)對任意的x，y，x1，y1∈R，若f( (2)對任意的 1，y＝ u?w2，則f( u?w2＋ u?w2，u?w2－>＝ u?w2－1(3)f( x?y?x?y2x?y?(x?y)2(4)f?f( 七、（15分）設X＝{1，2，3，4}，R是X上的二元關系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關系圖。(2)寫出R的關系矩陣。 (3)說明R是否是自反、反自反、對稱、傳遞的。解(1)R的關系圖如圖所示：(2)R的關系矩陣為： ?1??0M(R)??1??1?101110110??0? 0??0??(3)對于R的關系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的； 經過計算可得 ?1??02M(R)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0?? 八、（10分）若 對于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因為H是G非空子集，所以*在H上滿足結合律。綜上可知， 九、（10分）給定二部圖G＝ 證明 設|V1|＝m1，則|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22 2－ 1－1 －1 m12。因為(m2?m1)2?0，即4?mm1?m1，所以n≤m2/4。離散數學試題（B卷答案） 一、（20分）用公式法判斷下列公式的類型：(1)(?P∨?Q)?(P??Q)(2)(P?Q)?(P∧?(Q∨?R))解：（1）因為(?P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q) ?(P∧Q)∨(P∧?Q)∨(?P∧Q)?m1∨m2∨m3 ?M0 所以，公式(?P∨?Q)?(P??Q)為可滿足式。 （2）因為(P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1 ?m2∨m3∨m4∨m5∨m6∨m7 所以，公式(P?Q)?(P∧?(Q∨?R))為可滿足式。 二、（15分）在謂詞邏輯中構造下面推理的證明：每個科學家都是勤奮的，每個勤奮又身體健康的人在事業中都會獲得成功。存在著身體健康的科學家。所以，存在著事業獲得成功的人或事業半途而廢的人。 Q(x)：x是勤奮的；x是科學家；C(x)：解：論域：所有人的集合。H(x)：x是身體健康的；S(x)：x是事業獲得成功的人；F(x)：x是事業半途而廢的人；則推理化形式為： ?x(S(x)?Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧H(x)) ?x(C(x)∨F(x))下面給出證明： (1)?x(S(x)∧H(x)) P(2)S(a)∧H(a) T(1)，ES(3)?x(S(x)?Q(x)) P(4)S(a)?Q(a) T(1)，US(5)S(a) T(2)，I(6)Q(a) T(4)(5)，I(7)H(a) T(2)，I(8)Q(a)∧H(a) T(6)(7)，I(9)?x(Q(x)∧H(x)?C(x)) P(10)Q(a)∧H(a)?C(a) T(9)，Us(11)C(a) T(8)(10)，I(12)?xC(x) T(11)，EG(13)?x(C(x)∨F(x)) T(12)，I 三、（10分）設A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}} 四、（15分）設R和S是集合A上的任意關系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對稱的，則R*S也是對稱的。(4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則R∩S是自反的。(6)若R和S是傳遞的，則R∪S是傳遞的。 解 (1)成立。對任意的a∈A，因為R和S是自反的，則 (2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，則R和S是反自反的，但R*S＝{<1，1>}不是反自反的。 (3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，則R和S是對稱的，但R*S＝{<1，3>，<3，2>}不是對稱的。 (4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，則R和S是傳遞的，但R*S＝{<1，3>，<1，1>，<2，1>}不是傳遞的。 (5)成立。對任意的a∈A，因為R和S是自反的，則 五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。問(1)有多少個不同的由X到Y的函數？ (2)當n、m滿足什么條件時，存在單射，且有多少個不同的單射？(3)當n、m滿足什么條件時，存在雙射，且有多少個不同的雙射？ 解 (1)由于對X中每個元素可以取Y中任一元素與其對應，每個元素有n種取法，所以不同的函數共n個。 (2)顯然當|m|≤|n|時，存在單射。由于在Y中任選m個元素的任一全排列都形成X到Y的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個。 (3)顯然當|m|＝|n|時，才存在雙射。此時Y中元素的任一不同的全排列都形成X到Y的不同的雙射，mm故不同的雙射有m!個。 六、（5分）集合X上有m個元素，集合Y上有n個元素，問X到Y的二元關系總共有多少個？ 解 X到Y的不同的二元關系對應X×Y的不同的子集，而X×Y的不同的子集共有個2mn，所以X到Y的二元關系總共有2mn個。 七、（10分）若 證明 設e是群 若x?∈G也是a*x＝b的解，則x?＝e*x?＝(a*a)*x?＝a*(a*x?)＝a*b＝x。所以，x＝a*b是a*x － 1－1 －1 －1＝b的惟一解。 八、（10分）給定連通簡單平面圖G＝ 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝24。若存在f∈ f?FF，使得d(f)＞3，則3|F|＜2|E|＝24，于是|F|＜8，與|F|＝8矛盾。故對任意f∈F，d(f)＝3。 學習體會 專業：計算機 姓名：范文芳 學號： 成績： 院校： 離散數學是計算機科學與技術專業的基礎核心課程。通過本課程的學習，使學生具有現代數學的觀點和方法，并初步掌握處理離散結構所必須的描述工具和方法。同時，也要培養學生抽象思維和慎密概括的能力，使學生具有良好的開拓專業理論的素質和使用所學知識，分析和解決實際問題的能力，為學生以后學習計算機基礎理論與專業課程打下良好的基礎。 學習離散數學有兩項最基本的任務：其一是通過學習離散數學，使學生了解和掌握在后續課程中要直接用到的一些數學概念和基本原理，掌握計算機中常用的科學論證方法，為后續課程的學習奠定一個良好的數學基礎；其二是在離散數學的學習過程中，培訓自學能力、抽象思維能力和邏輯推理能力，以提高專業理論水平。因此學習離散數學對于計算機、通信等專業后續課程的學習和今后從事計算機科學等工作是至關重要的。但是由于離散數學的離散性、知識的分散性和處理問題的特殊性，使部分學生在剛剛接觸離散數學時，對其中的一些概念和處理問題的方法往往感到困惑，特別是在做證明題時感到無從下手，找不到正確的解題思路。因此，對離散數學的學習方法給予適當的指導和對學習過程中遇到的一些問題分析是十分必要的。 一、認知離散數學 離散數學是計算機科學基礎理論的核心課程之一，是計算機及應用、通信等專業的一門重要的基礎課。它以研究量的結構和相互關系為主要目標，其研究對象一般是有限個或可數個元素，充分體現了計算機科學離散性的特點。學習離散數學的目的是為學習計算機、通信等專業各后續課程做好必要的知識準備，進一步提高抽象思維和邏輯推理的能力，為計算機的應用提供必要的描述工具和理論 基礎。 1．定義和定理多 離散數學是建立在大量定義、定理之上的邏輯推理學科，因此對概念的理解是學習這門課程的核心。在學習這些概念的基礎上，要特別注意概念之間的聯系，而描述這些聯系的實體則是大量的定理和性質。在考試中有一部分內容是考查學生對定義和定理的識記、理解和運用，因此要真正理解離散數學中所給出的每個基本概念的真正的含義。比如，命題的定義、五個基本聯結詞、公式的主析取范式和主合取范式、三個推理規則以及反證法；集合的五種運算的定義；關系的定義和關系的四個性質；函數（映射）和幾種特殊函數（映射）的定義；圖、完全圖、簡單圖、子圖、補圖的定義；圖中簡單路、基本路的定義以及兩個圖同構的定義；樹與最小生成樹的定義。掌握和理解這些概念對于學好離散數學是至關重要的。2.方法性強 在離散數學的學習過程中，一定要注重和掌握離散數學處理問題的方法，在做題時，找到一個合適的解題思路和方法是極為重要的。如果知道了一道題用怎樣的方法去做或證明，就能很容易地做或證出來。反之，則事倍功半。在離散數學中，雖然各種各樣的題種類繁多，但每類題的解法均有規律可循。所以在聽課和平時的復習中，要善于總結和歸納具有規律性的內容。在平時的講課和復習中，老師會總結各類解題思路和方法。作為學生，首先應該熟悉并且會用這些方法，同時，還要勤于思考，對于一道題，進可能地多探討幾種解法。3.抽象性強 離散數學的特點是知識點集中，對抽象思維能力的要求較高。由于這些定義的抽象性，使初學者往往不能在腦海中直接建立起它們與現實世界中客觀事物的聯系。不管是哪本離散數學教材，都會在每一章中首先列出若干個定義和定理，接著就是這些定義和定理的直接應用，如果沒有較好的抽象思維能力，學習離散數學確實具有一定的困難。因此，在離散數學的學習中，要注重抽象思維能力、邏輯推理能力的培養和訓練，這種能力的培養對今后從事各種工作都是極其重要的。 在學習離散數學中所遇到的這些困難，可以通過多學、多看、認真分析講課 中所給出的典型例題的解題過程，再加上多練，從而逐步得到解決。在此特別強調一點：深入地理解和掌握離散數學的基本概念、基本定理和結論，是學好離散數學的重要前提之一。所以，同學們要準確、全面、完整地記憶和理解所有這些基本定義和定理。4.內在聯系性 離散數學的三大體系雖然來自于不同的學科，但是這三大體系前后貫通，形成一個有機的整體。通過認真的分析可尋找出三大部分之間知識的內在聯系性和規律性。如：集合論、函數、關系和圖論，其解題思路和證明方法均有相同或相似之處。 二、認知解題規范 一般來說，離散數學的考試要求分為：了解、理解和掌握。了解是能正確判別有關概念和方法；理解是能正確表達有關概念和方法的含義；掌握是在理解的基礎上加以靈活應用。為了考核學生對這三部分的理解和掌握的程度，試題類型一般可分為：判斷題、填空題、選擇題、計算題和證明題。判斷題、填空題、選擇題主要涉及基本概念、基本理論、重要性質和結論、公式及其簡單計算；計算題主要考核學生的基本運用技能和速度，要求寫出完整的計算過程和步驟；證明題主要考查應用概念、性質、定理及重要結論進行邏輯推理的能力，要求寫出嚴格的推理和論證過程。 學習離散數學的最大困難是它的抽象性和邏輯推理的嚴密性。在離散數學中，假設讓你解一道題或證明一個命題，你應首先讀懂題意，然后尋找解題或證明的思路和方法，當你相信已找到了解題或證明的思路和方法，你必須把它嚴格地寫出來。一個寫得很好的解題過程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經過簡單的推理而得到的。仔細地寫解題過程或證明是很重要的，既能讓讀者理解它，又能保證解題過程或證明準確無誤。一個好的解題過程或證明應該是條理清楚、論據充分、表述簡潔的。針對這一要求，在講課中老師會提供大量的典型例題供同學們參考和學習。 通過離散數學的學習和訓練，能使同學們學會在離散數學中處理問題的一般性的規律和方法，一旦掌握了離散數學中這種處理問題的思想方法，學習和掌握離散數學的知識就不再是一件難事了。復習離散數學的整個過程可大致分為三個 階段。 第一階段，大量進行知識儲備的階段。 離散數學是建立在大量定義上面的邏輯推理學科。因而對概念的理解是我們學習這門學科的核心。由于這些定義非常抽象，初學者往往不能在腦海中建立起它們與現實世界中客觀事物的聯系。對于跨專業自學的朋友來說更是如此。這是離散數學學習中的第一個困難。因此，對于第一遍復習，我們提出一個最為重要的要求，即準確、全面、完整地記憶所有的定義和定理。具體做法可以是：在進行完一章的學習后，用專門的時間對該章包括的定義與定理實施強記，直到能夠全部正確地默寫出來為止。無須強求一定要理解，記住并能準確復述 各定義定理是此階段的最高要求。也不需做太多的題（甚至不做課后習題也是可以的，把例題看懂就行），重心要放在對定義和定理的記憶上。請牢記，這是為未來的向廣度和深度擴張作必要的準備。 這一過程視各人情況不同耗時約在一到兩個月內。第二階段，深入學習，并大量做課后習題的階段。 這是最漫長的一個階段，耗時也很難估計，一般來說，若能熟練解出某一章75%以上的課后習題，可以考慮結束該章。 解離散數學的題，方法非常重要，如果拿到一道題，立即能夠看出它所屬的類型及關聯的知識點，就不難選用正確的方法將其解決，反之則事倍功半。例如在命題邏輯部分，無非是這么幾種題目：將自然語言表述的命題符號化，等價命題的相互轉化（包括化為主合取范式與主析取范式），以給出的若干命題為前提進行推理和證明。相應的對策也馬上就可以提出來。以推理題為例，主要是利用P、T規則，加上蘊涵和等價公式表，由給定的前提出發進行推演，或根據題目特點采用真值表法、CP規則和反證法。由此可見，在平常復習中，要善于總結和歸納，仔細體會題目類型和此類題目的解題套路。如此多作練習，則即使遇到比較陌生的題也可以較快地領悟其本質，從而輕松解出。 “熟讀唐詩三百首，不會做詩也會吟。”要是拿到一本習題集，從頭到尾做過，甚至背會的話。那么，在考場上就會發現絕大多數題見過或似曾相識。這時，要取得較好的成績也就不是太難的事情了。這一情況具有普遍性，對許多院校的考試都適用。 第三階段，進行真題模擬訓練，提高整體水平和綜合能力的階段。 這一階段從第二階段結束一直持續到考試。 除了我們使用的課本外，應盡可能地弄到報考院校的專業課歷年試題。因為每個單位對該科目的側重點畢竟有不同，從歷年試題中可以獲取許多有用的信息。這些歷年試題此時就有了巨大的作用。 第三章部分課后習題參考答案 14.在自然推理系統P中構造下面推理的證明：(2)前提：p?q,?(q?r),r 結論：?p(4)前提：q?p,q?s,s?t,t?r 結論：p?q 證明：（2） ①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p ⑤⑥拒取式 證明（4）： ①t?r 前提引入 ②t ①化簡律 ③q?s 前提引入 ④s?t 前提引入 ⑤q?t ③④等價三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取 15在自然推理系統P中用附加前提法證明下面各推理：(1)前提：p?(q?r),s?p,q 結論：s?r 證明 ①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統P中用歸謬法證明下面各推理： (1)前提：p??q,?r?q,r??s 結論：?p 證明： ①p 結論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡律 ⑥r?￢s 前提引入 ⑦r ⑥化簡律 ⑧r?﹁r ⑤⑦ 合取 由于最后一步r?﹁r 是矛盾式,所以推理正確. 集合論 1.A={?,1}，B={{a}}求A的冪集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x 4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b關于R的等價類。 5.R是A上的等價關系，A/R={{1,2}，{3}},求A，R。6.請分別判斷以下結論是否一定成立，如果一定成立請證明，否則請舉出反例。 ①如果A∪B?C，則A?C或者B?C。②如果A×B=A×C且A??，則B=C。 27.如果R是A上的等價關系，R,r(R)是否一定是A上的等價關系？證明或舉例。 8.已知A∩C?B∩C,A-C?B-C,證明：A?B。9.證明：AX(B∩C)=(AXB)∩(AXC)10.證明：P(A)∪P(B)?P(A∪B)-111.證明：R[sym] iff R=R -1212.證明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.證明：s(R∪S)=s(R)∪s(S)14.R是A上的關系，證明：如果R是對稱的，則r(R)也是對稱的。 15.I是整數集，R={(x,y)|x-y是3的倍數}，證明：R是I上的等價關系。 16.如果R是A上的等價關系，則A/R一定是A的劃分。17.R是集合A上的自反關系，S是A上的自反和對稱關系，證明t(R∪S)是A上的等價關系。18.I是正整數集合，R是I×I上的二元關系，R={< 19.f:A?B，R是B上的等價關系，令S={ 20.R是集合A上的自反關系，S是A上的自反和對稱關系，證明t(R∪S)是A上的等價關系。 21.P和Q都是集合A上的劃分，請問P∪Q，P-Q是否是A上的劃分，22.R?AXA,R[irref]且R[tra],證明：r(R)是A上的偏序關系。 23.畫出{1,2,3,4,6}上整除關系的哈斯圖，求{2,3,6}的4種元素。 24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),畫出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。 25.f:A→B,g:B→C都是單（滿）射，證明：復合映射gof一定是單（滿）射。 26.f:A→B,g:B→C，gof是單射，請問f和g是否一定是單射？請證明或舉出反例。27.R是實數集，f:R×R?R×R,f( 代數系統 1. 2.求 3.R是實數集，在R上定義運算*為x*y=x+y+xy,問： 5.R是實數集，R上的6運算定義如下：對R中元素x,y，f1( 6. 7.證明：如果群G中每個元素的逆元素都是它自已，則G是交換群。 8.循環群一定是交換群。 9.證明：階為素數的群一定是循環群。 -110. 11.整數集Z上定義運算*：對任意整數x和y,x*y=x+y-4,其中+，-為普通加減法。證明： 12.證明：如果群G中至少有兩個元素，則群中沒有零元。13.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分 14. 15.H，K都是群G的子群，請問H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的兩個子群，a?G, 試證：aH?aK當且僅當H?K。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請問(G,*)是否構成群？ n18. 19.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分 20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21. ++23.R為實數集，R為正實數集， 1.如何判斷二部圖？完全圖、完全二部圖的邊數。2.如何求E回路？ 3.Petersen圖是否為E圖或H圖。 4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時輪圖為H圖？ 6.如何求最小生成樹。 7.證明：奇數個頂點的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數個頂點的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。并由此證明K5不是平面圖。 11.證明：有6個頂點的簡單無向圖G和它的補圖中至少有一個三角形。 12.證明：在至少有兩個頂點的無向樹中，至少有2個一度頂點。 13.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？ 14.證明：簡單無向圖G和它的補圖中至少有一個是連通圖。15.證明：無向圖中奇度點（度數為奇數的點）有偶數個。16.證明：n個頂點的無向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點集，證明：對任意頂點集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數目。18.一棵無向樹有3個3次點，1個頂點次數為2，其余頂點次數為1，問它有幾個次數為1的頂點？寫出求解過程。19.證明：每個簡單平面圖都包含一個次至多為5的頂點。20.連通平面圖G有n個頂點，m條邊和f個面，證明：n-m+f=2。21.如果圖G的最大頂點次數≤ρ，證明：G是ρ+1可點著色的。 22.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？ 23.如果一個簡單圖G和它的補圖同構，則稱G是自補圖，求所有4個頂點自補圖。 24.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。如果G中無三角形，則m?2n-4。數理邏輯 1.如果今天是星期一，則要進行英語或數理邏輯考試。 沒有不犯錯誤的人。整數都是有理數。有的有理數不是整數。 不存在最大的整數。有且只有一個偶數是素數。2.求真值表及范式：P?(┓Q?R)、(┓Q?R)?(P?R)3.推理： p?(q?r)，┓s∨p，q ├ s?r p?r，q?s，p∨q ├ r∨s p∨q，p?┓r，s?t，┓s?r，┓t ├ q p?(┓(r∧s)?┓q),p,┓s ├ ┓q 4.如果小王是理科學生，他一定會學好數學。如果小王不是文科學生，他一定是理科學生。小王沒學好數學。所以小王是文科學生。 5.判斷各公式在給定解釋時的真假值，并且改變論域使該公式在新的解釋下取值相反。論域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①?x(F(x)∨G(x))②?y?yR(x,y)第二篇：離散數學
第三篇：離散數學自學
第四篇：離散數學第三章
第五篇：離散數學習題
點擊咨詢 