第三章集合與關系

1、第三章第三章 集合與關系集合與關系 SetsSets andand RelationsRelations3.1 集合集合3.2 關系及相關的概念關系及相關的概念3.3 關系的運算關系的運算3.4 關系的性質關系的性質3.5 關系的閉包關系的閉包3.6 等價關系與集合的劃分等價關系與集合的劃分3.7 序關系序關系4/30/2022 12:09 PMchapter323.1 集合集合 1、集合、集合 把具有共同性質的一些東西，匯集成一個整體，就形把具有共同性質的一些東西，匯集成一個整體，就形成一個集合。成一個集合。 由確定的相互區(qū)別的一些對象組成的整體稱為集合。由確定的相互區(qū)別的一些對象組成的整體

2、稱為集合。 可確定的可分辨的事物構成的整體?？纱_定的可分辨的事物構成的整體。3.1.1 集合的基本概念集合的基本概念4/30/2022 12:09 PMchapter333.1 集合集合 集合通常用大寫英文字母集合通常用大寫英文字母A，B，C，標記。標記。例如，例如，N代表自然數集合（包括代表自然數集合（包括0），），Z代表整數集合，代表整數集合，Q代表有理數集合，代表有理數集合，R代表實數集合，代表實數集合，C代表復數集合。代表復數集合。3.1.1 集合的基本概念集合的基本概念4/30/2022 12:09 PMchapter343.1 集合集合 2 2、元素、元素 組成集合的每個事物叫做這

3、個集合的元素，通常用組成集合的每個事物叫做這個集合的元素，通常用小寫字母小寫字母a a，b b，c c，標記。標記。 如果如果a a是集合是集合A A的一個元素，則記為的一個元素，則記為aAaA，讀做，讀做“a a屬屬于于A A”，或說或說“a a在在A A中中” 。 如果如果a a不是集合不是集合A A的一個元素，則記為的一個元素，則記為a a A A，讀做，讀做“a a不屬于不屬于A A”，或說或說“a a不在不在A A中中” 。3.1.1 集合的基本概念集合的基本概念4/30/2022 12:09 PMchapter353.1 集合集合 任一元素，對某一集合而言，或屬于該集合，或不任一元

4、素，對某一集合而言，或屬于該集合，或不屬于該集合，二者必居其一，不可兼得。屬于該集合，二者必居其一，不可兼得。 含有有限個元素的集合為有限集合有限集合。稱不是有限集合的集合為無限集合無限集合或無窮集無窮集。有限集合的元素個數稱為該集合的基數基數。集合A的基數記為|A|。例如，例如，若若 A=a, bA=a, b，則，則 |A|=2|A|=2，又，又|A|=1A|=1 。3.1.1 集合的基本概念集合的基本概念4/30/2022 12:09 PMchapter363.1 集合集合 1 1、列舉法列舉法 把集合中的元素一一列舉出來。把集合中的元素一一列舉出來。例如，例如，A=1, 2, 3, 4

5、在能清楚表示集合成員的情況下可使用省略號。在能清楚表示集合成員的情況下可使用省略號。例如，從例如，從1 到到50 的整數集的整數集合可記為合可記為1, 2, 3, , 50，偶數集合可記為偶數集合可記為,-4,-2,0,2,4,。 3.1.2 集合的表示集合的表示4/30/2022 12:09 PMchapter373.1 集合集合 2 2、描述法描述法 B=x|P(x) ，P(x) 是謂詞，概括集合中元素屬性。是謂詞，概括集合中元素屬性。 B=x|P(x)表示表示xS當且僅當當且僅當P(x)是真。是真。例如，例如，B=x|xZ3X6，即，即B=4，5，6。3、文氏圖法、文氏圖法 用一個大的矩

6、形表示全集，在矩形內畫一些圓或其它用一個大的矩形表示全集，在矩形內畫一些圓或其它的幾何圖形，來表示集合，有時也用一些點來表示集合中的幾何圖形，來表示集合，有時也用一些點來表示集合中的特定元素。的特定元素。3.1.2 集合的表示集合的表示4/30/2022 12:09 PMchapter383.1 集合集合 定義定義3-1.1 3-1.1 設設A和和B是集合，是集合，若集合集合A中的每個元素都是中的每個元素都是集合集合B中的元素，則稱中的元素，則稱A是是B的子集，也可以說的子集，也可以說A包含于包含于B，或者，或者B包含包含A，這種關系寫作，這種關系寫作A AB B或或B B A A。 A AB

7、 B x(x(x A Ax x B)B) 如果如果A不是不是B的子集，即在的子集，即在A中至少有一個元素不屬中至少有一個元素不屬于于B，稱，稱B不包含不包含A，記作，記作B B A A或或A A B B。 3.1.3 集合之間的關系集合之間的關系4/30/2022 12:09 PMchapter393.1 集合集合 定義定義3.1-2 3.1-2 若兩個集合若兩個集合A A和和B B的元素完全相同，則稱這兩的元素完全相同，則稱這兩個集合相等，記作個集合相等，記作A=BA=B。例如，例如，A=A=1,2,3,41,2,3,4 B=B=3,1,4,23,1,4,2 顯然有顯然有A AB B。定理定

8、理3.1-1 3.1-1 集合集合A和集合和集合B相等的充分必要條件是相等的充分必要條件是A B且且B A。 A=B A=B A BB A3.1.3 集合之間的關系集合之間的關系4/30/2022 12:09 PMchapter3103.1 集合集合 定義定義3.1-33.1-3 如果如果A B且且AB，也就是說在也就是說在B B中至少有一中至少有一個元素不屬于個元素不屬于A A，則稱，則稱A A是是B B的真子集，的真子集，記作記作A B 。 A A B B x(x(x A Ax x B)B) x(x x B Bx x A)A)例如，集合例如，集合A=A=1 1，2 2，B=B=1 1，2

9、2，3 3則則A A是是B B的真子集。的真子集。3.1.3 集合之間的關系集合之間的關系4/30/2022 12:09 PMchapter3113.1 集合集合 定義定義3.1-43.1-4 A A是有限集，由是有限集，由A A的所有子集作為元素而構成的所有子集作為元素而構成的集合稱為的集合稱為A A的冪集，記作的冪集，記作(A)(A)。即。即(A)=(A)=X|XX|X A A。在在A A的所有子集中，的所有子集中，A A和和這兩個子集又叫平凡子集。這兩個子集又叫平凡子集。例如：例如：A=A=1 1，2 2，3 3，則，則(A)=(A)=,1,2,3,1,2,1,3,2,3,1,2,3,1

10、,2,3,1,2,1,3,2,3,1,2,3 A A B B x(x(x A Ax x B)B) x(x Bx x A)A)定理定理3.1-2 3.1-2 設設A A是有限集，是有限集，| |A|=nA|=n，則，則A A的冪集的冪集(A)(A)的基的基為為2 2n n。3.1.3 集合之間的關系集合之間的關系4/30/2022 12:09 PMchapter3123.1 集合集合 【例【例1】設】設A=,B=, , , ,求求(A)和和(B)。解：解：(A)=, , , , (B)= , , , , , , , , , , , , , , , 3.1.3 集合之間的關系集合之間的關系4/30

11、/2022 12:09 PMchapter3133.1 集合集合 1、集合的并、集合的并 定義定義3.1-53.1-5 設設A A，B B是兩個集合，所有屬于是兩個集合，所有屬于A A或者屬于或者屬于B B的的元素組成的集合，稱為元素組成的集合，稱為A A和和B B的并集，記作的并集，記作ABAB。 ABABx|xAxBx|xAxB3.1.4 集合的運算集合的運算UAB4/30/2022 12:09 PMchapter3143.1 集合集合 2、集合的交、集合的交 定義定義3.1-63.1-6 設設A A，B B是兩個集合，由屬于是兩個集合，由屬于A A且屬于且屬于B B的元素的元素組成的集合

12、，稱為組成的集合，稱為A A和和B B的交集，記作的交集，記作ABAB。 AB=AB=x|xAxBx|xAxB3.1.4 集合的運算集合的運算UAB4/30/2022 12:09 PMchapter3153.1 集合集合 3、集合的差、集合的差 定義定義3.1-73.1-7 設設A A、B B是兩個集合，由屬于集合是兩個集合，由屬于集合A A而不屬于集而不屬于集合合B B的所有元素組成的集合，稱為的所有元素組成的集合，稱為A A與與B B的差集，記作的差集，記作A-B A-B 。 A-B=A-B=x|xAxx|xAx B B 3.1.4 集合的運算集合的運算4/30/2022 12:09 PM

13、chapter3163.1 集合集合 3.1.4 集合的運算集合的運算4、集合的補、集合的補 定義定義3.1-83.1-8 設設A A是一個集合，全集是一個集合，全集E E與與A A的差集稱為的差集稱為A A的余集的余集或補集，記作或補集，記作A A。即。即A=E-AA=E-A。EE 特別地，特別地， ，4/30/2022 12:09 PMchapter3173.1 集合集合 【例【例2】設設A=aA=a，b b，c c，dd，B=cB=c，d d，e e，ff，那么，那么AB=aAB=a，b b，c c，d d，e e，ff；AB=cAB=c，dd；A-B=aA-B=a，bb；B-A=eB-

14、A=e，ff。3.1.4 集合的運算集合的運算4/30/2022 12:09 PMchapter3183.1 集合集合 5、常用的集合運算定律、常用的集合運算定律(1)等冪律：等冪律： AA=A，AA=A。(2)交換律：交換律： AB=BA，AB=BA。(3)結合律：結合律： (AB)C=A(BC)， (AB)C=A(BC)。(4)分配律：分配律： A(BC)=(AB)(AC)，A(BC)=(AB)(AC)。(5)吸收律：吸收律： A(AB)=A，A(AB)=A3.1.4 集合的運算集合的運算4/30/2022 12:09 PMchapter3193.1 集合集合 3.1.4 集合的運算集合的

15、運算(6)互補律：互補律： (7)摩根律：摩根律：(8)同一律：同一律： EA=A， A=A。(9)零一律：零一律： A= ，EA=E。(10)雙重否定律：雙重否定律：B BA AB B) )( (A A E EA AA A, ,A AA A BABA)(AA 4/30/2022 12:09 PMchapter3203.1 集合集合 定理定理3.1-3 3.1-3 設設A A、B B為有限集合，為有限集合，| |A|A|、|B|B|為其基數，則為其基數，則| |A AB|B|A|+|B|A|+|B|- -|A|AB|B| 這個結論稱作包含排斥原理。這個結論稱作包含排斥原理。推廣：推廣：設設A1

16、, A2, ，An是有限集合，其元素的基數分別為是有限集合，其元素的基數分別為|A1|, |A2|, ，|An|， 則則3.1.5 包含排斥原理包含排斥原理| |A AA AA A| |1 1) )( (| |A AA AA A| | |A AA A| | |A A| | |A AA AA A| |n n2 21 11 1n nk kj ji in nk kj ji i1 1n n1 1i in nj ji i1 1j ji ii in n2 21 1 4/30/2022 12:09 PMchapter3213.1 集合集合 【例【例3】 在一個班級在一個班級5050個學生中個學生中, , 有

17、有 26 26 人在第一次考試人在第一次考試中得到中得到A A，2121人在第二次考試中得到人在第二次考試中得到A A，假如有，假如有1717人兩次考人兩次考試都沒有得到試都沒有得到A, A, 問有多少學生在兩次考試中都得到問有多少學生在兩次考試中都得到A? A? 解：設第一次得解：設第一次得A A的是集合的是集合A A1 1, , 第二次得第二次得A A的是集合的是集合A A2 2。則則 根據題設有根據題設有 | |A A1 1|=26|=26， | |A A2 2|=21|=21， | |A A1 1A A2 2|=50|=50- -17=3317=33 | |A A1 1A A2 2|=

18、|=|A A1 1|+|+|A A2 2| |- -| |A A1 1A A2 2| | | |A A1 1A A2 2| | =|=|A A1 1|+|+|A A2 2| |- -| |A A1 1A A2 2| |=26+21-33=14 =26+21-33=14 所以有所以有1414個人兩項均得個人兩項均得A A。3.1.5 包含排斥原理包含排斥原理4/30/2022 12:09 PMchapter3223.1 集合集合 【例【例4】某教研室有某教研室有3030名老師名老師, , 可供他們選修的第二外語可供他們選修的第二外語是日語、是日語、 法語、德語。已知有法語、德語。已知有 15 1

19、5 人進修日語人進修日語, 8 , 8 人選人選修法語修法語, 6 , 6 人選修德語人選修德語, , 而且其中而且其中 3 3 人選修三門外語人選修三門外語, , 我們希望知道至少有多少人一門也沒有選修。我們希望知道至少有多少人一門也沒有選修。解：設解：設A1、A2、A3分別表示選修日語、法語和德語的人。分別表示選修日語、法語和德語的人。因此因此 | |A A1 1|=15|=15，| |A A2 2|=8|=8，| |A A3 3|=6|=6， | |A A1 1A A2 2A A3 3 |=3|=3| |A A1 1A A2 2A A2 2|=15+8+6|=15+8+6- -| |A

20、A1 1A A2 2|-|-|A A1 1A A3 3|-|-|A A2 2A A3 3|+3|+3 =32-| =32-|A A1 1A A2 2|-|-|A A1 1A A3 3|-|-|A A2 2A A3 3| |3.1.5 包含排斥原理包含排斥原理4/30/2022 12:09 PMchapter3233.1 集合集合 | |A A1 1A A2 2|A A1 1A A2 2A A3 3| | | |A A1 1A A3 3|A A1 1A A2 2A A3 3| | | |A A2 2A A3 3|A A1 1A A2 2A A3 3| | | |A A1 1A A2 2A A2

21、2|32-3-3-3=23|32-3-3-3=23 即至少有即至少有7 7人一門都沒有選修。人一門都沒有選修。3.1.5 包含排斥原理包含排斥原理4/30/2022 12:09 PMchapter3243.2 關系及相關的概念關系及相關的概念 3.2.1 序對序對定義定義3-2.1 由兩個元素由兩個元素x和和y按一定的順序排列成的二元按一定的順序排列成的二元組叫做一個組叫做一個序對序對(也稱也稱序偶序偶)，記作，記作。其中。其中x是它的第一元素，是它的第一元素，y是它的第二元素。是它的第二元素。例如，平面直角坐標系中點的坐標例如，平面直角坐標系中點的坐標(x, y)就是序偶，就是序偶，而全體這

22、種實數對的集合而全體這種實數對的集合(x, y)|xRyR就表就表示整個平面。示整個平面。4/30/2022 12:09 PMchapter3253.2 關系及相關的概念關系及相關的概念 序對的特點：序對的特點：(1) 一般若一般若a b，則，則 。 (2) 組成序偶的元素組成序偶的元素a和和b可來自相同或不同的集合?？蓙碜韵嗤虿煌募稀?例如，例如， a：操作碼：操作碼 b：地址：地址 ：單地址指令：單地址指令(3) 若干個序偶可以構成一個集合。若干個序偶可以構成一個集合。(以序偶為元素的集合以序偶為元素的集合)(4) 兩序偶兩序偶，是相等的，當且僅當是相等的，當且僅當a=c，b=d；記

23、作；記作=。3.2.1 序對序對4/30/2022 12:09 PMchapter326 序偶的概念可以進一步推廣到有序序偶的概念可以進一步推廣到有序n元組的情況。元組的情況。定義定義3-2.2 一個一個有序有序n元組元組(n3)是一個有序對，其中第一是一個有序對，其中第一個元素是一個有序個元素是一個有序n-1元組，一個有序元組，一個有序n元組記作元組記作，即，即 , xn。 其中其中ai(i1,2,n)叫做有序叫做有序n元組的第元組的第i個坐標。個坐標。 兩個有序兩個有序n元組元組和和相等相等,當且當且僅當僅當aibi(i1,2,n)。記為。記為。3.2 關系及相關的概念關系及相關的概念 3

24、.2.1 序對序對4/30/2022 12:09 PMchapter327定義定義3-2.3 設設A和和B是兩個集合，則由是兩個集合，則由A中元素作為第中元素作為第1個個坐標坐標,B中元素作為第個坐標而構成的所有序偶的集合中元素作為第個坐標而構成的所有序偶的集合叫做叫做A和和B的的笛卡兒積笛卡兒積,記為記為AB,讀作讀作“A叉乘叉乘B”。即。即 AB|aAbB 兩個集合的笛卡兒積是一個特殊的集合，其元素是兩個集合的笛卡兒積是一個特殊的集合，其元素是序偶。當序偶。當A=B時，時，AB簡記為簡記為A2。3.2 關系及相關的概念關系及相關的概念 3.2.2 笛卡兒積（叉積）笛卡兒積（叉積）4/30/

25、2022 12:09 PMchapter328【例【例1】已知】已知A=1,2,3，B=a,b，求，求AB，BA，A2，B2。解：解：AB=, BA=, A2=, , B2=, 當當AB時，時，ABBA。3.2 關系及相關的概念關系及相關的概念 3.2.2 笛卡兒積（叉積）笛卡兒積（叉積）4/30/2022 12:09 PMchapter329n階笛卡兒積階笛卡兒積若若nN，且，且n1， A1, A2, , An是是n 個個集合，集合， 它們的它們的n 階笛卡兒積階笛卡兒積記作記作A1A2An , 并定并定義為義為:A1A2An=x1, x2, , xn|x1A1x2A2, , xnAn3.2

26、 關系及相關的概念關系及相關的概念 3.2.2 笛卡兒積（叉積）笛卡兒積（叉積）4/30/2022 12:09 PMchapter330定理定理3-2.1 若若A,B是兩個有限集合是兩個有限集合,則則|AB|A|B|。如在例如在例1中，中，|A|3，|B|2,故故 |AB|326 |BA|236 |A2|339 |B2|224推論：推論：對任意有限集合對任意有限集合A1， A2, ， An， 有有 |A1A2An|A1| |An|3.2 關系及相關的概念關系及相關的概念3.2.2 笛卡兒積（叉積）笛卡兒積（叉積）4/30/2022 12:09 PMchapter331【例【例2】(1)A=a，

27、b，B=c，d，求，求AB。 (2)A=a，b，B=c，d，求，求BA。 (3)A=a，b，B=1，2，C=c，求，求(AB)C和和A(BC)。解解:(1):(1)A AB=a,bB=a,bc,d=,c,d=, (2) B (2) BA=c,dA=c,da,b=,a,b=,3.2 關系及相關的概念關系及相關的概念3.2.2 笛卡兒積（叉積）笛卡兒積（叉積）4/30/2022 12:09 PMchapter332(3)(3)(A AB)=a,bB)=a,b1,2=,1,2=,(A(AB)B)C=,c,cC=,c,c，,c,c,c,c =, =,B BC=1,2C=1,2c=,c=,A A(B(B

28、C)=a,a,b,b,C)=a,a,b,b,3.2 關系及相關的概念關系及相關的概念3.2.2 笛卡兒積（叉積）笛卡兒積（叉積）4/30/2022 12:09 PMchapter333 二元關系是在集合中兩個元素之間的某種相關性。二元關系是在集合中兩個元素之間的某種相關性。例如，甲、乙、丙三人進行乒乓球比賽，若任兩人之間都例如，甲、乙、丙三人進行乒乓球比賽，若任兩人之間都要賽一場，則共要賽三場。假設三場比賽的結果是乙勝甲、要賽一場，則共要賽三場。假設三場比賽的結果是乙勝甲、甲勝丙、乙勝丙，結果可記作甲勝丙、乙勝丙，結果可記作,其中其中表示表示x勝勝y。它表示了集合。它表示了集合甲甲,乙乙,丙丙

29、中元素之間中元素之間的一種勝負關系。的一種勝負關系。定義定義3-2.3 設設A，B是兩個集合，是兩個集合，R是笛卡兒積是笛卡兒積AB的任的任一子集，則稱一子集，則稱R為從為從A到到B的一個的一個二元關系二元關系，簡稱，簡稱關系關系。特。特別地，若別地，若A=B，則稱，則稱R為為A上的一個關系。上的一個關系。3.2 關系及相關的概念關系及相關的概念3.2.3 關系關系4/30/2022 12:09 PMchapter334關系的特點：關系的特點：(1) A到到B的關系的關系R是一個集合。是一個集合。R AB |A|=n， |B|=m， |AB|=nm， |(AB)|=2 nm 即從即從A到到B一

30、共有一共有2 nm個關系。個關系。3.2 關系及相關的概念關系及相關的概念3.2.3 關系關系3) 3) 三種特殊的關系：三種特殊的關系：，空關系；，空關系； A AB B，全關系；，全關系； I IA A|a|aA ，A A上的恒等關系。上的恒等關系。(2) 若若RR，則稱，則稱x x和和y y滿足關系滿足關系R R，可記為，可記為xRyxRy。 若若 R R，則稱，則稱x x和和y y不滿足關系不滿足關系R R，可記為，可記為 。4/30/2022 12:09 PMchapter335 【例【例3】設】設A=1，2，3，4，則，則A上的上的“”關系關系R為：為：解：解：R=, 【例【例4】

31、設】設A=2,3,4，B=2,3,4,5,6，定義，定義A到到B的關系的關系R為為aRb當且僅當當且僅當a|b （a整除整除b） 。解解:R=, 【 例【 例 5 】 設】 設 A = 1 , 2 , 3 , 4 ， A 上 的 關 系上 的 關 系 R 定 義 為定 義 為R=|a,bA，(a-b)/2=k，k為整數為整數 。解解:R=, ,3.2 關系及相關的概念關系及相關的概念3.2.3 關系關系4/30/2022 12:09 PMchapter336 【例【例6】設】設Aa，b，R是是(A)(A)上的包含關系，上的包含關系， R|x，y(A)(A)x y。解：解：(A)(A)=，a，b

32、，A。 R=， ，。3.2 關系及相關的概念關系及相關的概念3.2.3 關系關系4/30/2022 12:09 PMchapter337定義域定義域設設R是二元關系，由是二元關系，由 R的所有的所有x組成組成的集合稱為的集合稱為R的的定義域定義域，記作，記作domR，即，即 domR=x| y(y B R)。值域值域由由 R的所有的所有y組成的集合稱為組成的集合稱為R的的值域值域，記作記作ranR，即，即ranR=y| x(xAR)。域域R的前域和值域一起稱作的前域和值域一起稱作R的的域域，記作，記作FLD R，即，即 FLD R=domRranR。3.2 關系及相關的概念關系及相關的概念3.

33、2.3 關系關系4/30/2022 12:09 PMchapter338【例【例7】設】設A=a，b，c，d，e，B=1，2，3，R=，求，求R的定義域和值域。的定義域和值域。解：解：domR=a，b，c， ranR=2，3?！纠纠?】設】設A=1,3,5,7，R是是A上的二元關系，當上的二元關系，當a,b A且且ab時，時， R，求，求R和它的定義域和值域。和它的定義域和值域。解：解：R=， domR =1，3，5， ranR =3，5，7。3.2 關系及相關的概念關系及相關的概念3.2.3 關系關系4/30/2022 12:09 PMchapter339 令令X X和和Y Y是任意兩個集

34、合，直積是任意兩個集合，直積X XY Y的子集的子集R R稱作稱作X X到到Y Y的關系。的關系。 X X到到Y Y的關系的關系R R，可以由下圖表示：，可以由下圖表示：x1x2x6x7x3x4x5y1y2y3y3y5y6domRranR3.2 關系及相關的概念關系及相關的概念3.2.3 關系關系4/30/2022 12:09 PMchapter3401、集合表示法。如列舉法、描述法等。、集合表示法。如列舉法、描述法等。2、關系矩陣、關系矩陣3.2 關系及相關的概念關系及相關的概念3.2.4 關系的表示關系的表示 0 R mij= 1 R4/30/2022 12:09 PMchapter341

35、【例【例9 9】設】設A=1,2,3,4A=1,2,3,4，R R A AA A， R=, , , R=, , , 。解：解： 0 0 0 1 0 0 1 0 MR= 1 0 0 1 0 0 0 13.2 關系及相關的概念關系及相關的概念3.2.4 關系的表示關系的表示4/30/2022 12:09 PMchapter3423、關系圖、關系圖 若若RR，則，則可畫為可畫為a b。則上例則上例R R的關系圖：的關系圖：1234123414233.2 關系及相關的概念關系及相關的概念3.2.4 關系的表示關系的表示4/30/2022 12:09 PMchapter343【例【例10】 求集合求集合

36、A=1 , 2 , 3 , 4 上的恒等關系、空關系、上的恒等關系、空關系、全關系和小于關系的關系圖。全關系和小于關系的關系圖。 解：恒等關系解：恒等關系 IA = ， 空關系空關系 = 全關系全關系AA=, , , 小于關系小于關系LA=, , , ,3.2 關系及相關的概念關系及相關的概念3.2.4 關系的表示關系的表示4/30/2022 12:09 PMchapter34412341234134212343.2 關系及相關的概念關系及相關的概念3.2.4 關系的表示關系的表示4/30/2022 12:09 PMchapter3453.3 關系的運算關系的運算 設設R,S AB ，a A，

37、b B，則：，則： RS| R S RS| R S R - S | R S RAB - R| R3.3.1 關系的并、交、補、差關系的并、交、補、差 4/30/2022 12:09 PMchapter3463.3 關系的運算關系的運算 定義定義3-3.1 設設R AB，則，則R的的逆關系逆關系 R-1= R 即將即將R中每序偶的第一元素和第二元素的順序互換，中每序偶的第一元素和第二元素的順序互換，所得到的集合稱為所得到的集合稱為R的逆關系，記為的逆關系，記為R-1。(1)若設若設R AB，則，則R-1 BA， R AB。(2)若若R的關系矩陣為的關系矩陣為M(R) ，則，則M(R-1)= M(

38、R)T (轉置轉置)3.3.2 關系的逆運算關系的逆運算 (3)若若R的關系圖中有的關系圖中有a b，則，則R-1 為為a b。4/30/2022 12:09 PMchapter347例，整數集上的例，整數集上的“” ，而補關系是，而補關系是“”?！纠纠?】 A=1 , 2 , 3，B=a ,b , c， R, , 則則R-1, , R, , 0 1 0M(R)= 0 0 1 1 0 0 0 0 1M(R-1)= 1 0 0 0 1 0 3.3 關系的運算關系的運算 3.3.2 關系的逆運算關系的逆運算 4/30/2022 12:09 PMchapter348定理定理3-3.1 設設R,S,

39、T AB ，則下列各式成立：，則下列各式成立：(1) (R-1)-1=R(2) (RS)-1=R-1S-1(3) (RS) -1 =R -1 S -1(4) (R)-1 = (R -1 )（這里（這里R=AB-R） (5) (R-S) -1 =R-1 - S-1 (6) (AB) -1 =BA(7) -1 = 3.3 關系的運算關系的運算3.3.2 關系的逆運算關系的逆運算 4/30/2022 12:09 PMchapter349R: 弟兄關系弟兄關系 aRb：a是是b的弟弟的弟弟S: 父子關系父子關系 bSc：b是是c的父親的父親T:叔侄關系叔侄關系 aTc：a是是c的叔叔的叔叔T：由：由R

40、和和S合成而成的關系。表示為合成而成的關系。表示為T=R S。定義定義3-3.2 設設R AB ， S BC，則，則R S稱為稱為R和和S的復的復合關系，表示為合關系，表示為R S= xAzC y(yBRS) R S 的前域是的前域是R的前域，后域是的前域，后域是S的后域。的后域。 而而R的后域應是的后域應是S 的前域才能進行合成的前域才能進行合成條件條件3.3 關系的運算關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter350【例【例2】A=1,2,3,4，B=3,5,7，C=1,2,3，R=,，S=,，R S=,。3.3 關系的運算關系的

41、運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter351【例【例3】A=1,2,3，B=a,b,c，C=x,y,z，R=， ABS=， BCR S=，RS123abcABCRSxyz3.3 關系的運算關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter352【例【例4】A=a,b,c,d R=， A2S=， A2R S=， A2S R= A2R R=， A2S S=， A2一般地，若一般地，若RS，則，則R S S R。3.3 關系的運算關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/

42、2022 12:09 PMchapter353合成關系的關系矩陣合成關系的關系矩陣定理定理3-3.2 設設R AB，S BC，其中，其中A=aA=a1 1,a,a2 2, ,a,am m ，B=bB=b1 1,b,b2 2, ,b,bn n ，C=cC=c1 1,c,c2 2, ,c,ct t 。而。而M MR R，M MS S和和M MR R S S分別分別為關系為關系R R，S S和和R R S S的關系矩陣，則有的關系矩陣，則有M MR R S S=M=MR RM MS S。定理定理3-3.3 設設R AB ，S BC，T CD ,則則 R (S T)=(R S) T。3.3 關系的運算

43、關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter354分析：集合相等分析：集合相等證明互為子集。證明互為子集。 S R， a S S，有，有a R R。 R R S， a R R，有，有a S S。證明：證明： a,d (R S) T， 則則c C C ，有，有 a,c R S ， c,d T a,c R S ， b B B ，有，有 a,b R， b,c S 則有則有 b,d S S T T，由，由 a,b R， 則則 a,d R R (S(S T)T)。 即即 ( (R R S)S) T T R R (S(S T) T) 。 同理，同理

44、， a,d R R (S(S T) T) a,d (R S) T R R (S(S T) T) = (R S) T3.3 關系的運算關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter355定理定理3-3.4 設設R AB ，S1,S2 BC，則有，則有(1) R (S1S2)=(R S1)(R S2) (2) R (S1S2)=(R S1)(R S2)(3) (S1S2) R=(S1 R) (S2 R)(4) (S1S2) R=(S1 R)(S2 R)3.3 關系的運算關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 1

45、2:09 PMchapter356證證R R (S(S1 1SS2 2)=(R)=(R S S1 1)(R)(R S S2 2) ) 證明：證明： R R (S(S1 1SS2 2) ) b B B ( a,b R b,c S S1 1SS2 2) )b B B ( (a,b R ( b,c S S1 1 b,c S S2 2) )b B B ( ( a,b R b,c S S1 1)( a,b R b,c S S2 2) )( a,c R R S S1 1)( a,c R R S S2 2) ) a,c (R(R S S1 1)(R)(R S S2 2) ) 3.3 關系的運算關系的運算3.

46、3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter357定理定理3-3.5 設設R AB ，S BC，則，則(R S)-1=S-1 R-1證明：證明： c,a (R S)-1 a,c R S b B B ( a,b R Sb,cS ) )b B B ( b,a R-1 c,b S-1) ) c,a S-1 R-1 (R S)-1 = S-1 R-13.3 關系的運算關系的運算3.3.3 關系的復合運算關系的復合運算 4/30/2022 12:09 PMchapter358定義定義3-3.3 設設R為為A上的關系上的關系,n為自然數為自然數,則則R的的n次冪

47、次冪規(guī)規(guī)定如下：定如下：(1) R0=xA=IA；(2) Rn+1=Rn R，n0。定理定理3-3.6 設設R為為A上的關系上的關系,m,n是自然數是自然數,則下面的等則下面的等式成立：式成立：(1) Rn+m=Rn Rm；(2) (Rn)m=Rnm。3.3 關系的運算關系的運算3.3.4 集合上關系的乘冪集合上關系的乘冪 4/30/2022 12:09 PMchapter3593.3 關系的運算關系的運算3.3.4 集合上關系的乘冪集合上關系的乘冪 證明：任意給定證明：任意給定m，對，對n進行歸納。進行歸納。(1)n=0，Rm R0=Rm= Rm+0 。假設假設Rm Rn=Rm+n，則則Rm

48、 Rn+1= Rm (Rn R)=(Rm Rn) R= Rm+n R= Rm+n+1 。(2)n=0，(Rm)0=R0=Rm*0。假設假設(Rm)n=Rm*n，則則(Rm)n+1= (Rm)n Rm=Rmn Rm=Rmn+m=Rm(n+1)。由歸納法知由歸納法知(1)、(2)都成立。都成立。4/30/2022 12:09 PMchapter36022n定理定理3-3.7 設設R是集合是集合A上的關系，上的關系，|A|=n，則存在，則存在s、t，0s，t ，使，使Rs=Rt。證明：證明： 在在A A上可以定義上可以定義 個關系。個關系。而且而且mm N，Rm A AA A， 在在 R0, R1

49、, R2, R 一定有兩個是相同的，分別令為一定有兩個是相同的，分別令為Rs=Rt。22n22n3.3 關系的運算關系的運算3.3.4 集合上關系的乘冪集合上關系的乘冪 4/30/2022 12:09 PMchapter361【例【例5】設】設A= a , b , c , d ，R=,，求，求R0，R1，R2，R3，R4和和R5。解：下圖給出了解：下圖給出了R的各次冪：的各次冪：3.3 關系的運算關系的運算3.3.4 集合上關系的乘冪集合上關系的乘冪 abcdR0abcdR1abcdR2 =R4abcdR3 = R54/30/2022 12:09 PMchapter3623.4 關系的性質關系

50、的性質 定義定義3-4.1 設設R R是集合是集合A A上的二元關系，如果對于每個上的二元關系，如果對于每個x x A A，都有都有 x R R，則稱二元關系，則稱二元關系R R是自反的。是自反的。 R在在A上是自反的上是自反的 x（xAR）定義定義3-4.2 設設R R是集合是集合A A上的二元關系，上的二元關系，如果對于每個如果對于每個x A，都有都有 R，則稱二元關系，則稱二元關系R是反自反的。是反自反的。R在在A上是反自反的上是反自反的 x x（xxA R）3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter3633.4 關系的性質關系的性質 定義定義3

51、-4.3 設設R R是集合是集合A A上的二元關系，如果對于每個上的二元關系，如果對于每個x x，yAyA，當，當xRyR，就有，就有yRxR，則稱二元關系，則稱二元關系R R是是對稱的。對稱的。R R在在A A上是對稱的上是對稱的 x x y(xAyAxy(xAyARyRyR) xR) 3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter3643.4 關系的性質關系的性質 定義定義3-4.4 設設R R是集合是集合A A上的二元關系，如果對于每個上的二元關系，如果對于每個x x，yAyA，當，當xRyR和和yRxR時，必有時，必有x=yx=y，則稱二元，則稱二

52、元關系關系R R是反對稱的。是反對稱的。R R是反對稱的是反對稱的 x x y(xAyARRx=y)y(xAyARRx=y)或或 x x y(xAyAxyy(xAyAxy RR R)R)3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter3653.4 關系的性質關系的性質 定義定義3-4.5 設設R R是集合是集合A A上的二元關系，如果對于任意上的二元關系，如果對于任意x x，y y，zAzA，當，當xRyR，yRzR，就有，就有xRzR，則稱二元關系則稱二元關系R R在在A A上是傳遞的。上是傳遞的。 R R在在A A上是傳遞的上是傳遞的x x y y z

53、z（xAyAzAxxAyAzARRRzRxRzR）3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter366【例【例1 1】整數集】整數集Z Z上的上的“”是是 自反的、反對稱的和傳遞的。自反的、反對稱的和傳遞的。 整數集整數集Z Z上的上的“”是是 反自反的、反對稱的和傳遞的。反自反的、反對稱的和傳遞的。 整數集整數集Z Z上的上的“=”=”是是 自反的、對稱的、反對稱的和傳遞的。自反的、對稱的、反對稱的和傳遞的。 整數集整數集Z Z上的上的“”是是 反自反的、對稱的。反自反的、對稱的。 若若A A是非空集合，是非空集合，A A的冪集的冪集(A)(A)上的上的

54、“ ”關系關系是是 自反的、反對稱的、傳遞的。自反的、反對稱的、傳遞的。3.4 關系的性質關系的性質3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter367【例【例2】設】設A=1,2,3,4，R是是A上的一個關系，上的一個關系，R=|a，bAA，(a-b)/2=k(a-b)/2=k，kZkZ，證明，證明R R是自反、對稱、傳遞的。是自反、對稱、傳遞的。證明證明： a aAA，(a-a)/2=k(a-a)/2=kZZ，RR a,ba,bAA，若，若 a,bRR，則，則( (a-b)/2=ka-b)/2=kZZ， (b-a)/2=-k (b-a)/2=-kZZ，

55、 RR。 a,b,ca,b,cAA，若，若 a,bRR且且 b,cRR ， 則則( (a-b)/2=ka-b)/2=k1 1ZZ， (b-c)/2=k(b-c)/2=k2 2ZZ (a-c)/2= k (a-c)/2= k1 1+k+k2 2ZZ， RR。3.4 關系的性質關系的性質3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter368【例【例3】設】設A=1,2,3，下列關系都是，下列關系都是A上的關系。上的關系。123R1R3123231R2123R4123R51 0 00 1 00 0 1 0 1 00 0 11 0 0 0 1 11 0 11 1 0

56、 0 0 00 0 00 0 0 1 1 11 1 11 1 1 3.4 關系的性質關系的性質3.4.1 關系的性質關系的性質 4/30/2022 12:09 PMchapter3691、關系的性質表現(xiàn)在關系圖中、關系的性質表現(xiàn)在關系圖中 自反自反每個點都有自反環(huán)。每個點都有自反環(huán)。反自反反自反每個點都沒有自反環(huán)。每個點都沒有自反環(huán)。對稱對稱不同結點間要么沒有邊，要么有一對邊。不同結點間要么沒有邊，要么有一對邊。反對稱反對稱不同結點間要么沒有邊，要么只有一條邊。不同結點間要么沒有邊，要么只有一條邊。3.4 關系的性質關系的性質3.4.2 關系性質的判定關系性質的判定4/30/2022 12:0

57、9 PMchapter3702、關系的性質表現(xiàn)在關系矩陣中、關系的性質表現(xiàn)在關系矩陣中 自反自反主對角線上的元素全為主對角線上的元素全為1。反自反反自反主對角線上的元素全為主對角線上的元素全為0。對稱對稱關于主對角線對稱的元素，都是關于主對角線對稱的元素，都是0或都是或都是1。反對稱反對稱關于主對角線對稱的元素，要么都是關于主對角線對稱的元素，要么都是0；要么；要么一個為一個為0，一個為，一個為1。3.4 關系的性質關系的性質3.4.2 關系性質的判定關系性質的判定4/30/2022 12:09 PMchapter3713、利用定理判斷關系的性質、利用定理判斷關系的性質定理定理3-4.1 設設

58、R R是是A A上的二元關系，則上的二元關系，則R R在在A A上是自反的當上是自反的當且僅當且僅當I IA A R R。 證明：先證必要性。證明：先證必要性。對對 IyIA A ，xIyIA Ax x，y y Ax=yAx=y由于由于R R在在A A上是自反的，可推出上是自反的，可推出x=RxR從而證明了從而證明了I IA A R R。再證充分性。任取再證充分性。任取x x A A，有，有xAxA x IxIA AxRxR因此，因此，R R在在A A上是自反的。上是自反的。 3.4 關系的性質關系的性質3.4.2 關系性質的判定關系性質的判定4/30/2022 12:09 PMchapter

59、372定理定理3-4.2 設設R R是是A A上的二元關系，則上的二元關系，則R R在在A A上是反自反的上是反自反的當且僅當當且僅當I IA AR=R=。定理定理3-4.3 設設R R是是A A上的二元關系，則上的二元關系，則R R在在A A上是對稱的當上是對稱的當且僅當且僅當R=RR=R11。定理定理3-4.4 設設R R是是A A上的二元關系，則上的二元關系，則R R在在A A上是反對稱的上是反對稱的當且僅當當且僅當RRRR11 I IA A。定理定理3-4.5 設設R R是是A A上的二元關系，則上的二元關系，則R R在在A A上是傳遞的當上是傳遞的當且僅當且僅當R R R R R R

60、。3.4 關系的性質關系的性質3.4.2 關系性質的判定關系性質的判定4/30/2022 12:09 PMchapter373性質性質關系圖關系圖關系矩陣關系矩陣充要條件充要條件自反自反每個點都有自反環(huán)每個點都有自反環(huán)主對角線全為主對角線全為1I IA A R R反自反反自反每個點都沒有自反環(huán)每個點都沒有自反環(huán)主對角線全為主對角線全為0I IA AR=R=對稱對稱不同結點間要么沒有不同結點間要么沒有邊，要么有一對邊。邊，要么有一對邊。關于主對角線對稱的元素，關于主對角線對稱的元素，要么都是要么都是0，要么都是，要么都是1。R RR R-1-1反對稱反對稱不同結點間要么沒有不同結點間要么沒有邊，