DM-專題1：集合和二元關(guān)系.ppt

《DM-專題1：集合和二元關(guān)系.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《DM-專題1：集合和二元關(guān)系.ppt（65頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

電子科技大學(xué)信息與軟件工程學(xué)院SchoolofInformationandSoftwareEngineering UESTC2016 集合論與二元關(guān)系 2 第一部分集合論 預(yù)備知識(shí)集合的基本概念屬于 包含冪集 空集文氏圖等集合的基本運(yùn)算并 交 補(bǔ) 差等集合恒等式集合運(yùn)算的算律 恒等式的證明方法 命題邏輯的基本概念 命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值 命題與真值命題 判斷結(jié)果惟一的陳述句命題的真值 判斷的結(jié)果真值的取值 真與假真命題與假命題注意 感嘆句 祈使句 疑問句都不是命題陳述句中的悖論 判斷結(jié)果不惟一確定的不是命題 命題與聯(lián)結(jié)詞 5 例1下列句子中那些是命題 1 是有理數(shù) 2 2 5 7 3 x 5 3 4 你去教室嗎 5 這個(gè)蘋果真大呀 6 請(qǐng)不要講話 7 2050年元旦下大雪 假命題 命題概念 真命題 不是命題 不是命題 不是命題 不是命題 命題 但真值現(xiàn)在不知道 6 命題分類 簡(jiǎn)單命題 也稱原子命題 與復(fù)合命題簡(jiǎn)單命題符號(hào)化用小寫英文字母p q r pi qi ri i 1 表示簡(jiǎn)單命題用 1 表示真 用 0 表示假例如 令p 是有理數(shù) 則p的真值為0 q 2 5 7 則q的真值為1p q r 可表示命題常元或者變?cè)?7 否定 合取 析取聯(lián)結(jié)詞 定義1 3設(shè)p q為兩個(gè)命題 復(fù)合命題 p或q 稱作p與q的析取式 記作p q 稱作析取聯(lián)結(jié)詞 規(guī)定p q為假當(dāng)且僅當(dāng)p與q同時(shí)為假 定義1 1設(shè)p為命題 復(fù)合命題 非p 或 p的否定 稱為p的否定式 記作 p 符號(hào) 稱作否定聯(lián)結(jié)詞 規(guī)定 p為真當(dāng)且僅當(dāng)p為假 定義1 2設(shè)p q為兩個(gè)命題 復(fù)合命題 p并且q 或 p與q 稱為p與q的合取式 記作p q 稱作合取聯(lián)結(jié)詞 規(guī)定p q為真當(dāng)且僅當(dāng)p與q同時(shí)為真 8 例2將下列命題符號(hào)化 1 吳穎既用功又聰明 2 吳穎不僅用功而且聰明 3 吳穎雖然聰明 但不用功 4 張輝與王麗都是三好生 5 張輝與王麗是同學(xué) 合取聯(lián)結(jié)詞的實(shí)例 9 解令p 吳穎用功 q 吳穎聰明 1 p q 2 p q 3 p q 4 設(shè)p 張輝是三好生 q 王麗是三好生p q 5 p 張輝與王麗是同學(xué) 1 3 說明描述合取式的靈活性與多樣性 4 5 要求分清 與 所聯(lián)結(jié)的成分 合取聯(lián)結(jié)詞的實(shí)例 10 例3將下列命題符號(hào)化 1 2或4是素?cái)?shù) 2 2或3是素?cái)?shù) 3 4或6是素?cái)?shù) 4 小元元只能拿一個(gè)蘋果或一個(gè)梨 5 王小紅生于1975年或1976年 析取聯(lián)結(jié)詞的實(shí)例 11 解 1 令p 2是素?cái)?shù) q 4是素?cái)?shù) p q 2 令p 2是素?cái)?shù) q 3是素?cái)?shù) p q 3 令p 4是素?cái)?shù) q 6是素?cái)?shù) p q 4 令p 小元元拿一個(gè)蘋果 q 小元元拿一個(gè)梨 p q p q 5 p 王小紅生于1975年 q 王小紅生于1976年 p q p q 或p q 1 3 為相容或 4 5 為排斥或 符號(hào)化時(shí) 5 可有兩種形式 而 4 則不能 析取聯(lián)結(jié)詞的實(shí)例 12 定義1 4設(shè)p q為兩個(gè)命題 復(fù)合命題 如果p 則q 稱作p與q的蘊(yùn)涵式 記作p q 并稱p是蘊(yùn)涵式的前件 q為蘊(yùn)涵式的后件 稱作蘊(yùn)涵聯(lián)結(jié)詞 規(guī)定 p q為假當(dāng)且僅當(dāng)p為真q為假 蘊(yùn)涵聯(lián)結(jié)詞 1 p q的邏輯關(guān)系 q為p的必要條件 2 如果p 則q 有很多不同的表述方法 若p 就q只要p 就qp僅當(dāng)q只有q才p除非q 才p或除非q 否則非p 3 當(dāng)p為假時(shí) p q恒為真 稱為空證明 4 常出現(xiàn)的錯(cuò)誤 不分充分與必要條件 13 例4設(shè)p 天冷 q 小王穿羽絨服 將下列命題符號(hào)化 1 只要天冷 小王就穿羽絨服 2 因?yàn)樘炖?所以小王穿羽絨服 3 若小王不穿羽絨服 則天不冷 蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例 p q p q p q 定義1 5設(shè)p q為兩個(gè)命題 復(fù)合命題 p當(dāng)且僅當(dāng)q 稱作p與q的等價(jià)式 記作p q 稱作等價(jià)聯(lián)結(jié)詞 規(guī)定p q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假 p q的邏輯關(guān)系 p與q互為充分必要條件 等價(jià)聯(lián)結(jié)詞 例5求下列復(fù)合命題的真值 1 2 2 4當(dāng)且僅當(dāng)3 3 6 2 2 2 4當(dāng)且僅當(dāng)3是偶數(shù) 3 2 2 4當(dāng)且僅當(dāng)太陽從東方升起 4 2 2 4當(dāng)且僅當(dāng)美國(guó)位于非洲 5 函數(shù)f x 在x0可導(dǎo)的充要條件是它在x0連續(xù) 1 0 0 1 0 命題公式 1 單個(gè)命題命題常元或者變?cè)敲}公式 2 若A是命題公式 A也是命題公式 3 若A B是命題公式 則A B A B A B A B也是命題公式 4 有限次應(yīng)用 1 3 規(guī)則形成的符號(hào)串才是命題公式 或稱命題形式 簡(jiǎn)稱公式 命題公式 針對(duì)含變?cè)墓?可進(jìn)行賦值成真賦值成假賦值重言式 永真式 矛盾式 永假式 可滿足式 等值式與基本的等值式 等值式定義2 1若等價(jià)式A B是重言式 則稱A與B等值 記作A B 并稱A B是等值式幾點(diǎn)說明 定義中 A B 均為元語言符號(hào)A或B中可能有啞元出現(xiàn) 例如 在 p q p q r r 中 r為左邊公式的啞元 基本的等值式 雙重否定律 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吸收律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蘊(yùn)涵等值式A B A B等價(jià)等值式A B A B B A 假言易位A B B A等價(jià)否定等值式A B A B歸謬論 A B A B A注意 要牢記各個(gè)等值式 這是繼續(xù)學(xué)習(xí)的基礎(chǔ) 等值演算 置換規(guī)則 設(shè) A 是含公式A的公式 用公式B替換A 得到 B 如果A B 則 A B 由已知等值式 應(yīng)用置換規(guī)則 推演出新的等值式的過程 稱為等值演算例 證明p q r 和 p q r等值 教材P2 21 p q r 均表示命題 聯(lián)結(jié)詞集為 p p q p q p q p q為基本復(fù)合命題 其中要特別注意理解p q的涵義 反復(fù)使用 中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題 設(shè)p 是無理數(shù) q 3是奇數(shù) r 蘋果是方的 s 太陽繞地球轉(zhuǎn)則復(fù)合命題 p q r s p 是假命題 命題相關(guān)小結(jié) 聯(lián)結(jié)詞的運(yùn)算順序 同級(jí)按先出現(xiàn)者先運(yùn)算 一階謂詞邏輯基本概念 在命題邏輯中 我們把命題分析到簡(jiǎn)單命題為止 而簡(jiǎn)單命題是不再進(jìn)行分析的基本元素 因此 當(dāng)推理涉及到簡(jiǎn)單命題的結(jié)構(gòu)時(shí) 命題邏輯對(duì)此是無能為力的 例如下面的推理 所有的自然數(shù)都是實(shí)數(shù) 3是自然數(shù) 所以 3是實(shí)數(shù) 根據(jù)數(shù)學(xué)方面的知識(shí) 我們知道這個(gè)推理是正確的 然而 在命題邏輯中 這個(gè)推理的正確性是無法證明的 這是因?yàn)樯鲜鐾评碇械娜湓捑呛?jiǎn)單命題 且各不相同 如果把它們形式化為命題邏輯中的公式 以p表 所有的自然數(shù)都是實(shí)數(shù) 以q表 3是自然數(shù) 以r表 3是實(shí)數(shù) 則推理可以寫為 p q r 一階謂詞邏輯基本概念 而 p q r是一個(gè)可滿足式 可知這個(gè)推理無法在命題邏輯推理理論中得到證明 另外 命題 所有的自然數(shù)都是實(shí)數(shù) 事實(shí)上隱含著 0是實(shí)數(shù) 1是實(shí)數(shù) 2是實(shí)數(shù) 等無窮多個(gè)命題 單用一個(gè)p表示 很難體現(xiàn)這些 因此 為了能夠進(jìn)一步深入地研究推理 需要對(duì)簡(jiǎn)單命題做進(jìn)一步的分析 將簡(jiǎn)單命題的結(jié)構(gòu)分解為個(gè)體詞 謂詞 量詞等 并討論它們與推理之間的關(guān)系 這一部分的內(nèi)容稱為一階邏輯 謂詞邏輯 一階謂詞邏輯基本概念 首先我們將簡(jiǎn)單命題的結(jié)構(gòu)分解成個(gè)體和謂詞 個(gè)體 客體 我們討論的對(duì)象 可以是具體的 也可以是抽象的 個(gè)體域 論域 個(gè)體所構(gòu)成的非空集合 全總個(gè)體域 無限域 包含宇宙中一切事物的個(gè)體域謂詞 簡(jiǎn)單命題中 表示一個(gè)個(gè)體的性質(zhì)或多個(gè)個(gè)體間的關(guān)系的詞 之所以稱之為謂詞 是因?yàn)橹^詞和個(gè)體詞一起構(gòu)成了簡(jiǎn)單命題中的主謂結(jié)構(gòu) 如 小王是學(xué)生 3是素?cái)?shù) 2整除6 3位于2與5之間 一階謂詞邏輯基本概念 上面這些簡(jiǎn)單命題中 小王 2 3 5 6均是個(gè)體 是學(xué)生 是素?cái)?shù) 整除 位于 與 之間 均是謂詞 前兩個(gè)謂詞描述的是一個(gè)個(gè)體的性質(zhì) 稱為一元謂詞 第三個(gè)表示兩個(gè)個(gè)體之間的關(guān)系 稱為二元謂詞 第四個(gè)表示三個(gè)個(gè)體之間的關(guān)系 稱為三元謂詞 以此類推 我們將描述n n 2 個(gè)個(gè)體之間關(guān)系的謂詞稱為n元謂詞 通常用大寫字母F G H 可加下標(biāo) 來表示謂詞 如 F表示 是學(xué)生 G表示 整除 H表示 位于 與 之間 一階謂詞邏輯基本概念 這時(shí)F G H表示的是具體的謂詞 稱為謂詞常元 否則 稱為謂詞變?cè)?顯然 單獨(dú)的一個(gè)謂詞 即使是謂詞常元 并不能構(gòu)成一個(gè)完整的句子 必須以個(gè)體詞取代 方能構(gòu)成一個(gè)句子 通常用小寫的英文字母a b c 可加下標(biāo) 等表示個(gè)體 小王是學(xué)生 可符號(hào)化為F a 其中a表示小王 若用b表示小李 則F b 就表示 小李是學(xué)生 若用c1表示2 用c2表示6 則G c1 c2 就表示 2整除6 一階謂詞邏輯基本概念 這里 a b c1 c2均是具體的個(gè)體 稱為個(gè)體常元 一般我們用F x 表示 x是學(xué)生 其中的x稱為個(gè)體變?cè)?簡(jiǎn)稱變?cè)?亦稱個(gè)體詞 類似地 我們也可用G x y 表示 x整除y 由謂詞符和變?cè)M成的符號(hào)串稱為命題函數(shù) 只有謂詞為常元并將其中的變?cè)跃唧w的個(gè)體后 才能構(gòu)成命題 例如 G x y x整除y 并不是命題 但若取a 2 b 6 則G a a G a b 以及G b a 均是命題 前兩個(gè)是真命題 第三個(gè)是假命題 G a a G a b 等稱為0元謂詞 它們不含個(gè)體變?cè)?0元謂詞即命題 一階謂詞邏輯基本概念 注意 1 多元謂詞中變?cè)捻樞虿煌?表示的意義也不同 如G x y 表 x整除y 而G y x 表 y整除x 2 在謂詞邏輯中 仍是聯(lián)結(jié)詞 其含義和用法與命題邏輯中的相同 例 將下列語句形式化為謂詞邏輯中的命題或命題函數(shù) 1 小王是二年級(jí)大學(xué)生 2 小王是李老師的學(xué)生 3 如果x y且y x 則x y 一階謂詞邏輯基本概念 解 1 令F x x是大學(xué)生 G x x是二年級(jí)的 a 小王 則原句形式化為 F a G a 2 令F x y x是y的學(xué)生 a 小王 b 李老師 則原句形式化為 F a b 3 令F x y x y G x y x y 則原句形式化為 F x y F y x G x y 一階謂詞邏輯基本概念 此外 在一般的簡(jiǎn)單命題中 常有一些表示數(shù)量的詞語 諸如 所有的 有一些 等等 用來表示謂詞中的變量取自論域中的全體或部分個(gè)體 例如下面的兩個(gè)陳述句 對(duì)所有的x D 論斷F x 為真 對(duì)某些x D 論斷F x 為真 在謂詞邏輯中 我們用量詞把它們形式化 一階謂詞邏輯基本概念 1 全稱量詞 全稱量詞 用來表示個(gè)體域中的全體 表自然語言中的 所有的 任意的 每一個(gè) 等等 如 任意偶數(shù)均能被2整除 句子可改寫成 在偶數(shù)集合中的任意的x x能被2整除 取個(gè)體域?yàn)榕紨?shù)集 用F x 表示 x能被2整除 用 x表示 任意的x 則原句形式化為 xF x 一階謂詞邏輯基本概念 注意 xF x 表示的是 在個(gè)體域中 任意的x均有F x 這個(gè)性質(zhì) 這是一個(gè)可以確定真值的命題 當(dāng)個(gè)體域D為有窮集時(shí) xF x 的真值為1 當(dāng)且僅當(dāng)對(duì)于每一個(gè)x D 均有F x 真值為1 xF x 的真值為0 當(dāng)且僅當(dāng)至少有一個(gè)x0 D 使得F x0 真值為0 一階謂詞邏輯基本概念 2 存在量詞 存在量詞 用來表示論域中的部分個(gè)體 表自然語言中的 存在著一些 至少有一個(gè) 有 等等 如 我們班有人會(huì)吸煙 句子可改寫成 在我們班有一些x x會(huì)吸煙 取個(gè)體域?yàn)?我們班的同學(xué) 用G x 表示 x會(huì)吸煙 用 x表示 有些x 則原句形式化為 xG x 一階謂詞邏輯基本概念 注意 xG x 表示的是 在個(gè)體域中 至少有一個(gè)x具有G x 這個(gè)性質(zhì) 這是一個(gè)可以確定真值的命題 當(dāng)個(gè)體域D為有窮集時(shí) 不妨設(shè)D a1 a2 an xG x 的真值為0 當(dāng)且僅當(dāng)對(duì)于每一個(gè)x D 均有G x 真值為0 xG x 的真值為1 當(dāng)且僅當(dāng)至少有一個(gè)x0 D 均有G x0 真值為1 一階邏輯謂詞概念總結(jié) 基本概念 個(gè)體詞 謂詞 量詞個(gè)體 個(gè)體詞 所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體 名詞或代詞充當(dāng) 個(gè)體常項(xiàng) 具體的事務(wù) 用a b c表示個(gè)體變項(xiàng) 抽象的事物 用x y z表示各體域 個(gè)體變項(xiàng)的取值范圍 有限個(gè)體域 如 a b c 1 2 無限個(gè)體域 如N Z R 全總個(gè)體域 宇宙間一切事物組成 一階邏輯謂詞概念總結(jié) 謂詞 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞謂詞常項(xiàng) F 是人 F a a是人謂詞變項(xiàng) F 具有性質(zhì)F F x x具有性質(zhì)Fn n 1 元謂詞 n 1 一元謂詞 表示性質(zhì) n 2 多元謂詞 表示事物之間的關(guān)系L x y x與y有關(guān)系L L x y x y 4 0元謂詞 不含個(gè)體變項(xiàng)的謂詞 命題常項(xiàng)或變項(xiàng)3 量詞 表示數(shù)量的詞全程量詞 x存在量詞 x 一階邏輯謂詞概念總結(jié) 例 在一階邏輯中將下面命題符號(hào)化人都愛美有人用左手寫字個(gè)體域分別為 a D 人類集合 x x是人 b D為全總個(gè)體域解 a 1 xG x G x x愛美 2 xG x G x x用左手寫字 b F x x為人 G x 同 a 中 一階邏輯謂詞概念總結(jié) 例在一階邏輯中將下面命題符號(hào)化正數(shù)都大于負(fù)數(shù)有的無理數(shù)大于有的有理數(shù)解注意 題目中沒給個(gè)體域 一律用全總個(gè)體域 1 令F x x為正數(shù) G y y為負(fù)數(shù)L x y x y x F x y G y L x y x y F x G y L x y 以后討論 2 令F x x是無理數(shù) G y y是有理數(shù) L x y x y x F x y G y L x y x y F x G y L x y 以后討論 39 集合的基本概念 1 集合定義集合沒有精確的數(shù)學(xué)定義理解 由離散個(gè)體構(gòu)成的整體稱為集合 稱這些個(gè)體為集合的元素常見的數(shù)集 N Z Q R C等分別表示自然數(shù) 整數(shù) 有理數(shù) 實(shí)數(shù) 復(fù)數(shù)集合 2 集合表示法枚舉法 通過列出全體元素來表示集合謂詞表示法 是將集合中元素的共同屬性描述出來文氏圖 用于示意性地表示集合及其包含元素間的關(guān)系實(shí)例 枚舉法自然數(shù)集合N 0 1 2 3 謂詞法S x x是實(shí)數(shù) x2 1 0 40 元素與集合 1 集合的元素具有的性質(zhì)無序性 元素列出的順序無關(guān)相異性 集合的每個(gè)元素只計(jì)數(shù)一次確定性 對(duì)任何元素和集合都能確定這個(gè)元素是否為該集合的元素任意性 集合的元素也可以是集合2 元素與集合的關(guān)系隸屬關(guān)系 或者 3 集合的樹型層次結(jié)構(gòu) d A a A 41 集合與集合 集合與集合之間的關(guān)系 定義1 1A B x x A x B 定義1 2A B A B B A定義1 3A B A B A BA B x x A x B 思考 和 的定義注意 和 是不同層次的問題 42 空集 全集和冪集 1 定義1 4空集 不含有任何元素的集合實(shí)例 x x R x2 1 0 定理1 1空集是任何集合的子集 證對(duì)于任意集合A A x x x A T 恒真命題 推論 是惟一的 3 定義1 6全集E 包含了所有集合的集合全集具有相對(duì)性 與問題有關(guān) 不存在絕對(duì)的全集 2 定義1 5冪集 P A x x A 實(shí)例 P P 計(jì)數(shù) 如果 A n 則 P A 2n 43 集合的運(yùn)算 初級(jí)運(yùn)算集合的基本運(yùn)算有定義1 7并A B x x A x B 交A B x x A x B 相對(duì)補(bǔ)A B x x A x B 定義1 8對(duì)稱差A(yù) B A B B A A B A B 定義1 9絕對(duì)補(bǔ) A E A 44 文氏圖 集合運(yùn)算的表示 A B A B A B A B A B A B A B A B A B A 45 幾點(diǎn)說明 并和交運(yùn)算可以推廣到有窮個(gè)集合上 即A1 A2 An x x A1 x A2 x An A1 A2 An x x A1 x A2 x An A B A B A B A B A 46 廣義運(yùn)算 1 集合的廣義并與廣義交定義1 10廣義并 A x z z A x z 廣義交 A x z z A x z 實(shí)例 1 1 2 1 2 3 1 2 3 1 1 2 1 2 3 1 a a a a a a a a 47 關(guān)于廣義運(yùn)算的說明 2 廣義運(yùn)算的性質(zhì) 1 無意義 2 單元集 x 的廣義并和廣義交都等于x 3 廣義運(yùn)算減少集合的層次 括弧減少一層 4 廣義運(yùn)算的計(jì)算 一般情況下可以轉(zhuǎn)變成初級(jí)運(yùn)算 A1 A2 An A1 A2 An A1 A2 An A1 A2 An3 引入廣義運(yùn)算的意義可以表示無數(shù)個(gè)集合的并 交運(yùn)算 例如 x x R R這里的R代表實(shí)數(shù)集合 48 運(yùn)算的優(yōu)先權(quán)規(guī)定 1類運(yùn)算 初級(jí)運(yùn)算 優(yōu)先順序由括號(hào)確定2類運(yùn)算 廣義運(yùn)算和 運(yùn)算 運(yùn)算由右向左進(jìn)行混合運(yùn)算 2類運(yùn)算優(yōu)先于1類運(yùn)算 例1A a a b 計(jì)算 A A A 解 A A A a b a b a a b a b a a b b a b 49 有窮集合元素的計(jì)數(shù) 1 文氏圖法2 包含排斥原理定理設(shè)集合S上定義了n條性質(zhì) 其中具有第i條性質(zhì)的元素構(gòu)成子集Ai 那么集合中不具有任何性質(zhì)的元素?cái)?shù)為 推論S中至少具有一條性質(zhì)的元素?cái)?shù)為 50 實(shí)例 例2求1到1000之間 包含1和1000在內(nèi) 既不能被5和6整除 也不能被8整除的數(shù)有多少個(gè) 解嘗試方法一 文氏圖定義以下集合 S x x Z 1 x 1000 A x x S x可被5整除 B x x S x可被6整除 C x x S x可被8整除 畫出文氏圖 然后填入相應(yīng)的數(shù)字 但是A B C之間有交集 所以難以計(jì)算 A B C 200 166 125 8 33 25 41 51 實(shí)例 方法二 利用容斥原理 S 1000 A 1000 5 200 B 1000 6 166 C 1000 8 125 A B 1000 lcm 5 6 1000 30 33 A C 1000 lcm 5 8 1000 40 25 B C 1000 lcm 6 8 1000 24 41 A B C 1000 lcm 5 6 8 1000 120 8 1000 200 166 125 33 25 41 8 600 52 集合恒等式 集合算律1 只涉及一個(gè)運(yùn)算的算律 交換律 結(jié)合律 冪等律 53 集合算律 2 涉及兩個(gè)不同運(yùn)算的算律 分配律 吸收律 54 集合算律 3 涉及補(bǔ)運(yùn)算的算律 DM律 雙重否定律 55 集合算律 4 涉及全集和空集的算律 補(bǔ)元律 零律 同一律 否定律 2020 2 21 集合論與圖論 第3講 56 對(duì)偶原理 dualprinciple 對(duì)偶式 dual 一個(gè)集合關(guān)系式 如果只含有 E 那么 同時(shí)把 與 互換 把 與E互換 把 與 互換 得到的式子稱為原式的對(duì)偶式 對(duì)偶原理 對(duì)偶式同真假 或者說 集合恒等式的對(duì)偶式還是恒等式 2020 2 21 集合論與圖論 第3講 57 對(duì)偶原理舉例 分配律A B C A B A C A B C A B A C 排中律A A E矛盾律A A 2020 2 21 集合論與圖論 第3講 58 對(duì)偶原理舉例 零律A E EA 同一律A AA E A 2020 2 21 集合論與圖論 第3講 59 對(duì)偶原理舉例 A B AA B A AE A 60 集合證明題 證明方法 命題演算法 等式置換法命題演算證明法的書寫規(guī)范 以下的X和Y代表集合公式 1 證X Y任取x x X x Y 2 證X Y方法一分別證明X Y和Y X方法二任取x x X x Y注意 在使用方法二的格式時(shí) 必須保證每步推理都是充必要的 包含等價(jià)條件的證明 例5證明A B A B B A B A A B 證明思路 確定問題中含有的命題 本題含有命題 確定命題間的關(guān)系 哪些命題是已知條件 哪些命題是要證明的結(jié)論 本題中每個(gè)命題都可以作為已知條件 每個(gè)命題都是要證明的結(jié)論確定證明順序 按照順序依次完成每個(gè)證明 證明集合相等或者包含 62 證明 證明A B A B B A B A A B 證 顯然B A B 下面證明A B B 任取x x A B x A x B x B x B x B因此有A B B 綜合上述 得證 A A A B A A B 由 知A B B 將A B用B代入 63 證明A B A B B A B A A B 假設(shè)A B 即 x A B 那么可知x A且x B 而x B x A B從而與A B A矛盾 假設(shè)A B不成立 那么 x x A x B x A B A B 與條件 矛盾 證明 64 主要內(nèi)容小結(jié) 集合的三種表示法集合與元素之間的隸屬關(guān)系 集合之間的包含關(guān)系的區(qū)別與聯(lián)系特殊集合 空集 全集 冪集文氏圖及有窮集合的計(jì)數(shù)集合的 等運(yùn)算以及廣義 運(yùn)算集合運(yùn)算的算律及其應(yīng)用 65 基本要求 熟練掌握集合的三種表示法能夠判別元素是否屬于給定的集合能夠判別兩個(gè)集合之間是否存在包含 相等 真包含等關(guān)系熟練掌握集合的基本運(yùn)算 普通運(yùn)算和廣義運(yùn)算 掌握證明集合等式或者包含關(guān)系的基本方法