1、第三章 集合與關(guān)系3-1 集合的概念和表示方法定義定義(集合集合set)：把具有共同性質(zhì)的一些對象匯集成一個整體，就構(gòu)成一個集合，這些對象稱為元素(element)或成員(member)用大寫英文字母A,B,C,表示集合用小寫英文字母a,b,c,表示元素aA：表示a是A的元素，讀作“a屬于A”aA：表示a不是A的元素，讀作“a不屬于A”3-1.4 集合之間的關(guān)系集合之間的關(guān)系子集、相等、真子集；空集、全集；冪集、n元集、有限集；（1 1）子集）子集定義子集(subset)：設(shè)A、B是任意兩個集合，如果A的每一個元素是B的成員，則稱A為B的子集, 或說A包含于B, 或說B包含A, 記作AB，或B

2、A。AB (x)(xAxB)若A不是B的子集, 則記作ABAB (x)(xAxB)包含()的性質(zhì)：1AA（自反性）證明: AA(x)(xAxA) T2若AB,且AB,則 BA（反對稱性）3若AB,且BC, 則AC（傳遞性）證明: AB (x)(xAxB)x, xA xB (AB) xC (BC) (x)(xAxC), 即AC. （2）真子集真子集定義真子集(proper subset)如果集合A的每一個元素都屬于B，但集合B至少有一個元素不屬于A，則稱A為B的真子集，記作AB。AB AB ABAB(x)(xAxB)(x)(xBxA)真包含()的性質(zhì)1AA （反自反性）證明: A A AA AA

3、 TF F. 2若AB,則 BA （反對稱性）證明: (反證) 設(shè)BA, 則AB AB AB AB (化簡)BA BA BA BA所以 AB BA A=B (=定義)但是 AB AB AB AB (化簡) 矛盾! 3若AB,且BC, 則AC （傳遞性）證明: AB AB AB AB (化簡),同理 BC BC, 所以AC.假設(shè)A=C, 則BCBA, 又AB, 故A=B, 此與AB矛盾, 所以AC.所以, AC. #（3）空集空集定義空集(empty set)：沒有任何元素的集合是空集,記作例如： xR|x2 +1=0定理 對任意集合A空集是它的子集也就是對任意集合A, A證明: Ax(xxA)

4、x(FxA)T. 對于每一個非空集合A，至少有兩個不同的子集，A和，稱為A的平凡子集。（4） 全集全集定義全集: 在一定范圍內(nèi)，如果所有集合均為某一集合的子集,則稱這個集合是全集,記作E。E=x | P(x) P(x)，P(x)為任何謂詞全集是相對的, 視情況而定, 因此不唯一。例如, 討論(a,b)區(qū)間里的實(shí)數(shù)性質(zhì)時, 可以選 E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+), E=(-,+)等（5）冪集冪集定義冪集(power set)給定集合A，由集合A的所有子集為元素組成的集合,稱為A的冪集,記作P (A)P (A)=x|xA注意: xP (A) xA例如

5、: A=a,b, P (A)=,a,b,a,b. 定理如果有限集合A有n個元素，則冪集P (A)有2n個元素。證明: 見課本第85頁，利用二項(xiàng)式展開定理。3-2集合的運(yùn)算3.1.1 定義 集合的交(intersection): 設(shè)任意兩個集合A和B，由集合A和B的所有共同元素組成的集合S，稱為A和B的交集，記作AB 。S=AB = x | (xA) (xB) xAB (xA) (xB)3.1.4 集合交運(yùn)算的性質(zhì)a) A A = A （冪等律）b) A = （零律）c) A E = A （同一律）d) A B = B A （交換律）e) (A B) C = A (B C) （結(jié)合律）因?yàn)榧辖?/p>

6、運(yùn)算滿足結(jié)合律，故n個集合的交記為： nP=A1 A2 An = Ai i=13.2 集合的并3.3.1 定義并集(union)：設(shè)任意兩個集合A和B，由所有集合A和B的元素組成的集合S，稱為A和B的并集，記作AB 。 S=AB = x | (xA) (xB) xAB (xA) (xB)3.3.3 集合并運(yùn)算的性質(zhì)a) A A = A （冪等律）b) A = A （同一律）c) A E = E （零律）d) A B = B A （交換律）e) (A B) C = A (B C) （結(jié)合律）因?yàn)榧喜⑦\(yùn)算滿足結(jié)合律，故n個集合的并記為： nP=A1A2 An = Ai i=13.3 集合的補(bǔ)相對

7、補(bǔ)3.3.1 定義補(bǔ)集相對補(bǔ)集(relative complement , difference set)：屬于A而不屬于B的全體元素組成的集合S，稱為B對于A的補(bǔ)集相對補(bǔ)集, 記作A-BS=A-B = x | (xA) (xB) 3.3.2 定義絕對補(bǔ)(complement)：設(shè)E為全集，對任一集合A關(guān)于E的補(bǔ)E-A，稱為集合A的絕對補(bǔ)，記作 A。A=x|(xExA)集合運(yùn)算的性質(zhì)（集合恒等式）(1) 冪等律( idempotent laws)AA=A AA=A(2) 結(jié)合律(associative laws)(AB)C=A(BC) (AB)C=A(BC) (3) 交換律(commutati

8、ve laws)AB=BAAB=BA(4) 分配律(distributive laws)A(BC)=(AB)(AC) A(BC)=(AB)(AC) (5) 對合律(double complement law)A=A(6) 零律(dominance laws)AE=E A=(11) 吸收律(absorption laws)A(AB)=AA(AB)=A(12) 德.摩根律( DeMorgans laws)(AB)=AB(AB)=AB(13) 補(bǔ)交轉(zhuǎn)換律(difference as intersection)A-B=AB 集合恒等式證明(方法)（1）邏輯演算法: 利用邏輯等價式和邏輯推理規(guī)則（2）集

9、合演算法: 利用集合恒等式和已知的集合結(jié)論（1）邏輯演算法(格式) 題型: A=B. 證明： x, xA (?) xB A=B 證畢. 或證明： x, xA (?) xB . 另，x, xB (?) xA . A=B證畢.題型: A B. 證明: x, xA (?) xB A B證畢.例1：分配律(證明)A(BC)=(AB)(AC)證明: x, xA(BC) xA x(BC) (定義) xA (xB xC) (定義) (xAxB)(xAxC) (命題邏輯分配律) (xAB)(xAC) (定義) x(AB)(AC) (定義) A(BC)=(AB)(AC)成立(2) 集合演算法（格式）集合演算法（

10、格式）題型: A=B. 題型: AB. 證明: A 證明: A =(?) (?) =B B A=B. # AB. #例1：吸收律(一式證明)A(AB)=A證明: A(AB) = (AE)(AB) (同一律) = A(EB) (逆用分配律) = AE (零律) = A (同一律) A(AB)=A(2) 集合演算法（格式）續(xù) 題型題型: A B 證明: AB (或AB) =(?) = A (或B) AB. # 說明說明: 化化 成成=題型題型: A=B證明: () AB () A B A = B. #說明說明: 把把=分成分成 與與 AB=AABAB=BAB集合恒等式證明(舉例)1. 基本集合恒等

11、式例如：補(bǔ)交轉(zhuǎn)換律A-B = AB 證明: x, xA-B xA xB xA xB x ABA-B = AB. 德摩根律的相對形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C) ？（怎么做）證明: A-(BC) = A(BC) (補(bǔ)交轉(zhuǎn)換律) = A(BC) (德摩根律) = (AA)(BC) (冪等律) = (AB)(AC) (交換律,結(jié)合律)= (A-B)(A-C) (補(bǔ)交轉(zhuǎn)換律). #3-4 序偶與笛卡爾積3-4.1 序偶(二元組)定義序偶o(jì)rdered pair：由兩個固定次序的客體 a,b組成的序列稱為序偶，記作，其中a,b稱為序偶的分量。 其中, a是第一元素

12、, b是第二元素, 記作也記作(a,b)。定理：序偶和 相等，當(dāng)且僅當(dāng)a=c 且b=d，即= (a=c)(b=d)推論: ab 3-4.2 三元組(ordered triple)定義三元組：=,c.定義 n(2)元組： =,an.定理: = ai = bi, i =1,2,n. 3-4.3 笛卡爾積(Cartesian product)及其性質(zhì) 定義笛卡爾積：A和B為任意兩個集合，若序偶的第一個成員是A的元素，第二個成員是B的元素，所有這樣序偶的集合，稱為A和B的笛卡爾積或直積，記為： AB=|(xA)(yB).例1: A=,a, B=1,2,3.AB= ,.BA= ,.AA= , , , .

13、BB= , , . 3-4.4 笛卡爾積的性質(zhì)：當(dāng)|A|=m，|B|=n時，|AB|是多少？|AB|= mn3-4.4 笛卡爾積的性質(zhì)：1. 非交換: AB BA (除非 A=B A= B=)反例: A=1, B=2.AB=, BA=.2. 非結(jié)合: (AB)C A(BC) (除非 A= B= C=)反例: A=B=C=1. (AB)C=,1, A(BC)=1,.3. 笛卡爾積分配律：（對或運(yùn)算滿足）（1） A(BC) = (AB)(AC)（2） A(BC) = (AB)(AC)（3） (BC)A = (BA)(CA)（4） (BC)A = (BA)(CA)對任意非空集合A,B,C，是否一定有

14、ABAC BC，試證明或舉出反例。l正確l證明：因?yàn)锳,B,C非空，故xA，yB，有AB AC，l故AC，因此有yC，于是有B C。定義關(guān)系：二元關(guān)系(binary relation) ，簡稱關(guān)系，任一序偶的集合即確定了一個二元關(guān)系R，R中任一序偶 可記為 R或xRy。不在R中的任一序偶 可記為 R或xRy例1: 在實(shí)數(shù)中關(guān)系“”可記作 “ ”=|x,y是實(shí)數(shù)且x y。例2: R1=, R1是二元關(guān)系. 例3: A=,a,1 A不是關(guān)系. A到B的二元關(guān)系也可定義關(guān)系為：設(shè)有任意兩個集合A和B，直積AB的子集R稱為A到B的二元關(guān)系。R是A到B的二元關(guān)系 RAB RP (AB)（冪集）若|A|=

15、m, |B|=n, 則|AB|= mn , 故|P (AB)|=2mn，即A到B不同的二元關(guān)系共有2mn個A到B的二元關(guān)系(舉例)例: 設(shè) A=a1,a2, B=b, 則A到B的二元關(guān)系共有221=4個: R1=, R2=, R3=, R4=,B到A的二元關(guān)系也有4個: R5=, R6=, R7=, R8=,。 A上的二元關(guān)系定義 A上的二元關(guān)系: 是AA的任意子集。 R是A上的二元關(guān)系 RAA RP (AA)。若|A|=m, 則|AA|=m2, 故|P (AA)|= 2 m2 ，即A上不同的二元關(guān)系共有2 m2個。A上的二元關(guān)系(舉例)例1: 設(shè) A=a1,a2, 則A上的二元關(guān)系共有16個

16、: R1 = , R2 = , R3 = , R4 = , R5 = , R6 = , , R7 = , , R8 = , ,R9 = , ,R10 = , ,R11 = , , R12 = , ，R13 = , ，R14 = , , ，R15 = , ，R16 = , 。例2:已知有限集合A，|A| =2 ，A上可以定義 ? 個二元運(yùn)算，其中 8 個是可交換的， 4 個是冪等的。若|A| =3 ，|P(A)| = ? , |AA| = ? , A上有 ?個不同的二元關(guān)系，其中 ?個是反自反的， 23（8） 個既是對稱的也是反對稱的，A到A共有 見P149 個不同的函數(shù)，其中 ?個是雙射函數(shù)。

17、 3-5.2 與二元關(guān)系有關(guān)的概念對任意集合R, 可以定義:前域定義域（domain）： dom R = x | y (xRy) 值域（range）: ran R = y | x(xRy) 域（field）: FLD R = dom R ran R定義域,值域,域(舉例)例: R1=a,b, R2=, R3=,.當(dāng)a,b不是序偶時, R1不是關(guān)系.dom R1=, ran R1=, FLD R1=dom R2=c,e, ran R2=d,f, FLDR2=c,d,e,fdom R3=1,3,5, ran R3=2,4,6,FLD R3=1,2,3,4,5,6. 3-5.3 一些特殊關(guān)系設(shè)A是任

18、意集合, 則可以定義A上的：空關(guān)系(empty relation): 恒等關(guān)系(identity relation): IA = | a A 全域關(guān)系(universal relation): UA = AA = | xA yA3-6 3-6 關(guān)系的性質(zhì)關(guān)系的性質(zhì)（1） 自反性(reflexivity)（2） 反自反性( irreflexivity)（3） 對稱性(symmetry)（4） 反對稱性( antisymmetry)（5） 傳遞性(transitivity)3-6.1自反性(reflexivity)定義（自反性reflexivity）：設(shè)R為定義在A上的二元關(guān)系，即RAA, 如果對

19、于每一個xA，有xRx (R)，則稱二元關(guān)系R是自反的。 R在A上是自反的 (x)( xA xRx) R在A上是非自反的 (x)( xA R)。定理： R是自反的 IA RMR主對角線上的元素全為1GR的每個頂點(diǎn)處均有自環(huán)。自反性(舉例)：平面上三角形的全等關(guān)系，實(shí)數(shù)集中實(shí)數(shù)的小于等于關(guān)系，冪集上的集合的相等、包含關(guān)系，命題集合上的命題的等價、蘊(yùn)含關(guān)系。3-6.2反自反性(irreflexivity)定義（反自反性irreflexivity）：設(shè)RAA, 如果對于每一個xA，有R，則稱二元關(guān)系R是反自反的。R在A上是反自反的 (x)(xA R )。R在A上是非反自反的 (x)( xA xRx)

20、注意：非自反不一定是反自反的。即存在有關(guān)系既不是自反的也不是反自反的。3-6.3對稱性(symmetry)定義（對稱性symmetry）：設(shè)RAA, 如果對于每個x,yA,每當(dāng) xRy，就有 yRx，則稱集合A上的關(guān)系R是對稱的。R在A上對稱 (x)(y)(xAyA xRyyRx).R非對稱 (x)(y)(xAyA xRyyRx)3-6.4 反對稱性(antisymmetry)定義（反對稱性antisymmetry）：設(shè)RAA,如果對于每個x,yA,每當(dāng) xRy和yRx，必有x=y，則稱集合A上的關(guān)系R是反對稱的。R是反對稱的 (x)(y)(xAyA xRy yRx x=y )(x)(y)(x

21、AyA xy xRy yRx ).R非反對稱 (x)(y)(xA yA xRy yRx xy)3-6.5傳遞性(transitivity)定義（傳遞性transitivity）：設(shè)RAA, 如果對于任意的x,y,zA, 每當(dāng)xRy， yRz 時就有xRz ，稱關(guān)系R在A上是傳遞的。 R在A上是傳遞的 (x)(y)(z)(xAyAzAxRy yRz xRz)R非傳遞 (x)(y)(z)(xAyAzAxRy yRzxRz)。判斷以下關(guān)系所具有的性質(zhì)。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7 =解答：R1=,反對稱,傳遞R2=,反對稱R3=,自反,對稱,傳遞R4=,對稱R5

22、=,自反,反對稱,傳遞R6=,R6= （空關(guān)系） 反自反，對稱，傳遞，反對稱. 設(shè)A=1,5,8，A上的關(guān)系R=(1,1),(1,5),(5,1),(5,5),(8,8),(8,5), (5,8)， R具備哪些性質(zhì)（自反性、反自反性、對稱性、反對稱性、傳遞性） ？ 3-7 復(fù)合關(guān)系和逆關(guān)系3-7.1復(fù)合關(guān)系復(fù)合關(guān)系定義定義1復(fù)合復(fù)合 (合成合成)(composite)關(guān)系關(guān)系:設(shè)設(shè)R為為X到到Y(jié)的關(guān)系，的關(guān)系，S為從為從Y到到Z上的關(guān)系，上的關(guān)系，則則RS稱為稱為R和和S的復(fù)合關(guān)系，表示為：的復(fù)合關(guān)系，表示為：RS= |xXzZ(y)(yYRS).例題：設(shè)關(guān)系f=(1,5),(3,8) ，g=

23、(8,5),(5,3) ，則關(guān)系fog= (1,3),(3,5) ，關(guān)系gof= (5,8) 。 3-7.23-7.2逆關(guān)系逆關(guān)系定義定義2逆逆(inverse)關(guān)系關(guān)系 : 設(shè)R是X到Y(jié)的二元關(guān)系，則從Y到X的二元關(guān)系Rc定義為： Rc = |R.整數(shù)集合上的“”關(guān)系的逆關(guān)系是“”關(guān)系。人群中的父子關(guān)系的逆關(guān)系是子父關(guān)系。容易看出(Rc) c=R例1: 設(shè) R= , , S= , .求: (1)Rc ，Sc. (2) RS, SR解: (1) Rc = , Sc = ,. (2) RS= , SR=. 由復(fù)合關(guān)系滿足結(jié)合律，可以把關(guān)系R本身所組成的復(fù)合關(guān)系寫成：RR， RRR， RRR(m個

24、)，分別記作 R(2)， R(3)， ， R(m)。可以證明復(fù)合關(guān)系不滿足交換律。R1R2 R2R1證明: 若關(guān)系R是對稱的, 則Rk(k1, kN)也是對稱的。 證明: 對于任意的(a, b) Rk, 存在(a, c1) R, (c1, c2) R, , (ck-1, b) R。由R是對稱的, (b, ck-1) R, (ck-1, ck-2) R, , (c2, c1) R, (c1, a) R 。所以(b, a) Rk , 即Rk是對稱的。3-9 3-9 集合的劃分和覆蓋集合的劃分和覆蓋定義定義3-9.1覆蓋覆蓋cover：若把一個集合若把一個集合A分分成若干個叫做分塊的非空子集，使得成

25、若干個叫做分塊的非空子集，使得A中每個中每個元素至少屬于一個分塊，這些分塊的全體叫元素至少屬于一個分塊，這些分塊的全體叫做做A的一個覆蓋。的一個覆蓋。即：設(shè)即：設(shè)A為非空集合，為非空集合，S=S1,S2 ,Sm，其中其中Si A，Si(i=1,2, ,m) 且且S1 S2 SmA，則集合則集合S稱作集合稱作集合A的覆蓋。的覆蓋。定義定義3-9.2劃分劃分partition ：給定集合給定集合A的一個覆蓋的一個覆蓋S，若，若A中的每個元素屬于且僅中的每個元素屬于且僅屬于屬于S的一個分塊，則的一個分塊，則S稱作是稱作是A的一個劃的一個劃分。分。即：若即：若S是集合是集合A的覆蓋，的覆蓋，且滿足且滿

26、足SiSj=， （這里（這里ij），），則稱則稱S是是A的劃分。的劃分。定義定義3-9.3交叉劃分交叉劃分：若若A1,A2, ,Ar與與B1,B2, ,Bs是同一集合是同一集合A的兩種劃分，的兩種劃分，則其中所有則其中所有AiBj組成的非空集合，稱為原組成的非空集合，稱為原來兩種劃分的交叉劃分。來兩種劃分的交叉劃分。定義定義3-9.4加細(xì)加細(xì)：給定給定X集合的任意兩集合的任意兩個劃分個劃分A1,A2, ,Ar和和B1,B2, ,Bs，若，若對于每一個對于每一個Aj，均有，均有Bk使使Aj Bk，則稱，則稱A1,A2, ,Ar為為B1,B2, ,Bs的加細(xì)。的加細(xì)。定理定理3-9.1:設(shè)設(shè)A1,

27、A2, ,Ar與與B1,B2, ,Bs是同一集合是同一集合X的兩種劃分，則其交叉劃分仍是的兩種劃分，則其交叉劃分仍是原集合的一種劃分。原集合的一種劃分。定理定理3-9.2: 任何兩種劃分的交叉劃分，任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。都是原來各劃分的一種加細(xì)。證明見書證明見書130頁。頁。3-10 等價關(guān)系與等價類3-10.1 等價關(guān)系定義3-10.1等價關(guān)系Equivalence Relations：設(shè)A ，R A A，若R是自反的、對稱的和傳遞的，則稱R為A上的等價關(guān)系。3-10.2 等價類定義3-10.2等價類Equivalence classes：設(shè)R是非空集合A上的等價

28、關(guān)系，對任意的aA，定義 aR = xA | aRx，稱為a關(guān)于R的等價類，簡稱a的等價類，在不混淆的情況下記為a。顯然aR非空，因?yàn)閍 aR 定理3-10.2：非空集合A上的等價關(guān)系R，決定了A的一個劃分，該劃分就是商集A/R。集合A上有多少個不同的等價關(guān)系，就有多少種不同的劃分。 是否正確？3-12 序關(guān)系在這一節(jié)中，我們將介紹以下一些序關(guān)系：偏序關(guān)系全序關(guān)系良序關(guān)系擬序關(guān)系*3-13.1 偏序關(guān)系定義定義3-13.1偏偏序關(guān)系序關(guān)系 (partial order) : 設(shè)設(shè)A ，R A A，若，若R是自反的、反對是自反的、反對稱的和傳遞的，則稱稱的和傳遞的，則稱R是是A上的偏序關(guān)系。上的

29、偏序關(guān)系。常將偏序關(guān)系常將偏序關(guān)系R記為記為“”，并將，并將 xRy記為記為xy。序偶。序偶稱為偏序集稱為偏序集(partially ordered set, poset) 。定義定義3-13.2蓋住蓋住:設(shè)設(shè)是偏序集，若有是偏序集，若有x, y A，x y ，且，且x y，且不存在其它元素，且不存在其它元素z， z A，使得，使得x z z y，則稱元素，則稱元素y蓋住元素蓋住元素x。并且記蓋住集為：并且記蓋住集為：COVA=|x,y A ;y蓋住蓋住x。例例2 2：求蓋住集。求蓋住集。P140 例例2COVA=, , 。例例3 3： P140 例例3COVA=, 。3-13.2 哈斯圖根據(jù)

30、上述定義，可以簡化偏序關(guān)系的關(guān)系圖根據(jù)上述定義，可以簡化偏序關(guān)系的關(guān)系圖得到哈斯圖得到哈斯圖(Hasse diagram)，具體畫法如下：，具體畫法如下：用小圓圈代表元素；用小圓圈代表元素； 若若x y，x y，將代表，將代表y的小圓圈放在代的小圓圈放在代表表x的小圓圈之上，的小圓圈之上，1.如果如果 COVCOVA A，則，則在在y與與x之間用直線連之間用直線連接。接。列出集合a,b,c的所有子集，畫出各子集之間包含關(guān)系的哈斯圖。 4-1 4-1 函數(shù)的概念函數(shù)的概念定義4-1.1：函數(shù)（function）集合之間的函數(shù)(function，或說映射mapping)：設(shè)X和Y是任意兩個集合，而

31、f 是X到Y(jié)的一個關(guān)系，如果對于每一個xX,有唯一的yY，使得f，稱關(guān)系f 為函數(shù)，記作f : XY或 X Y如果f，則x稱為自變元（原象），y稱為在f 作用下x的象(image)，f 亦可記作y=f(x)，且記 f(X)= f(x)| xX f從函數(shù)的定義可以知道它與關(guān)系有別于如下兩點(diǎn)：a：函數(shù)的定義域是X，而不能是X的某個真子集。b：一個x只能對應(yīng)于唯一的一個y。即如果f(x)=y 且 f(x)=z，那么y=z。從X到Y(jié)的函數(shù)往往也叫做從X到Y(jié)的映射。 函數(shù)f : XY的前域就是函數(shù)的定義域(domain) dom f 定義為：dom f = x | 存在某個yB使得f =X函數(shù)f : XY的值域(range) ran f 定義為：ran f = y | (x)(xA)f Yf 的值域有時也記作Rf集合Y稱為f 的共域，ran f 稱為函數(shù)的像集合。 有限集X、Y上函數(shù)的個數(shù)設(shè)X和Y都為有限集，|X|=m，|Y|=n(1) 從X到Y(jié)任意一個函數(shù)的定義域是X，在這些函數(shù)中，每一個函數(shù)恰有m個序偶。(2) 任何元素xX，可以有Y的n個元素中的任何一個作為它的像，故共有nm個不同的函數(shù)。例如n=2，m=3，故應(yīng)有23個不同的函數(shù)。今后我們用符號YX表示從X到Y(jié)的所有函數(shù)的集合，甚至當(dāng)X和Y是無限集時，也用這個符號。定義定義4-1.4：f 是是滿射滿射( surjectio