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

電子科技大學(xué)信息與軟件工程學(xué)院 School of Information and Software Engineering, UESTC 2016,集合論與二元關(guān)系,2,第一部分 集合論,預(yù)備知識(shí) 集合的基本概念 屬于、包含 冪集、空集 文氏圖等 集合的基本運(yùn)算 并、交、補(bǔ)、差等 集合恒等式 集合運(yùn)算的算律、恒等式的證明方法,命題邏輯的基本概念,命題與聯(lián)結(jié)詞 命題及其分類 聯(lián)結(jié)詞與復(fù)合命題 命題公式及其賦值,命題與真值 命題：判斷結(jié)果惟一的陳述句 命題的真值：判斷的結(jié)果 真值的取值：真與假 真命題與假命題 注意： 感嘆句、祈使句、疑問(wèn)句都不是命題 陳述句中的悖論，判斷結(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 (i1)表示簡(jiǎn)單命題 用“1”表示真，用“0”表示假 例如，令 p： 是有理數(shù)，則 p 的真值為0， q：2 + 5 = 7，則 q 的真值為1 p, q, r可表示命題常元或者變?cè)?7,否定、合取、析取聯(lián)結(jié)詞,定義1.3 設(shè)p, q為兩個(gè)命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq，稱作析取聯(lián)結(jié)詞. 規(guī)定pq為假當(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的合取式，記作pq，稱作合取聯(lián)結(jié)詞. 規(guī)定pq為真當(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) pq (2) pq (3) pq (4) 設(shè)p:張輝是三好生, q:王麗是三好生 pq (5) p:張輝與王麗是同學(xué) (1)(3) 說(shuō)明描述合取式的靈活性與多樣性 (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ù), pq (2) 令p:2是素?cái)?shù), q:3是素?cái)?shù), pq (3) 令p:4是素?cái)?shù), q:6是素?cái)?shù), pq (4) 令p:小元元拿一個(gè)蘋果, q:小元元拿一個(gè)梨 (pq)(pq) (5) p:王小紅生于 1975 年, q:王小紅生于1976 年, (pq)(pq) 或 pq (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)涵式，記作pq，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，稱作蘊(yùn)涵聯(lián)結(jié)詞. 規(guī)定：pq為假當(dāng)且僅當(dāng)p為真q為假.,蘊(yùn)涵聯(lián)結(jié)詞,(1) pq 的邏輯關(guān)系：q為 p 的必要條件 (2) “如果 p, 則 q” 有很多不同的表述方法： 若p，就q 只要p，就q p僅當(dāng)q 只有q 才p 除非q, 才p 或 除非q，否則非p， (3) 當(dāng) p 為假時(shí)，pq恒為真，稱為空證明 (4) 常出現(xiàn)的錯(cuò)誤：不分充分與必要條件,13,例4 設(shè) p：天冷，q：小王穿羽絨服，將下列命題符號(hào)化 (1) 只要天冷，小王就穿羽絨服. (2) 因?yàn)樘炖?，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷.,蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例,pq,pq,pq,定義1.5 設(shè) p, q為兩個(gè)命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq，稱作等價(jià)聯(lián)結(jié)詞. 規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假. pq 的邏輯關(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) 太陽(yá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是命題公式，則AB，AB ，AB ，AB也是命題公式 （4）有限次應(yīng)用（1）-（3）規(guī)則形成的符號(hào)串才是命題公式，或稱命題形式，簡(jiǎn)稱公式,命題公式,針對(duì)含變?cè)墓?，可進(jìn)行賦值 成真賦值 成假賦值 重言式（永真式） 矛盾式（永假式） 可滿足式,等值式與基本的等值式,等值式 定義2.1 若等價(jià)式AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式 幾點(diǎn)說(shuō)明： 定義中，A, B, 均為元語(yǔ)言符號(hào) A或B中可能有啞元出現(xiàn). 例如，在 (pq) (pq) (rr) 中，r為左邊公式的啞元.,基本的等值式,雙重否定律 AA 冪等律 AAA, AAA 交換律 ABBA, ABBA 結(jié)合律 (AB)CA(BC), (AB)CA(BC) 分配律 A(BC) (AB)(AC), A(BC) (AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A,基本的等值式,零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蘊(yùn)涵等值式 ABAB 等價(jià)等值式 AB(AB)(BA) 假言易位 ABBA 等價(jià)否定等值式 ABAB 歸謬論 (AB)(AB) A 注意：要牢記各個(gè)等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ),等值演算,置換規(guī)則：設(shè)(A)是含公式A的公式，用公式B替換A，得到(B)。如果A B,則 (A) (B) 由已知等值式，應(yīng)用置換規(guī)則，推演出新的等值式的過(guò)程，稱為等值演算 例：證明p (q r ) 和(p q) r 等值 （教材P2）,21,p, q, r, 均表示命題.,聯(lián)結(jié)詞集為, , , , ，p, pq, pq, pq, pq為基本復(fù)合命題. 其中要特別注意理解pq的涵義. 反復(fù)使用, , , , 中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題. 設(shè) p: 是無(wú)理數(shù)，q: 3是奇數(shù)， r: 蘋果是方的， s: 太陽(yáng)繞地球轉(zhuǎn) 則復(fù)合命題 (pq) (rs) 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ì)此是無(wú)能為力的。例如下面的推理： 所有的自然數(shù)都是實(shí)數(shù)，3是自然數(shù)。所以，3是實(shí)數(shù)。 根據(jù)數(shù)學(xué)方面的知識(shí)，我們知道這個(gè)推理是正確的。然而，在命題邏輯中，這個(gè)推理的正確性是無(wú)法證明的，這是因?yàn)樯鲜鐾评碇械娜湓捑呛?jiǎn)單命題，且各不相同，如果把它們形式化為命題邏輯中的公式，以p表“所有的自然數(shù)都是實(shí)數(shù)”，以q表“3是自然數(shù)”，以r表“3是實(shí)數(shù)”，則推理可以寫為： (pq) r,一階謂詞邏輯基本概念,而(pq)r是一個(gè)可滿足式，可知這個(gè)推理無(wú)法在命題邏輯推理理論中得到證明。另外，命題“所有的自然數(shù)都是實(shí)數(shù)”事實(shí)上隱含著“0是實(shí)數(shù)”，“1是實(shí)數(shù)”，“2是實(shí)數(shù)”，等無(wú)窮多個(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ì)象?？梢允蔷唧w的，也可以是抽象的。 個(gè)體域(論域)個(gè)體所構(gòu)成的非空集合。 全總個(gè)體域(無(wú)限域)包含宇宙中一切事物的個(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(n2)個(gè)個(gè)體之間關(guān)系的謂詞稱為n元謂詞。通常用大寫字母F、G、H(可加下標(biāo))來(lái)表示謂詞。如： 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è)?元謂詞即命題。,一階謂詞邏輯基本概念,注意 (1) 多元謂詞中變?cè)捻樞虿煌?，表示的意義也不同。如G(x，y)表“x整除y”，而G(y，x)表“y整除x”。 (2) 在謂詞邏輯中， 、 仍是聯(lián)結(jié)詞，其含義和用法與命題邏輯中的相同。 【例】將下列語(yǔ)句形式化為謂詞邏輯中的命題或命題函數(shù)。 (1) 小王是二年級(jí)大學(xué)生。 (2) 小王是李老師的學(xué)生。 (3) 如果xy且yx，則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)：xy；G(x，y)：x=y。則原句形式化為 (F(x，y)F(y，x)G(x，y),一階謂詞邏輯基本概念,此外，在一般的簡(jiǎn)單命題中，常有一些表示數(shù)量的詞語(yǔ)，諸如“所有的”、“有一些”等等，用來(lái)表示謂詞中的變量取自論域中的全體或部分個(gè)體，例如下面的兩個(gè)陳述句： “對(duì)所有的xD，論斷F(x)為真?！?“對(duì)某些xD，論斷F(x)為真?！?在謂詞邏輯中，我們用量詞把它們形式化。,一階謂詞邏輯基本概念,1 全稱量詞 “” 全稱量詞用來(lái)表示個(gè)體域中的全體。表自然語(yǔ)言中的“所有的”、“任意的”、“每一個(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è)xD，均有F(x)真值為1； xF(x)的真值為0，當(dāng)且僅當(dāng)至少有一個(gè)x0D，使得F(x0)真值為0。,一階謂詞邏輯基本概念,2 存在量詞 “” 存在量詞 用來(lái)表示論域中的部分個(gè)體。表自然語(yǔ)言中的“存在著一些”、“至少有一個(gè)”、“有”等等。如： “我們班有人會(huì)吸煙?！?句子可改寫成：“在我們班有一些x，x會(huì)吸煙?！?取個(gè)體域?yàn)椤拔覀儼嗟耐瑢W(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è)xD，均有G(x)真值為0； xG(x)的真值為1，當(dāng)且僅當(dāng)至少有一個(gè)x0D，均有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 無(wú)限個(gè)體域，如N, Z, R, 全總個(gè)體域宇宙間一切事物組成,一階邏輯謂詞概念總結(jié),謂詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞 謂詞常項(xiàng)：F: 是人，F(xiàn)(a)：a是人 謂詞變項(xiàng)：F: 具有性質(zhì)F，F(xiàn)(x)：x具有性質(zhì)F n（n1）元謂詞 n=1，一元謂詞表示性質(zhì) n2，多元謂詞表示事物之間的關(guān)系 L(x,y)：x與y有關(guān)系L，L(x,y)：xy， （4）0元謂詞不含個(gè)體變項(xiàng)的謂詞命題常項(xiàng)或變項(xiàng) 3. 量詞表示數(shù)量的詞 全程量詞：“”，x 存在量詞：“”，x,一階邏輯謂詞概念總結(jié),例： 在一階邏輯中將下面命題符號(hào)化 人都愛(ài)美 有人用左手寫字 個(gè)體域分別為 (a) D=“人類集合”=x | x是人 (b) D為全總個(gè)體域 解：(a) （1）xG(x), G(x)：x愛(ài)美 （2）xG(x), G(x)：x用左手寫字 (b) F(x)：x為人，G(x)：同(a)中,一階邏輯謂詞概念總結(jié),例 在一階邏輯中將下面命題符號(hào)化 正數(shù)都大于負(fù)數(shù) 有的無(wú)理數(shù)大于有的有理數(shù) 解 注意：題目中沒(méi)給個(gè)體域，一律用全總個(gè)體域 （1）令F(x)：x為正數(shù)，G(y)：y為負(fù)數(shù) L(x,y)：xy x(F(x)y(G(y)L(x,y) xy(F(x)G(y)L(x,y) （以后討論） （2）令F(x)：x是無(wú)理數(shù)，G(y)：y是有理數(shù)， L(x,y)：xy x(F(x)y(G(y)L(x,y) xy(F(x)G(y)L(x,y) （以后討論）,39,集合的基本概念,1. 集合定義 集合沒(méi)有精確的數(shù)學(xué)定義 理解：由離散個(gè)體構(gòu)成的整體稱為集合，稱這些個(gè)體為集合的元素 常見(jiàn)的數(shù)集：N, Z, Q, R, C 等分別表示自然數(shù)、整數(shù)、有理數(shù)、實(shí)數(shù)、復(fù)數(shù)集合,2. 集合表示法 枚舉法-通過(guò)列出全體元素來(lái)表示集合 謂詞表示法-是將集合中元素的共同屬性描述出來(lái) 文氏圖 -用于示意性地表示集合及其包含元素間的關(guān)系 實(shí)例： 枚舉法 自然數(shù)集合 N=0,1,2,3, 謂詞法 S= x | x是實(shí)數(shù)，x21=0,40,元素與集合,1. 集合的元素具有的性質(zhì) 無(wú)序性：元素列出的順序無(wú)關(guān) 相異性：集合的每個(gè)元素只計(jì) 數(shù)一次 確定性：對(duì)任何元素和集合都 能確定這個(gè)元素是否 為該集合的元素 任意性：集合的元素也可以是 集合 2元素與集合的關(guān)系 隸屬關(guān)系：或者 3集合的樹(shù)型層次結(jié)構(gòu),d A , a A,41,集合與集合,集合與集合之間的關(guān)系：, =, , , , 定義1.1 A B x ( xA xB ) 定義1.2 A = B A B B A 定義1.3 A B A B A B A B x ( xA xB ) 思考： 和 的定義 注意 和 是不同層次的問(wèn)題,42,空集、全集和冪集,1定義1.4 空集 ：不含有任何元素的集合 實(shí)例： x | xR x2+1=0 定理1.1 空集是任何集合的子集。 證 對(duì)于任意集合A， A x (xxA) T (恒真命題) 推論 是惟一的,3. 定義1.6 全集 E：包含了所有集合的集合 全集具有相對(duì)性：與問(wèn)題有關(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 并 AB = x | xA xB 交 AB = x | xA xB 相對(duì)補(bǔ) AB = x | xA xB 定義1.8 對(duì)稱差 AB = (AB)(BA) = (AB)-(AB) 定義1.9 絕對(duì)補(bǔ) A = EA,44,文氏圖,集合運(yùn)算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,45,幾點(diǎn)說(shuō)明,并和交運(yùn)算可以推廣到有窮個(gè)集合上，即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAn A B AB = AB = AB = A,46,廣義運(yùn)算,1. 集合的廣義并與廣義交 定義1.10 廣義并 A = x | z ( zA xz ) 廣義交 A= x | z ( zA xz ) 實(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)算的說(shuō)明,2. 廣義運(yùn)算的性質(zhì) (1) =，無(wú)意義 (2) 單元集x的廣義并和廣義交都等于x (3) 廣義運(yùn)算減少集合的層次（括弧減少一層） (4) 廣義運(yùn)算的計(jì)算：一般情況下可以轉(zhuǎn)變成初級(jí)運(yùn)算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An 3. 引入廣義運(yùn)算的意義 可以表示無(wú)數(shù)個(gè)集合的并、交運(yùn)算，例如 x | xR=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)算,例1 A=a,a,b，計(jì)算A(AA). 解： A(AA) = a,b(a,ba) = (ab)(ab)a) = (ab)(ba) = 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 | xZ 1x1000 A= x | xS x可被5整除 B= x | xS x可被6整除 C= x | xS 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 |AB| = 1000/lcm(5,6) = 1000/30 = 33 |AC| = 1000/lcm(5,8) = 1000/40 = 25 |BC| = 1000/lcm(6,8) = 1000/24 = 41 |ABC| = 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ǔ)元律、零律、同一律、否定律,2019/6/29,集合論與圖論第3講,56,對(duì)偶原理(dual principle),對(duì)偶式(dual): 一個(gè)集合關(guān)系式, 如果只含有, , E,=, , 那么, 同時(shí)把與互換, 把與E互換, 把與互換, 得到的式子稱為原式的對(duì)偶式. 對(duì)偶原理: 對(duì)偶式同真假. 或者說(shuō), 集合恒等式的對(duì)偶式還