DM-專題1：集合和二元關系.ppt

電子科技大學信息與軟件工程學院 School of Information and Software Engineering, UESTC 2016,集合論與二元關系,2,第一部分 集合論,預備知識 集合的基本概念 屬于、包含 冪集、空集 文氏圖等 集合的基本運算 并、交、補、差等 集合恒等式 集合運算的算律、恒等式的證明方法,命題邏輯的基本概念,命題與聯(lián)結詞 命題及其分類 聯(lián)結詞與復合命題 命題公式及其賦值,命題與真值 命題：判斷結果惟一的陳述句 命題的真值：判斷的結果 真值的取值：真與假 真命題與假命題 注意： 感嘆句、祈使句、疑問句都不是命題 陳述句中的悖論，判斷結果不惟一確定的不是命題,命題與聯(lián)結詞,5,例1 下列句子中那些是命題？ (1) 是有理數(shù). (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室嗎？ (5) 這個蘋果真大呀！ (6) 請不要講話！ (7) 2050年元旦下大雪.,假命題,命題概念,真命題,不是命題,不是命題,不是命題,不是命題,命題，但真值現(xiàn)在不知道,6,命題分類：簡單命題（也稱原子命題）與復合命題 簡單命題符號化 用小寫英文字母 p, q, r, , pi, qi, ri (i1)表示簡單命題 用“1”表示真，用“0”表示假 例如，令 p： 是有理數(shù)，則 p 的真值為0， q：2 + 5 = 7，則 q 的真值為1 p, q, r可表示命題常元或者變元,7,否定、合取、析取聯(lián)結詞,定義1.3 設p, q為兩個命題，復合命題“p或q”稱作p與q的析取式，記作pq，稱作析取聯(lián)結詞. 規(guī)定pq為假當且僅當p與q同時為假.,定義1.1 設 p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結詞. 規(guī)定p 為真當且僅當p為假.,定義1.2 設p,q為兩個命題，復合命題“p并且q”(或“p與 q”)稱為p與q的合取式，記作pq，稱作合取聯(lián)結詞. 規(guī)定pq為真當且僅當p與q同時為真.,8,例2 將下列命題符號化. (1) 吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明. (3) 吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學.,合取聯(lián)結詞的實例,9,解 令p:吳穎用功, q:吳穎聰明 (1) pq (2) pq (3) pq (4) 設p:張輝是三好生, q:王麗是三好生 pq (5) p:張輝與王麗是同學 (1)(3) 說明描述合取式的靈活性與多樣性 (4)(5) 要求分清 “與” 所聯(lián)結的成分,合取聯(lián)結詞的實例,10,例3 將下列命題符號化 (1) 2 或 4 是素數(shù). (2) 2 或 3 是素數(shù). (3) 4 或 6 是素數(shù). (4) 小元元只能拿一個蘋果或一個梨. (5) 王小紅生于 1975 年或 1976 年.,析取聯(lián)結詞的實例,11,解 (1) 令p:2是素數(shù), q:4是素數(shù), pq (2) 令p:2是素數(shù), q:3是素數(shù), pq (3) 令p:4是素數(shù), q:6是素數(shù), pq (4) 令p:小元元拿一個蘋果, q:小元元拿一個梨 (pq)(pq) (5) p:王小紅生于 1975 年, q:王小紅生于1976 年, (pq)(pq) 或 pq (1)(3) 為相容或 (4)(5) 為排斥或, 符號化時(5)可有兩種形式，而(4)則不能,析取聯(lián)結詞的實例,12,定義1.4 設p, q為兩個命題，復合命題“如果p, 則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結詞. 規(guī)定：pq為假當且僅當p為真q為假.,蘊涵聯(lián)結詞,(1) pq 的邏輯關系：q為 p 的必要條件 (2) “如果 p, 則 q” 有很多不同的表述方法： 若p，就q 只要p，就q p僅當q 只有q 才p 除非q, 才p 或 除非q，否則非p， (3) 當 p 為假時，pq恒為真，稱為空證明 (4) 常出現(xiàn)的錯誤：不分充分與必要條件,13,例4 設 p：天冷，q：小王穿羽絨服，將下列命題符號化 (1) 只要天冷，小王就穿羽絨服. (2) 因為天冷，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷.,蘊涵聯(lián)結詞的實例,pq,pq,pq,定義1.5 設 p, q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結詞. 規(guī)定pq為真當且僅當p與q同時為真或同時為假. pq 的邏輯關系：p與q互為充分必要條件,等價聯(lián)結詞,例5 求下列復合命題的真值 (1) 2 + 2 4 當且僅當 3 + 3 6. (2) 2 + 2 4 當且僅當 3 是偶數(shù). (3) 2 + 2 4 當且僅當 太陽從東方升起. (4) 2 + 2 4 當且僅當 美國位于非洲. (5) 函數(shù) f (x) 在 x0 可導的充要條件是 它在 x0 連續(xù).,1,0,0,1,0,命題公式,（1）單個命題命題常元或者變元是命題公式 （2）若A是命題公式，A也是命題公式 （3）若A,B是命題公式，則AB，AB ，AB ，AB也是命題公式 （4）有限次應用（1）-（3）規(guī)則形成的符號串才是命題公式，或稱命題形式，簡稱公式,命題公式,針對含變元的公式，可進行賦值 成真賦值 成假賦值 重言式（永真式） 矛盾式（永假式） 可滿足式,等值式與基本的等值式,等值式 定義2.1 若等價式AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式 幾點說明： 定義中，A, B, 均為元語言符號 A或B中可能有啞元出現(xiàn). 例如，在 (pq) (pq) (rr) 中，r為左邊公式的啞元.,基本的等值式,雙重否定律 AA 冪等律 AAA, AAA 交換律 ABBA, ABBA 結合律 (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 蘊涵等值式 ABAB 等價等值式 AB(AB)(BA) 假言易位 ABBA 等價否定等值式 ABAB 歸謬論 (AB)(AB) A 注意：要牢記各個等值式，這是繼續(xù)學習的基礎,等值演算,置換規(guī)則：設(A)是含公式A的公式，用公式B替換A，得到(B)。如果A B,則 (A) (B) 由已知等值式，應用置換規(guī)則，推演出新的等值式的過程，稱為等值演算 例：證明p (q r ) 和(p q) r 等值 （教材P2）,21,p, q, r, 均表示命題.,聯(lián)結詞集為, , , , ，p, pq, pq, pq, pq為基本復合命題. 其中要特別注意理解pq的涵義. 反復使用, , , , 中的聯(lián)結詞組成更為復雜的復合命題. 設 p: 是無理數(shù)，q: 3是奇數(shù)， r: 蘋果是方的， s: 太陽繞地球轉 則復合命題 (pq) (rs) p) 是假命題.,命題相關小結,聯(lián)結詞的運算順序：, , , , , 同級按先出現(xiàn)者先運算.,一階謂詞邏輯基本概念,在命題邏輯中，我們把命題分析到簡單命題為止，而簡單命題是不再進行分析的基本元素，因此，當推理涉及到簡單命題的結構時，命題邏輯對此是無能為力的。例如下面的推理： 所有的自然數(shù)都是實數(shù)，3是自然數(shù)。所以，3是實數(shù)。 根據(jù)數(shù)學方面的知識，我們知道這個推理是正確的。然而，在命題邏輯中，這個推理的正確性是無法證明的，這是因為上述推理中的三句話均是簡單命題，且各不相同，如果把它們形式化為命題邏輯中的公式，以p表“所有的自然數(shù)都是實數(shù)”，以q表“3是自然數(shù)”，以r表“3是實數(shù)”，則推理可以寫為： (pq) r,一階謂詞邏輯基本概念,而(pq)r是一個可滿足式，可知這個推理無法在命題邏輯推理理論中得到證明。另外，命題“所有的自然數(shù)都是實數(shù)”事實上隱含著“0是實數(shù)”，“1是實數(shù)”，“2是實數(shù)”，等無窮多個命題，單用一個p表示，很難體現(xiàn)這些。 因此，為了能夠進一步深入地研究推理，需要對簡單命題做進一步的分析，將簡單命題的結構分解為個體詞、謂詞、量詞等，并討論它們與推理之間的關系，這一部分的內容稱為一階邏輯(謂詞邏輯)。,一階謂詞邏輯基本概念,首先我們將簡單命題的結構分解成個體和謂詞。 個體(客體)我們討論的對象?？梢允蔷唧w的，也可以是抽象的。 個體域(論域)個體所構成的非空集合。 全總個體域(無限域)包含宇宙中一切事物的個體域 謂詞簡單命題中，表示一個個體的性質或多個個體間的關系的詞。 之所以稱之為謂詞，是因為謂詞和個體詞一起構成了簡單命題中的主謂結構。如： 小王是學生。 3是素數(shù)。 2整除6。 3位于2與5之間。,一階謂詞邏輯基本概念,上面這些簡單命題中，小王、2、3、5、6均是個體，“是學生”，“是素數(shù)”，“整除”，“位于與之間”均是謂詞。前兩個謂詞描述的是一個個體的性質，稱為一元謂詞； 第三個表示兩個個體之間的關系，稱為二元謂詞； 第四個表示三個個體之間的關系，稱為三元謂詞。以此類推，我們將描述n(n2)個個體之間關系的謂詞稱為n元謂詞。通常用大寫字母F、G、H(可加下標)來表示謂詞。如： F表示“是學生”； G表示“整除”； H表示“位于與之間”。,一階謂詞邏輯基本概念,這時F、G、H表示的是具體的謂詞，稱為謂詞常元，否則，稱為謂詞變元。 顯然，單獨的一個謂詞(即使是謂詞常元)并不能構成一個完整的句子，必須以個體詞取代“”方能構成一個句子。 通常用小寫的英文字母a、b、c(可加下標)等表示個體： “小王是學生”可符號化為F(a)，其中a表示小王。若用b表示小李，則F(b)就表示“小李是學生”。若用c1表示2，用c2表示6，則G(c1，c2)就表示“2整除6”,一階謂詞邏輯基本概念,這里，a、b、c1、c2均是具體的個體，稱為個體常元。一般我們用F(x)表示“x是學生”，其中的x稱為個體變元(簡稱變元，亦稱個體詞)。類似地，我們也可用G(x，y)表示“x整除y”。 由謂詞符和變元符組成的符號串稱為命題函數(shù)。只有謂詞為常元并將其中的變元代以具體的個體后，才能構成命題。例如： “G(x，y)：x整除y?！?并不是命題，但若取a：2，b：6，則G(a，a)，G(a，b)以及G(b，a)均是命題，前兩個是真命題，第三個是假命題。G(a，a)、G(a，b)等稱為0元謂詞，它們不含個體變元，0元謂詞即命題。,一階謂詞邏輯基本概念,注意 (1) 多元謂詞中變元的順序不同，表示的意義也不同。如G(x，y)表“x整除y”，而G(y，x)表“y整除x”。 (2) 在謂詞邏輯中， 、 仍是聯(lián)結詞，其含義和用法與命題邏輯中的相同。 【例】將下列語句形式化為謂詞邏輯中的命題或命題函數(shù)。 (1) 小王是二年級大學生。 (2) 小王是李老師的學生。 (3) 如果xy且yx，則x=y。,一階謂詞邏輯基本概念,解： (1) 令F(x)：x是大學生；G(x)：x是二年級的； a：小王。則原句形式化為： F(a)G(a) (2) 令F(x，y)：x是y的學生；a：小王；b：李老師。則原句形式化為： F(a，b) (3) 令F(x，y)：xy；G(x，y)：x=y。則原句形式化為 (F(x，y)F(y，x)G(x，y),一階謂詞邏輯基本概念,此外，在一般的簡單命題中，常有一些表示數(shù)量的詞語，諸如“所有的”、“有一些”等等，用來表示謂詞中的變量取自論域中的全體或部分個體，例如下面的兩個陳述句： “對所有的xD，論斷F(x)為真。” “對某些xD，論斷F(x)為真?！?在謂詞邏輯中，我們用量詞把它們形式化。,一階謂詞邏輯基本概念,1 全稱量詞 “” 全稱量詞用來表示個體域中的全體。表自然語言中的“所有的”、“任意的”、“每一個”等等。如： “任意偶數(shù)均能被2整除?！?句子可改寫成：“在偶數(shù)集合中的任意的x，x能被2整除?！?取個體域為偶數(shù)集，用F(x)表示“x能被2整除”，用 x表示“任意的x”，則原句形式化為： xF(x),一階謂詞邏輯基本概念,注意 xF(x)表示的是“在個體域中，任意的x均有F(x)這個性質”，這是一個可以確定真值的命題。當個體域D為有窮集時： xF(x)的真值為1，當且僅當對于每一個xD，均有F(x)真值為1； xF(x)的真值為0，當且僅當至少有一個x0D，使得F(x0)真值為0。,一階謂詞邏輯基本概念,2 存在量詞 “” 存在量詞 用來表示論域中的部分個體。表自然語言中的“存在著一些”、“至少有一個”、“有”等等。如： “我們班有人會吸煙?！?句子可改寫成：“在我們班有一些x，x會吸煙。” 取個體域為“我們班的同學”，用G(x)表示“x會吸煙”，用 x表示“有些x”，則原句形式化為： xG(x),一階謂詞邏輯基本概念,注意 xG(x)表示的是“在個體域中，至少有一個x具有G(x)這個性質”，這是一個可以確定真值的命題。當個體域D為有窮集時，不妨設D=a1，a2，an： xG(x)的真值為0，當且僅當對于每一個xD，均有G(x)真值為0； xG(x)的真值為1，當且僅當至少有一個x0D，均有G(x0)真值為1。,一階邏輯謂詞概念總結,基本概念個體詞、謂詞、量詞 個體（個體詞）所研究對象中可以獨立存在的具體或抽象的客體（名詞或代詞充當） 個體常項：具體的事務，用a, b, c表示 個體變項：抽象的事物，用x, y, z表示 各體域個體變項的取值范圍 有限個體域，如a, b, c, 1, 2 無限個體域，如N, Z, R, 全總個體域宇宙間一切事物組成,一階邏輯謂詞概念總結,謂詞表示個體詞性質或相互之間關系的詞 謂詞常項：F: 是人，F(xiàn)(a)：a是人 謂詞變項：F: 具有性質F，F(xiàn)(x)：x具有性質F n（n1）元謂詞 n=1，一元謂詞表示性質 n2，多元謂詞表示事物之間的關系 L(x,y)：x與y有關系L，L(x,y)：xy， （4）0元謂詞不含個體變項的謂詞命題常項或變項 3. 量詞表示數(shù)量的詞 全程量詞：“”，x 存在量詞：“”，x,一階邏輯謂詞概念總結,例： 在一階邏輯中將下面命題符號化 人都愛美 有人用左手寫字 個體域分別為 (a) D=“人類集合”=x | x是人 (b) D為全總個體域 解：(a) （1）xG(x), G(x)：x愛美 （2）xG(x), G(x)：x用左手寫字 (b) F(x)：x為人，G(x)：同(a)中,一階邏輯謂詞概念總結,例 在一階邏輯中將下面命題符號化 正數(shù)都大于負數(shù) 有的無理數(shù)大于有的有理數(shù) 解 注意：題目中沒給個體域，一律用全總個體域 （1）令F(x)：x為正數(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) （以后討論） （2）令F(x)：x是無理數(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. 集合定義 集合沒有精確的數(shù)學定義 理解：由離散個體構成的整體稱為集合，稱這些個體為集合的元素 常見的數(shù)集：N, Z, Q, R, C 等分別表示自然數(shù)、整數(shù)、有理數(shù)、實數(shù)、復數(shù)集合,2. 集合表示法 枚舉法-通過列出全體元素來表示集合 謂詞表示法-是將集合中元素的共同屬性描述出來 文氏圖 -用于示意性地表示集合及其包含元素間的關系 實例： 枚舉法 自然數(shù)集合 N=0,1,2,3, 謂詞法 S= x | x是實數(shù)，x21=0,40,元素與集合,1. 集合的元素具有的性質 無序性：元素列出的順序無關 相異性：集合的每個元素只計 數(shù)一次 確定性：對任何元素和集合都 能確定這個元素是否 為該集合的元素 任意性：集合的元素也可以是 集合 2元素與集合的關系 隸屬關系：或者 3集合的樹型層次結構,d A , a A,41,集合與集合,集合與集合之間的關系：, =, , , , 定義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 ) 思考： 和 的定義 注意 和 是不同層次的問題,42,空集、全集和冪集,1定義1.4 空集 ：不含有任何元素的集合 實例： x | xR x2+1=0 定理1.1 空集是任何集合的子集。 證 對于任意集合A， A x (xxA) T (恒真命題) 推論 是惟一的,3. 定義1.6 全集 E：包含了所有集合的集合 全集具有相對性：與問題有關，不存在絕對的全集,2. 定義1.5 冪集：P(A)= x | x A 實例：P()=, P()=, 計數(shù)：如果 |A|=n，則 |P(A)|=2n.,43,集合的運算,初級運算 集合的基本運算有 定義1.7 并 AB = x | xA xB 交 AB = x | xA xB 相對補 AB = x | xA xB 定義1.8 對稱差 AB = (AB)(BA) = (AB)-(AB) 定義1.9 絕對補 A = EA,44,文氏圖,集合運算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,45,幾點說明,并和交運算可以推廣到有窮個集合上，即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAn A B AB = AB = AB = A,46,廣義運算,1. 集合的廣義并與廣義交 定義1.10 廣義并 A = x | z ( zA xz ) 廣義交 A= x | z ( zA xz ) 實例 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,關于廣義運算的說明,2. 廣義運算的性質 (1) =，無意義 (2) 單元集x的廣義并和廣義交都等于x (3) 廣義運算減少集合的層次（括弧減少一層） (4) 廣義運算的計算：一般情況下可以轉變成初級運算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An 3. 引入廣義運算的意義 可以表示無數(shù)個集合的并、交運算，例如 x | xR=R 這里的 R 代表實數(shù)集合.,48,運算的優(yōu)先權規(guī)定,1 類運算：初級運算, , , ， 優(yōu)先順序由括號確定 2 類運算：廣義運算和運算， 運算由右向左進行 混合運算：2 類運算優(yōu)先于1 類運算,例1 A=a,a,b，計算A(AA). 解： A(AA) = a,b(a,ba) = (ab)(ab)a) = (ab)(ba) = b,49,有窮集合元素的計數(shù),1. 文氏圖法 2. 包含排斥原理 定理 設集合S上定義了n條性質，其中具有第 i 條性質的 元素構成子集Ai, 那么集合中不具有任何性質的元素數(shù)為,推論 S中至少具有一條性質的元素數(shù)為,50,實例,例2 求1到1000之間（包含1和1000在內）既不能被5和6整除，也不能被8整除的數(shù)有多少個？,解 嘗試方法一：文氏圖 定義以下集合： S= x | xZ 1x1000 A= x | xS x可被5整除 B= x | xS x可被6整除 C= x | xS x可被8整除 畫出文氏圖，然后填入相應的數(shù)字，但是A,B,C之間有交集，所以難以計算,A,B,C,200,166,125,8,33,25,41,51,實例,方法二利用容斥原理 |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只涉及一個運算的算律： 交換律、結合律、冪等律,53,集合算律,2涉及兩個不同運算的算律： 分配律、吸收律,54,集合算律,3涉及補運算的算律： DM律，雙重否定律,55,集合算律,4涉及全集和空集的算律： 補元律、零律、同一律、否定律,2019/6/29,集合論與圖論第3講,56,對偶原理(dual principle),對偶式(dual): 一個集合關系式, 如果只含有, , E,=, , 那么, 同時把與互換, 把與E互換, 把與互換, 得到的式子稱為原式的對偶式. 對偶原理: 對偶式同真假. 或者說, 集合恒等式的對偶式還