第三章 集合與關(guān)系-20111024

1、第二篇第二篇 集合論集合論第三章第三章 集合與關(guān)系集合與關(guān)系第四章第四章 函數(shù)函數(shù)23-1 3-1 集合的概念和表示方法集合的概念和表示方法v定義定義( (集合集合set)set)：把具有共同性質(zhì)的一些對象匯集把具有共同性質(zhì)的一些對象匯集 成一個(gè)整體，就構(gòu)成一個(gè)集合，這些對象稱為元素成一個(gè)整體，就構(gòu)成一個(gè)集合，這些對象稱為元素 (element) (element)或成員或成員(member)(member) 用大寫英文字母用大寫英文字母A,B,C,A,B,C,表示集合表示集合 用小寫英文字母用小寫英文字母a,b,c,a,b,c,表示元素表示元素 a a A A：表示：表示a a是是A A的元

2、素，讀作的元素，讀作“a a屬于屬于A”A” a a A A：表示：表示a a不是不是A A的元素，讀作的元素，讀作“a a不屬于不屬于A”A”33-1 3-1 集合的概念和表示方法集合的概念和表示方法v集合的表示方法集合的表示方法通常使用通常使用“列舉法列舉法”和和“敘述法敘述法” 兩種方法來兩種方法來給出一個(gè)集合給出一個(gè)集合（1 1）列舉法）列舉法(roster)(roster)列出集合中的全體元素，元素之間用逗號分開，列出集合中的全體元素，元素之間用逗號分開，然后用花括號括起來，例如然后用花括號括起來，例如A=a,b,c,d,x,y,zA=a,b,c,d,x,y,zB=0,1,2,3,4

3、,5,6,7,8,9B=0,1,2,3,4,5,6,7,8,9無序性無序性C=2,1=1,2C=2,1=1,2互異性互異性C=2,1,1,2=2,1C=2,1,1,2=2,143-1 3-1 集合的概念和表示方法集合的概念和表示方法（2 2）敘述法）敘述法(defining predicate)(defining predicate) 用謂詞用謂詞P(x)P(x)表示表示“x x具有性質(zhì)具有性質(zhì)P” P” ，用，用 A=x|P(x)A=x|P(x)表示具有性質(zhì)表示具有性質(zhì) P P的元素的集合，如果的元素的集合，如果P(b)P(b)為真，那么為真，那么b b A A，否則，否則b b A A。P

4、 P1 1(x): x(x): x是英文字母是英文字母A=x|PA=x|P1 1(x)=x| x(x)=x| x是英文字母是英文字母 =a,b,c,d,x,y,z =a,b,c,d,x,y,zP P2 2(x): x(x): x是十進(jìn)制數(shù)字是十進(jìn)制數(shù)字B=x|PB=x|P2 2(x)= x|x(x)= x|x是十進(jìn)制數(shù)字是十進(jìn)制數(shù)字 =0,1,2,3,4,5,6,7,8,9 =0,1,2,3,4,5,6,7,8,953-1 3-1 集合的概念和表示方法集合的概念和表示方法v兩種表示法可以互相轉(zhuǎn)化兩種表示法可以互相轉(zhuǎn)化例如：例如：E=2,4,6,8,E=2,4,6,8, =x|x0 =x|x0且

5、且x x是偶數(shù)是偶數(shù) =x|x=2(k+1) =x|x=2(k+1)，k k為非負(fù)整數(shù)為非負(fù)整數(shù) =2(k+1) | k =2(k+1) | k為非負(fù)整數(shù)為非負(fù)整數(shù) 兩個(gè)集合相等的外延性原理：兩個(gè)集合相等的外延性原理： 兩個(gè)集合兩個(gè)集合A A、B B是相等的，當(dāng)且僅當(dāng)它們有相是相等的，當(dāng)且僅當(dāng)它們有相同的成員，記作同的成員，記作A=BA=B；否則記作；否則記作A A B B 。集合的元素還可以是一個(gè)集合。集合的元素還可以是一個(gè)集合。 例如：例如：S=a,1,2,p,qS=a,1,2,p,q63-1 3-1 集合的概念和表示方法集合的概念和表示方法v集合之間的關(guān)系集合之間的關(guān)系子集、相等、真子集

6、；子集、相等、真子集；空集、全集；空集、全集；冪集；冪集；73-1 3-1 集合的概念和表示方法集合的概念和表示方法v（1）子集）子集定義子集(subset)：設(shè)設(shè)A A、B B是任意兩個(gè)集合，如果是任意兩個(gè)集合，如果A A的每一個(gè)元素是的每一個(gè)元素是B B的成員，則稱的成員，則稱A A為為B B的子集的子集, , 或說或說A A包含于包含于B, B, 或說或說B B包包含含A, A, 記作記作A A B B，或，或B B A A。A A B B ( ( x)(xx)(x A Ax x B)B)若若A A不是不是B B的子集的子集, , 則記作則記作A A B BA A B B ( ( x)(

7、xx)(x A A x x B)B)設(shè)設(shè)A=a,b,c,B=a,b,c,d,C=a,b,A=a,b,c,B=a,b,c,d,C=a,b,則則A A B, CB, C A, CA, C B B83-1 3-1 集合的概念和表示方法集合的概念和表示方法v定理定理3-1.13-1.1集合集合A A和集合和集合B B相等的充分必要條件是這相等的充分必要條件是這兩個(gè)集合互為子集。兩個(gè)集合互為子集。 （B B A A）（ A A B B） 如果如果A A和和B B不相等，則記作不相等，則記作ABAB證明證明：設(shè)任意兩個(gè)集合相等，則根據(jù)定義，有相同的：設(shè)任意兩個(gè)集合相等，則根據(jù)定義，有相同的元素。故元素。故

8、 x(xx(xxB)xB)為真，且為真，且 x(xBxA)x(xBxA)為為真。即：（真。即：（B B A A）（ A A B B）反之，若有反之，若有 且且 A A，假設(shè)，假設(shè) ，則與的，則與的元素不完全相同，設(shè)有某一元素元素不完全相同，設(shè)有某一元素xx但但x x ，這與，這與 條件相矛盾；或設(shè)有某一元素條件相矛盾；或設(shè)有某一元素xx但但x x ，這與，這與 條件相矛盾；故，的元素必須相同，即。條件相矛盾；故，的元素必須相同，即。1.子集93-1 3-1 集合的概念和表示方法集合的概念和表示方法v包含包含( ( ) )的性質(zhì)：的性質(zhì)：1 1A A A A（自反性自反性）證明證明: A: A

9、A A( ( x)(xx)(x A Ax x A) A) T T2 2若若A A B,B,且且A A B,B,則則 B B A A（反對稱性反對稱性）3 3若若A A B,B,且且B B C,C,則則 A A C C（傳遞性傳遞性）證明證明: A: A B B ( ( x)(xx)(x A Ax x B) B) x, xx, x A A x x B (AB (A B)B) x x C (BC (B C)C) ( ( x)(xx)(x A Ax x C), C), 即即A A C.C. 1.子集103-1 3-1 集合的概念和表示方法集合的概念和表示方法2.真子集v 定義定義 真子集真子集(pr

10、oper subset)(proper subset)如果集合如果集合A A的每一個(gè)元素都屬于的每一個(gè)元素都屬于B B，但集合，但集合B B至少至少有一個(gè)元素不屬于有一個(gè)元素不屬于A A，則稱，則稱A A為為B B的真子集，記作的真子集，記作A A B B。A A B B A A B B A A B BA A B B( ( x)(xx)(x A Ax x B)B) ( ( x)(xx)(x B B x x A)A)113-1 3-1 集合的概念和表示方法集合的概念和表示方法3.空集v 定義定義 空集空集(empty set)(empty set)：沒有任何元沒有任何元 素的集合是空集素的集合是

11、空集, ,記作記作例如：例如：xx R|xR|x2 2+1=0+1=0v 定理定理 對任意集合對任意集合A A，空集是它的子集，空集是它的子集也就是對任意集合也就是對任意集合A, A, A A證明見書上的反證法。證明見書上的反證法。對于每一個(gè)非空集合對于每一個(gè)非空集合A A，至少有兩個(gè)不同，至少有兩個(gè)不同 的子集，的子集，A A和和，稱為，稱為A A的的平凡子集。平凡子集。123-1 3-1 集合的概念和表示方法集合的概念和表示方法4.全集v 定義定義 全集全集: : 在一定范圍內(nèi)，如果所有集合均為某一集合的子在一定范圍內(nèi)，如果所有集合均為某一集合的子集集, ,則稱這個(gè)集合是全集則稱這個(gè)集合是

12、全集, ,記作記作E E。E=x| P(x) E=x| P(x) P(x)P(x)，P(x)P(x)為任何謂詞。為任何謂詞。全集是相對的全集是相對的, , 視情況而定視情況而定, , 因此不唯一。因此不唯一。133-1 3-1 集合的概念和表示方法集合的概念和表示方法5.冪集冪集v 定義定義 冪集冪集(power set)(power set)給定集合給定集合A A，由集合，由集合A A的所有子集為元素組成的的所有子集為元素組成的集合集合, ,稱為稱為A A的冪集的冪集, ,記作記作P(A)P(A)P(A)=x|xP(A)=x|x AA注意注意: x: x P(A) P(A) x x A A例

13、如例如: A=a,b, : A=a,b, P(A)= P(A)=,a,b,a,b.,a,b,a,b. 143-1 3-1 集合的概念和表示方法集合的概念和表示方法v 定理定理 如果有限集合如果有限集合A A有有n n個(gè)元素，則冪集個(gè)元素，則冪集P(A) P(A) 有有2 2n n個(gè)元素。個(gè)元素。 證明證明: : 見課本第見課本第8585頁，利用二項(xiàng)式展開定理。頁，利用二項(xiàng)式展開定理。5.冪集153-1 3-1 集合的概念和表示方法集合的概念和表示方法v注意：注意：與與 的聯(lián)系與區(qū)別的聯(lián)系與區(qū)別(1) (1) 表示集合的元素（可以為集合）與集合本身表示集合的元素（可以為集合）與集合本身的從屬關(guān)系

14、，的從屬關(guān)系，(2) (2) 表示兩個(gè)集合之間的包含關(guān)系。表示兩個(gè)集合之間的包含關(guān)系。例如：對于集合例如：對于集合A=a,b,c,aA=a,b,c,a是是A A的子集：的子集： a a A A，a a是是A A的元素：的元素：aAaA。注意：不要寫成注意：不要寫成aAaA和和a a A A。a a aa，但，但aaaa； 是一元集，而不是空集。是一元集，而不是空集。| |=1|=1，| |=0|=0。163-1 3-1 集合的概念和表示方法集合的概念和表示方法v確定下列命題是否為真確定下列命題是否為真? ?(1) (1) (2) (2) (3) (3) (4) (4) 解：（解：（1 1），（

15、），（3 3），（），（4 4）為真，）為真， （2 2）為假）為假173-23-2 集合的運(yùn)算集合的運(yùn)算v 定義定義 集合的交集合的交(intersection):(intersection): 設(shè)任意兩個(gè)集合設(shè)任意兩個(gè)集合A A和和B B，由集合，由集合A A和和B B的所有共同的所有共同元素組成的集合元素組成的集合S S，稱為，稱為A A和和B B的交集，記作的交集，記作A A B B 。S=AS=A B = x | (xB = x | (x A) A) (x (x B) B) x x A A B B (x (x A) A) (x (x B)B)183-23-2 集合的運(yùn)算集合的運(yùn)算例例

16、3 3：設(shè)集合：設(shè)集合A=0A=0，2 2，4 4，6 6，8 8，1010，1212，B=1B=1，2 2，3 3，4 4，5 5，66。則。則 A A B=2 B=2，4 4，66例例4 4：設(shè)：設(shè)A A是所有矩形的集合，是所有矩形的集合，B B是平面上所有菱形的是平面上所有菱形的集合，則集合，則A A B B是所有正方形的集合。是所有正方形的集合。例例5 5：設(shè)：設(shè)A A是所有被是所有被K K除盡的整數(shù)的集合，除盡的整數(shù)的集合，B B是所有被是所有被L L除盡的整數(shù)的集合，則除盡的整數(shù)的集合，則A A B B是被是被K K與與L L最小公倍數(shù)最小公倍數(shù)除得盡的整數(shù)的集合除得盡的整數(shù)的集合

17、。193-23-2 集合的運(yùn)算集合的運(yùn)算集合交運(yùn)算的性質(zhì)集合交運(yùn)算的性質(zhì)a) A a) A A = A A = A （冪等律）（冪等律）b) A b) A = = （零律）（零律）c) Ac) A E = A E = A （同一律）（同一律）d) A d) A B = B B = B A A （交換律）（交換律）e) (A e) (A B) B) C = A C = A (B (B C) C) （結(jié)合律）（結(jié)合律）證明證明(e)(e)：(A(A B)B) C=C=x|xx|x （A A B)B) x x C C A A ( (B B C)=x|xC)=x|x A A x x ( (B B C)

18、C) x|xx|x ( (A A B)B) x x C C x|(xx|(x A A x x B)B) x x C C x|xx|x A A (x(x B B x x C)C) x|xx|x A)A) x x ( (B B C)C) 203-23-2 集合的運(yùn)算集合的運(yùn)算v集合的并集合的并(union)(union)：設(shè)任意兩個(gè)集合設(shè)任意兩個(gè)集合A A和和B B，由所有集合，由所有集合A A和和B B的元素組的元素組成的集合成的集合S S，稱為，稱為A A和和B B的并集，記作的并集，記作A A B B 。 S=AS=A B = x | (xB = x | (x A) A) (x (x B)

19、B) x x A A B B (x (x A) A) (x (x B)B)213-23-2 集合的運(yùn)算集合的運(yùn)算例例1 1：設(shè)集合：設(shè)集合A=1A=1，2 2，3 3，44，B=2B=2，4 4，55。 則則A A B=1 B=1，2 2，3 3，4 4，55例例2 2：設(shè)：設(shè)A A B B，C C D D，則，則A A C C B B D D證明證明：對任意的：對任意的x x A A C C，則有，則有x x A A或或x x C C，若，若x x A A， 由由A A B B則則x x B B，故，故x x B B D D。 若若x x C C，由，由C C D D則則x x D D，故，

20、故x x B B D D。 因此，得因此，得A A C C B B D D 同理可證：同理可證：A A B B，則，則A A C C B B C C223-23-2 集合的運(yùn)算集合的運(yùn)算v集合并運(yùn)算的性質(zhì)集合并運(yùn)算的性質(zhì)a) A a) A A = A A = A （冪等律）（冪等律）b) A b) A = = A A （同一律）（同一律）c) Ac) A E = E E = E （零律）（零律）d) A d) A B = B B = B A A （交換律）（交換律）e) (A e) (A B) B) C = A C = A (B (B C) C) （結(jié)合律（結(jié)合律）證明證明(e)(e)：(A

21、(A B) B) C=C=x|xx|x （A A B)B) x x C C A A ( (B B C)=x|xC)=x|x A)A) x x ( (B B C)C) x|xx|x ( (A A B)B) x x C C x|(xx|(x A A x x B)B) x x C C x|xx|x A A (x(x B B x x C)C) x|xx|x A)A) x x ( (B B C)C) 233-2 3-2 集合的運(yùn)算集合的運(yùn)算 分配律分配律(distributive laws)(distributive laws) A A (B(B C)=(AC)=(A B)B) (A(A C) C) A

22、 A (B(B C)=(AC)=(A B)B) (A(A C)C) 吸收律吸收律(absorption laws)(absorption laws) A A (A(A B)=AB)=A A A (A(A B)=AB)=A243-23-2 集合的運(yùn)算集合的運(yùn)算v3.2.3 3.2.3 集合的補(bǔ)相對補(bǔ)集合的補(bǔ)相對補(bǔ) 定義定義 補(bǔ)集相對補(bǔ)集：補(bǔ)集相對補(bǔ)集： 屬于屬于A A而不屬于而不屬于B B的全體元素組成的集合的全體元素組成的集合S S，為，為B B對于對于A A的補(bǔ)集相對補(bǔ)集的補(bǔ)集相對補(bǔ)集, , 記作記作A-BA-B S=A-B = x | (x S=A-B = x | (x A) A) (x

23、(x B) B) 定義定義 絕對補(bǔ)：絕對補(bǔ)： 設(shè)設(shè)E E為全集，對任一集合為全集，對任一集合A A關(guān)于關(guān)于E E的補(bǔ)的補(bǔ)E-AE-A，稱為，稱為集合集合A A的絕對補(bǔ)，記作的絕對補(bǔ)，記作 A A。 A=x|(xA=x|(x E E x x A)A)253-23-2 集合的運(yùn)算集合的運(yùn)算A-BA-B A A263-23-2 集合的運(yùn)算集合的運(yùn)算 補(bǔ)集運(yùn)算有以下性質(zhì)：補(bǔ)集運(yùn)算有以下性質(zhì)：1 1、 （ A A）=A=A2 2、 E= E= 3 3、 =E=E4 4、 A A A=EA=E5 5、 A A A=A=6 6、 (A(A B)= B)= A A B B (A(A B)= B)= A A B

24、 B7 7、 A-B=AA-B=A B B 273-23-2 集合的運(yùn)算集合的運(yùn)算v集合的對稱差集合的對稱差定義對稱差定義對稱差 (symmetricdifference)(symmetricdifference)：屬于屬于A A而不屬于而不屬于B, B, 或?qū)儆诨驅(qū)儆贐 B而不屬于而不屬于A A的全體元素組的全體元素組 成的集合成的集合S, S, 稱為稱為A A與與B B的對稱差的對稱差, , 記作記作A A B B。A A B=x|(xB=x|(x A A x x B)B) (x(x A A x x B)B)A A B=(A-B)B=(A-B) (B-A)=(A(B-A)=(A B)-(A

25、B)-(A B)B)283-23-2 集合的運(yùn)算集合的運(yùn)算v對稱差對稱差( )的性質(zhì)的性質(zhì)（1）A B=B A（2）A=A（3）A A=（4）A B=(A B) ( ( A B) )（5）結(jié)合律：結(jié)合律：A (B C)=(A B) C293-23-2 集合的運(yùn)算集合的運(yùn)算v相對補(bǔ)、對稱差相對補(bǔ)、對稱差 (舉例舉例)例例: : 設(shè)設(shè)A=xA=x R|0R|0 x2, B=xx2, B=x R|1R|1 x3,x3,則則 A-B=x A-B=x R|0R|0 x1=0,1)x1=0,1) B-A=x B-A=x R|2R|2 x3=2,3)x3=2,3) A A B=xB=x R|(0R|(0 x

26、1)x1) (2(2 x3)=0,1)x3)=0,1) 2,3)2,3)303-23-2 集合的運(yùn)算集合的運(yùn)算v集合恒等式證明集合恒等式證明(方法方法)（1 1）邏輯演算法）邏輯演算法: : 利用邏輯等價(jià)式和邏輯推理規(guī)則利用邏輯等價(jià)式和邏輯推理規(guī)則（2 2）集合演算法）集合演算法: : 利用集合恒等式和已知的集合結(jié)論利用集合恒等式和已知的集合結(jié)論313-23-2 集合的運(yùn)算集合的運(yùn)算v（1）邏輯演算法）邏輯演算法(格式格式) 題型: A=B. 證明： x, xA (?) xB A=B 證畢. 或證明： x, xA (?) xB . 另，x, xB (?) xA . A=B證畢.題型: A B.

27、 證明: x, xA (?) xB A B證畢.323-23-2 集合的運(yùn)算集合的運(yùn)算v例例1 1：分配律：分配律( (證明證明) )A A (B(B C)=(AC)=(A B)B) (A(A C)C)證明證明: : x, xx, x A A (B(B C)C) x x A A x x (B(B C) (C) ( 定義定義) ) x x A A (x (x B B x x C) (C) ( 定義定義) ) (x (x A A x x B)B) (x(x A A x x C) (C) (命題邏輯分配律命題邏輯分配律) ) (x (x A A B)B) (x(x A A C) (C) ( 定義定義

28、) ) x x (A(A B)B) (A(A C) (C) ( 定義定義) ) A A (B(B C)=(AC)=(A B)B) (A(A C)C)成立成立333-23-2 集合的運(yùn)算集合的運(yùn)算v例例2 2：零律：零律( (證明證明) ) A A = = 證明證明: : x, xx, x A A x x A A x x ( ( 定義定義) ) x x A A F ( F (定義定義) ) F ( F (命題邏輯零律命題邏輯零律) ) A A = = 成立成立343-23-2 集合的運(yùn)算集合的運(yùn)算v(2) (2) 集合演算法（格式）集合演算法（格式）題型題型:A=B.題型題型:A B.證明證明:

29、A證明證明:A=(?) (?)=B BA=BA B353-23-2 集合的運(yùn)算集合的運(yùn)算v例例1 1：吸收律：吸收律( (一式證明一式證明) )A (A B)=A證明證明:A (A B)=(A E) (A B)(同一律同一律)=A (E B)(逆用分配律逆用分配律)=A E(零律零律)=A(同一律同一律)A (A B)=A363-23-2 集合的運(yùn)算集合的運(yùn)算v例例2 2：吸收律：吸收律( (二式證明二式證明) )A (A B)=A證明證明:A (A B)=(A A) (A B)(分配律分配律)=A (A B)(冪等律冪等律)=A(吸收律第一式吸收律第一式)A (A B)=A373-23-2

30、集合的運(yùn)算集合的運(yùn)算v(2)集合演算法（格式）續(xù)集合演算法（格式）續(xù) 題型題型: A B 證明: AB (或AB) =(?) = A (或B) AB. 說明說明: 化化 成成=題型題型: A=B證明: () AB () A B A = B. 說明說明: 把把=分成分成 與與 AB=AABAB=BAB38作業(yè)作業(yè)(3-1,3-2)P94(5)a)3-3 包含排斥原理包含排斥原理v 定理定理3-3.1 3-3.1 設(shè)設(shè)A A1 1，A A2 2為有限集合，其元素個(gè)數(shù)分別為有限集合，其元素個(gè)數(shù)分別為為|A|A1 1| |，|A|A2 2| |，則，則|A|A1 1AA2 2|= |A|= |A1 1

31、|+|A|+|A2 2|- |A|- |A1 1AA2 2| |證明：見證明：見P96P96v 推理：推理：對于任意三個(gè)有限集合對于任意三個(gè)有限集合A A1 1，A A2 2和和A A3 3，則，則|A|A1 1AA2 2AA3 3 |= |A |= |A1 1|+|A|+|A2 2| +|A| +|A3 3| - |A| - |A1 1AA2 2|- |- |A|A1 1AA3 3| - |A| - |A2 2AA3 3|+ |A|+ |A1 1AA2 2AA3 3| |403-3 包含排斥原理包含排斥原理例例: :在在2020名青年有名青年有1010名是公司職員名是公司職員,12,12名是

32、學(xué)生名是學(xué)生, ,其其中中5 5名既是職員又是學(xué)生名既是職員又是學(xué)生, ,問有幾名既不是職員問有幾名既不是職員, ,又又不是學(xué)生。不是學(xué)生。解解: :設(shè)職員和學(xué)生的集合分別是設(shè)職員和學(xué)生的集合分別是A A和和B B。 由已知條件由已知條件 A A =10,=10, B B =12, =12, A A B B =5=5 A A B B = = A A + + B B - - A A B B =10+12-5=17=10+12-5=17 則則(A(A B)B) = = E E - - A A B B =20-17=3=20-17=3 有有3 3名既不是職員又不是學(xué)生。名既不是職員又不是學(xué)生。413

33、-4 序偶與笛卡爾積序偶與笛卡爾積v 3-4.13-4.1 序偶序偶( (二元組二元組) )定義序偶定義序偶o(jì)rdered pairordered pair：由兩個(gè)固定次序的客體由兩個(gè)固定次序的客體 a,ba,b組成的序列稱為序組成的序列稱為序偶，記作偶，記作，其中，其中a,ba,b稱為序偶的分量。稱為序偶的分量。 其中其中, a, a是第一元素是第一元素, b, b是第二元素。是第二元素。定理定理: :序偶序偶和和 相等，當(dāng)且僅當(dāng)相等，當(dāng)且僅當(dāng)a=c a=c 且且b=db=d，即，即= = (a=c) (a=c) ( (b=d)b=d)推論推論: : a a b b 423-4 序偶與笛卡爾

34、積序偶與笛卡爾積v 3-4.2 3-4.2 三元組三元組(ordered triple)(ordered triple)三元組是一個(gè)序偶，其第一元素本身也是一個(gè)序三元組是一個(gè)序偶，其第一元素本身也是一個(gè)序偶，可形式化為偶，可形式化為,z,z。,z = ,w iff = ,z=w,z = ,w iff = ,z=w。即即x=u,y=v,z=wx=u,y=v,z=w注意：注意：1 1、 當(dāng)當(dāng)x x y y時(shí)時(shí), , 。 2 2、 ,z ,z x, x,因?yàn)橐驗(yàn)閤,x,不是不是三元組三元組。433-4 序偶與笛卡爾積序偶與笛卡爾積定義定義: :三元組：三元組：=,c.=,c.定義定義: : n(n(

35、 2)2)元組：元組： a=,a,an n.定理定理: : a= = a ai i = b= bi i, i =1,2,n. , i =1,2,n. 443-4 序偶與笛卡爾積序偶與笛卡爾積v3-4.33-4.3 笛卡爾積笛卡爾積(Cartesian product)(Cartesian product)及其性質(zhì)及其性質(zhì)定義笛卡爾積：定義笛卡爾積：A A和和B B為任意兩個(gè)集合，若為任意兩個(gè)集合，若序偶的第一個(gè)成員是序偶的第一個(gè)成員是A A的元素，第二個(gè)成員是的元素，第二個(gè)成員是B B的的元素，所有這樣序偶的集合，稱為元素，所有這樣序偶的集合，稱為A A和和B B的笛卡爾的笛卡爾積或直積，記為

36、：積或直積，記為： A A B=|(xB=|(x A)A) ( (y y B).B).453-4 序偶與笛卡爾積序偶與笛卡爾積v 例例1: A=,a, B=1,2,3. AB= ,. BA= ,. AA= , , , . BB= , , . 463-4 序偶與笛卡爾積序偶與笛卡爾積v3-4.4 3-4.4 笛卡爾積的性質(zhì)笛卡爾積的性質(zhì)1.1.若若A,BA,B中有一個(gè)空集中有一個(gè)空集, ,則它們的笛卡兒積是空集則它們的笛卡兒積是空集, ,即即 B BB B 2.2.當(dāng)當(dāng)ABAB且且A,BA,B都不是空集時(shí)都不是空集時(shí), ,有有A ABBBBA A。所以所以, ,笛卡兒積運(yùn)算笛卡兒積運(yùn)算不適合交換

37、律不適合交換律。反例反例: A=1, B=2.: A=1, B=2. A A B=, BB=, B A=.A=.473-4 序偶與笛卡爾積序偶與笛卡爾積3.3.當(dāng)當(dāng)A,B,CA,B,C都不是空集時(shí)都不是空集時(shí),(A,(AB)B)CACA(B(BC).C).所以所以, ,笛卡兒積運(yùn)算笛卡兒積運(yùn)算不適合結(jié)合律不適合結(jié)合律。反例反例: A=B=C=1.: A=B=C=1. (A (A B)B) C=,1, C=,1, A A (B(B C)=1,.C)=1,.4.4.當(dāng)當(dāng)|A|=m|A|=m，|B|=n|B|=n時(shí)，時(shí)，|A|AB|= mB|= mn n 483-4 序偶與笛卡爾積序偶與笛卡爾積笛卡

38、爾積分配律：（對笛卡爾積分配律：（對 或或 運(yùn)算滿足）運(yùn)算滿足）（1 1） A A (B(B C) = (AC) = (A B)B) (A(A C)C)（2 2） A A (B(B C) = (AC) = (A B)B) (A(A C)C)（3 3） (B(B C)C) A = (BA = (B A)A) (C(C A)A)（4 4） (B(B C)C) A = (BA = (B A)A) (C(C A)A)493-4 序偶與笛卡爾積序偶與笛卡爾積 笛卡爾積分配律笛卡爾積分配律( (證明證明(1) (1) A A (B(B C) = (AC) = (A B)B) (A(A C).C). 證明證

39、明: : , , A A (B(B C)C) x x A A y y (B(B C) C) x x A A (y(y B B y y C) C) (x (x A A y y B)B) (x(x A A y y C)C) ( ( A A B)B) ( A A C)C) (A(A B)B) (A(A C)C) A A (B(B C) = (AC) = (A B)B) (A(A C).C). 503-4 序偶與笛卡爾積序偶與笛卡爾積 其他性質(zhì)：其他性質(zhì)： 設(shè)設(shè)A,B,C,DA,B,C,D是任意集合是任意集合, , (1) (1) 若若A A, , 則則A A B B A A C C B B A A

40、C C A A B B C C（即書上的定理（即書上的定理3-4.23-4.2） (2) A (2) A C C B B D D A A B B C C D.D.（即書上的定（即書上的定 理理3-4.33-4.3） (3) A (3) A B=B= A= A= B= B=513-4 序偶與笛卡爾積序偶與笛卡爾積證明證明(1) (1) 若若A A, , 則則A A B B A A C C B B C.C.證明證明: (: () ) 若若 B=B=, , 則則 B B C.C. 設(shè)設(shè) B B, , 由由A A, , 設(shè)設(shè)x x A, A, y, yy, y B B， A A B B A A C C

41、 x x A A y y C C y y C.C. B B C C ( () )若若B=B=, ,則則A A B=B=A A C.C. 設(shè)設(shè) B B. . , , A A B B x x A A y y B B x x A A y y C C A A C C A A B B A A C.C.523-4 序偶與笛卡爾積序偶與笛卡爾積vn維笛卡爾積維笛卡爾積定義 n維笛卡爾積：A1A2An = | x1A1x2A2xn An AAA = An|Ai|=ni , i =1,2,n |A1A2An| = n1n2nn.n維笛卡爾積性質(zhì)維笛卡爾積性質(zhì)與與2維笛卡爾積類似維笛卡爾積類似.53作業(yè)作業(yè) P1

42、04 (1) b)P104 (1) b) 543-5關(guān)系及其表示關(guān)系及其表示v 關(guān)系的概念及記號關(guān)系的概念及記號兄弟關(guān)系、長幼關(guān)系、同學(xué)關(guān)系、鄰居關(guān)系，兄弟關(guān)系、長幼關(guān)系、同學(xué)關(guān)系、鄰居關(guān)系，上下級關(guān)系等。上下級關(guān)系等。在數(shù)學(xué)上有大于關(guān)系、小于關(guān)系，整除關(guān)系。在數(shù)學(xué)上有大于關(guān)系、小于關(guān)系，整除關(guān)系。例如：例如：“3 3小于小于5”5”，“x x大于大于y”y”， “ “點(diǎn)點(diǎn)a a在在b b與與c c之間之間”。我們又知道序偶可以表達(dá)兩個(gè)客體、三個(gè)客體我們又知道序偶可以表達(dá)兩個(gè)客體、三個(gè)客體或或n n個(gè)客體之間的聯(lián)系，因此用序偶表達(dá)這個(gè)概念是個(gè)客體之間的聯(lián)系，因此用序偶表達(dá)這個(gè)概念是非常自然的。

43、非常自然的。553-5關(guān)系及其表示關(guān)系及其表示v 例如：火車票與座位之間有對號關(guān)系。例如：火車票與座位之間有對號關(guān)系。設(shè)設(shè)X X表示火車票的集合，表示火車票的集合，Y Y表示座位的集合，表示座位的集合，則對于任意的則對于任意的 x x X X 和和 y y Y Y，必定有，必定有x x與與y y存在存在“對號對號”關(guān)系或者關(guān)系或者x x與與y y無無“對號對號”關(guān)系。關(guān)系。令令R R表示表示“對號對號”關(guān)系，關(guān)系，則上述問題可以表示為則上述問題可以表示為 xRy xRy 或或 xRy xRy 。亦可表示為亦可表示為 R R 或或 R R，因此我們看到對號關(guān)系是序偶的集合。因此我們看到對號關(guān)系是

44、序偶的集合。563-5關(guān)系及其表示關(guān)系及其表示v 定義關(guān)系：定義關(guān)系：二元關(guān)系二元關(guān)系(binary relation) (binary relation) ，簡稱關(guān)系，任一序偶的集合即確定了一個(gè)二元簡稱關(guān)系，任一序偶的集合即確定了一個(gè)二元關(guān)系關(guān)系R R，R R中任一序偶中任一序偶 可記為可記為 R R或或xRyxRy。不在不在R R中的任一序偶中的任一序偶 可記為可記為 R R或或xRyxRy573-5關(guān)系及其表示關(guān)系及其表示v例例1: 1: 在實(shí)數(shù)中關(guān)系在實(shí)數(shù)中關(guān)系“”“”可記作可記作 “ ” “ ”=|x,y=|x,y是實(shí)數(shù)且是實(shí)數(shù)且x yx y。v例例2: R1=,2: R1=, R1

45、 R1是二元關(guān)系。是二元關(guān)系。v例例3: A=,a,13: A=,a,1 A A不是關(guān)系。不是關(guān)系。 583-5 關(guān)系及其表示關(guān)系及其表示v3-5.23-5.2 與二元關(guān)系有關(guān)的概念與二元關(guān)系有關(guān)的概念對任意集合對任意集合R, R, 可以定義可以定義: :前域定義域（前域定義域（domaindomain）：）： dom R = x | dom R = x | y (xRy) y (xRy) 值域（值域（rangerange）: : ran R = y | ran R = y | x (xRy) x (xRy) 域（域（fieldfield）: : FLD R = dom R FLD R = d

46、om R ran R ran R593-5 關(guān)系及其表示關(guān)系及其表示v定義域定義域,值域值域,域域(舉例舉例) 例例: : R R1 1=a,b, R=a,b, R2 2=, =, R R3 3=,.=,. 當(dāng)當(dāng)a,ba,b不是序偶時(shí)不是序偶時(shí), R, R1 1不是關(guān)系不是關(guān)系. . dom R dom R1 1= =, ran R, ran R1 1= =, , FLD R FLD R1 1= = dom R dom R2 2=c,e, ran R=c,e, ran R2 2=d,f, =d,f, FLDR FLDR2 2=c,d,e,f=c,d,e,f dom R dom R3 3=1,3

47、,5, ran R=1,3,5, ran R3 3=2,4,6,=2,4,6, FLD R FLD R3 3=1,2,3,4,5,6.=1,2,3,4,5,6. 603-5 關(guān)系及其表示關(guān)系及其表示vA到到B的二元關(guān)系的二元關(guān)系也可定義關(guān)系為：設(shè)有任意兩個(gè)集合A和B，直積AB的子集R稱為A到B的二元關(guān)系。R是A到B的二元關(guān)系 RAB RP (AB)（冪集）若|A|=m, |B|=n, 則|AB|= mn故|P (AB)|=2mn，即A到B不同的二元關(guān)系共有2mn個(gè)613-5 關(guān)系及其表示關(guān)系及其表示例: 設(shè) A=a1,a2, B=b, 則A到B的二元關(guān)系共有221=4個(gè): R1=, R2=,

48、R3=, R4=,B到A的二元關(guān)系也有4個(gè): R5=, R6=, R7=, R8=,。623-5 關(guān)系及其表示關(guān)系及其表示v一些特殊關(guān)系 設(shè)A是任意集合, 則可以定義A上的： 空關(guān)系 (empty relation): 恒等關(guān)系(identity relation): IA = | a A 全域關(guān)系(universal relation): UA = AA = | xA yA633-5 關(guān)系及其表示關(guān)系及其表示v設(shè)AR, 則可以定義A上的： 小于等于(less than or equal to)關(guān)系： LEA = | xA yA xy 小于(less than)關(guān)系： LA = | xA yA

49、 xy 大于等于(greater than or equal to)關(guān)系，大于(great than)關(guān)系,643-5 關(guān)系及其表示關(guān)系及其表示v 設(shè)A為任意集合, 則可以定義P (A)上的:包含關(guān)系: A = | xA yA xy 真包含關(guān)系： A = | xA yA xy P107 例2和例3653-5 關(guān)系及其表示關(guān)系及其表示v關(guān)系的運(yùn)算關(guān)系的運(yùn)算定理：若Z和S是從集合X到集合Y的兩個(gè)關(guān)系，則Z和S的并、交、補(bǔ)、差仍是X到Y(jié)的關(guān)系。證明見書108頁。663-5 關(guān)系及其表示關(guān)系及其表示v二元關(guān)系的表示(1) 序偶集合的形式表達(dá) (2) 關(guān)系矩陣：設(shè) A=a1,a2,an,B=b1,b2,

50、 ,bm ,RAB, 則R的關(guān)系矩陣 MR=rijnm, 其中rij = 1, ai R bj 或 R 0, ai R bj 或 R673-5 關(guān)系及其表示關(guān)系及其表示v例題：P108 例題5 例如: A=a,b,c, R1=, R2=, 則 1 1 0 0 1 1 MR1 = 1 0 1 MR2= 0 0 1 0 0 0 0 0 0 683-5 關(guān)系及其表示關(guān)系及其表示 (3) 關(guān)系圖：A=a1,a2,an，B=b1,b2,bn ，RAB,首先在平面上做結(jié)點(diǎn)a1,a2,an ，b1,b2,bn以“”表示(稱為頂點(diǎn))， 若aiRbj ，則從結(jié)點(diǎn)ai向結(jié)點(diǎn)bj畫有向邊，箭頭指向bj，若aiRbj

51、 , 則ai與bj之間沒有線段連接，這樣得到的圖稱為R的關(guān)系圖 GR 。P109 例題7693-5 關(guān)系及其表示關(guān)系及其表示abcGR2abcGR1v定義在集合A上的關(guān)系圖有所不同例如（上例）, A=a,b,c, R1=,R2=, 則關(guān)系圖如下：703-5 關(guān)系及其表示關(guān)系及其表示v關(guān)系矩陣、關(guān)系圖(討論)：當(dāng)A中元素標(biāo)定次序后, RAA的關(guān)系圖GR與R的序偶集合表達(dá)式可以唯一互相確定。R的序偶集合表達(dá)式，關(guān)系矩陣，關(guān)系圖三者均可以唯一互相確定。713-5 關(guān)系及其表示關(guān)系及其表示作業(yè)作業(yè)(3-5)(3-5)P109 (5) c) 給出關(guān)系圖和關(guān)系矩陣 723-6 關(guān)系的性質(zhì)（1）自反性(re

52、flexivity)（2）對稱性(symmetry)（3）傳遞性(transitivity)（4）反自反性( irreflexivity)（5）反對稱性( antisymmetry)733-6 關(guān)系的性質(zhì)v需要指出：需要指出：從X到Y(jié)的關(guān)系R是XY 的子集，即RXY，而XY （XY）（XY）所以 R （XY）（XY）令Z= XY，則RZZ因此，我們今后通常限于討論同一集合上的關(guān)系。743-6 關(guān)系的性質(zhì)v 定義（自反性定義（自反性reflexivity）：）：設(shè)R為定義在A上的二元關(guān)系，即RAA, 如果對于每一個(gè)xA，有xRx (R)，則稱二元關(guān)系R是自反的。 R在A上是自反的 (x)( xA

53、 xRx)753-6 關(guān)系的性質(zhì)v定理：定理： R是自反的 IA R MR主對角線上的元素全為1 GR的每個(gè)頂點(diǎn)處均有自環(huán)。 自反性自反性(舉例舉例)： 平面上三角形的全等關(guān)系， 實(shí)數(shù)集中實(shí)數(shù)的小于等于關(guān)系， 冪集上的集合的相等、包含關(guān)系， 命題集合上的命題的等價(jià)、蘊(yùn)含關(guān)系。763-6 關(guān)系的性質(zhì)v 定義（對稱性定義（對稱性symmetry）：）：設(shè)RAA, 如果對于每個(gè)x,yA,每當(dāng) xRy，就有 yRx，則稱集合A上的關(guān)系R是對稱的。R在A上對稱 (x)(y)(xAyA xRyyRx).773-6 關(guān)系的性質(zhì)v 定理： R是對稱的 MR是對稱的 GR的任何兩個(gè)頂點(diǎn)之間若有邊, 則必有兩條方

54、向相反的有向邊。 v 對稱性(舉例)：平面上三角形的相似關(guān)系，人群中人之間的同學(xué)、同事、鄰居關(guān)系，冪集中集合相等的關(guān)系。命題集合上的命題的等價(jià)關(guān)系。783-6 關(guān)系的性質(zhì)v 定義（傳遞性定義（傳遞性transitivity）：）：設(shè)RAA, 如果對于任意的x,y,zA, 每當(dāng)xRy， yRz 時(shí)就有xRz ，稱關(guān)系R在A上是傳遞的。R在A上是傳遞的 (x)(y)(z)(xAyAzAxRy yRz xRz)793-6 關(guān)系的性質(zhì)v定理：定理：R是傳遞的 在GR中, xi xj xk(ijk), 若有有向 邊和, 則必有 。v傳遞性傳遞性( (舉例舉例) )： 實(shí)數(shù)集中的實(shí)數(shù)之間的小于等于、小于、

55、等于關(guān)系 冪集上的集合之間的包含、真包含關(guān)系; 命題集合上的命題的等價(jià)、蘊(yùn)含關(guān)系。 人群中人之間的同姓關(guān)系。803-6 關(guān)系的性質(zhì)v定義（反自反性定義（反自反性irreflexivity）：）：設(shè)RAA, 如果對于每一個(gè)xA，R，則稱二元關(guān)系R是反自反的。R在A上是反自反的 (x)(xA R )。813-6 關(guān)系的性質(zhì)v定理： R是反自反的 IAR= MR主對角線上的元素全為0 GR的每個(gè)頂點(diǎn)處均無自回路（無環(huán)）v反自反性(舉例)：數(shù)的大于關(guān)系，冪集上的集合之間的真包含關(guān)系。v注意：非自反不一定是反自反的。即存在有關(guān)系既不是自反的也不是反自反的。823-6 關(guān)系的性質(zhì)v定義（反對稱性定義（反對

56、稱性antisymmetry）：）：設(shè)RAA,如果對于每個(gè)x,yA,每當(dāng) xRy和yRx，必有x=y，則稱集合A上的關(guān)系R是反對稱的。 R是反對稱的 (x)(y)(xAyA xRy yRx x=y ) 833-6 關(guān)系的性質(zhì)v 定理：R是反對稱的 在MR中, xi xj( ij rij=1rji=0)在GR中, xi xj (ij), 若有有向邊 , 則必沒有。843-6 關(guān)系的性質(zhì)v反對稱性反對稱性(舉例舉例)： 實(shí)數(shù)集中的小于等于關(guān)系、整數(shù)的整除關(guān)系，集合的包含關(guān)系、命題的蘊(yùn)含關(guān)系。 注意：注意：非對稱不一定反對稱；可能有某種關(guān)系即是對稱的又是反對稱的。 例如：A=1,2,3, S=, S

57、在A上即是對稱的又是反對稱的。 N=, N在A上即不是對稱的又不是反對稱的。853-6 關(guān)系的性質(zhì)v例：判斷以下關(guān)系所具有的性質(zhì)。 A=a,b,c R1=, R2=, R3=, R4=, R5=, R6=, R7 =863-6 關(guān)系的性質(zhì)v解答：解答：R1=,反對稱,傳遞R2=,反對稱R3=, 自反,對稱,傳遞R4=,對稱R5=, 自反,反對稱,傳遞R6=,R7= （空關(guān)系）反自反，對稱，傳遞，反對稱. 87作業(yè)作業(yè)(3-6) P113 （3） 883-7 復(fù)合關(guān)系和逆關(guān)系v 定義 復(fù)合 (合成)(composite)關(guān)系: 設(shè)R為X到Y(jié)的關(guān)系，S為從Y到Z上的關(guān)系， 則 RS稱為R和S的復(fù)合

58、關(guān)系，表示為：RS= |xXzZ(y)(yYRS).893-7 復(fù)合關(guān)系和逆關(guān)系 例: X=1,2,3,4,5，X上的二元關(guān)系R和S定義如下： R=1,2,3,4,2,2,S=4,2,2,5,3,1,1,3試求R S，S R，R (S R)，(R S) R，R R，S S，R R R R S=1,5,3,2,2,5 S R=4,2,3,2,1,4 (R S) R=3,2 R (S R)=3,2 R R=1,2,2,2 S S=4,5,3,3,1,1 R R R =1,2,2,2 903-7 復(fù)合關(guān)系和逆關(guān)系v 由復(fù)合關(guān)系滿足結(jié)合律，可以把關(guān)系R本身所組成的復(fù)合關(guān)系寫成：RR，RRR， RRR(

59、m個(gè))，分別記作 R(2)，R(3)，R(m)。91 設(shè)設(shè)X= x1,x2,xm ，Y= y1,y2,yn ， Z= z1,z2,zP R XY，S YZ，R S XZ MR=m n i=1,m，j=1,n MS=n p i=1,n，j=1,p MR S=m p i=1,m，j=1, p ijuRRyyxxujjiiij,01 ijvSSzzyyvjjiiij,01ijwSSRRzzxxwjjiiij,013-7 復(fù)合關(guān)系和逆關(guān)系923-7 復(fù)合關(guān)系和逆關(guān)系用矩陣符號記為： MR S=MR MS， 其中，i=1,m，j =1,p 矩陣運(yùn)算“ ”叫做關(guān)系矩陣MR和MS的布爾乘法。 )(1kjik

60、nkijvuw 關(guān)系矩陣的布爾乘法公式與線性代數(shù)中的矩陣乘法公式相比發(fā)現(xiàn)，只要把矩陣乘法公式中的數(shù)乘改為合取，把數(shù)加改為析取，就得到了關(guān)系矩陣的布爾乘法公式。93 例:A=1,2,3,4,5，A上的二元關(guān)系R和S定義如下： R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2試求MR S和MS R ，它們是否相等 ? MR= MS=000000000001000000100001000000000100000110000001003-7 復(fù)合關(guān)系和逆關(guān)系940000000000010000001000010000000001000001100000010000000000000001