《离散数学》课件1第2章 关系.pptx
《《离散数学》课件1第2章 关系.pptx》由会员分享,可在线阅读,更多相关《《离散数学》课件1第2章 关系.pptx(152页珍藏版)》请在文库网上搜索。
1、关系的基本概念关系的基本概念关系的表示方法关系的表示方法 关系的运算关系的运算 关系的性质关系的性质 关系的闭包关系的闭包等价关系与划分等价关系与划分偏序关系偏序关系12.1关系的基本概念为了讨论关系,首先引入有序对和笛卡儿积两个概念。为了讨论关系,首先引入有序对和笛卡儿积两个概念。由两个元素由两个元素a,ba,b组成的集合组成的集合a,ba,b中,中,a a和和b b是没有次是没有次序的。有时需要考虑有次序的两个元素,所以需要由序的。有时需要考虑有次序的两个元素,所以需要由两个元素组成新的东西,并且两个元素是有次序的。两个元素组成新的东西,并且两个元素是有次序的。定义定义2.12.1两个元素
2、两个元素a,b a,b 有次序地放在一起,称为一个有次序地放在一起,称为一个有有序对序对或或序偶序偶,记为,记为(a,b)(a,b)。在有序对。在有序对(a,b)(a,b)中,中,a a 称称为为第一元素第一元素,b b称为称为第二元素第二元素。且。且(a(a1 1,b,b1 1)=(a)=(a2 2,b,b2 2)当且仅当当且仅当a a1 1=a=a2 2 且且b b1 1=b=b2 2。例例2.1 2.1 直角坐标系中的点直角坐标系中的点(1,2)(1,2)与点与点(2,1)(2,1)是两个不同的是两个不同的点。点。2定义定义2.2 2.2 任给任给n2,n n2,n 个元素个元素a a1
3、 1,a,a2 2,a,an n 有有次序地放在一起次序地放在一起,称为一个称为一个n n 元有序元有序 组组,记为记为(a(a1 1,a,a2 2,a,an n)。为了体现。为了体现n n 元有序组的次序元有序组的次序,规定规定(a(a1 1,a,a2 2,a,an n)=(b)=(b1 1,b,b2 2,b,bn n)当且仅当当且仅当任给任给1in,1in,都有都有a ai i=b=bi i。例例2.2 2.2 三维坐标系中的点三维坐标系中的点(1,2,3)(1,2,3)与点与点(3,2,1)(3,2,1)是两个不同的点。是两个不同的点。34定义定义2.32.3 设设A,B 是两个集合,集
4、合是两个集合,集合(x,y)|xA 且且yB 称为称为A 和和B 的的笛卡儿积笛卡儿积,也称也称卡氏积卡氏积,记为,记为AB。用属于关系来表示。用属于关系来表示就是:就是:(x,y)AB 当且仅当当且仅当xA 且且yB和和(x,y)AB 当且仅当当且仅当x A或或y B。其中。其中A 称为称为第一集合第一集合,B 称为称为第二集合第二集合。5例例2.32.3 设设A=1,2,3,B=A,BA=1,2,3,B=A,B,求求ABAB。由笛卡儿积的定义可知有由笛卡儿积的定义可知有AA=A=A=。又由有序对的性质可知,一般没有又由有序对的性质可知,一般没有ABBAABBA。ABAB也是一个集合,所以可
5、以也是一个集合,所以可以和另一集合和另一集合C C作笛卡儿积作笛卡儿积(AB)C(AB)C,类似地,类似地有有A(BC)A(BC)。但是,一般没有。但是,一般没有(AB)C=A(BC)(AB)C=A(BC),且,且ABAB中的元素既中的元素既不是不是A A 中的元素,也不是中的元素,也不是B B中的元素。中的元素。定义定义2.4 2.4 任给任给n2,An2,A1 1,A,A2 2,A,An n 是是n n 个集合个集合,集合集合(x(x1 1,x,x2 2,x,xn n)|)|任给任给1i n,1i n,都有都有x xi iAAi i 称为称为A A1 1,A,A2 2,A,An n的笛卡儿
6、积的笛卡儿积,记为记为 A A1 1AA2 2AAn n。任给。任给1in,A1in,Ai i 称为这个称为这个卡氏积的第卡氏积的第i i个集合。个集合。6例例2.4 2.4 设集合设集合A=1,2,A=1,2,集合集合B=a,b,B=a,b,集合集合C=C=,计算计算ABC,(AB)C,A(BC)ABC,(AB)C,A(BC)。解解:ABC:ABC=(1,a,=(1,a,),(1,),(1,b,b,),(2,),(2,a,a,),(2,),(2,b,b,),(1,),(1,a,a,),),(1,(1,b,b,),(2,),(2,a,a,),(2,),(2,b,b,)(AB)C AB)C=(1
7、,a),=(1,a),),(1,),(1,b),b),),(2,),(2,a),a),),(2,),(2,b),b),),(),(1,(1,a),a),),(1,),(1,b),b),),(2,),(2,a),a),),(2,),(2,b),b),)A(BC)A(BC)=(1,(a,=(1,(a,),(1,(),(1,(b,b,),(2,(),(2,(a,a,),(2,(),(2,(b,b,),(),(1,(1,(a,a,),(1,(),(1,(b,b,),(2,(),(2,(a,a,),(2,(),(2,(b,b,)78定理定理2.1 2.1 如果如果B B1 1 A A1 1,B B2 2
8、 A A2 2,则,则B B1 1B B2 2 A A1 1A A2 2。证明证明 对对(x,y)B B1 1B B2 2,有,有xB B1 1 且且yB B2 2,又因为,又因为B B1 1 A A1 1 ,B B2 2 A A2 2 ,则,则xA A1 1 且且yA A2 2,所以,所以(x,y)A A1 1A A2 2,即,即B B1 1B B2 2 A A1 1A A2 2。9定理定理2.22.2 A,B,C 是任意集合,则:是任意集合,则:(1)(1)A(BC)=(AB)(AC),(BC)A=(BA)(CA)。(2)A(BC)=(AB)(AC),(BC)A=(BA)(CA)。(3)A
9、(B-C)=(AB)-(AC),(B-C)A=(BA)-(CA)。10证明证明 (1)(1)对对(x,y)A(BC),有,有xA 且且yBC,因此,因此xA且且(yB 或或yC),当,当y B时,由时,由xA 和和yB 得得(x,y)AB,当,当yC 时,由时,由xA 和和yC得得(x,y)AC,所,所以以(x,y)(AB)(AC),即,即A(BC)(AB)(AC)。因为因为AA,BBC 和和CBC 得得ABA(BC)和和ACA(BC),因此,因此(AB)(AC)A(BC)。因此因此A(BC)=(AB)(AC)成立。成立。同理可证同理可证(BC)A=(BA)(CA)。11(2)对对(x,y)(
10、AB)(AC),有,有(x,y)AB且且(x,y)AC,所以(,所以(xA且且yB)且()且(xA且且yC)。由)。由yB且且yC得得yBC,由,由xA且且yBC得得(x,y)A(BC)。因此。因此(AB)(AC)A(BC)。因为因为AA,BCB和和BCC,所以有,所以有A(BC)AB和和A(BC)AC成立,因此成立,因此A(BC)(AB)(AC)。因此因此A(BC)=(AB)(AC)。同理可证同理可证(BC)A=(BA)(CA)。12(3)(3)对对(x,y)A(B-C),有,有xA且且yB-C,所以,所以xA且且yB且且y C。由。由xA且且yB得得(x,y)AB,由,由y C得得(x,y
11、)AC,所以,所以(x,y)(AB)-(AC)。因此。因此A(B-C)(AB)-(AC)。对对(x,y)(AB)-(AC),有,有(x,y)AB且且(x,y)AC,由,由(x,y)AB得得xA且且yB,由,由xA和和(x,y)AC得得y C,所以,所以xA且且yB且且y C。由。由yB且且y C得得yB-C,所,所以以(x,y)A(B-C)。因此。因此(AB)-(AC)A(B-C)。因此因此A(B-C)=(AB)-(AC)。同理可证同理可证(B-C)A=(BA)-(CA)。13定义定义2.52.5 如果一个集合满足以下条件之一:如果一个集合满足以下条件之一:(1 1)集合非空,且它的元素都是有
12、序对;)集合非空,且它的元素都是有序对;(2 2)集合是空集。)集合是空集。则称该集合为一个则称该集合为一个二元关系二元关系,记作,记作R R。二元关系也可。二元关系也可简称为简称为关系关系。对于二元关系。对于二元关系R R,如果,如果(x,y)R)R,可,可记作记作xR Ry;如果;如果(x,y)R R,则记作,则记作xR R y。设设A A,B B为集合,为集合,ABAB的任何子集所定义的二元关系的任何子集所定义的二元关系叫做叫做从从A A到到B B的二元关系的二元关系,特别当,特别当A=BA=B时则叫做时则叫做A A上的上的二元关系二元关系。例例2.5 2.5 判断下列集合是否是二元关系
13、。判断下列集合是否是二元关系。(1)A=(1)A=。(2)B=(1,2),(a,b)(2)B=(1,2),(a,b)。(3)C=a,(a,b)(3)C=a,(a,b)。(4)D=(1,2),(a,b),(3,4),(c,d)(4)D=(1,2),(a,b),(3,4),(c,d)。1415例例2.62.6 设集合设集合A=0,1A=0,1,B=1,2,3B=1,2,3,那么,那么R R1 1=(0,2)=(0,2),R R2 2=AB=AB,R R3 3=,R R4 4=(0,1)=(0,1)等都是从等都是从A A到到B B的二元关系,而的二元关系,而R R3 3和和R R4 4同时也同时也是
14、是A A上的二元关系。上的二元关系。16定义定义2.62.6笛卡尔积笛卡尔积A1A2An的任意一个子集的任意一个子集R称称为为A1,A2,An上的一个上的一个n元关系。当元关系。当A1=A2=An=A时,称时,称R为为A上的上的n元关系元关系。定义定义2.7空集空集上定义一个二元关系,简称上定义一个二元关系,简称空关系空关系;若一个若一个n元关系元关系R本身是笛卡儿积本身是笛卡儿积A1A2An,则称则称R为为全关系全关系,用符号用符号UA表示,即表示,即UA=(ai,aj)|ai,ajA为为A上的全关系。上的全关系。符号符号IA=(x,x)|xA为为A上的上的恒等恒等关系关系 17例例2.8
15、2.8 设设A=1,2,3,4A=1,2,3,4,下面各式定义的,下面各式定义的R R都是都是A A上的关系,试用列元素法表示上的关系,试用列元素法表示R.R.(1)R(1)R1 1=(x,y)|x=(x,y)|x是是y y的倍数的倍数(2)R(2)R2 2=(x,y)|(x-y)=(x,y)|(x-y)2 2AA(3)R(3)R3 3=(x,y)|x/y=(x,y)|x/y是素数是素数(4)R(4)R4 4=(x,y)|xy=(x,y)|xy18解解:(1)(1)R R1 1=(4,4)(4,4),(4(4,2),2),(4,14,1),(3,3),(3,1),(2,2),(2,1),(1,
16、1),(3,3),(3,1),(2,2),(2,1),(1,1)(2)R(2)R2 2=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,3),(1,2)3),(1,2)(3)R(3)R3 3=(2,1),(3,1),(4,2)=(2,1),(3,1),(4,2)(4)R(4)R4 4=U=UA A-I-IA A=(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,=(1,2),(1,3),
17、(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)4),(4,1),(4,2),(4,3)例例2.9 2.9 设集合设集合A=a,b,A=a,b,求出定义在求出定义在A A 上的所上的所有二元关系。有二元关系。解解:首先计算出首先计算出AA=(a,a),(a,b),(b,a),(b,b),AA=(a,a),(a,b),(b,a),(b,b),则定义在则定义在 A A上的二元关系共有上的二元关系共有1616个个,即即AAAA的所有子集。的所有子集。1920定义定义2.82.8 R R ABAB中所有的有序对的第一元素中所有的有序
18、对的第一元素构成的集合称为构成的集合称为R R的的定义域定义域,记为,记为domRdomR。形。形式化表示为:式化表示为:domR=x|x A,domR=x|x A,y B,y B,使使得得(x,y)R(x,y)R。R R ABAB中所有有序对的第中所有有序对的第二元素构成的集合称为二元素构成的集合称为R R的的值域值域,记作,记作ranRranR。形式化表示为形式化表示为ranR=y|yB,ranR=y|yB,xA,xA,使使得得(x,y)R(x,y)R。21定义定义2.92.9 设设R R为二元关系为二元关系,R R的的逆关系逆关系,简称简称R R的的逆逆,记作记作R R-1-1,其中其中
19、R R-1-1=(y,x)|(x,y)R=(y,x)|(x,y)R。例例2.102.10 整除关系整除关系设设A=2,3,4,8,B=3,4,5,6,7,A=2,3,4,8,B=3,4,5,6,7,定义从定义从A A到到B B的二元关系的二元关系R:(a,b)R:(a,b)R Ra a整除整除b b。则。则 R=(2,4),(2,6),(3,3),(3,6),(4,4)R=(2,4),(2,6),(3,3),(3,6),(4,4),Dom R=2,3,4,Ran R=3,4,6Dom R=2,3,4,Ran R=3,4,6,R R-1-1=(4,2),(6,2),(3,3),(6,3),(4,
20、4)=(4,2),(6,2),(3,3),(6,3),(4,4)例例2.11 2.11 设集合设集合A=1,2,A=1,2,集合集合B=2,3,4,B=2,3,4,定义定义A A到到B B上的二元关系上的二元关系R=(1,2),(1,3),(2,2),(2,4)R=(1,2),(1,3),(2,2),(2,4)则则domR=1,2,ranR=2,3,4domR=1,2,ranR=2,3,4。例例2.12 2.12 设集合设集合A=a,b,c,A=a,b,c,定义定义A A上的二元关上的二元关系系R=(a,a),(a,b),(b,c),R=(a,a),(a,b),(b,c),则则 domR=a,
21、b,ranR=a,b,c,domR=a,b,ranR=a,b,c,R R-1-1=(a,a),(b,a),(c,b),=(a,a),(b,a),(c,b),domRdomR-1-1=a,b,c,=a,b,c,ranRranR-1-1=a,b=a,b。2223关系从本质上讲,仍是集合,只是这个集合中关系从本质上讲,仍是集合,只是这个集合中的元素都是以有序对的形式出现。既然关系的元素都是以有序对的形式出现。既然关系是一个集合,那么集合的表示方法就可以用是一个集合,那么集合的表示方法就可以用来表示关系,又因为关系是一个特殊的集合,来表示关系,又因为关系是一个特殊的集合,其中的元素均以序偶的形式出现,
22、除了可以其中的元素均以序偶的形式出现,除了可以用集合的表示方法外,还可以用其他的表示用集合的表示方法外,还可以用其他的表示方法。这里主要介绍如下几种表示方法。方法。这里主要介绍如下几种表示方法。241.1.用列举法表示二元关系用列举法表示二元关系如果二元关系中的序偶个数是有限的,可以用列举如果二元关系中的序偶个数是有限的,可以用列举法将其所包含的全部元素一一列举出来。法将其所包含的全部元素一一列举出来。例例2.132.13 设集合设集合A=1,2,3A=1,2,3,在集合,在集合A A上定义的小于上定义的小于等于关系,等于关系,L LA A=(a,b)|a,bA,ab=(a,b)|a,bA,a
23、b,则,则L LA A=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)。252.2.用描述法表示二元关系用描述法表示二元关系用确定的条件表示某些序偶是否属于这个关系,并把用确定的条件表示某些序偶是否属于这个关系,并把这个条件写在大括号内表示关系的方法。这个条件写在大括号内表示关系的方法。格式是:格式是:L LR R=(x,y)|xR=(x,y)|xR且且yRyR且且xyxy。例例2.142.14设设A=1A=1,2 2,3 3,44,下面两式定义的,下面两式定义的R R1 1和和R R2 2都是都是
24、A A上的关系,分别列出上的关系,分别列出R R1 1与与R R2 2的元素如下:的元素如下:(1)R(1)R1 1=(x,y)|x=(x,y)|x是是y y的倍数的倍数 (2)R(2)R2 2=(x,y)|(x-y)=(x,y)|(x-y)2 2AA26解解:(1)(1)R1=(4,4),(4,2),(4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2)(2)R2=(2,1),(1,2),(3,1),(1,3),(2,3),(3,2),(4,2),(2,4),(3,4),(4,3)27定义定义2.102.10设设A A和和B B是两个有限集是两个有限集A=aA=a1 1
25、,a,am m,B=B=bb1 1,b,bn n,R R是从是从A A到到B B的二元关系,称的二元关系,称m m n n阶矩阵阶矩阵M MR R=(r=(rijij)为为R R的关系矩阵,其中的关系矩阵,其中 r rijij=1=1 ,当且仅当,当且仅当(a(ai i,b,bj j)R R r rijij=0 =0,当且仅当,当且仅当(a(ai i,b,bj j)R R28例例2.162.16设集合设集合A=1,2,3,A=1,2,3,在集合在集合 A A 上定义的小于或等于关上定义的小于或等于关系系,则关系则关系R R 的关系的关系 矩阵为矩阵为 :例例2.172.17设设A=1,2,3,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 离散数学课件1第2章 关系 课件