離散數(shù)學(xué)-1.1-1.2數(shù)學(xué)語言與證明方法

1、第1章 數(shù)學(xué)語言與證明方法1第1章 數(shù)學(xué)語言與證明方法1.1 邏輯符號1.2 集合及其運算1.3 證明方法概述21.1 邏輯符號命題與真值聯(lián)結(jié)詞(, ,)命題公式(重言式,矛盾式,可滿足式)重要等值式重要推理規(guī)則個體,個體域與謂詞全稱量詞與存在量詞3聯(lián)結(jié)詞真值:真, 假 或 1, 0命題:具有確定真值的陳述句, 通常用p,q,r等表示真命題:真值為真的命題假命題:真值為假的命題例如, p:2+2=4, q:3是偶數(shù)它們都是命題, p是真命題, q是假命題.否定聯(lián)結(jié)詞否定式p: 非p (p的否定) p 為真當(dāng)且僅當(dāng)p為假4聯(lián)結(jié)詞(續(xù))合取聯(lián)結(jié)詞合取式pq:p并且q (p與q) pq為真當(dāng)且僅當(dāng)p

2、與q同時為真析取聯(lián)結(jié)詞析取式pq: p或q pq為假當(dāng)且僅當(dāng)p與q同時為假排斥或聯(lián)結(jié)詞排斥或p q: p并且非q, 或者q并且非p p q為真當(dāng)且僅當(dāng)p與q中一個為真,另一個為假5聯(lián)結(jié)詞(續(xù))蘊涵聯(lián)結(jié)詞蘊涵式pq:如果p,則q pq為假當(dāng)且僅當(dāng) p 為真 q 為假等價聯(lián)結(jié)詞等價式pq:p當(dāng)且僅當(dāng)q pq為真當(dāng)且僅當(dāng)p與q同時為真或同時為假6實例 設(shè)p:2是偶數(shù), q:1+1=3, 則p的真值為1q的真值為p的真值為q的真值為pq的真值為pq的真值為pq的真值為 pq的真值為pq的真值為pq的真值為p q的真值為p q的真值為p q的真值為p q的真值為0010110111001pq的真值為pq

3、的真值為007實例(續(xù)) pq的真值為pq的真值為pq的真值為pq的真值為0111又設(shè) r:今天是星期一, s:明天是星期二, t:明天是星期三rs的真值為rt的真值為1不定8命題公式命題變項:取值為0或1的變元, 也用p,q,r等表示.命題公式:用聯(lián)結(jié)詞和圓括號把命題和命題變項按照一定規(guī)則連接起來的符號串, 常用A,B,C等表示.例如, A=(pq)(rp)公式的賦值:對公式中每一個命題變項給定一個值(0或1).公式的成真賦值:使公式為真的賦值.公式的成假賦值:使公式為假的賦值.例如, p=1,q=1,r=1是A的成真賦值, p=0,q=1,r=0是A的成假賦值.9重言式,矛盾式與可滿足式重

4、言式(永真式):無成假賦值的命題公式矛盾式(永假式):無成真賦值的命題公式可滿足式:不是矛盾式的命題公式例如, A= (pq)(rp)是可滿足式, 但不是重言式, B= (pq)(pq)(pq)(pq)是重言式, C= p(pq)(pq)是矛盾式.AB:蘊涵式AB是重言式的簡記.AB:等價式AB是重言式的簡記， 稱A與B等值，AB是等值式. 10基本等值式雙重否定律 AA冪等律 AAA, AAA交換律 ABBA, ABBA結(jié)合律 (AB)CA(BC) (AB)CA(BC)分配律 A(BC)(AB)(AC) A(BC) (AB)(AC)德摩根律 (AB)AB (AB)AB11基本等值式(續(xù))吸收

5、律 A(AB)A, A(AB)A零律 A11, A00 同一律 A0A, A1A排中律 AA1矛盾律 AA0蘊涵等值式 AB AB等價等值式 AB(AB)(BA)假言易位等值式 AB B A等價否定等值式 AB A B歸謬論 (AB)(AB) A12重要推理規(guī)則(推理定律)附加律 A (AB) 化簡律 (AB) A假言推理 (AB)A B拒取式 (AB)B A析取三段論 (AB)B A假言三段論 (AB)(BC) (AC)等價三段論 (AB)(BC) (AC)構(gòu)造性二難 (AB)(CD)(AC) (BD) 破壞性二難 (AB)(CD)( BD) (AC) 13謂詞與量詞個體域:被研究對象的全體

6、, 如自然數(shù)集, 人類等.個體詞:個體域中的一個元素.全稱量詞: 表示任意的, 所有的, 一切的等.存在量詞: 表示存在, 有的, 至少有一個等.謂詞: 表示個體詞性質(zhì)或相互之間關(guān)系的詞例如, 謂詞P(x)表示x具有性質(zhì)P x P(x) 表示個體域中所有的x具有性質(zhì)P x P(x) 表示個體域中存在x具有性質(zhì)P141.2 集合及其運算集合及其表示法包含(子集)與相等空集與全集集合運算(, - , , )基本集合恒等式包含與相等的證明方法15集合的概念樸素集合論(康托, G.Cantor), 羅素(Russell)悖論集合是數(shù)學(xué)中最基本的概念,沒有嚴(yán)格的定義 理解成某些個體組成的整體, 常用A,

7、B,C等表示元素:集合中的個體xA(x屬于A): x是A的元素 xA(x不屬于A): x不是A的元素?zé)o窮集:元素個數(shù)無限的集合有窮集(有限集):元素個數(shù)有限的集合. |A|:A中元素個數(shù)k元集:k個元素的集合, k 016集合的表示法列舉法 如 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) 有時兩種方法都適用, 可根據(jù)需要選用.常用集合 自然數(shù)集N, 整數(shù)集Z, 正整數(shù)集Z+, 有

8、理數(shù)集Q, 非零有理數(shù)集Q*, 實數(shù)集R, 非零實數(shù)集R*, 復(fù)數(shù)集C, 區(qū)間a,b,(a,b)等17包含與相等包含(子集) A B x (xA xB)不包含 A B x (xA xB) 相等 A = B A B B A不相等 A B A B B A真包含(真子集) A B A B A B 例如, A=1,2,3, B= x | xR|x|1 , C= x | xRx2=1 , D=-1,1, C B, C B, C A, A B, B A, C = D性質(zhì) (1) A A (2) A B B C A C18空集與全集空集: 不含任何元素的集合例如, x | x20 xR=定理1.1 空集是任

9、何集合的子集證 用歸謬法. 假設(shè)不然, 則存在集合A, 使得 A, 即存在x, x且xA, 矛盾. 推論 空集是惟一的.證 假設(shè)存在1和2，則12 且12，因此1=2全集E:限定所討論的集合都是E的子集. 相對性 19冪集冪集P(A):A的所有子集組成的集合, 即 P(A) = x | xA 例如, 設(shè)A=a,b,c A的0元子集: A的1元子集: a, b, c A的2元子集:a,b,a,c,b,c A的3元子集: a,b,c P(A) =, a, b, c, a,b. a,c, b,c, a,b,c定理1.2 如果 |A| = n，則 |P(A)| = 2n 證20集合運算并 AB = x

10、 | xA xB 交 AB = x | xA xB 相對補 AB = x | xA xB 對稱差 AB = (AB)(BA) = (AB)(AB) 絕對補 A = EA= x | xA 例如 設(shè)E=0,1, ,9, A=0,1,2,3, B=1,3,5,7,9, 則 AB =0,1,2,3,5,7,9, AB =1,3, AB =0,2, AB =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)其他.同級別的按從左到右運算21實例例1 設(shè)E= x | x是北京某大學(xué)學(xué)生, A,

11、B,C,D是E的子集,A= x | x是北京人, B= x | x是走讀生,C= x | x是數(shù)學(xué)系學(xué)生, D= x | x是喜歡聽音樂的學(xué)生.試描述下列各集合中學(xué)生的特征:(AD) C= AB=(A-B) D= D B= x | x是北京人或喜歡聽音樂, 但不是數(shù)學(xué)系學(xué)生 x | x是外地走讀生 x | x是北京住校生, 并且喜歡聽音樂 x | x是不喜歡聽音樂的住校生22文氏圖表示23集合運算(續(xù))并和交運算可以推廣到有窮個集合上 A1A2An= x | xA1xA2xAn A1A2An= x | xA1xA2xAn并和交運算還可以推廣到可數(shù)無窮個集合上 A1A2= x | i (i=1,

12、2,) xAi A1A2= x | i (i=1,2,) xAi 24實例例2 設(shè)Ai=0, 1/i ), Bi=(0, i ), i=1,2, , 則0, 1)0, 1)0, 1/n ) 0 (0, n)(0, +)(0, 1)(0, 1)25基本集合恒等式1. 冪等律AA=A, AA=A2. 交換律AB=BA, AB=BA3. 結(jié)合律(AB)C=A(BC) (AB)C=A(BC)4. 分配律A(BC)=(AB)(AC) A(BC)=(AB)(AC)5. 德摩根律 絕對形式(BC)=BC, (BC)=BC 相對形式 A(BC)=(AB)(AC) A(BC)=(AB)(AC)26基本集合恒等式

13、(續(xù))6. 吸收律 A(AB)=A, A(AB)=A7. 零律 AE=E, A=8. 同一律 A=A,AE=A9. 排中律 AA=E10. 矛盾律 AA=11. 余補律 =E, E=12. 雙重否定律 A=A13. 補交轉(zhuǎn)換律 A-B= AB27基本集合恒等式(續(xù))14. 關(guān)于對稱差的恒等式 (1) 交換律 AB=BA (2) 結(jié)合律 (AB)C=A(BC) (3) 對的分配律 A(BC)=(AB)(AC) (4) A=A, AE= A (5) AA=, A A= E注意: 對沒有分配律, 反例如下 A=a,b,c, B=b,c,d, C=c,d,e A(BC)= a,b,cb,e= a,b,

14、c,e (AB)(AC)= a,b,c,da,b,c,d,e= e, 兩者不等28證明集合包含或相等方法一. 根據(jù)定義, 通過邏輯等值演算證明方法二. 利用已知集合等式或包含式, 通過集合演算證明例3 證明:(1) AB=BA (交換律)證 x xAB xAxB (并的定義) xBxA (邏輯演算的交換律) xBA (并的定義)29例3(續(xù))(2) A(BC)=(AB)(AC) (分配律)證 x xA(BC) xA(xB xC) (并,交的定義) (xAxB)(xAxC) (邏輯演算的分配律) x(AB)(AC) (并,交的定義)(3) AE=E (零律)證 x xAE xAxE (并的定義)

15、 xA1 (全集E的定義) 1 (邏輯演算的零律) xE (全集E的定義)30例3(續(xù))(4) AE=A (同一律)證 x xAE xAxE (交的定義) xA1 (全集E的定義) xA (邏輯演算的同一律)31實例例4 證明 A(AB)=A （吸收律）證 利用例3證明的4條等式證明 A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = A(BE) (交換律) = AE (零律) = A (同一律)對其余的基本集合恒等式不再一一證明(請自行證明),今后把它們作為已知的集合等式使用.32實例例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)換律)33實例例6 證明 (AB)(AC)= (BC) - A證 (AB)(AC) =(AB) - (AC)(AC) - (AB) =(AB)AC)(AC)AB) = (BAC)(CAB) =(BC)(CB)A =(B-C)(C-B)A