第1節(jié) 集合及其運(yùn)算

1、集合論集合論與圖論與圖論1/42集合論與圖論集合論與圖論集合論集合論與圖論與圖論2/42引引 言言離散數(shù)學(xué)主要內(nèi)容離散數(shù)學(xué)主要內(nèi)容:集合論、圖論、近世代數(shù)、數(shù)理邏輯、集合論、圖論、近世代數(shù)、數(shù)理邏輯、組合數(shù)學(xué)、組合數(shù)學(xué)、(初等初等)數(shù)論等數(shù)論等二、集合論與圖論與后繼課程二、集合論與圖論與后繼課程 集合論：近世代數(shù)、形式語言、集合論：近世代數(shù)、形式語言、 數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)等等圖圖 論：數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)等論：數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)等一、一、集合論與圖論是離散數(shù)學(xué)的重要組成部分集合論與圖論是離散數(shù)學(xué)的重要組成部分集合論集合論與圖論與圖論3/42三、教學(xué)主要內(nèi)容和教學(xué)安排三、教學(xué)主要內(nèi)容和教學(xué)安

2、排(32學(xué)時(shí)學(xué)時(shí)) 第第1章章 集合集合(4學(xué)時(shí)學(xué)時(shí)) 第第2章章 映射映射(2學(xué)時(shí)學(xué)時(shí))第第4章章 無窮集合及其基數(shù)無窮集合及其基數(shù)(2學(xué)時(shí)學(xué)時(shí))第第3章章 關(guān)系關(guān)系(8學(xué)時(shí)學(xué)時(shí)) 第第6章章 圖的基本概念圖的基本概念(8學(xué)時(shí)學(xué)時(shí)) 第第7章章 樹與樹與割集割集(2學(xué)時(shí)學(xué)時(shí))第第8章章 連通度連通度和匹配和匹配(2學(xué)時(shí)學(xué)時(shí))第第9章章 平面圖和平面圖和圖的著色圖的著色(2學(xué)時(shí)學(xué)時(shí))引引 言言集合論集合論與圖論與圖論4/42四、主要教材四、主要教材離散數(shù)學(xué)引論離散數(shù)學(xué)引論 王義和王義和 哈爾濱工業(yè)大學(xué)出版社哈爾濱工業(yè)大學(xué)出版社離散數(shù)學(xué)離散數(shù)學(xué) 耿素云等耿素云等 高等教育出版社高等教育出版社離散

3、數(shù)學(xué)離散數(shù)學(xué) 左孝凌等左孝凌等 上?？萍嘉墨I(xiàn)出版社上?？萍嘉墨I(xiàn)出版社方式：筆試方式：筆試成績：總成績成績：總成績(100分分)其中：平時(shí)成績其中：平時(shí)成績(作業(yè)與出勤作業(yè)與出勤)(20分分) 筆試成績筆試成績(80分分)五、考試方式與成五、考試方式與成績績引引 言言集合論集合論與圖論與圖論5/42 集合論集合論 集合論成了數(shù)學(xué)各分支的基礎(chǔ)，也是計(jì)算機(jī)科集合論成了數(shù)學(xué)各分支的基礎(chǔ)，也是計(jì)算機(jī)科學(xué)非常重要的基礎(chǔ)知識(shí)。學(xué)非常重要的基礎(chǔ)知識(shí)。 它的起源可追溯到它的起源可追溯到16世紀(jì)末，主要是對(duì)數(shù)集進(jìn)世紀(jì)末，主要是對(duì)數(shù)集進(jìn)行了卓有成效的研究。但集合論實(shí)際發(fā)展是由行了卓有成效的研究。但集合論實(shí)際發(fā)展是由

4、19世世紀(jì)紀(jì)70年代德國數(shù)學(xué)家康托年代德國數(shù)學(xué)家康托(G. Cantor)在無窮序列和在無窮序列和分析的有關(guān)課題的理論研究中創(chuàng)立的?？低袑?duì)具有分析的有關(guān)課題的理論研究中創(chuàng)立的。康托對(duì)具有任意特性的無窮集合進(jìn)入了深入的探討，提出了關(guān)任意特性的無窮集合進(jìn)入了深入的探討，提出了關(guān)于于基數(shù)基數(shù)、序數(shù)、序數(shù)、超窮數(shù)超窮數(shù)和良序集等理論，奠定了集和良序集等理論，奠定了集合論的深厚基礎(chǔ)。因此，合論的深厚基礎(chǔ)。因此，康托被譽(yù)為集合論的創(chuàng)始康托被譽(yù)為集合論的創(chuàng)始人人。集合論集合論與圖論與圖論6/42 但隨著集合論的發(fā)展，以及它與數(shù)學(xué)哲學(xué)密切但隨著集合論的發(fā)展，以及它與數(shù)學(xué)哲學(xué)密切聯(lián)系所作的討論，在聯(lián)系所作的討論

5、，在20世紀(jì)初，出現(xiàn)了許多似是而世紀(jì)初，出現(xiàn)了許多似是而非、自相矛盾的悖論，如非、自相矛盾的悖論，如康托悖論康托悖論、羅素羅素(Russell)悖悖論論，有力沖擊了或者說動(dòng)搖了集合論的發(fā)展。由此，有力沖擊了或者說動(dòng)搖了集合論的發(fā)展。由此，激發(fā)許多數(shù)學(xué)家、哲學(xué)家為克服這些矛盾建立了各激發(fā)許多數(shù)學(xué)家、哲學(xué)家為克服這些矛盾建立了各種種公理化集合論體系公理化集合論體系。 集合論集合論 樸素集合論體系樸素集合論體系 (也稱也稱康托康托(Cantor)集合論體系集合論體系) 公理集合論體系公理集合論體系集合論集合論集合論集合論與圖論與圖論7/42 1965年，美國學(xué)者年，美國學(xué)者L. A. Zadeh提出

6、了提出了Fuzzy集概集概念念(理論理論)。 20世紀(jì)世紀(jì)80年代初，波蘭學(xué)者年代初，波蘭學(xué)者Z. Pawlak發(fā)表了發(fā)表了Rough集理論。集理論。 這兩種理論區(qū)別以往的集合論，是一種新的模這兩種理論區(qū)別以往的集合論，是一種新的模糊集理論。糊集理論。 集合論集合論 集合論在計(jì)算機(jī)科學(xué)、人工智能領(lǐng)域、邏輯學(xué)集合論在計(jì)算機(jī)科學(xué)、人工智能領(lǐng)域、邏輯學(xué)及語言學(xué)等方面都有著重要的應(yīng)用。對(duì)于從事計(jì)算及語言學(xué)等方面都有著重要的應(yīng)用。對(duì)于從事計(jì)算機(jī)科學(xué)的工作者來說，集合論是不可缺少的理論知機(jī)科學(xué)的工作者來說，集合論是不可缺少的理論知識(shí)，熟悉和掌握它是十分必要的。識(shí)，熟悉和掌握它是十分必要的。集合論集合論與圖

7、論與圖論8/42畢業(yè)舞會(huì)上，小伙子與姑娘跳舞，已知每個(gè)小伙子畢業(yè)舞會(huì)上，小伙子與姑娘跳舞，已知每個(gè)小伙子至少與一個(gè)姑娘跳過舞，但未能與所有姑娘跳過。至少與一個(gè)姑娘跳過舞，但未能與所有姑娘跳過。同樣地，每個(gè)姑娘也至少與一個(gè)小伙子跳舞，但也同樣地，每個(gè)姑娘也至少與一個(gè)小伙子跳舞，但也未能與所有的小伙子跳過舞。未能與所有的小伙子跳過舞。證明：證明：在所有參加舞會(huì)的小伙與姑娘中，必可找到在所有參加舞會(huì)的小伙與姑娘中，必可找到兩個(gè)小伙子和兩個(gè)姑娘，這兩個(gè)小伙子中的每一個(gè)兩個(gè)小伙子和兩個(gè)姑娘，這兩個(gè)小伙子中的每一個(gè)只與這兩個(gè)姑娘中的一個(gè)跳過舞，而這兩個(gè)姑娘中只與這兩個(gè)姑娘中的一個(gè)跳過舞，而這兩個(gè)姑娘中的每

8、一個(gè)也只與這兩個(gè)小伙中的一個(gè)跳過舞。的每一個(gè)也只與這兩個(gè)小伙中的一個(gè)跳過舞。 問問 題題問題問題1：畢業(yè)舞會(huì)問題：畢業(yè)舞會(huì)問題問題問題2：在至少有兩個(gè)人的團(tuán)隊(duì)里，總有兩個(gè)人在此團(tuán)隊(duì)在至少有兩個(gè)人的團(tuán)隊(duì)里，總有兩個(gè)人在此團(tuán)隊(duì)里有相同個(gè)數(shù)的朋友？里有相同個(gè)數(shù)的朋友？集合論集合論與圖論與圖論9/42 第第1節(jié)節(jié) 集合及其運(yùn)算集合及其運(yùn)算主要內(nèi)容：主要內(nèi)容： 集合的概念集合的概念 集合的基本運(yùn)算集合的基本運(yùn)算 笛卡兒乘積笛卡兒乘積集合論集合論與圖論與圖論10/421.1 集合的概念集合的概念 在樸素集合論體系中，在樸素集合論體系中，“集合集合”是集合論中的一個(gè)是集合論中的一個(gè)原始概念，我們知道在歐氏幾

9、何中對(duì)點(diǎn)、線不加定義，原始概念，我們知道在歐氏幾何中對(duì)點(diǎn)、線不加定義，在樸素集合論中在樸素集合論中“集合集合”不能嚴(yán)格定義。不能嚴(yán)格定義。 通常把一些互不相同的東西放在一起所形成的整體通常把一些互不相同的東西放在一起所形成的整體就叫做一個(gè)就叫做一個(gè)集合集合。構(gòu)成集合的每一個(gè)東西，稱為該集合。構(gòu)成集合的每一個(gè)東西，稱為該集合的一個(gè)的一個(gè)元素元素。集合的定義集合的定義集合論集合論與圖論與圖論11/42康托康托(Cantor) 1874年所給的年所給的“集合集合”定義：定義： 把若干確定的有區(qū)別的（不論是具體的或抽象把若干確定的有區(qū)別的（不論是具體的或抽象的）事物合并起來，看作一個(gè)整體，就稱為一個(gè)的

10、）事物合并起來，看作一個(gè)整體，就稱為一個(gè)集集合合，其中各事物稱為該集合的，其中各事物稱為該集合的元素元素。 常用大寫英文字母常用大寫英文字母A,B,C,.表示集合，用小寫英表示集合，用小寫英文字母文字母a,b,c,.,表示集合中的元素。表示集合中的元素。如果如果x是集合是集合A的元素，就說的元素，就說x屬于屬于A，記為，記為x A； 如果如果x不是集合不是集合A的元素，就說的元素，就說x不屬于不屬于A，記為，記為x A或者或者x A；集合的概念集合的概念集合論集合論與圖論與圖論12/42 (3)確定性確定性：對(duì)于一個(gè)集合：對(duì)于一個(gè)集合A來說，某一對(duì)象來說，某一對(duì)象x或者是或者是集合集合A的元素

11、，或者不是，兩者必居其一。的元素，或者不是，兩者必居其一。集合的性質(zhì)集合的性質(zhì) (2)無序性無序性：集合中的元素不規(guī)定順序。：集合中的元素不規(guī)定順序。(1)互異性互異性：集合中的元素是各不相同的。：集合中的元素是各不相同的。 (4)任意性任意性：集合的元素可以是具體的，也可以是抽：集合的元素可以是具體的，也可以是抽象的；集合的元素可以是集合。象的；集合的元素可以是集合。集合論集合論與圖論與圖論13/42集合的表示方法集合的表示方法 列舉法列舉法：列出集合中的全體元素，元素之間用：列出集合中的全體元素，元素之間用逗號(hào)分開，然后用花括號(hào)括起來。逗號(hào)分開，然后用花括號(hào)括起來。 描述法描述法：當(dāng)集合當(dāng)

12、集合A是具有某種性質(zhì)是具有某種性質(zhì)P的元素全體的元素全體時(shí)，我們往往用下面的形式表示時(shí)，我們往往用下面的形式表示A。A=x| x具有性質(zhì)具有性質(zhì)P注：集合的兩種表示法有時(shí)是可以互相轉(zhuǎn)化的。注：集合的兩種表示法有時(shí)是可以互相轉(zhuǎn)化的。集合論集合論與圖論與圖論14/42集合之間的關(guān)系集合之間的關(guān)系 定義定義1.1 設(shè)設(shè)A，B為二集合，若為二集合，若A中的每個(gè)元素中的每個(gè)元素都是都是B中的元素，則稱中的元素，則稱A是是B的的子集合子集合，簡稱，簡稱子集子集。這時(shí)我們說這時(shí)我們說A包含包含在在B里里(A包含于包含于B)，或，或B包含著包含著A(B包含包含A)，記作，記作A B。 其符號(hào)化形式為：其符號(hào)化

13、形式為：A B x A, x B 定義定義1.2 設(shè)設(shè)A，B為二集合，若為二集合，若A B且且 x B使使得得x A，則稱，則稱A是是B的的真子集真子集，記作記作A B，讀作，讀作A是是B的真子集。的真子集。 A BA B且且 x B但但x A 定義定義1.3 設(shè)設(shè)A，B是集合，如果是集合，如果A B且且B A，則，則稱稱A與與B相等相等，記作，記作A=B。集合論集合論與圖論與圖論15/42 定義定義1.4 不擁有任何元素的集合稱為空集合，簡不擁有任何元素的集合稱為空集合，簡稱為稱為空集空集，記作，記作。幾個(gè)特殊的集合：空集幾個(gè)特殊的集合：空集 定理定理1.1 空集是一切集合的子集?？占且磺?/p>

14、集合的子集。推論推論1：空集是唯一的。：空集是唯一的。 由推論可知，空集無論以什么形式出現(xiàn)，它們都由推論可知，空集無論以什么形式出現(xiàn)，它們都是相等的。是相等的。 空集是一切集合的子集，從這個(gè)意義上看，可以空集是一切集合的子集，從這個(gè)意義上看，可以形象地說：形象地說： 是是“最小最小”的集合，有無最大的集合呢？的集合，有無最大的集合呢？回答是否定的?；卮鹗欠穸ǖ摹?B x , x B集合論集合論與圖論與圖論16/42定義定義1.5以集合為元素的集合稱為以集合為元素的集合稱為集族集族。幾個(gè)特殊的集合：集族幾個(gè)特殊的集合：集族 若若J為任一集合，對(duì)為任一集合，對(duì)J中每個(gè)元素中每個(gè)元素i有唯一的一個(gè)有

15、唯一的一個(gè)集合與之對(duì)應(yīng)，這個(gè)集合記為集合與之對(duì)應(yīng)，這個(gè)集合記為Ai，那么所有這些，那么所有這些Ai，形成的集族就用形成的集族就用Aii J表示，其表示，其J稱為標(biāo)號(hào)集。稱為標(biāo)號(hào)集。 A =A0,A1,.,Ap是以是以J=0,1,2,.p為標(biāo)號(hào)集的集族，為標(biāo)號(hào)集的集族，也可以記為也可以記為 A =Akk 0,1,2,.p =Akk J集合論集合論與圖論與圖論17/42 定義定義1.6 集合集合S的所有子集的所有子集(包括空集包括空集和和S本身本身)形形成的集族稱為成的集族稱為S的的冪集冪集，并記為，并記為2S，或記為，或記為P(S)。P(S)=2S=A|A S 為了求出給定集合為了求出給定集合A

16、的冪集，首先求出的冪集，首先求出A的元素個(gè)的元素個(gè)數(shù)由少到多的所有子集，再將它們組成集合即可。數(shù)由少到多的所有子集，再將它們組成集合即可。幾個(gè)特殊的集合：冪集幾個(gè)特殊的集合：冪集例如例如： 設(shè)設(shè)S=1,2,3，求，求2S. 定理定理1.2 設(shè)集合設(shè)集合S的元素個(gè)數(shù)的元素個(gè)數(shù)|S|=n(n為自然數(shù)為自然數(shù))，則則|P(S)|=| 2S|=2n。集合論集合論與圖論與圖論18/42注意：注意：2=。 在這里要區(qū)分在這里要區(qū)分和和: 為空集為空集,而而是一個(gè)集族。是一個(gè)集族。 和和?集合論集合論與圖論與圖論19/42就一個(gè)問題來說，常稱包含所考慮問題的所有集就一個(gè)問題來說，常稱包含所考慮問題的所有集合

17、的集合合的集合S，稱為該問題的，稱為該問題的全集全集。幾個(gè)特殊的集合：全集幾個(gè)特殊的集合：全集集合論集合論與圖論與圖論20/421.2 集合的基本運(yùn)算集合的基本運(yùn)算 AB=x|x A或者或者x B。AB=x|x A且且x BAB=x|x A且且x B=A-BA B=(AB)(BA) = (AB)(AB)=A BAc=SA（S為全集，為全集，A S ）設(shè)設(shè)A，B為兩個(gè)集合，則為兩個(gè)集合，則A與與B的并：的并：A與與B的交：的交：A與與B的差：的差：A與與B的對(duì)稱差：的對(duì)稱差：A對(duì)對(duì)S的余：的余：集合論集合論與圖論與圖論21/42在這種圖示法中，用矩形中各點(diǎn)表示全集在這種圖示法中，用矩形中各點(diǎn)表示

18、全集S的各的各個(gè)元素。矩形中的圓里的點(diǎn)表示個(gè)元素。矩形中的圓里的點(diǎn)表示S的子集的各元素。的子集的各元素。SABAB文氏圖文氏圖SABABSABA BSABAB集合論集合論與圖論與圖論22/42集合集合A對(duì)對(duì)S的余集的余集Ac可用文氏圖表示，如下圖：可用文氏圖表示，如下圖：AAcS文氏圖文氏圖集合論集合論與圖論與圖論23/42 性質(zhì)性質(zhì)1 設(shè)設(shè)A,B,C為任意的三個(gè)集合為任意的三個(gè)集合 (1)交換律成立交換律成立,(3)冪等律成立，即冪等律成立，即AA=A; 即即AB=BA; (4)A=A;(5)AB=BA B。(2)結(jié)合律成立，即結(jié)合律成立，即(AB)C=A(BC);(AB)C=A(BC)=A

19、BC。由于結(jié)合律成立，由于結(jié)合律成立， 所以所以ABC有意義有意義。從而有。從而有問題：消去律成立嗎？即問題：消去律成立嗎？即 若若AB=AC，則，則B=C？基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論24/42性質(zhì)性質(zhì)2 設(shè)設(shè)A,B,C為任意的三個(gè)集合，則為任意的三個(gè)集合，則:(8)冪等律成立，即冪等律成立，即AA=A;(6)交換律成立，即交換律成立，即AB=BA; (9)A=;(10)AB=AA B。(7)結(jié)合律成立，即結(jié)合律成立，即(AB)C=A(BC);基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論25/42性質(zhì)性質(zhì)3 設(shè)設(shè)A,B,C為任意三個(gè)集合，則為任意三個(gè)集合，則

20、(11)交運(yùn)算對(duì)并運(yùn)算滿足分配律交運(yùn)算對(duì)并運(yùn)算滿足分配律, 即即A(BC)=(AB)(AC); (12)并運(yùn)算對(duì)交運(yùn)算滿足分配律并運(yùn)算對(duì)交運(yùn)算滿足分配律, 即即A(BC)=(AB)(AC)。 性質(zhì)性質(zhì)4 對(duì)任何集合對(duì)任何集合A,B，吸收律成立。，吸收律成立。 (13)A(AB)=A; (14)A(AB)=A?；具\(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論26/42基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)性質(zhì)性質(zhì)5 設(shè)設(shè)A,B,C為任意三個(gè)集合，則為任意三個(gè)集合，則 (15)A(BC)=(AB)(AC)。 性質(zhì)性質(zhì)6 設(shè)設(shè)A,B,C為任意三個(gè)集合，則為任意三個(gè)集合，則 (16)A B=B A;(18)

21、A A=;(19)A=A; (17)(A B) C=A (B C);(20)交運(yùn)算關(guān)于對(duì)稱差滿足分配律，即交運(yùn)算關(guān)于對(duì)稱差滿足分配律，即 A(B C)=(AB) (AC)。集合論集合論與圖論與圖論27/42性質(zhì)性質(zhì)7 A對(duì)對(duì)S的余集的余集Ac有如下性質(zhì)有如下性質(zhì):(21)S對(duì)對(duì)S的余集的余集Sc為空集，即為空集，即Sc=；(22)c=S；(23)AAc=；(24)AAc=S。 基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論28/42性質(zhì)性質(zhì)8 德摩根德摩根(De Morgan)公式公式: (25)(AB)c=AcBc;(26)(AB)c=AcBc.下面的定理表明余集、差集、對(duì)稱差之間的聯(lián)

22、系。下面的定理表明余集、差集、對(duì)稱差之間的聯(lián)系。性質(zhì)性質(zhì)9 設(shè)設(shè)A,B都是都是S的子集，則的子集，則(27)AB=ABc;(28)A B=(ABc)(BAc);(29)Ac=S A.基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論29/42 A1A2.An定義為至少屬于定義為至少屬于A1, A2, . , An中中之一的那些元素構(gòu)成的集合。之一的那些元素構(gòu)成的集合。 若若A1, A2, . , An, . 是一個(gè)集合的無窮序列，則它是一個(gè)集合的無窮序列，則它們的并集記為：們的并集記為：A1A2.An. ,niiA1 A1A2.An簡記為簡記為1iiA 簡記為簡記為定義定義:A1A2.An.

23、= =x| n N使得使得x An集合并運(yùn)算的推集合并運(yùn)算的推廣廣1iiA集合論集合論與圖論與圖論30/42集合交運(yùn)算的推廣集合交運(yùn)算的推廣),.,2 , 1.121iniinAxnixAAAA,.121nnnnAxNnxAAAA類似定義集合論集合論與圖論與圖論31/42性質(zhì)性質(zhì)10 設(shè)設(shè)A為一集合，為一集合，Bll I為任一集族，則為任一集族，則)()(IllIllBABAIllIllBABA)()(其中其中I?；具\(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論32/42設(shè)設(shè)S為任一集合，為任一集合，I為標(biāo)號(hào)集，為標(biāo)號(hào)集，I有有A S，則有，則有性質(zhì)性質(zhì)11 并集的余集等于各余集的交集，即

24、并集的余集等于各余集的交集，即IccIAA)(性質(zhì)性質(zhì)12 交集的余集等于各余集的并集，即交集的余集等于各余集的并集，即IccIAA)(基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)集合論集合論與圖論與圖論33/421.3 笛卡兒乘積笛卡兒乘積兩個(gè)對(duì)象兩個(gè)對(duì)象a和和b(允許允許a=b)按一定的次序排列的整體按一定的次序排列的整體就叫做一個(gè)就叫做一個(gè)二元組二元組或或有序?qū)τ行驅(qū)?。如果如果a排在排在b的前面，則這個(gè)有序?qū)陀涀鞯那懊?，則這個(gè)有序?qū)陀涀?a,b)，a稱為有序?qū)ΨQ為有序?qū)?a,b)的第一個(gè)元素，的第一個(gè)元素，b稱為第二個(gè)元素。稱為第二個(gè)元素。 有序?qū)κ怯捎写涡虻膬蓚€(gè)對(duì)象組成的，因此有序有序?qū)κ怯捎写涡?/p>

25、的兩個(gè)對(duì)象組成的，因此有序?qū)εc含兩個(gè)對(duì)象的集合是有區(qū)別的。集合對(duì)與含兩個(gè)對(duì)象的集合是有區(qū)別的。集合a,b中的元中的元素沒有次序，集合素沒有次序，集合a,b與與b,a是同一個(gè)集合。但是同一個(gè)集合。但(a,b)與與(b,a)在在ab時(shí)是不同的。時(shí)是不同的。我們規(guī)定我們規(guī)定(a,b)=(c,d)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a=c,b=d。有序?qū)τ行驅(qū)τ行驅(qū)Φ募隙x：有序?qū)Φ募隙x：(a,b)=a,a,b。集合論集合論與圖論與圖論34/42 定義定義3.1 設(shè)設(shè)A與與B為任意兩個(gè)集合，則稱集合為任意兩個(gè)集合，則稱集合 (a,b)|a A且且b B 為為A與與B的的笛卡爾乘積笛卡爾乘積，記為，記為A B。 A

26、B=(a,b)|a A且且b B 例如：在平面上建立了直角坐標(biāo)系后，平面上的例如：在平面上建立了直角坐標(biāo)系后，平面上的點(diǎn)就用實(shí)數(shù)的有序?qū)肀硎?。平面上的所有點(diǎn)之集就點(diǎn)就用實(shí)數(shù)的有序?qū)肀硎?。平面上的所有點(diǎn)之集就可視為可視為R R，其中，其中R為實(shí)數(shù)集。為實(shí)數(shù)集。笛卡兒乘積笛卡兒乘積集合論集合論與圖論與圖論35/42例如例如 設(shè)設(shè)A=a,b,B=1,2,3A A=(a,a),(a,b),(b,a),(b,b) A B=(a,1),(a,2),(a,3),(b,1),(b,2),(b,3) B A=(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)B B=(1,1),(1,2)

27、,(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) 對(duì)任意有窮集合，對(duì)任意有窮集合，B，如果用，如果用|A|，|B|分別表分別表示和示和B中元素的個(gè)數(shù)，那么中元素的個(gè)數(shù)，那么|A B|A| |B|。兩個(gè)集合的笛卡爾乘積的元素個(gè)數(shù)：兩個(gè)集合的笛卡爾乘積的元素個(gè)數(shù)：笛卡兒乘積笛卡兒乘積集合論集合論與圖論與圖論36/42由定義可知，對(duì)任一集合由定義可知，對(duì)任一集合A，有，有A=A。一般情況下一般情況下A B B A。含空集的兩個(gè)集合的笛卡爾積：含空集的兩個(gè)集合的笛卡爾積：是否滿足交換律是否滿足交換律?1 2=(1,2)2 1=(2,1)是否滿足結(jié)合律是否滿足結(jié)合律?

28、當(dāng)當(dāng)A,B,C時(shí)時(shí), (A B) C中的元素形中的元素形如如(x,y),z) A (B C)中的元素形如中的元素形如(x,(y,z)笛卡兒乘積笛卡兒乘積集合論集合論與圖論與圖論37/42性質(zhì)性質(zhì) 設(shè)設(shè)A,B,C為任意三個(gè)集合，則笛卡兒乘積為任意三個(gè)集合，則笛卡兒乘積運(yùn)算對(duì)并、交、差運(yùn)算分別滿足分配律，即運(yùn)算對(duì)并、交、差運(yùn)算分別滿足分配律，即 (30)A (BC)=(A B)(A C); (31)A (BC)=(A B)(A C); (32)A (BC)=(A B)(A C)。笛卡兒乘積笛卡兒乘積集合論集合論與圖論與圖論38/42有序?qū)σ步卸M，我們可將二元組推廣到三元有序?qū)σ步卸M，我們可

29、將二元組推廣到三元組，四元組，一直到組，四元組，一直到n元組。元組。三元組就是三個(gè)元素按一定次序組成的整體，設(shè)三元組就是三個(gè)元素按一定次序組成的整體，設(shè)第一個(gè)元素為第一個(gè)元素為x，第二個(gè)元素為，第二個(gè)元素為y，第三個(gè)元素為，第三個(gè)元素為z，則，則這個(gè)三元組就記為這個(gè)三元組就記為(x,y,z)。一般地，一個(gè)一般地，一個(gè)n元組就是元組就是n個(gè)元素按一定次序組個(gè)元素按一定次序組成的整體，設(shè)第一個(gè)元素為成的整體，設(shè)第一個(gè)元素為x1,第二個(gè)元素為第二個(gè)元素為x2,.,第第n個(gè)元素為個(gè)元素為xn,則這個(gè)則這個(gè)n元組就記為元組就記為(x1,x2,.,xn)。稱兩個(gè)稱兩個(gè)n元組元組(x1,x2,.,xn)與與(y1,y2,.,yn)相等當(dāng)且僅相等當(dāng)且僅當(dāng)當(dāng)x1y1,x2y2,.,xn=yn。笛卡兒乘積笛卡兒乘積集合論集合論與圖論與圖論39/42例如：例如： 一個(gè)一個(gè)n次整系數(shù)多項(xiàng)式次整系數(shù)多項(xiàng)式, a0 xn+a1xn-1+.+an-1x+an 在計(jì)算機(jī)中，存