離散數(shù)學第1章屈

1、1,參考教材,離散數(shù)學教程 耿素云 屈婉玲 王捍貧 北京大學出版社 2002年6月離散數(shù)學及其應用（英文版 第5版）Kenneth H.Rosen機械工業(yè)出版社 2006年7月,2,第1章 數(shù)學語言與證明方法,1.1 常用的數(shù)學符號1.2 集合及其運算1.3 證明方法概述,3,1.1 常用的數(shù)學符號,1.1.1 集合符號1.1.2 運算符號1.1.3 邏輯符號,4,1.2 集合及其運算,集

2、合及其表示法包含(子集)與相等空集與全集集合運算(?,?, ? , ~ , ?)基本集合恒等式包含與相等的證明方法,5,集合的概念,集合是數(shù)學中最基本的概念,沒有嚴格的定義 理解成某些個體組成的整體, 常用A,B,C等表示元素: 集合中的個體x?A(x屬于A): x是A的元素 x?A(x不屬于A): x不是A的元素無窮集: 元素個數(shù)無限的集合有窮集(有限集): 元素個數(shù)有限的集合. |

3、A|: 有窮集合A中的元素個數(shù)k元集: k個元素的集合, k ? 0,6,集合的表示法,列舉法 如 A={ a, b, c, d }, N={0,1,2,…}描述法 { x | P(x) } 如N={ x | x是自然數(shù) }說明: (1) 集合中的元素各不相同. 如, {1,2,3}={1,1,2,3}(2) 集合中的元素沒有次序. 如, {1,2,3}={3,1,2}={1,3,1,2,2}(3) 有時兩

4、種方法都適用, 可根據(jù)需要選用.常用集合 自然數(shù)集N , 整數(shù)集Z , 正整數(shù)集Z+, 有理數(shù)集Q , 非零有理數(shù)集Q* , 實數(shù)集R , 非零實數(shù)集R*, 復數(shù)集C , 區(qū)間[a,b], (a,b)等,7,包含與相等,包含(子集) A ? B ? ?x (x?A ? x?B)不包含 A ? B ? ?x (x?A ? x?B) 相等

5、 A = B ? A ? B ? B ? A不相等 A ? B ? A ? B ? B ? A真包含(真子集) A ? B ? A ? B ? A ? B 例如, A={1,2,3}, B={ x | x?R ?|x|?1 }, C={ x | x?R ? x2=1 }, D={?1,1}, C ? B, C ? B, C ?

6、A, A ? B, B ? A, C = D性質(zhì) (1) A ? A (2) A ? B ? B ? C ? A ? C,8,空集與全集,空集?: 不含任何元素的集合例如, { x | x2<0?x?R }=?定理1.1 空集是任何集合的子集證 用歸謬法. 假設(shè)不然, 則存在集合A, 使得? ? A, 即存在x, x??且x?A, 矛盾. 推論 空集是惟一的.證 假設(shè)存在?1和?2，則

7、?1??2 且?2??1，因此?1=?2全集E : 限定所討論的集合都是E的子集. 相對性,9,冪集,冪集P(A) :A的所有子集組成的集合, 即 P(A) = { x | x ? A }例如, 設(shè)A={a,b,c} A的0元子集: ? A的1元子集: {a}, , {c} A的2元子集:{a,b},{a

8、,c},{b,c} A的3元子集: {a,b,c} P(A) ={?, {a}, , {c}, {a,b}, {a,c}, {b,c}, {a,b,c}},定理1.2 如果 |A| = n，則 |P(A)| = 2n 證,10,集合運算,并 A?B = { x | x?A ? x?B }交 A?B = { x | x?A ? x?B }相對補

9、A?B = { x | x?A ? x?B }對稱差 A?B = (A?B)?(B?A) = (A?B)?(A?B) 絕對補 ?A = E?A= { x | x?A }例如 設(shè)E={0,1, … ,9}, A={0,1,2,3}, B={1,3,5,7,9}, 則 A?B ={0,1,2,3,5,7,9}, A?B ={1,3}, A?B ={0,2},

10、 A?B ={0,2,5,7,9}, ?A ={4,5,6,7,8,9}, ?B ={0,2,4,6,8}說明: 1. 只使用圓括號 2. 運算順序: 優(yōu)先級別為(1)括號, (2)?和冪集, (3)其他. 同級別的按從左到右運算

11、,11,實例,例1 設(shè)E={ x | x是北京某大學學生}, A,B,C,D是E 的子集,A= { x | x是北京人}, B= { x | x是走讀生},C= { x | x是數(shù)學系學生}, D= { x | x是喜歡聽音樂的學生}.試描述下列各集合中學生的特征:,(A?D) ? ~ C=,~ A?B=,(A?B) ? D=,~ D ? ~ B=,{ x | x是北京人或喜歡聽音樂, 但

12、不是數(shù)學系學生},{ x | x是外地走讀生},{ x | x是北京住校生, 并且喜歡聽音樂},{ x | x是不喜歡聽音樂的住校生},12,文氏圖表示,13,集合運算(續(xù)),并和交運算可以推廣到有窮個集合上 A1?A2?…?An= { x | x?A1 ? x?A2 ? … ? x?An } A1?A2?…?An= { x | x?A1 ? x?A2 ? …

13、 ? x?An }并和交運算還可以推廣到可數(shù)無窮個集合上 A1?A2?…= { x | ?i (i=1,2,…) x?Ai } A1?A2?…= { x | ?i (i=1,2,…) x?Ai },14,基本集合恒等式,1. 冪等律A?A=A, A?A=A2. 交換律A?B=B?A, A?B=B?A3. 結(jié)合律(A?B)?

14、C=A?(B?C) (A?B)?C=A?(B?C)4. 分配律A?(B?C)=(A?B)?(A?C) A?(B?C)=(A?B)?(A?C)5. 德摩根律 絕對形式?(B?C)=?B??C, ?(B?C)=?B??C 相對形式 A?(B?C)=(A?B)?(A?C) A?(B?

15、C)=(A?B)?(A?C),15,基本集合恒等式(續(xù)),6. 吸收律 A?(A?B)=A, A?(A?B)=A7. 零律 A?E=E, A??=?8. 同一律 A??=A, A?E=A9. 排中律 A??A=E10. 矛盾律 A??A=?11. 余補律 ??=E, ?E=

16、?12. 雙重否定律 ? ?A=A13. 補交轉(zhuǎn)換律 A?B= A??B,16,基本集合恒等式(續(xù)),14. 關(guān)于對稱差的恒等式 (1) 交換律 A?B=B?A (2) 結(jié)合律 (A?B)?C=A?(B?C) (3) ?對?的分配律 A?(B?C)=(A?B)?(A?C) (4) A??=A, A

17、?E=~A (5) A?A=?, A?~A= E,注意: ?對?沒有分配律, 反例如下 A={a,b,c}, B={b,c,d}, C={c,d,e} A?(B?C)= {a,b,c}?{b,e}= {a,b,c,e} (A?B)?(A?C)= {a,b,c,d}?{a,b,c,d,e}= {e}, 兩者不等,17,證明集合包含或相等,方法一. 根據(jù)定義, 通過邏輯等值演算證明方

18、法二. 利用已知集合等式或包含式, 通過集合演算證明例3 證明:(1) A?B=B?A (交換律)證 ?x x?A?B ? x?A ? x?B (并的定義) ? x?B ? x?A (邏輯演算的交換律) ? x?B?A (并的定義),18,例3(續(xù)),(2) A?(B?C)=(A

19、?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

20、? x?A ? x?E (并的定義) ? x?A ? 1 (全集E 的定義) ? 1 (邏輯演算的零律) ? x?E (全集E 的定義),19,例3(續(xù)),(4) A?E=A (同一律)證 ?x x?A?E ? x?A?x?E (交的定義) ? x

21、?A?1 (全集E的定義) ? x?A (邏輯演算的同一律),20,實例,例4 證明 A?(A?B)=A （吸收律）證 利用例3證明的4條等式證明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交換律)

22、 = A?E (零律) = A (同一律)對其余的基本集合恒等式不再一一證明(請自行證明),今后把它們作為已知的集合等式使用.,21,實例,例5 證明 (A? B)? C=(A? C)? (B? C)證 (A? C) ? (B? C) = (A?~C)?~(B?~C)

23、 (補交轉(zhuǎn)換律) = (A?~C)?(~B?~~C) (德摩根律) = (A?~C)?(~B?C) (雙重否定律) = (A?~C?~B)?(A?~C?C) (分配律) = (A?~C?~B)?(A??) (矛盾律) = A?~C?~B

24、 (零律,同一律) = (A?~B)?~C (交換律,結(jié)合律) = (A–B) – C (補交轉(zhuǎn)換律),22,實例,例6 證明 (A?B)?(A?C)=(B?C)?A證 (A?B)?(A?C)

25、 =((A?B) ? (A?C))?((A?C) ? (A?B)) =((A?B)?~A?~C)?((A?C)?~A?~B) = (B?~A?~C)?(C?~A?~B) =((B?~C)?(C?~B))?~A =((B? C)?(C? B))?~A = (B?C)? A,23,實例,例7 設(shè)A,B為任意集合, 證明:(1) A?A?B證 ?x x?A ? x?A ?

26、 x?B (附加律) ? x?A?B(2) A?B?A證 ?x x?A?B ? x?A ? x?B ? x?A (化簡律),24,實例(續(xù)),(3) A? B?A證 ?x x?A? B ? x?A ? x?B ? x?A

27、 (化簡律)(4) 若A?B, 則P(A)?P(B)證 ?x x?P(A) ? x?A ? x?B (已知A?B) ? x?P(B),25,實例,例8 已知 A?B=A?C, 證明 B=C.證 A?B=A?C ? A?(A?B)=A?(A?C) ? (A?A)

28、?B=(A?A)?C ? ??B= ??C ? B=C,26,1.3 證明方法概述,1.3.1 邏輯推理的形式結(jié)構(gòu)1.3.2 公理、定理與證明1.3.3 證明方法1.3.4 數(shù)學歸納法,27,1.3.1 邏輯推理的形式結(jié)構(gòu),邏輯推理的形式結(jié)構(gòu) A1?A2?…?Ak?B (*)當(*)為重言式時, 記作 A1?A2?…?Ak?B

29、 (**)并稱推理有效或推理正確, 又稱B是A1,A2,…,Ak的有效(或邏輯)結(jié)論; 否則稱推理不正確.,(1),(2),(4)推理正確(3)推理不正確(1)中B是A的邏輯結(jié)論,但不是正確結(jié)論; (2)和(4)中B既是邏輯結(jié)論,又是正確結(jié)論.,28,1.3.2 公理、定理與證明,許多真命題都是在某些條件下，證明結(jié)論B為真。常見形式: (1) 若A, 則B A?B

30、 (2) A當且僅當B A?B (3) 證明B B都可歸結(jié)為形式(1),公理 公認為真的命題定理 可以被證明為真的命題引理 為證明某條定理而引用的輔助性的真命題推論 從某條定理直接推導出來的真命題,29,1.3.3 證明方法,直接證明法間接證明法歸謬法（反證法） 分情況證明法（窮舉法）構(gòu)造證明法前件假證明法（空

31、證明法）后件真證明法（平凡證明法）謬誤的證明方法,30,直接證明法,做法 證明“若A為真, 則B為真” 理由 “若A為真, 則B為真” ? “A?B為真”例1 若n是奇數(shù), 則n2也是奇數(shù).證 存在k?N, n=2k+1. 于是, n2 = (2k+1)2 = 2(2k2+2k)+1得證n2是奇數(shù).,31,間接證明法,做法 證明“ ¬

32、;B? ¬A”為真理由 “A?B為真” ? “ ¬B? ¬A為真”例2 若n2是奇數(shù), 則n也是奇數(shù).證 用間接證明法. 只要證:若n是偶數(shù), 則n2也是偶數(shù).假設(shè)n是偶數(shù), 則存在k?N, n=2k. 于是, n2 = (2k)2 = 2(2k2)得證n2是偶數(shù).,32,歸謬法(反證法),做法 假設(shè)A真并且¬

33、B真, 推出矛盾, 即證明:A?¬B?0理由 A?¬B?0為真 ? A?¬B為假 ? A為假或 B為真 ? A?B為真間接證明法是歸謬法的特殊形式: ¬B ? ¬A, A?¬A?0例3 若A?B=A, 則A?B=?證 用歸謬法, 假設(shè)A?B??, 則存在x,使得 x?A?B ? x?A ?

34、x?B ? x?A?B ? x?B (A?B=A) ? x?A?x?B?x?B ? x?B?x?B, 矛盾,33,分情況證明法 (窮舉法),推理A?B, 其中A= A1?A2?…?Ak .做法 證明A1?B, A2?B,…, Ak?B 均為真理由 A1?A2?…?Ak?B ? ¬(A1?A2?…?Ak)?B ? (

35、72;A1?¬A2?…? ¬Ak)?B ? (¬A1?B)?(¬A2?B)?…?(¬Ak?B) ? (A1?B)?(A2?B)?…?(Ak?B),34,實例,例4 證明: max(a, max(b,c))=max(max(a,b),c)證,35,構(gòu)造證明法,推理A?B, 其中B是存在具有某種性質(zhì)的客體做法 在A為真的條件下, 構(gòu)造出具有這種性質(zhì)的

36、客體例5 對于每個正整數(shù)n, 存在n個連續(xù)的正合數(shù).證 令x=(n+1)!+1, 考慮n個連續(xù)的正整數(shù) x+1, x+2,…, x+n x+i=(n+1)!+1+i 其中 i=1,2,3,…,n (1+i) | (n+1)! 且 (1+i) | (1+i) 所以 x+i是合數(shù) 則 x+1, x+2,…, x+

37、n是n個連續(xù)的正合數(shù)。,36,空證明法與平凡證明法,空證明法(前件假證明法)做法 證明“A恒為假”理由 “A恒為假” ? “A?B為真”例如, “? 是任何集合的子集”(定理1.1)的證明 ? ? B ? ?x (x? ? ? x?B)平凡證明法(后件真證明法)做法 證明“B恒為真”理由 “B恒為真” ? “A?B為真”例如, 若a?b, 則a0?b0.常在歸納證明的歸納基礎(chǔ)中出現(xiàn),37,謬誤的證明方法,例6

38、 判斷下述命題是真是假: 若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, 故命題為假.,38,數(shù)學歸納法,命題形式: ?x(x?N?x?n0), P(x)命題的提出——歸納與猜想(1)歸納基礎(chǔ) 證P(n0)為真(2)歸納步驟 ?x(x?n0), 假設(shè)P(x)為真, 證P(