笛卡尔积和二元关系课件(离散数学)

1、第七章第七章 二元关系二元关系2022-5-917.17.2 笛卡儿积和二元关系笛卡儿积和二元关系n 有序对有序对n 笛卡儿积及其性质笛卡儿积及其性质n 二元关系的定义二元关系的定义n 二元关系的表示二元关系的表示22022-5-9 引例中涉及的概念引例中涉及的概念n有序对有序对n关系关系集合A上的关系集合A到B的关系32022-5-9一、有序对一、有序对 定义：定义： 由两个客体由两个客体 x 和和 y，按照一定的顺序，按照一定的顺序组成的二元组称为组成的二元组称为有序对有序对，记作，记作一般情况下一般情况下 与与 相等的充要条件是：相等的充要条件是： = x=u y=v有序性有序性4202

2、2-5-9二、笛卡儿积二、笛卡儿积 定义：定义：设设A和和B是两个集合，是两个集合，A到到B的笛卡尔的笛卡尔乘积用乘积用AB表示，它是表示，它是所有所有形如形如的有的有序对作为元素的集合，其中序对作为元素的集合，其中 。B Bb bA Aa a ,A B = | x A y B B到到A的笛卡尔乘积的笛卡尔乘积BAB A = | x B y A 52022-5-9二、笛卡儿积二、笛卡儿积 例例1： A=1,2,3, B=a,b,c A B=, , B A=, , , A B B A62022-5-9二、笛卡儿积二、笛卡儿积例例2：已知：已知A=, , 则则A P(A)。 P(A)=, , A

3、P(A)=, , , , 72022-5-9二、笛卡儿积二、笛卡儿积 特别的，当特别的，当A = B时，时，AA称为集合称为集合A上的上的笛卡尔乘积笛卡尔乘积，也可简写作，也可简写作A。当当| A | = m,| B | = n时时, | AB | = m n| AA | = n282022-5-9二、笛卡儿积二、笛卡儿积 例例3：设：设A=a,b,B=0,1,C=。试求出。试求出AA, AB,BA, (AB)C, A (BC)AA=, AB=,BC=,(AB)C= , , , , , , , A(BC)= a, , a, , b, , b, 92022-5-9二、笛卡儿积二、笛卡儿积 笛卡儿

4、积的性质：笛卡儿积的性质：nA=B=n当当A B, A, B时，时， A B B A n当当A, B时，时， (A B) C A (B C) 1. D DC CB BA AD DB BC CA A 102022-5-9二、笛卡儿积二、笛卡儿积n对于并或交运算满足分配律对于并或交运算满足分配律 A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C) A=(B A) (C A) 思考思考: A (B C)=(A B) (A C)成立吗成立吗? P(A) P(A) =P(A A)成立吗成立吗?112022-5-9二、笛卡儿积

5、二、笛卡儿积例例4：(1) 证明证明 A=B C=D A C=B D (2) A C=B D是否能推出是否能推出A=B C=D?为什么？为什么？解：解： (1) 任取任取 A C x A y C x B y D B D (2) 不一定。不一定。 反例如下：反例如下： A=1，B=2, C=D=, 则则 A C=B D 但是但是 A B.122022-5-9二、笛卡儿积二、笛卡儿积证：对于任意的证：对于任意的x，例例5：设：设A、B为任意集合，为任意集合， 证明：若证明：若 A A=B B,则则A=B。BxBBxxAAxxAx ,AxAAxxBBxxBx ,BAABBA ，即即且且132022-

6、5-9三、二元关系三、二元关系 定义：定义：A和和B是两个集合是两个集合,R是笛卡尔乘积是笛卡尔乘积AB的的子集子集，则称，则称R为为A到到B的一个二元关系的一个二元关系。e.g. A = a1,a2,a3,a4,a5 ,B = b1,b2,b3，可以写作可以写作a1Rb1 ,称称a1,b1以以R相关。相关。R = ,是是A到到B的一的一个二元关系。个二元关系。142022-5-9三、二元关系三、二元关系 例例6：列出从集合：列出从集合A=1,2到到B=1的所有的的所有的二元关系二元关系.解：解：AB的所有子集都是的所有子集都是A到到B的二元关系。的二元关系。R1= , R2=, R3=, R

7、4=,二元关系是一个集合，其元素是有序对。二元关系是一个集合，其元素是有序对。152022-5-9三、二元关系三、二元关系 定义：定义：A是集合，是集合，R是笛卡尔乘积是笛卡尔乘积AA的子的子集，则称集，则称R为为A上的二元关系上的二元关系。当当|A|=n时时, A上有多少个不同的二元关系？上有多少个不同的二元关系？|AA|=n2AA的子集有的子集有 个个22n所以，所以，A上有上有 个不同的二元关系个不同的二元关系22n162022-5-9三、二元关系三、二元关系 定义：定义： 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一： （1）集合非空）集合非空, 且它的元素都是有序对且它

8、的元素都是有序对 （2）集合是空集）集合是空集 则称该集合为一个则称该集合为一个二元关系二元关系, 简称为简称为关系关系，记，记作作R。如果如果R, 记作记作 xRy；如果；如果 R, 则记作则记作xRy。172022-5-9三、二元关系三、二元关系引例：引例：A=a,b, B=4,5,8R1=,R2=,R3=,R4=,=AA恒等关系恒等关系小于等于关系小于等于关系整除关系整除关系182022-5-9三、二元关系三、二元关系 设设 A 为任意集合，为任意集合，n称为称为A 上的上的空关系；空关系；nEA=|xAyA=AA称为称为A 上的上的全域关系；全域关系；1.IA=|xA称作称作A上的上的

9、恒等关系恒等关系。192022-5-9三、二元关系三、二元关系nLA=| x,yAxy称作称作A上的小于等上的小于等于关系于关系，其中，其中 A R，R为实数集合；为实数集合；nDA=| x,yAx整除整除y, 称作称作A上的整上的整除关系除关系A Z*, Z*为非为非0整数集；整数集；nR =| x,yAx y称作称作A上的包含关上的包含关系系， A是集合族。是集合族。202022-5-9例例7: A=,1,2,1,2, 求求 A上的包含关系。上的包含关系。 三、二元关系三、二元关系R =, , ,212022-5-9四、关系的表示四、关系的表示 常见的关系的表示方式有三种：常见的关系的表示

10、方式有三种：n集合表示法；集合表示法；n矩阵表示法；矩阵表示法；n关系图表示法。关系图表示法。222022-5-9四、关系的表示四、关系的表示e.g. A = a1,a2,a3B = b1,b2,b3,b4R =,关系关系R的关系矩阵如下：的关系矩阵如下： 100111000001R RM Mb1 b2 b3 b4a1 a2 a3232022-5-9四、关系的表示四、关系的表示 关系矩阵关系矩阵：若：若A=x1, x2, , xm，B=y1, y2, , yn，R是从是从A到到B的关系，的关系，R的关系矩的关系矩阵阵MR = rij m n, 其中其中 rij = 1 R.242022-5-9四、关系的表示四、关系的表示 例例8：A = 1,2,3,4,6 ，R是是A上的整除关系，上的整除关系，求求R的矩阵表示。的矩阵表示。 1 2 3 4 6 1 2 3 4 6 1 1 2 2 3 3 4 4 6 6 1000001000101001101011111252022-5-9四、关系的表示四、关系的表示例例9：A = 0,1,2,3 R=, 给出给出R的关系矩阵和关系图。的关系矩阵和关系图。 0100101100001001 R RM M262022-5-9四、关系的表示四、关系的表示 关系图关系图：若：若A= x1, x2, , xm，R是是A上的上的关系