1、河南工業大學離散數學課程組河南工業大學離散數學課程組第1頁集合與關系的結構圖集合與關系的結構圖枚舉法枚舉法有向圖有向圖矩陣矩陣等價關系等價關系有向圖有向圖等價類等價類商集商集劃分劃分偏序關系偏序關系相容類相容類最大相最大相容類容類完全覆蓋完全覆蓋簡化圖簡化圖全序全序哈斯圖哈斯圖計算方法計算方法運算性質運算性質二元關系二元關系概念及表示方法概念及表示方法性質性質自反自反對稱對稱傳遞傳遞反對稱反對稱反自反反自反相容關系相容關系運算運算復合復合求逆求逆閉包閉包重要重要元素元素河南工業大學離散數學課程組河南工業大學離散數學課程組2第第3 3章章 集合與關系集合與關系離 散 數 學河南工業大學河南工業大

2、學信息科學與工程學院信息科學與工程學院河南工業大學離散數學課程組河南工業大學離散數學課程組第3頁第二篇第二篇 集合論集合論n 集合論是現代數學的集合論是現代數學的基礎基礎，幾乎與，幾乎與現代數學的各個分支都有著密切聯系，現代數學的各個分支都有著密切聯系，并且滲透到所有科技領域，是不可缺并且滲透到所有科技領域，是不可缺少的數學工具和表達語言。少的數學工具和表達語言。n 集合論的起源可以追溯到集合論的起源可以追溯到16世紀末世紀末期，為了追尋微積分的堅實基礎，開期，為了追尋微積分的堅實基礎，開始時，人們僅進行了有關數集的研究。始時，人們僅進行了有關數集的研究。18761883年，年，康托爾康托爾(

3、Georg Cantor)發表了一系列有關集合論研究的文章，發表了一系列有關集合論研究的文章，奠定了集合論的深厚基礎。集合論在奠定了集合論的深厚基礎。集合論在程序語言、數據結構、編譯原理、數程序語言、數據結構、編譯原理、數據庫與知識庫、形式語言和人工智能據庫與知識庫、形式語言和人工智能等領域都得到了廣泛的應用，并且還等領域都得到了廣泛的應用，并且還得到了發展。得到了發展。康托爾康托爾河南工業大學離散數學課程組河南工業大學離散數學課程組第4頁第四章內容（自學）第四章內容（自學）第三章內容（重點）第三章內容（重點）第二篇第二篇 集合論集合論主要包括如下內容：主要包括如下內容：n集合論初步集合論初步

4、n二元關系二元關系n函數函數n實數集合與集合的基數實數集合與集合的基數河南工業大學離散數學課程組河南工業大學離散數學課程組第5頁第三章第三章 集合與關系集合與關系n本章的主要內容本章的主要內容n3-1 集合的概念和表示法集合的概念和表示法n3-2 集合的運算集合的運算n3-3 包含排斥原理包含排斥原理*n3-4 序偶和笛卡爾積序偶和笛卡爾積n3-5 關系和表示關系和表示n3-6 關系的性質關系的性質（重點）（重點）n3-7 復合關系和逆關系復合關系和逆關系n3-8 關系的閉包關系的閉包（重點）（重點）n3-9 集合的劃分和覆蓋集合的劃分和覆蓋n3-10 等價關系與等價類等價關系與等價類（重點）

5、（重點）n3-11 相容關系相容關系n3-12 序關系序關系河南工業大學離散數學課程組河南工業大學離散數學課程組第6頁1-2節的內容提要節的內容提要集合間的關系集合間的關系3特殊集合特殊集合4集合的概念集合的概念1集合的概念集合的概念1集合的表示方法集合的表示方法2集合的表示方法集合的表示方法2無限集合無限集合5集合的運算集合的運算5河南工業大學離散數學課程組河南工業大學離散數學課程組第7頁1-2節學習要求節學習要求重點掌握重點掌握一般掌握一般掌握11 1 集合的概念集合的概念及集合間關系及集合間關系2 2 集合的表示集合的表示3 3 集合運算及集合運算及定律定律4 4 冪集冪集P(A)P(A

6、) 21 1 集合的歸納集合的歸納法表示法表示2 2 集合的對稱集合的對稱差運算差運算 河南工業大學離散數學課程組河南工業大學離散數學課程組第8頁3-1 集合集合n一、集合的概念一、集合的概念n集合集合（SET）：）：n即是由一些即是由一些確定確定的的彼此不同彼此不同的客體（事物）匯集的客體（事物）匯集到一起組成一個整體，稱為集合。到一起組成一個整體，稱為集合。n討論：討論：n客體：泛指一切，可以是具體的、抽象的。客體：泛指一切，可以是具體的、抽象的。n元素元素(element，成員，成員)：n 即組成集合的客體，稱之為元素。即組成集合的客體，稱之為元素。n二、集合的記法二、集合的記法n通常用

7、帶通常用帶(不帶不帶)標號的大寫字母標號的大寫字母A、B、C、.、A1、 B1 、C1 、.、X、Y、Z、.表示表示集合集合；n通常用帶（不帶）標號的小寫字母通常用帶（不帶）標號的小寫字母a、b、c、.、a1、 b1 、c1 、.、x、y、z、.表示表示元素元素。河南工業大學離散數學課程組河南工業大學離散數學課程組第9頁固定的符號固定的符號0, 1, 2, 自然數集合自然數集合N, -2, -1, 0, 1, 2, 整數集合整數集合 Ip/q,p,q是整數，且是整數，且q0 有理數集合有理數集合 Q 實數集合實數集合 R復數集合復數集合 C河南工業大學離散數學課程組河南工業大學離散數學課程組第

8、10頁三、集合與元素的關系三、集合與元素的關系n客體客體a與集合與集合A之間的關系只能是之間的關系只能是屬于屬于和和不屬于不屬于之一。之一。na是集合是集合A的元素或的元素或a屬于屬于集合集合A，記為記為a A，稱稱a是是A的的成員，成員，A包含包含a，a在在A中。中。na不是集合不是集合A的元素或的元素或a不屬于不屬于集合集合A，記為記為a A，或者，或者 (a A)，稱稱a不是不是A的成員，的成員，A不包含不包含a，a不在不在A中。中。例如，例如，對元素對元素2和自然數集合和自然數集合N，就有，就有2屬于屬于N，即，即 2 N， 對元素對元素-2和自然數集合和自然數集合N，就有，就有-2不

9、屬于不屬于N，即，即 -2 N。n有限集：有限集：組成集合的元素個數是有限的。組成集合的元素個數是有限的。n|A|：有限集合：有限集合A中元素的個數。中元素的個數。n無限集：無限集：組成集合的元素個數是無限的。組成集合的元素個數是無限的。河南工業大學離散數學課程組河南工業大學離散數學課程組第11頁四、集合的表示方法四、集合的表示方法n 集合是由它包含的元素完全確定的，為了表集合是由它包含的元素完全確定的，為了表示一個集合，通常有：示一個集合，通常有： 枚舉法（列舉法）枚舉法（列舉法） 謂詞表示法（隱式法、敘述法）謂詞表示法（隱式法、敘述法）文氏文氏(Venn)圖圖-輔助的集合的表示方法輔助的集

10、合的表示方法河南工業大學離散數學課程組河南工業大學離散數學課程組第12頁1、枚舉法（顯式表示法）、枚舉法（顯式表示法）n就是把集合的元素（全部或部分）寫在花括號的里面，就是把集合的元素（全部或部分）寫在花括號的里面，每個元素僅寫一次，不考慮順序，并用每個元素僅寫一次，不考慮順序，并用”,”分開分開。例例 （1）命題的真假值組成的集合：）命題的真假值組成的集合：S=T,F （2）Aa，e，i，o，u河南工業大學離散數學課程組河南工業大學離散數學課程組第13頁在使用中，分兩種情況：在使用中，分兩種情況：（1）當集合中元素個數有限且較少時，將元素全部寫出。當集合中元素個數有限且較少時，將元素全部寫出

11、。 例例1：設集合：設集合A是由絕對值不超過是由絕對值不超過3的整數組成。的整數組成。 A=-3, -2, -1, 0, 1, 2, 3（2）當集合當集合A元素的個數元素的個數無限無限或或有限但個數較多有限但個數較多時，不時，不能或不需要一一列舉出來，只要寫出少數元素，以顯能或不需要一一列舉出來，只要寫出少數元素，以顯示出它的規律。（示出它的規律。（當規律不明確，不能用此方法當規律不明確，不能用此方法）。）。 例例2：設集合：設集合B是由自然數的平方構成的集合。是由自然數的平方構成的集合。 B = 0, 1, 4, 9, 16, , n2, 適用場景：適用場景：u一個集合僅含有限個元素。一個集

12、合僅含有限個元素。u一個集合的元素之間有明顯關系一個集合的元素之間有明顯關系 。河南工業大學離散數學課程組河南工業大學離散數學課程組第14頁2、謂詞表示法（隱式法、敘述法）、謂詞表示法（隱式法、敘述法）n用用謂詞謂詞描述集合中描述集合中元素的屬性元素的屬性，稱為謂詞表示法（敘述法、，稱為謂詞表示法（敘述法、隱式法）隱式法）n一般表示方法：一般表示方法：Ax|P(x)n若個體域內，客體若個體域內，客體a使得使得P(a)為真，則為真，則aA，否則，否則a A。n例如：例如：n大于大于10的整數的集合：的整數的集合： S=x| xIx10)n命題的真假值組成的集合：命題的真假值組成的集合：S=F,T

13、=x|x=Fx=Tn適用場景：適用場景：n一個集合含有很多或無窮多個元素；一個集合含有很多或無窮多個元素；n一個集合的元素之間有容易刻畫的共同特征。一個集合的元素之間有容易刻畫的共同特征。n其其突出優點突出優點是原則上不要求列出集合中全部元素，而只要是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性。給出該集合中元素的特性。P(x)是謂詞公式是謂詞公式，x具有的性質具有的性質P代表元素代表元素河南工業大學離散數學課程組河南工業大學離散數學課程組第15頁A3、文氏、文氏(Venn)圖圖-輔助的集合的表示方法輔助的集合的表示方法n文氏文氏(Venn)圖是一種利用平面上的點構成的圖圖是一

14、種利用平面上的點構成的圖形來形象展示集合的一種方法，用一個矩形的形來形象展示集合的一種方法，用一個矩形的內部表示全集，其他集合用矩形內的園面或一內部表示全集，其他集合用矩形內的園面或一封閉曲線圈成的面積來表示。封閉曲線圈成的面積來表示。U河南工業大學離散數學課程組河南工業大學離散數學課程組第16頁說明：說明：n 集合中的元素都是不同的，凡是相同集合中的元素都是不同的，凡是相同的元素，均視為同一個元素；的元素，均視為同一個元素；n1,1,2=1,2n 一旦給定了集合一旦給定了集合A，對于任意客體，對于任意客體a，可以準確地判定可以準確地判定a是否在是否在A中。中。n 集合中的元素是沒有順序的。集

15、合中的元素是沒有順序的。n 2,1=1,2集合的三大特征集合的三大特征1、互異性互異性2、確定性確定性3、無序性無序性集合中的元素可以是集合。集合中的元素可以是集合。如如 S=a,1,2,p,q河南工業大學離散數學課程組河南工業大學離散數學課程組第17頁同一個集合可以用不同的表示方法：同一個集合可以用不同的表示方法：例例n方程方程x2-1=0的所有實數解的集合的所有實數解的集合A；n謂詞法：謂詞法：nA=x|x Rx2-1=0或或nA=x|x是實數且是實數且x2-1=0n枚舉法：枚舉法：nA=1，-1河南工業大學離散數學課程組河南工業大學離散數學課程組第18頁五、集合與集合的關系五、集合與集合

16、的關系n（一）包含關系（一）包含關系n（二）相等關系（二）相等關系n（三）真包含關系（三）真包含關系河南工業大學離散數學課程組河南工業大學離散數學課程組第19頁“包含關系包含關系” 的謂詞表示：的謂詞表示： A B B A ( x)(xAxB)（一）包含關系（一）包含關系n 例：設例：設A = ADA, BASIC, PASCAL ， B = BASIC, PASCAL, ADA,C,JAVA定義：定義： A包含在包含在B內，內，A包含于包含于B，B包含包含A 設設A，B是任意兩個集合，是任意兩個集合，n若若A的每個元素都是的每個元素都是B的元素，的元素，則稱則稱A是是B的子集的子集(Subs

17、et)，也稱，也稱A包含在包含在B內，內，B包含包含A， n記作記作B A 或或A B，n若若A不被不被B所包含，則記作所包含，則記作A B 。顯然，顯然，對任意集合對任意集合A，都有都有A A。 AB河南工業大學離散數學課程組河南工業大學離散數學課程組第20頁（二）相等關系（二）相等關系n定義定義nAB當且僅當當且僅當A與與B具有相同的元素，否則，具有相同的元素，否則，A B。集合集合A, B中的中的元素完全相同元素完全相同，稱這樣的，稱這樣的兩個兩個集合集合相等相等。 n1,2,4=1,4,2 1,2,4n定理定理3-1.1 n 設設A和和B是任意兩個集合，是任意兩個集合，A=BA B且且

18、B A 。 n集合相等的謂詞表示：集合相等的謂詞表示：nA=B( x)(xAxB) 河南工業大學離散數學課程組河南工業大學離散數學課程組第21頁定理定理3-1.1 A=B A B且且 B A。n證明證明：n(1)證：證：若若A B且且 B A，則，則A=B。(反證法反證法)n 已知已知A B且且 B A，假設，假設AB，n 則則至少有一個元素至少有一個元素x，使得使得xA而而x B；或者；或者xB而而x A。n 如果如果xA而而x B，則與，則與A B矛盾。矛盾。n 如果如果xB而而x A，則與，則與 B A矛盾。矛盾。n 所以所以A=B。n(2)證：證：若若A=B ，則，則A B且且 B A

19、 。n若若A=B，則兩個集合有相同的元素，則兩個集合有相同的元素，n即即( x)(xAxB) 為真，且為真，且( x)(xBxA) 為真，即為真，即必有必有A B且且 B A。n所以，所以， A=B A B且且 B A。該定理是證明兩個集合相等的基本思路和依據。該定理是證明兩個集合相等的基本思路和依據。河南工業大學離散數學課程組河南工業大學離散數學課程組第22頁集合相等的謂詞定義集合相等的謂詞定義 A=BnA B B An( x)(xAxB) ( x)(xBxA)n( x)(xAxB) (xBxA)n( x)(xAxB) A=B( x)(xAxB)河南工業大學離散數學課程組河南工業大學離散數學

20、課程組第23頁（三）真包含關系（三）真包含關系定義定義1.2.2 ：A真包含于真包含于Bn設設A,B是任意兩個集合，是任意兩個集合，集合集合A中的每一個元素都中的每一個元素都屬于屬于B，但集合，但集合B中至少有一個元素不屬于中至少有一個元素不屬于A。 則稱則稱A是是B的的真子集真子集(Proper Subset)，記作，記作A B，n如果如果A不是不是B的真子集，則記作的真子集，則記作A B。“真包含關系真包含關系”的謂詞表示：的謂詞表示：nA BA B ABnA B ( x)(xAxB) ( x)(x B x A)對任意對任意x，如，如x A，則則x B，并且存在，并且存在x B，但是但是x

21、 A。河南工業大學離散數學課程組河南工業大學離散數學課程組第24頁自學自學 真包含關系的謂詞定義：真包含關系的謂詞定義： A BA B ABn( x)(xAxB) ( x)(xAxB)n( x)(xAxB) ( ( x)(xAxB) ( x)(xBxA)n( x)(xAxB) ( x)(xAxB) ( x)(xAxB) ( x)(xBxA)n( x)(xAxB) ( x)(xB x A)n集合集合A中的每一個元素都屬于中的每一個元素都屬于B，但集合，但集合B中至少中至少有一個元素不屬于有一個元素不屬于A。河南工業大學離散數學課程組河南工業大學離散數學課程組第25頁六、幾個特殊集合六、幾個特殊集

22、合n1、全集、全集n2、空集、空集n3、冪集、冪集河南工業大學離散數學課程組河南工業大學離散數學課程組第26頁1、全集、全集n定義定義 在一個在一個相對固定的范圍相對固定的范圍內，內，包含此范圍內所包含此范圍內所有客體的集合有客體的集合，稱為，稱為全集全集或或論集論集(Universal Set)，用用U或或E表示。表示。 n E=x| P(x) P(x) 其中：其中：P(x)為任何謂詞。為任何謂詞。n用文氏圖描述如下用文氏圖描述如下:U六、幾個特殊集合六、幾個特殊集合一般地，根據討論問題的范圍，選一般地，根據討論問題的范圍，選擇對問題討論方便的集合作為全集。擇對問題討論方便的集合作為全集。在

23、實際應用中，常常把某個適當大在實際應用中，常常把某個適當大的集合看成全集。的集合看成全集。河南工業大學離散數學課程組河南工業大學離散數學課程組第27頁2、空集、空集n定義定義：n不含任何元素的集合叫做不含任何元素的集合叫做空集空集(Empty Set)，記作，記作。 n空集可以符號化為空集可以符號化為n =x| P(x) P(x)= 其中：其中：P(x)為任何謂詞。為任何謂詞。 設設A = x|(xR) (x20)，試列舉，試列舉A中的所有元素。中的所有元素。解：解： A = 。與與: 是不含任何元素的集合，是不含任何元素的集合，是含一個元素是含一個元素的集合。的集合。 = ， |=0 ，|=

24、1， 定理定理3-1.23-1.2（1 1）空集是一切集合的子集；）空集是一切集合的子集；（2 2）空集是絕對唯一的。）空集是絕對唯一的。河南工業大學離散數學課程組河南工業大學離散數學課程組第28頁反證法反證法n（1）空集是一切集合的子集；）空集是一切集合的子集； An證明：證明：n因為因為( x)(xxA)為永真式，所以為永真式，所以 A。n（2）空集是絕對唯一的。）空集是絕對唯一的。n分析：分析： 對對“唯唯一性一性”的證明通常采用的證明通常采用反證法反證法。n即假設即假設“不不唯唯一一”，得出矛盾，從而說明結論正確。，得出矛盾，從而說明結論正確。n證明：（反證法）證明：（反證法）n假設空

25、集不唯一，即存在假設空集不唯一，即存在1和和2兩個空集，且兩個空集，且12，n因為是因為是1空集，則由性質空集，則由性質1得得 1 2 。n因為是因為是2空集，則由性質空集，則由性質1得得 2 1 。n所以所以1=2 。n與假設矛盾，所以空集是唯一的。與假設矛盾，所以空集是唯一的。 定理定理3-1.2 的證明的證明 河南工業大學離散數學課程組河南工業大學離散數學課程組第29頁3、冪集、冪集引例：求集合的子集及子集的個數引例：求集合的子集及子集的個數例例 A 子集子集 子集個數子集個數n 1na ,a 2na,b ,a,b,a,b 4na,b,c ,a,b,c,a,b, a,c, b,c, a,

26、b,c 8n一般來說，對于一般來說，對于n個元素的集合個元素的集合A，它的不同的子集，它的不同的子集總數有：總數有：n(1+1)n2nn所以，所以，n元集共有元集共有2n個子集。個子集。Cn2Cn0Cn1Cnn河南工業大學離散數學課程組河南工業大學離散數學課程組第30頁一般來說，對于一般來說，對于n個元素的集合個元素的集合A，它的不同的子，它的不同的子集總數有集總數有 Cn2Cn0Cn1CnnCn2Cn0Cn1Cnnxn-1yxn-2y2xnynCn2Cn0Cn1Cnn而而(x+y)n=令令x=y=1時得時得 2n=所以不同子集總數有所以不同子集總數有 2n河南工業大學離散數學課程組河南工業大

27、學離散數學課程組第31頁冪集冪集定義：冪集定義：冪集(power set)n給定集合給定集合A，由，由A的的所有子集為元素所有子集為元素組成的集組成的集合稱為合稱為A的的冪集冪集(power set)，記為，記為(A) 。冪集的冪集的符號化表示為符號化表示為 n(A)x| x A例如：計算下列冪集例如：計算下列冪集:(1)()；(2) (a) ; (3)()。n解解 ：(1) () = ；n (2) (a)=,an (3)() = , ；n定理定理3-1.3 n若有限集合有若有限集合有n個元素，則其冪集個元素，則其冪集(A)共有共有2n個元個元素。素。|A|=n,| (A)|= 2n河南工業大

28、學離散數學課程組河南工業大學離散數學課程組第32頁n子集子集Bijk編碼編碼 a,b,c n ijk是二進制數，是二進制數， Bi j k A, ni=1，aBijk；i=0，a Bijk； nj=1 ，bBijk；j=0，b Bijk ；nk=1，cBijk；k=0，c Bijk 。 n例：例：a,b,c 則則nB000 B001 B010 B011 B100 B101 B110 B111n c b b,c a a,c a,b a,b,cn B0 B1 B2 B3 B4 B5 B6 B7n故：故： (A)= ,c,b,b,c ,a, a,c ,a,b, a,b,cn例：例：a,b,c,dn

29、B0 = B00 =， B1 = B01 =b,c,d，B2 = B10= a， B3 = B11 =a,b,c,dn 故：故：(A)= , b,c,d, a,a,b,c,d利用子集利用子集Ba1a2a3an的下標編碼求集合的下標編碼求集合A的冪集，的冪集，a1a2a3an為二進制編碼，為二進制編碼，n為集合為集合A的元素個數。的元素個數。河南工業大學離散數學課程組河南工業大學離散數學課程組第33頁n設設A=， B=(A)n(A)= ,n在求在求(A)時，時，實際上是將實際上是將,中的元素分別看中的元素分別看成成=a ,=b, 于是于是,=a,bnB= (A)= (a,b) =B0, B1,B

30、2 ,B3 n =B00, B01,B10 ,B11n=, b, a, a,bn然后再將然后再將a,b代回即可代回即可nB=(A)= (,)=, ,n以后熟悉后就可以直接寫出。以后熟悉后就可以直接寫出。練習練習 P86 (7)河南工業大學離散數學課程組河南工業大學離散數學課程組第34頁3-2 集合的運算集合的運算一、定義一、定義 設設A、B是兩個集合，是兩個集合，n =x|xAxB xAB xAxBn =x|x A x B xAB xAxBn =x|xAx B xA-B xAx Bn =x|xEx A= x|x A n xA x A (xA) =x|(x A) (x B) (x B) (x A

31、)A B=(A-B)(B-A) A B=(AB)-(AB) EA B差集差集EA B交集交集補集補集EAA A并集并集EA B(1)并集并集 AB (2)交集交集 AB (3)差集差集 A-B (4)補集補集 A(5)對稱差集對稱差集A B河南工業大學離散數學課程組河南工業大學離散數學課程組第35頁例：例：A=4,1,2,3,B=3,1,2,3,4,1,2,1n則：則：A B=4,1,2,3=AnAB=4,1,2,3,1,2,3,1=BnA-B=nB-A=1,2,3,1河南工業大學離散數學課程組河南工業大學離散數學課程組第36頁二、集合的運算律二、集合的運算律等冪律等冪律: AA=A；AA=A

32、； 交換律交換律: AB=BA;AB=BA結合律結合律: A(BC)=(AB)C； A(BC)=(AB)C；恒等律恒等律: A=A； AE=A； 零律零律: AE=E； A=；分配律分配律: A(BC)=(AB)(AC) A(BC)=(AB)(AC)吸收律吸收律: A(AB)=A;A(AB)=A； 集合的運算律是指集合的交、并、補、差等運集合的運算律是指集合的交、并、補、差等運算的主要性質，也稱為集合的基本定律。算的主要性質，也稱為集合的基本定律。河南工業大學離散數學課程組河南工業大學離散數學課程組第37頁定理定理n否定律：否定律： A=A ；n德摩根定律：德摩根定律： (AB)=AB n (

33、AB)=AB n矛盾律：矛盾律： A A；n排中律：排中律： A A E。n其他：其他：n A - A = ；n A - B = A - (AB)；n A - B =A B;n (A - B) - C = A - (BC)；n A(B-A) = AB；EA B河南工業大學離散數學課程組河南工業大學離散數學課程組第38頁三、證明集合相等的四種方法三、證明集合相等的四種方法n方法一：方法一：命題演算法（邏輯等價式和推理規則）命題演算法（邏輯等價式和推理規則）n方法二：方法二：等式代入法等式代入法(假設交換律、分配律、同一假設交換律、分配律、同一律、零律已經成立律、零律已經成立)n方法三：方法三：證

34、明出：證明出：A B 且且 B A，則，則A=B。n方法四：方法四：反證法反證法河南工業大學離散數學課程組河南工業大學離散數學課程組第39頁三、證明集合相等的四種方法三、證明集合相等的四種方法方法一：方法一：命題演算法（邏輯等價式和推理規則）命題演算法（邏輯等價式和推理規則）n例：證明例：證明A(AB)=A （吸收律）（吸收律）n證證 任取任取x, x (A (A B) n x Ax (A B)n x A (x Ax B) n x A n因此得因此得A (A B) = A。方法二：方法二：等式代入法等式代入法(假設交換律、分配律、同一律、假設交換律、分配律、同一律、零律已經成立零律已經成立)n

35、例例 證明吸收律證明吸收律 A (A B) = (A E) (A B) n= A (E B) = A E = A河南工業大學離散數學課程組河南工業大學離散數學課程組第40頁集合等式的證明集合等式的證明n方法三：方法三：證明出：證明出：A B 且且 B A，則，則A=Bn依據：依據：n定理定理3-1.1 A=B，當且僅當當且僅當 A B且且 B A。n例如：例如： （P91定理定理3-2.5的證明方法）的證明方法）n方法四：方法四：反證法反證法n 假設不等，推出矛盾。假設不等，推出矛盾。河南工業大學離散數學課程組河南工業大學離散數學課程組第41頁分析：分析： ( x)(xAB xA) ( x)(

36、xAxB)證明：證明：AB=A，n ( x)(xAB xA)n( x)(xAB xA)(xA xAB)n( x)(x ABxA)(x AxAB)n( x)( (xAxB)xA)n (x A(xAxB)n( x)(x Ax B)xA)n (x A(xAxB)n( x)(T(T ( x A xB)n( x)( x A xB)n( x)(xAxB)n A B證明證明P90定理定理3-2.3： AB=A A B河南工業大學離散數學課程組河南工業大學離散數學課程組第42頁四、證明四、證明A B的四種方法：的四種方法：n方法一：方法一：A和和B是用枚舉方式定義的：是用枚舉方式定義的：n依次檢查依次檢查A的

37、每個元素是否在的每個元素是否在B中出現。中出現。n方法二：方法二：通過集合運算判斷通過集合運算判斷A B：n即即AB = B, AB = A, A B = 三個等式中有一個三個等式中有一個為真，則為真，則A B。n方法三：方法三：通過文氏圖判斷集合的包含（注意這里是通過文氏圖判斷集合的包含（注意這里是判斷，而不是證明）判斷，而不是證明）n方法四：方法四：A和和B是謂詞定義的，且是謂詞定義的，且A和和B中元素的性中元素的性 質分別為質分別為P和和Q：（即：（即：A=x|P(x) B=x|Q(x)n利用利用 的定義證明（按定義證明法）。的定義證明（按定義證明法）。河南工業大學離散數學課程組河南工業

38、大學離散數學課程組第43頁按定義證明按定義證明的方法的方法n若定義中有若定義中有“若若則則”來描述的，則來描述的，則在證明時在證明時應采用離散數學應采用離散數學中特有的中特有的按定義證明方法按定義證明方法n即證明時，首先敘述即證明時，首先敘述定義定義的前半部分的前半部分“若若”，將這部分的內容，將這部分的內容稱為稱為“附加的已知條件附加的已知條件”，此時利用該，此時利用該“附加的已知條件附加的已知條件”和和題目本身所給的題目本身所給的已知條件已知條件證明出定義的后半部分證明出定義的后半部分“則則”，這部，這部分的內容稱為分的內容稱為定義中的結論定義中的結論。n這種證明問題的方法在于：這種證明問

39、題的方法在于：證明時不能單純利用證明時不能單純利用題目題目所給的所給的已知條件已知條件，而應同時利用，而應同時利用定義中的定義中的“已知已知”，推出的并非整，推出的并非整個定義，而是個定義，而是定義中的結論定義中的結論。n這與一般的證明思路：這與一般的證明思路：已知已知中間結果中間結果結論結論是完全不同的。是完全不同的。本章的證明大部分都采用本章的證明大部分都采用按定義證明方法按定義證明方法。利用利用 的定義證明：的定義證明： A B定義：定義： A B( x)(xAxB)證明：證明：假設假設( x)(xA)，利用題目中的，利用題目中的已知條件和已有的定理和已知條件和已有的定理和公理去推出即公

40、理去推出即( x)(x B) ，從而證明，從而證明A B。注意：若已知注意：若已知A B，則可以設則可以設( x)(xA) ( x)(x B) 河南工業大學離散數學課程組河南工業大學離散數學課程組第44頁六、證明集合不等的方法六、證明集合不等的方法證證 A B： n方法一：方法一：舉例舉例 或或 畫文氏圖示意。畫文氏圖示意。n方法二：方法二：轉化為證明轉化為證明 邏輯判斷式不等價。邏輯判斷式不等價。pAB ( x)(x A且且x B) ( x)(x B且且x A)n方法三：方法三：反證法，假設反證法，假設A=B，推出矛盾。，推出矛盾。五、判斷客體五、判斷客體a是否是集合是否是集合A元素的基本方

41、法：元素的基本方法：n把把a作為一個整體，檢查它在作為一個整體，檢查它在A中是否出現。中是否出現。河南工業大學離散數學課程組河南工業大學離散數學課程組第45頁七、證明集合七、證明集合A是空集的方法是空集的方法 方法一：方法一：其邏輯判斷條件是永假。其邏輯判斷條件是永假。 =x| P(x) P(x)方法二：方法二：用反證法：設用反證法：設 a A，引出矛盾的結果。引出矛盾的結果。河南工業大學離散數學課程組河南工業大學離散數學課程組第46頁n自學自學n求證求證(A-B)-C=(A-C)-(B-C)證明：證明： 任取任取x， x(A-C)-(B-C)n x(A-C)x (B-C)n (xAx C)

42、(xBx C) n (xAx C) (x BxC)n (xAx Cx B)(xAx C xC)n xAx Cx Bn xAx Bx Cn (xAx B)x Cn xA-Bx Cn x(A-B)-Cn所以所以 (A-B)-C=(A-C)-(B-C)河南工業大學離散數學課程組河南工業大學離散數學課程組第47頁n自學自學nA-(BC)=(A-B)(A-C)nA-(BC)=(A-B)(A-C)證明：任取證明：任取xA-(BC) nxAx (BC)nxA (xBxC) nxA(x Bx C)n(xAx B)(xAx C )nxA-BxA-Cnx(A-B)(A-C) n所以所以 A-(BC)=(A-B)(

43、A-C)nA(B-C)=(AB)-(AC)n但但對對- 是不可分配的，是不可分配的，n如如A(A-B)=A， 而而(AA)-(AB)=注意注意:這不是這不是分配律分配律河南工業大學離散數學課程組河南工業大學離散數學課程組第48頁自學自學n證明：證明：A B B An證明證明： A B ( x)(xAxB)n ( x)(x Bx A)x(xBxA) n B An A B B An證明：德摩根定律證明：德摩根定律n(1)(AB)=AB n(2)(AB)=AB n證明證明: (1)：任取：任取x (AB)n x (AB) x AB (xAxB)n (x A)(x B)(xA)(xB)n x (AB)

44、 n(AB)=AB 河南工業大學離散數學課程組河南工業大學離散數學課程組第49頁自學自學nA=B 當且僅當當且僅當AB=E且且 AB=證明：證明： (AB=E)(AB=)n( x)(xABxE) (PT=P)n ( x)(xABx) (PF= P)n( x)(xABT) x(xABF)n( x)(xAB (xAB)n( x)(xAxB) (xAxB)n( x)(xAxB)(x Ax B)n( x)(x AxB)(xBx A)n( x)(xAxB)(xBxA)n( x)(xAxB)nA=B河南工業大學離散數學課程組河南工業大學離散數學課程組第50頁設設A是有窮集合，是有窮集合， 其元素個數為其元

45、素個數為|A|。n這節主要解決這節主要解決集合的計數問題集合的計數問題。例如有。例如有AB兩個商店，兩個商店，A店經營店經營1000種商品，種商品，B店經營店經營1200種商品，其中有種商品，其中有100種商品兩個商店都經營，問兩個商店共經營多少種商品兩個商店都經營，問兩個商店共經營多少種商品？種商品？n顯然顯然 |AB|=|A|+|B|-|AB|n如果有如果有ABC三個有限集合，則三個有限集合，則n|ABC|n=|AB|+|C|-|(AB)C|n=|A|+|B|-|AB|+|C|-|(AC)(BC)|n=|A|+|B|-|AB|+|C|-(|AC|+|BC|-|ABC|)n=|A|+|B|+

46、|C|-|AB|-|AC|-|BC|+|ABC| ABABAB*3-3. 包含排斥原理包含排斥原理ABCU河南工業大學離散數學課程組河南工業大學離散數學課程組第51頁n一般地一般地，有，有n個有限集合個有限集合A1, A2,. An,則則niinnkjikjinjijiniiniiAAAAAAAA111111) 1(.*3-3. 包含排斥原理包含排斥原理河南工業大學離散數學課程組河南工業大學離散數學課程組第52頁n令令U為全集，為全集，E、F、J分別為會英語、法語和日語人分別為會英語、法語和日語人的集合。的集合。n|U|=170 |E|=120 |F|=80 |J|=60 n|EF|=50 |

47、EJ|=25 |FJ|=30 |EFJ|=10n|EFJ|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ|n= 120806050253010n165n|U-(EFJ)|=170-165=5 n即有即有5人不會這三種語言。人不會這三種語言。例例3-3.1某個研究所有某個研究所有170名職工，其中名職工，其中120人會英語，人會英語，80人會法語，人會法語，60人會日語，人會日語，50人會英語和法語，人會英語和法語，25人人會英語和日語，會英語和日語，30人會法語和日語，人會法語和日語，10人會英語、日人會英語、日語和法語。問有多少人不會這三種語言？語和法語。問有多少人不會這三

48、種語言？EFJ10U河南工業大學離散數學課程組河南工業大學離散數學課程組第53頁n1.掌握集合的定義、謂詞定義、證明方法。掌握集合的定義、謂詞定義、證明方法。n2.掌握三個特殊集合，會求集合的冪集。掌握三個特殊集合，會求集合的冪集。n3.掌握集合的五種運算定義、計算方法、性質。掌握集合的五種運算定義、計算方法、性質。n*4.會用包含排斥原理解決集合計數問題會用包含排斥原理解決集合計數問題. n 作業：作業： 第第94頁頁d) b) 3.13.3小結小結河南工業大學離散數學課程組河南工業大學離散數學課程組第54頁3.4 序偶與集合的笛卡爾積序偶與集合的笛卡爾積要求：要求：n1、理解概念；、理解概

49、念；n2、掌握序偶和笛卡爾積的定義和性質。、掌握序偶和笛卡爾積的定義和性質。河南工業大學離散數學課程組河南工業大學離散數學課程組第55頁一、序偶與有序一、序偶與有序n元組元組n兩個具有固定次序的客體兩個具有固定次序的客體x、y組成序偶，也稱為有組成序偶，也稱為有序二元組，記作序二元組，記作；n稱稱x、y分別為序偶分別為序偶的第一，第二元素。的第一，第二元素。p固定次序固定次序是指調換第一和第二元素位置后，含義不同。是指調換第一和第二元素位置后，含義不同。n注意，注意， 第一、第一、 二元素二元素未必不同未必不同。1.定義定義：說明說明河南工業大學離散數學課程組河南工業大學離散數學課程組第56頁

50、序偶的性質序偶的性質（1）當）當xy時，時，。 x,y=y,x（2）序偶二個元素可以重復，即）序偶二個元素可以重復，即也是序偶。也是序偶。 無無x,x（3）序偶中兩個元素可以來自不同的集合。）序偶中兩個元素可以來自不同的集合。：x A, yB x,y A（4）序偶與集合的統一：）序偶與集合的統一： = x,x,y（5）序偶相等的定義：）序偶相等的定義： ( x,y = u,v )(x=u)(y=v)由由序偶序偶相等的定義有相等的定義有 x+252x+y4 解得解得 x3,y-2。 解答解答例例 已知已知，求，求x和和y。 河南工業大學離散數學課程組河南工業大學離散數學課程組第57頁序偶的推廣：

51、序偶的推廣： 有序有序N元組元組n 定義定義 由由N個元素個元素x1,x2,xn-1,xn按照一定的次序組成的按照一定的次序組成的N元元 組稱為組稱為有序有序N元組元組，記為，記為。 xi叫做該叫做該 n元組的第元組的第i個分量個分量i=1,n。n有序有序N元組與序偶的關系：元組與序偶的關系： =x1,x2,xn-1 ,xn n三元組三元組 x1, x2, x3 =x1, x2 , x3 n四元組四元組n x1, x2, x3, x4 =x1, x2, x3 , x4 = , x3, x4 n注意：注意：x1, x2 , x3 x1, x2, x3nx1, x2, x3 , x4 x1, x2

52、, x3, x4nx1, x2, x3, x4 , x5 x1, x2, x3, x4, x5例如：例如：a年年b月月c日日d時時e分分f秒，可用六元組表示秒，可用六元組表示河南工業大學離散數學課程組河南工業大學離散數學課程組第58頁n定義：定義：兩個兩個n元組相等元組相等n設設 x1,x2,xn 與與 y1,y2,y n 是兩個是兩個n元組，如元組，如果果xi=yi，i=1,n，則稱這兩個，則稱這兩個n元組相等，記元組相等，記為為 x1,x2,xn = y1,y2,yn 。n用邏輯的方法表示為用邏輯的方法表示為 n ( x1,x2,xn = y1,y2,y n )n(x1= y1)(x2=

53、y2)(xn= yn)。 n 河南工業大學離散數學課程組河南工業大學離散數學課程組第59頁二、集合的笛卡爾積二、集合的笛卡爾積引例引例 “斗獸棋斗獸棋”虎虎象象獅獅豹豹狼狼鼠鼠貓貓狗狗虎虎象象獅獅豹豹狼狼鼠鼠貓貓狗狗每個棋子可以看成一個序偶每個棋子可以看成一個序偶: , , , ,可看成是由可看成是由兩種顏色的集合兩種顏色的集合A和和8種動物的集合種動物的集合B做運算得做運算得到的到的。 A=紅紅,藍藍 B=象象,獅獅,虎虎,豹豹,狼狼,狗狗,貓貓,鼠鼠斗獸棋可記成集合：斗獸棋可記成集合：斗獸棋可記成集合：斗獸棋可記成集合：河南工業大學離散數學課程組河南工業大學離散數學課程組第60頁補充的補充

54、的定義定義: A和和B的的笛卡爾積笛卡爾積或或直積直積n設設A、B是集合，由是集合，由A的元素為第一元素，的元素為第一元素，B的元素的元素為第二元素組成的為第二元素組成的所有所有序偶的集合序偶的集合，稱為，稱為A和和B的的笛卡爾積笛卡爾積或或直積直積，記作記作AB，即即n A B=|x Ay Bn A B x A y Bn A B x A y Bq例如：例如：qA表示某大學所有學生的集合，表示某大學所有學生的集合，B表示大學開設的表示大學開設的所有課程的集合。所有課程的集合。q則則AB可以用來表示該校學生選課的所有可能情可以用來表示該校學生選課的所有可能情況。況。1、集合的笛卡爾積的定義、集合

55、的笛卡爾積的定義河南工業大學離散數學課程組河南工業大學離散數學課程組第61頁nA B=,nB A=,nA A=, ,n可見可見 ABBAn集合的笛卡爾積運算不滿足交換律。集合的笛卡爾積運算不滿足交換律。例：例： A=0,1，B=a,b，C=zn (A B) C=, z =,n A (B C)=0,1 , =0,0,1,1, (A B) C=,z| A B z C A (B C)=x,|x A B C,n可見可見 (A B) C A (B C)。n集合的笛卡爾積運算集合的笛卡爾積運算也不滿足結合律。也不滿足結合律。例：例： 設設A=0,1,2，B=a,b，求，求A B ， B A， A A 。|

56、A B |=6= |B A | |A A |=9河南工業大學離散數學課程組河南工業大學離散數學課程組第62頁n1) 如果如果A、B都是有限集，且都是有限集，且|A|=m, |B|=n， 則則 |A B |=mn. n證明：由笛卡爾積的定義及排列組合中的乘法原證明：由笛卡爾積的定義及排列組合中的乘法原理，直接推得此定理。理，直接推得此定理。n 2) A = B= n 3) 對對和和滿足分配律。滿足分配律。 設設A,B,C是任意集合，則是任意集合，則n A (BC)= (A B)(A C)；n A (BC)= (A B)(A C)；n (AB) C= (A C)(B C)；n (AB) C= (A

57、 C)(B C)n4) 若若C,則則 A B(A C B C) (C A C B)。n5) 設設A,B,C,D為為非空集合非空集合，則，則 A B C DA CB D。（兩個笛卡爾積具有。（兩個笛卡爾積具有包含關系，則相應的分量也具有包含關系）包含關系，則相應的分量也具有包含關系）2、集合的笛卡爾積的性質、集合的笛卡爾積的性質河南工業大學離散數學課程組河南工業大學離散數學課程組第63頁2、集合的笛卡爾積的性質、集合的笛卡爾積的性質（續）（續）求證：求證：A (BC)= (A B)(A C)n分析：分析： A (BC) ? (A B)(A C) n證明：證明：n任取任取 A (BC) nx A

58、y (BC) nx A (y By C) n(x A y B)(x A y C)n A B A C n (A B)(A C) n所以所以A (BC)= (A B)(A C)n其余可以類似證明其余可以類似證明。 A (BC) A (BC) (A B)(A C) (A B)(A C)A=a, B=1,2, C=2,3A (BC)= a 1,2,3=,A B= a 1,2=,A C= a 2,3=,(A B)(A C)=,A (BC)= (A B)(A C) 河南工業大學離散數學課程組河南工業大學離散數學課程組第64頁即即 A B(A C B C) 類似可以證明類似可以證明 A B (C A C B

59、)。4) 若若C,則則 A B(A C B C) (C A C B).n證明證明: 證證A B(A C B C) n證：證：A B A C B C n設設A B,n任取任取 A Cn x A y C n (由由A B) nx B y Cn B Cn即即 B Cn 所以所以, A C B C。2、集合的笛卡爾積的性質、集合的笛卡爾積的性質（續）（續）證：證：(A C B C) A B 若若C, 任取任取y C, 任取任取x An x A y Cn A C n(由由A C B C)n B Cnx B y Cnx Bn 所以所以, A B。 A B x A y B A B ( x)(xA xB)河南

60、工業大學離散數學課程組河南工業大學離散數學課程組第65頁 5) 設設A,B,C,D為為非空集合非空集合，則，則A B C DA CB D。n證明證明: 證：由證：由A B C D A CB D。n任取任取x A，任取，任取y B，n x A y Bn ABn(由由A B C D ) CDx C y D n即即 x C y D n 所以所以, A CB D.證：由證：由A C B D A B C D。n任取任取 AB n AB x A y Bn(由由A C，B D) x C y D CD n即即 CD n所以所以, A B C D 因此，因此，A B C DA CB D。2、集合的笛卡爾積的性質