第一篇：離散數(shù)學
第一章
數(shù)學語言與證明方法
例1 設E={ x | x是北京某大學學生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走讀生}, C= { x | x是數(shù)學系學生}，D= { x | x是喜歡聽音樂的學生}.試描述下列各集合中學生的特征:
(A?D)? ~ C={ x | x是北京人或喜歡聽音樂,但不是數(shù)學系學生} ~ 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)
(補交轉(zhuǎn)換律)
=(A ? ~C)?(~B ? ~~C)
(德摩根律)
=(A ? ~C)?(~B ? C)
(雙重否定律)
=(A ? ~C ? ~B)?(A ? ~C ? C)
(分配律)
=(A ? ~C ? ~B)?(A ? ?)
(矛盾律)
= A ? ~C ? ~B
(零律,同一律)
=(A ? ~B)? ~C
(交換律,結(jié)合律)
=(A – B)– C
(補交轉(zhuǎn)換律)例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 證明
是無理數(shù)
證
假設
是有理數(shù), 存在正整數(shù)n,m, 使得
=m/n,不妨設m/n為既約分數(shù).于是m=n, m2=2n2, m2是偶數(shù), 從而m是偶數(shù).設m=2k, 得(2k)2=2n2, n2=2k2, 這又得到n也 是偶數(shù), 與m/n為既約分數(shù)矛盾.例6 對于每個正整數(shù)n, 存在n個連續(xù)的正合數(shù).證
令x=(n+1)!
則 x+2, x+3,…, x+n+1是n個連續(xù)的正合數(shù):
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, 結(jié)論成立.歸納步驟.假設對n?1結(jié)論成立, 則有
1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)
(歸納假設)
=(n+1)(n+2)/2 得證當n+1時結(jié)論也成立.例9 任何大于等于2的整數(shù)均可表成素數(shù)的乘積 證 歸納基礎.對于2, 結(jié)論顯然成立.歸納步驟.假設對所有的k(2?k?n)結(jié)論成立, 要證結(jié)論 對n+1也成立.若n+1是素數(shù), 則結(jié)論成立;否則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是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(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是偶數(shù).0(3)2+2＝4 當且僅當 太陽從東方升起.(4)2+2＝5 當且僅當 美國位于非洲.(5)f(x)在x0處可導的充要條件是它在 x0處連續(xù).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 （結(jié)合律） ? ?(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) （交換律，結(jié)合律） ? 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(續(xù))求?(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號 推理的形式結(jié)構(gòu)為 (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號.推理的形式結(jié)構(gòu)為 (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 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: 前提: púq, q?r, p?s, ?s 結(jié)論: rù(púq)證明 ① p?s 前提引入 ② ? s 前提引入 ③ ? p ①②拒取式 ④ púq 前提引入 ⑤ q ③④析取三段論 ⑥ q?r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ rù(púq) ⑦④合取 推理正確, rù(púq)是有效結(jié)論 例3 構(gòu)造推理的證明: 若明天是星期一或星期三, 我就有 課.若有課, 今天必需備課.我今天下午沒備課.所以, 明天 不是星期一和星期三.解 設 p:明天是星期一, q:明天是星期三，r:我有課，s:我備課 前提:(púq)?r, r?s, ?s 結(jié)論: ?pù?q 例4 構(gòu)造下面推理的證明: 前提: ?púq, ?qúr, r?s 結(jié)論: p?s 證明 ① p 附加前提引入 ② ?púq 前提引入 ③ q ①②析取三段論 ④ ?qúr 前提引入 ⑤ r ③④析取三段論 ⑥ r?s 前提引入 ⑦ s ⑤⑥假言推理 推理正確, p?s是有效結(jié)論 例5 構(gòu)造下面推理的證明 前提: ?(pùq)úr, r?s, ?s, p 結(jié)論: ?q 證明 用歸繆法 ① q 結(jié)論否定引入 ② r?s 前提引入 ③ ?s 前提引入 ④ ?r ②③拒取式 ⑤ ?(pùq)úr 前提引入 ⑥ ?(pùq) ④⑤析取三段論 ⑦ ?pú?q ⑥置換 ⑧ ?p ①⑦析取三段論 ⑨ p 前提引入 ⑩ ?pùp ⑧⑨合取 推理正確, ?q是有效結(jié)論 例6 用歸結(jié)證明法構(gòu)造下面推理的證明: 前提:(p?q)?r, r?s, ?s 結(jié)論:(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 結(jié)論: pù(?qús) 第3章 一階邏輯 例1(1)4是偶數(shù) 4是個體常項, “是偶數(shù)”是謂詞常項, 符號化為: F(4)(2)小王和小李同歲 小王, 小李是個體常項, 同歲是謂詞常項.記a:小王，b: 小李, G(x,y): x與y同歲, 符號化為: G(a,b)(3)x< y x,y是命題變項, < 是謂詞常項, 符號化為: L(x,y)(4)x具有某種性質(zhì)P x是命題變項, P是謂詞變項, 符號化為: P(x)例2 將下述命題用0元謂詞符號化, 并討論它們的真值:(1) 是無理數(shù), 而 是有理數(shù)(2)如果2>3，則3<4 解 (1)設F(x): x是無理數(shù), G(x): x是有理數(shù) 符號化為 真值為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(xiàn)(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的兩次出現(xiàn)均為約束出現(xiàn) y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn) z為自由出現(xiàn).例7 公式 ?x(F(x)??xG(x))?x的轄域:(F(x)??xG(x))，指導變元為x ?x的轄域:G(x)，指導變元為x x的兩次出現(xiàn)均為約束出現(xiàn).但是, 第一次出現(xiàn)的x是?x中 的x, 第二次出現(xiàn)的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是整數(shù)，:x是有理數(shù), 取解釋I2, D2=R，:x是整數(shù)，:x是自然數(shù), 非永真式的可滿足式(2)?(?xF(x))?(?xF(x)) 這是 ?p?p 的代換實例, ?p?p是重言式，永真式(3)?(?xF(x)??yG(y))? ?yG(y)這是?(p?q)?q的代換實例, ?(p?q)?q是矛盾式 矛盾式 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個體變項 真命題 假命題 (1)?xF(x,y,z)? ?yG(x,y,z)? ?uF(u,y,z)? ?yG(x,y,z) 換名規(guī)則 ? ?uF(u,y,z)? ?vG(x,v,z) 換名規(guī)則 或者 ? ?xF(x,u,z)? ?yG(x,y,z) 代替規(guī)則 ? ?xF(x,u,z)? ?yG(v,y,z) 代替規(guī)則(2)?x(F(x,y)? ?yG(x,y,z))? ?x(F(x,y)? ?tG(x,t,z)) 換名規(guī)則 或者 ? ?x(F(x,t)? ?yG(x,y,z)) 代替規(guī)則 例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是奇數(shù)，: 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) 換名規(guī)則 ? ?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 判斷下圖中關系的性質(zhì), 并說明理由 (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},zmvxqqw}，? 2={{a, b},{c},6oscd49} ? 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的所有劃分, 然后根據(jù)劃分寫出 對應的等價關系.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>} 根據(jù)有序?qū)?x,y>的 x+y=2,3,4,5,6,7,8 將A?A劃分.(A?A)/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>}，{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>}，{<3,4>, <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 判斷下面函數(shù)是否為單射, 滿射, 雙射的, 為什么?（1）f : R→R, f(x)= ?x2+2x?1（2）f : Z+→R, f(x)=lnx, Z+為正整數(shù)集（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+為正實數(shù)集.解(1)f : R→R, f(x)= ?x2+2x?1 在x=1取得極大值0.既不是單射也不是滿射的.(2)f : Z+→R, f(x)=lnx 單調(diào)上升, 是單射的.但不滿射, 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 是滿射、單射、雙射的, 因為它是單調(diào)函數(shù)并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x 有極小值f(1)=2.該函數(shù)既不是單射的也不是滿射的.例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] 構(gòu)造雙射 f : A→B解 令 f : [0,1]→[1/4,1/2] f(x)=(x+1)/4 例5 A=Z, B=N，構(gòu)造雙射 f : A→B 將Z中元素以下列順序排列并與N中元素對應： Z：0?11 ?22?33 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N：0 1 2 4 5 6 … 則這種對應所表示的函數(shù)是： 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 存在反函數(shù), 求出它們的反函數(shù).解 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不存在反函數(shù)；g : R→R的反函數(shù)是 g?1: R→R, g?1(x)=x?2 第6章 圖 例1 下述2組數(shù)能成為無向圖的度數(shù)列嗎?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇數(shù)個奇數(shù).(2)能 例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數(shù)均小 于等于2, 問G至少有多少個頂點? 解 設G有n個頂點.由握手定理，4?3+2?(n-4)?2?10 解得 n?8 例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的 多面體.證 用反證法.假設存在這樣的多面體, 作無向圖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條邊的所有非同構(gòu)的無向簡單圖 解 總度數(shù)為6, 分配給4個頂點, 最大度為3, 且奇度頂點數(shù) 為偶數(shù), 有下述3個度數(shù)列:(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為度數(shù)列的非同構(gòu)的無向簡單圖 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)中是內(nèi)部面;R2在(1)中是內(nèi)部面, 在(2)中是外部面.R3 R1 R3 R2(1) R2 R1(2) 說明:(1)一個平面圖可以有多個不同形式的平面嵌入, 它們都同構(gòu).(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 畫出所有非同構(gòu)的6階11條邊的簡單連通非平面圖 解 在K5(5階10條邊)上加一個頂點和一條邊 在K3,3(6階9條邊)上加2條邊 例1 某中學有3個課外活動小組:數(shù)學組, 計算機組和生物組.有趙,錢,孫,李,周5名學生, 問分別在下述3種情況下, 能否選出3人各任一個組的組長?(1)趙, 錢為數(shù)學組成員, 趙,孫,李為計算機組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學組成員, 錢,孫,李為計算機組成員, 錢,孫,李,周為生物組成員.(3)趙為數(shù)學組和計算機組成員, 錢,孫,李,周為生物組成員.解 數(shù) 計 生 數(shù) 計 生 趙 錢 孫 李 周 趙 錢 孫 李 周 (1(數(shù) 計 生 趙 錢 孫 李 周 (3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖: (a(b(c) (c)中存在哈密頓通路 例3 證明右圖不是哈密頓圖 證 假設存在一條哈密頓回路, a,f,g是2度頂點, 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點c出現(xiàn)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是一條哈密頓回路,按此順序就坐即可. 離散數(shù)學試題（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分） 在謂詞邏輯中構(gòu)造下面推理的證明：每個喜歡步行的人都不喜歡做汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。 解 論域：所有人的集合。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上的自反和傳遞關系，則對任意的正整數(shù)n，R＝R。 證明 當n＝1時，結(jié)論顯然成立。設n＝k時，Rk＝R。當n＝k＋1時，Rk+1＝Rk*R＝R*R。下面由R是自反和傳遞的推導出R*R＝R即可。 由傳遞性得R*R?R。另一方面，對任意的 由數(shù)學歸納法知，對任意的正整數(shù)n，Rn＝R。 n 六、（15分）設函數(shù)f：R×R?R×R，f定義為：f( (1)證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f。 (4)求復合函數(shù)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不是對稱的； 經(jīng)過計算可得 ?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上滿足結(jié)合律。綜上可知， 九、（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。離散數(shù)學試題（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分）在謂詞邏輯中構(gòu)造下面推理的證明：每個科學家都是勤奮的，每個勤奮又身體健康的人在事業(yè)中都會獲得成功。存在著身體健康的科學家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。 Q(x)：x是勤奮的；x是科學家；C(x)：解：論域：所有人的集合。H(x)：x是身體健康的；S(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為： ?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是自反的，則∈R，∈S，于是∈R*S，故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(jié)的函數(shù)？ (2)當n、m滿足什么條件時，存在單射，且有多少個不同的單射？(3)當n、m滿足什么條件時，存在雙射，且有多少個不同的雙射？ 解 (1)由于對X中每個元素可以取Y中任一元素與其對應，每個元素有n種取法，所以不同的函數(shù)共n個。 (2)顯然當|m|≤|n|時，存在單射。由于在Y中任選m個元素的任一全排列都形成X到Y(jié)的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個。 (3)顯然當|m|＝|n|時，才存在雙射。此時Y中元素的任一不同的全排列都形成X到Y(jié)的不同的雙射，mm故不同的雙射有m!個。 六、（5分）集合X上有m個元素，集合Y上有n個元素，問X到Y(jié)的二元關系總共有多少個？ 解 X到Y(jié)的不同的二元關系對應X×Y的不同的子集，而X×Y的不同的子集共有個2mn，所以X到Y(jié)的二元關系總共有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。 學習體會 專業(yè)：計算機 姓名：范文芳 學號： 成績： 院校： 離散數(shù)學是計算機科學與技術(shù)專業(yè)的基礎核心課程。通過本課程的學習，使學生具有現(xiàn)代數(shù)學的觀點和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法。同時，也要培養(yǎng)學生抽象思維和慎密概括的能力，使學生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學知識，分析和解決實際問題的能力，為學生以后學習計算機基礎理論與專業(yè)課程打下良好的基礎。 學習離散數(shù)學有兩項最基本的任務：其一是通過學習離散數(shù)學，使學生了解和掌握在后續(xù)課程中要直接用到的一些數(shù)學概念和基本原理，掌握計算機中常用的科學論證方法，為后續(xù)課程的學習奠定一個良好的數(shù)學基礎；其二是在離散數(shù)學的學習過程中，培訓自學能力、抽象思維能力和邏輯推理能力，以提高專業(yè)理論水平。因此學習離散數(shù)學對于計算機、通信等專業(yè)后續(xù)課程的學習和今后從事計算機科學等工作是至關重要的。但是由于離散數(shù)學的離散性、知識的分散性和處理問題的特殊性，使部分學生在剛剛接觸離散數(shù)學時，對其中的一些概念和處理問題的方法往往感到困惑，特別是在做證明題時感到無從下手，找不到正確的解題思路。因此，對離散數(shù)學的學習方法給予適當?shù)闹笇Ш蛯W習過程中遇到的一些問題分析是十分必要的。 一、認知離散數(shù)學 離散數(shù)學是計算機科學基礎理論的核心課程之一，是計算機及應用、通信等專業(yè)的一門重要的基礎課。它以研究量的結(jié)構(gòu)和相互關系為主要目標，其研究對象一般是有限個或可數(shù)個元素，充分體現(xiàn)了計算機科學離散性的特點。學習離散數(shù)學的目的是為學習計算機、通信等專業(yè)各后續(xù)課程做好必要的知識準備，進一步提高抽象思維和邏輯推理的能力，為計算機的應用提供必要的描述工具和理論 基礎。 1．定義和定理多 離散數(shù)學是建立在大量定義、定理之上的邏輯推理學科，因此對概念的理解是學習這門課程的核心。在學習這些概念的基礎上，要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的實體則是大量的定理和性質(zhì)。在考試中有一部分內(nèi)容是考查學生對定義和定理的識記、理解和運用，因此要真正理解離散數(shù)學中所給出的每個基本概念的真正的含義。比如，命題的定義、五個基本聯(lián)結(jié)詞、公式的主析取范式和主合取范式、三個推理規(guī)則以及反證法；集合的五種運算的定義；關系的定義和關系的四個性質(zhì)；函數(shù)（映射）和幾種特殊函數(shù)（映射）的定義；圖、完全圖、簡單圖、子圖、補圖的定義；圖中簡單路、基本路的定義以及兩個圖同構(gòu)的定義；樹與最小生成樹的定義。掌握和理解這些概念對于學好離散數(shù)學是至關重要的。2.方法性強 在離散數(shù)學的學習過程中，一定要注重和掌握離散數(shù)學處理問題的方法，在做題時，找到一個合適的解題思路和方法是極為重要的。如果知道了一道題用怎樣的方法去做或證明，就能很容易地做或證出來。反之，則事倍功半。在離散數(shù)學中，雖然各種各樣的題種類繁多，但每類題的解法均有規(guī)律可循。所以在聽課和平時的復習中，要善于總結(jié)和歸納具有規(guī)律性的內(nèi)容。在平時的講課和復習中，老師會總結(jié)各類解題思路和方法。作為學生，首先應該熟悉并且會用這些方法，同時，還要勤于思考，對于一道題，進可能地多探討幾種解法。3.抽象性強 離散數(shù)學的特點是知識點集中，對抽象思維能力的要求較高。由于這些定義的抽象性，使初學者往往不能在腦海中直接建立起它們與現(xiàn)實世界中客觀事物的聯(lián)系。不管是哪本離散數(shù)學教材，都會在每一章中首先列出若干個定義和定理，接著就是這些定義和定理的直接應用，如果沒有較好的抽象思維能力，學習離散數(shù)學確實具有一定的困難。因此，在離散數(shù)學的學習中，要注重抽象思維能力、邏輯推理能力的培養(yǎng)和訓練，這種能力的培養(yǎng)對今后從事各種工作都是極其重要的。 在學習離散數(shù)學中所遇到的這些困難，可以通過多學、多看、認真分析講課 中所給出的典型例題的解題過程，再加上多練，從而逐步得到解決。在此特別強調(diào)一點：深入地理解和掌握離散數(shù)學的基本概念、基本定理和結(jié)論，是學好離散數(shù)學的重要前提之一。所以，同學們要準確、全面、完整地記憶和理解所有這些基本定義和定理。4.內(nèi)在聯(lián)系性 離散數(shù)學的三大體系雖然來自于不同的學科，但是這三大體系前后貫通，形成一個有機的整體。通過認真的分析可尋找出三大部分之間知識的內(nèi)在聯(lián)系性和規(guī)律性。如：集合論、函數(shù)、關系和圖論，其解題思路和證明方法均有相同或相似之處。 二、認知解題規(guī)范 一般來說，離散數(shù)學的考試要求分為：了解、理解和掌握。了解是能正確判別有關概念和方法；理解是能正確表達有關概念和方法的含義；掌握是在理解的基礎上加以靈活應用。為了考核學生對這三部分的理解和掌握的程度，試題類型一般可分為：判斷題、填空題、選擇題、計算題和證明題。判斷題、填空題、選擇題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡單計算；計算題主要考核學生的基本運用技能和速度，要求寫出完整的計算過程和步驟；證明題主要考查應用概念、性質(zhì)、定理及重要結(jié)論進行邏輯推理的能力，要求寫出嚴格的推理和論證過程。 學習離散數(shù)學的最大困難是它的抽象性和邏輯推理的嚴密性。在離散數(shù)學中，假設讓你解一道題或證明一個命題，你應首先讀懂題意，然后尋找解題或證明的思路和方法，當你相信已找到了解題或證明的思路和方法，你必須把它嚴格地寫出來。一個寫得很好的解題過程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經(jīng)過簡單的推理而得到的。仔細地寫解題過程或證明是很重要的，既能讓讀者理解它，又能保證解題過程或證明準確無誤。一個好的解題過程或證明應該是條理清楚、論據(jù)充分、表述簡潔的。針對這一要求，在講課中老師會提供大量的典型例題供同學們參考和學習。 通過離散數(shù)學的學習和訓練，能使同學們學會在離散數(shù)學中處理問題的一般性的規(guī)律和方法，一旦掌握了離散數(shù)學中這種處理問題的思想方法，學習和掌握離散數(shù)學的知識就不再是一件難事了。復習離散數(shù)學的整個過程可大致分為三個 階段。 第一階段，大量進行知識儲備的階段。 離散數(shù)學是建立在大量定義上面的邏輯推理學科。因而對概念的理解是我們學習這門學科的核心。由于這些定義非常抽象，初學者往往不能在腦海中建立起它們與現(xiàn)實世界中客觀事物的聯(lián)系。對于跨專業(yè)自學的朋友來說更是如此。這是離散數(shù)學學習中的第一個困難。因此，對于第一遍復習，我們提出一個最為重要的要求，即準確、全面、完整地記憶所有的定義和定理。具體做法可以是：在進行完一章的學習后，用專門的時間對該章包括的定義與定理實施強記，直到能夠全部正確地默寫出來為止。無須強求一定要理解，記住并能準確復述 各定義定理是此階段的最高要求。也不需做太多的題（甚至不做課后習題也是可以的，把例題看懂就行），重心要放在對定義和定理的記憶上。請牢記，這是為未來的向廣度和深度擴張作必要的準備。 這一過程視各人情況不同耗時約在一到兩個月內(nèi)。第二階段，深入學習，并大量做課后習題的階段。 這是最漫長的一個階段，耗時也很難估計，一般來說，若能熟練解出某一章75%以上的課后習題，可以考慮結(jié)束該章。 解離散數(shù)學的題，方法非常重要，如果拿到一道題，立即能夠看出它所屬的類型及關聯(lián)的知識點，就不難選用正確的方法將其解決，反之則事倍功半。例如在命題邏輯部分，無非是這么幾種題目：將自然語言表述的命題符號化，等價命題的相互轉(zhuǎn)化（包括化為主合取范式與主析取范式），以給出的若干命題為前提進行推理和證明。相應的對策也馬上就可以提出來。以推理題為例，主要是利用P、T規(guī)則，加上蘊涵和等價公式表，由給定的前提出發(fā)進行推演，或根據(jù)題目特點采用真值表法、CP規(guī)則和反證法。由此可見，在平常復習中，要善于總結(jié)和歸納，仔細體會題目類型和此類題目的解題套路。如此多作練習，則即使遇到比較陌生的題也可以較快地領悟其本質(zhì)，從而輕松解出。 “熟讀唐詩三百首，不會做詩也會吟?！币悄玫揭槐玖曨}集，從頭到尾做過，甚至背會的話。那么，在考場上就會發(fā)現(xiàn)絕大多數(shù)題見過或似曾相識。這時，要取得較好的成績也就不是太難的事情了。這一情況具有普遍性，對許多院校的考試都適用。 第三階段，進行真題模擬訓練，提高整體水平和綜合能力的階段。 這一階段從第二階段結(jié)束一直持續(xù)到考試。 除了我們使用的課本外，應盡可能地弄到報考院校的專業(yè)課歷年試題。因為每個單位對該科目的側(cè)重點畢竟有不同，從歷年試題中可以獲取許多有用的信息。這些歷年試題此時就有了巨大的作用。 第三章部分課后習題參考答案 14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：(2)前提：p?q,?(q?r),r 結(jié)論：?p(4)前提：q?p,q?s,s?t,t?r 結(jié)論：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在自然推理系統(tǒng)P中用附加前提法證明下面各推理：(1)前提：p?(q?r),s?p,q 結(jié)論：s?r 證明 ①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統(tǒng)P中用歸謬法證明下面各推理： (1)前提：p??q,?r?q,r??s 結(jié)論：?p 證明： ①p 結(jié)論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡律 ⑥r(nóng)?￢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.請分別判斷以下結(jié)論是否一定成立，如果一定成立請證明，否則請舉出反例。 ①如果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是整數(shù)集，R={(x,y)|x-y是3的倍數(shù)}，證明：R是I上的等價關系。 16.如果R是A上的等價關系，則A/R一定是A的劃分。17.R是集合A上的自反關系，S是A上的自反和對稱關系，證明t(R∪S)是A上的等價關系。18.I是正整數(shù)集合，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是實數(shù)集，f:R×R?R×R,f( 代數(shù)系統(tǒng) 1. 2.求 3.R是實數(shù)集，在R上定義運算*為x*y=x+y+xy,問： 5.R是實數(shù)集，R上的6運算定義如下：對R中元素x,y，f1( 6. 7.證明：如果群G中每個元素的逆元素都是它自已，則G是交換群。 8.循環(huán)群一定是交換群。 9.證明：階為素數(shù)的群一定是循環(huán)群。 -110. 11.整數(shù)集Z上定義運算*：對任意整數(shù)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,*)是否構(gòu)成群？ n18. 19.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分 20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21. ++23.R為實數(shù)集，R為正實數(shù)集， 1.如何判斷二部圖？完全圖、完全二部圖的邊數(shù)。2.如何求E回路？ 3.Petersen圖是否為E圖或H圖。 4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時輪圖為H圖？ 6.如何求最小生成樹。 7.證明：奇數(shù)個頂點的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數(shù)個頂點的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。并由此證明K5不是平面圖。 11.證明：有6個頂點的簡單無向圖G和它的補圖中至少有一個三角形。 12.證明：在至少有兩個頂點的無向樹中，至少有2個一度頂點。 13.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？ 14.證明：簡單無向圖G和它的補圖中至少有一個是連通圖。15.證明：無向圖中奇度點（度數(shù)為奇數(shù)的點）有偶數(shù)個。16.證明：n個頂點的無向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點集，證明：對任意頂點集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數(shù)目。18.一棵無向樹有3個3次點，1個頂點次數(shù)為2，其余頂點次數(shù)為1，問它有幾個次數(shù)為1的頂點？寫出求解過程。19.證明：每個簡單平面圖都包含一個次至多為5的頂點。20.連通平面圖G有n個頂點，m條邊和f個面，證明：n-m+f=2。21.如果圖G的最大頂點次數(shù)≤ρ，證明：G是ρ+1可點著色的。 22.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？ 23.如果一個簡單圖G和它的補圖同構(gòu)，則稱G是自補圖，求所有4個頂點自補圖。 24.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。如果G中無三角形，則m?2n-4。數(shù)理邏輯 1.如果今天是星期一，則要進行英語或數(shù)理邏輯考試。 沒有不犯錯誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。 不存在最大的整數(shù)。有且只有一個偶數(shù)是素數(shù)。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.如果小王是理科學生，他一定會學好數(shù)學。如果小王不是文科學生，他一定是理科學生。小王沒學好數(shù)學。所以小王是文科學生。 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)第二篇：離散數(shù)學
第三篇：離散數(shù)學自學
第四篇：離散數(shù)學第三章
第五篇：離散數(shù)學習題
點擊咨詢 