1.1-2離散數(shù)學課件及復習資料.ppt

1 第1章數(shù)學語言與證明方法 2 第1章數(shù)學語言與證明方法 1 1邏輯符號1 2集合及其運算1 3證明方法概述 3 1 1邏輯符號 命題與真值聯(lián)結(jié)詞 命題公式 重言式 矛盾式 可滿足式 重要等值式重要推理規(guī)則個體 個體域與謂詞全稱量詞與存在量詞 4 聯(lián)結(jié)詞 真值 真 假或1 0命題 具有確定真值的陳述句 通常用p q r等表示真命題 真值為真的命題假命題 真值為假的命題例如 p 2 2 4 q 3是偶數(shù)它們都是命題 p是真命題 q是假命題 否定聯(lián)結(jié)詞 否定式 p 非p p的否定 p為真當且僅當p為假 5 聯(lián)結(jié)詞 續(xù) 合取聯(lián)結(jié)詞 合取式p q p并且q p與q p q為真當且僅當p與q同時為真析取聯(lián)結(jié)詞 析取式p q p或qp q為假當且僅當p與q同時為假排斥或聯(lián)結(jié)詞排斥或pq p并且非q 或者q并且非ppq為真當且僅當p與q中一個為真 另一個為假 6 聯(lián)結(jié)詞 續(xù) 蘊涵聯(lián)結(jié)詞 蘊涵式p q 如果p 則qp q為假當且僅當p為真q為假等價聯(lián)結(jié)詞 等價式p q p當且僅當qp q為真當且僅當p與q同時為真或同時為假 7 實例 設(shè)p 2是偶數(shù) q 1 1 3 則 p的真值為 1 q的真值為 p的真值為 q的真值為 p q的真值為 p q的真值為 p q的真值為 p q的真值為 p q的真值為 p q的真值為 pq的真值為 pq的真值為 p q的真值為 p q的真值為 0 0 1 0 1 1 0 1 1 1 0 0 1 p q的真值為 p q的真值為 0 0 8 實例 續(xù) p q的真值為 p q的真值為 p q的真值為 p q的真值為 0 1 1 1 又設(shè)r 今天是星期一 s 明天是星期二 t 明天是星期三 r s的真值為 r t的真值為 1 不定 9 命題公式 命題變項 取值為0或1的變元 也用p q r等表示 命題公式 用聯(lián)結(jié)詞和圓括號把命題和命題變項按照一定規(guī)則連接起來的符號串 常用A B C等表示 例如 A p q r p 公式的賦值 對公式中每一個命題變項給定一個值 0或1 公式的成真賦值 使公式為真的賦值 公式的成假賦值 使公式為假的賦值 例如 p 1 q 1 r 1是A的成真賦值 p 0 q 1 r 0是A的成假賦值 10 重言式 矛盾式與可滿足式 重言式 永真式 無成假賦值的命題公式矛盾式 永假式 無成真賦值的命題公式可滿足式 不是矛盾式的命題公式例如 A p q r p 是可滿足式 但不是重言式 B p q p q p q p q 是重言式 C p p q p q 是矛盾式 A B 蘊涵式A B是重言式的簡記 A B 等價式A B是重言式的簡記 稱A與B等值 A B是等值式 11 基本等值式 雙重否定律 A A冪等律A A A A A A交換律A B B A A B B A結(jié)合律 A B C A B C A B C A B C 分配律A B C A B A C A B C A B A C 德 摩根律 A B A B A B A B 12 基本等值式 續(xù) 吸收律A A B A A A B A零律A 1 1 A 0 0同一律A 0 A A 1 A排中律A A 1矛盾律A A 0蘊涵等值式A B A B等價等值式A B A B B A 假言易位等值式A B B A等價否定等值式A B A B歸謬論 A B A B A 13 重要推理規(guī)則 推理定律 附加律A A B 化簡律 A B A假言推理 A B A B拒取式 A B B A析取三段論 A B B A假言三段論 A B B C A C 等價三段論 A B B C A C 構(gòu)造性二難 A B C D A C B D 破壞性二難 A B C D B D A C 14 謂詞與量詞 個體域 被研究對象的全體 如自然數(shù)集 人類等 個體詞 個體域中的一個元素 全稱量詞 表示任意的 所有的 一切的等 存在量詞 表示存在 有的 至少有一個等 謂詞 表示個體詞性質(zhì)或相互之間關(guān)系的詞例如 謂詞P x 表示x具有性質(zhì)P xP x 表示個體域中所有的x具有性質(zhì)P xP x 表示個體域中存在x具有性質(zhì)P 15 1 2集合及其運算 集合及其表示法包含 子集 與相等空集與全集集合運算 基本集合恒等式包含與相等的證明方法 16 集合的概念 樸素集合論 康托 G Cantor 羅素 Russell 悖論集合是數(shù)學中最基本的概念 沒有嚴格的定義理解成某些個體組成的整體 常用A B C等表示元素 集合中的個體x A x屬于A x是A的元素x A x不屬于A x不是A的元素無窮集 元素個數(shù)無限的集合有窮集 有限集 元素個數(shù)有限的集合 A A中元素個數(shù)k元集 k個元素的集合 k 0 17 集合的表示法 列舉法如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 有理數(shù)集Q 非零有理數(shù)集Q 實數(shù)集R 非零實數(shù)集R 復數(shù)集C 區(qū)間 a b a b 等 18 包含與相等 包含 子集 A B x x A x B 不包含A B x x A x B 相等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 A A B B A C D性質(zhì) 1 A A 2 A B B C A C 19 空集與全集 空集 不含任何元素的集合例如 x x2 0 x R 定理1 1空集是任何集合的子集證用歸謬法 假設(shè)不然 則存在集合A 使得 A 即存在x x 且x A 矛盾 推論空集是惟一的 證假設(shè)存在 1和 2 則 1 2且 1 2 因此 1 2全集E 限定所討論的集合都是E的子集 相對性 20 冪集 冪集P A A的所有子集組成的集合 即P A x x A 例如 設(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證 21 集合運算 并A B x x A x B 交A B x x A x B 相對補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 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 其他 同級別的按從左到右運算 22 實例 例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是北京人或喜歡聽音樂 但不是數(shù)學系學生 x x是外地走讀生 x x是北京住校生 并且喜歡聽音樂 x x是不喜歡聽音樂的住校生 23 文氏圖表示 24 集合運算 續(xù) 并和交運算可以推廣到有窮個集合上A1 A2 An x x A1 x A2 x An A1 A2 An x x A1 x A2 x An 并和交運算還可以推廣到可數(shù)無窮個集合上A1 A2 x i i 1 2 x Ai A1 A2 x i i 1 2 x Ai 25 實例 例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 26 基本集合恒等式 1 冪等律A A A A A A2 交換律A B B A A B B A3 結(jié)合律 A B 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 C A B A C 27 基本集合恒等式 續(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 12 雙重否定律 A A13 補交轉(zhuǎn)換律A B A B 28 基本集合恒等式 續(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 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 兩者不等 29 證明集合包含或相等 方法一 根據(jù)定義 通過邏輯等值演算證明方法二 利用已知集合等式或包含式 通過集合演算證明例3證明 1 A B B A 交換律 證 xx A B x A x B 并的定義 x B x A 邏輯演算的交換律 x B A 并的定義 30 例3 續(xù) 2 A B C A B A C 分配律 證 xx 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 零律 證 xx A E x A x E 并的定義 x A 1 全集E的定義 1 邏輯演算的零律 x E 全集E的定義 31 例3 續(xù) 4 A E A 同一律 證 xx A E x A x E 交的定義 x A 1 全集E的定義 x A 邏輯演算的同一律 32 實例 例4證明A A B A 吸收律 證利用例3證明的4條等式證明A A B A E A B 同一律 A E B 分配律 A B E 交換律 A E 零律 A 同一律 對其余的基本集合恒等式不再一一證明 請自行證明 今后把它們作為已知的集合等式使用 33 實例 例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)換律 34 實例 例6證明 A B A C B C A證 A B A C 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 35 實例 例7設(shè)