2.1-2 集合叉积与关系

,单击此处编辑母版文本样式,*,第二章,第二章,1,一. 集合的叉积：基本概念,定义1 由两个元素x和y按一定顺序排列成的二元组叫做一个有序对或序偶(Ordered Pair), 记作或(x,y), 其中x是它的第一元素, y是它的第二元素.,注：有序对具有以下性质:,当,x,y,时, ,;, = ,的充分必要条件是,x = u,且,y = v.,这些性质是二元集 x, y 所不具备的.,例如当x,y时, 有: x, y = y, x .原因在于有序对中的元素是有序的, 而集合中的元素是无序的.,2,例 已知 = , 求x和y.,解 由有序对相等的充要条件有,解得: x = 3, y = -2.,3,定义2 设A和B为集合, 用A中元素为第一元素, B中元素为第 二元素构成有序对;,所有这样的有序对组成的集合叫做A和B的叉积或笛卡儿积(,Cartesian Product/Product Set), 记作A,B.,叉积(笛卡儿积)的符号化表示为:,A,B = | x,A, y,B ,例如, 设A = a, b , B = 0, 1, 2 , 则,A,B = , , , , , ,B,A = , , , , , ,由排列组合的知识不难证明, 如果|A| = m, |B| = n, 则|A,B| = mn.,4,二. 叉积的性质,1. 对任意集合A, 根据定义有,A, ,=, ,A =,2. 一般地说, 叉积(笛卡儿积)运算不满足交换律, 即,A,B,B,A (当A,B, A, B,时),3.叉积(笛卡儿积)运算不满足结合律, 即,(A,B),C,A,(B,C) (当A, B, C,时),5,4. 叉积(笛卡儿积)运算对并和交运算满足分配律, 即,(1) A,(BC) = (A,B)(A,C),(2) (BC),A = (B,A)(C,A),(3) A,(BC) = (A,B)(A,C),(4) (BC),A = (B,A)(C,A),我们只证明等式(1).,证 任取,A,(BC),x,Ay,(BC),x,A(y,By,C),(,x,Ay,B)(x,Ay,C),A,B,A,C,(A,B)(A,C),6,5. (A,C)(B,D),A,B,C,D,性质5的证明和性质4类似, 也采用命题演算的方法.,注意性质5的逆命题不成立, 可分多种情况来讨论.,例 设A = 1, 2 , 求P(A),A.,解: 由幂集可知: P(A) = , 1 , 2 , 1, 2 ,P(A),A,= , , ,7,例 设A, B, C, D为任意集合, 判断以下命题是否为真, 并说明理由.,1). A,B =,A,C,B =,C,2). A - (B,C) = (A - B),(A - C),3). (A = B),(,C = D),A,C = B,D,4). 存在集合A, 使得: A,A,A,解:,1). 不一定为真.当A =, B = 1 , C = 2 时,有: A,B = A,C =,但, B,C.,2). 不一定为真.当A = B = 1 , C = 2 时,A - (B,C) = 1 - = 1 ,(A - B),(A - C) =, , 2 =,3). 真.可由代入的原理证得.,4). 真.当A =,时, 有: A,A,A成立.,8,三. 二元关系的基本概念,定义1 若一个集合满足以下条件之一:,(1)集合非空, 且它的元素都是有序对,(2)集合是空集,则称该集合为二元关系(Binary Relation), 记作R, 可简称为关系.,注：*当(2)成立时，称为空关系.,*关系是集合，其元素为有序对.,若,R, 可记作: xRy;否则, 记作: xRy.,例如 : R,1,= , , R,2,= , a, b , 则R,1,是二元关系, R,2,不是二元关系.,9,定义,2,设A和B为集合, A,B的任何子集所定义的二元关系叫做从A到B的二元关系.当A = B时, 则称该关系为A上的二元关系.,例如: A = 0, 1 , B = 1, 2, 3 , 那么,R,1,= R,2,= A,B,R,3,=,R,4,= ,都是从A到B的二元关系, 且R,3,和R,4,也是A上的二元关系.,*集合A上二元关系的数目依赖于A中的元素数.,若|A| = n, 则, |A,A| = n,2, A,A的子集就有2,n,2,个.,因为每一个子集代表一个A上的二元关系, 所以, A上有2,n,2,个不同的二元关系.,例如,: |,A| = 3, 则A上有2,3,2,= 512个不同的二元关系.,10,定义3 设A,i,(i=1,2m)是m个非空集合，若R,A,1,A,2,A,m,， 则称R是m个集合,A,i,(i=1,2m)的元素之间的一个m元关系.,定义4 设A,B是两个非空集合，若R,B，,(1),D(R)=a|存在b,B,使得(a,b),R,称D(R)为R的前 域.,(2)R(R)=b|存在a,A,使得(a,b),R,称R(R)为R的后域.,定理1 A,B为非空集，R,1,A,B,R,2,A,B.若,R,1,R,2，,则,(1)D(R,1,),D(R,2,)；,(2)R(R,1,),R(R,2,),11,定理2,A,B为非空集合，,R,1，,R,2,A,B,则,(1)D(,R,1,R,2,) = D(,R,1,),D(,R,2,);,(2)R(,R,1,R,2,) = R(,R,1,),R(,R,2,);,(3)D(,R,1,R,2,),D(,R,1,),D(,R,2,);,(4)R(,R,1,R,2,),R(,R,1,),R(,R,2,);,证明(3):,任取a,D(,R,1, R,2,),由定义知，存在bB,使得(a,b),(,R,1,R,2,).由交集定义知，必有(a,b),R,1,且(a,b),R,2,，由前域定义知，,a,D(,R,1,)且a,D(,R,2,),.故有,a,D(,R,1,),D(,R,2,).故结论成立。证毕。,12,(1)对于任何集合A, 称空集,为A上的空关系.,(2)A上的全域关系E,A,(Universal Relation),(3)A上的恒等关系I,A,(Identity Relation).,定义,5,对任意集合A, 定义:,E,A,= |,x, y,A, = A,A,I,A,= |,x,A,例 A = 1, 2 , 则,E,A,= , , , ,I,A,= , ,四. 几种常用的关系,13,除上面三种特殊关系(,空关系,全域关系,和,恒等关系,)之外, 还有一些常用的关系, 例如:,L,A,= | x, y,A, x,y, A,R ,D,B,= | x, y,B, x整除y, B,Z,*,R,= | x, y,A, x,y, A是集合族 ,L,A,叫做A上的小于等于(,)关系, D,B,叫做B上的整除关系, 其中x是y的因子, R,叫做A上的包含关系.,例 A = 1, 2, 3 , B = a, b , 则,L,A,= , , , , , ,D,A,= , , , , ,类似地, 还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等.,14,五. 典型实例,例 设A = 1, 2, 3, 4 , 下面各式定义的R都是A上的关系, 试用列元素法表示R.,(1) R = | x是y的倍数 ,(2) R = | (x-y),2,A ,(3) R = | x/y是素数 ,(4) R = | x,y ,解,(1) R =, , , , , , , , ,(2) R =, , , , , , , , , ,(3) R =, , , ,(4) R = E,A,- I,A,=, , , , , , , , , , , , ,15,六. 关系的表示法,(1)集合表达式：见上例，略.,(2)关系矩阵,(3)关系图,(2)关系矩阵：设A = ,x,1, x,2, ., x,n, R是A上的关系.令,则, R的关系矩阵M,R,如下所示.,16,例 A = 1, 2, 3, 4 , R = , , , , , 则R的关系矩阵是,17,(3)关系图,设A =, x,1, x,2, ., x,n, R是A上的关系.,令: 图G = , 其中顶点集合V = A, 边集为E.,对于,x,1, x,2,V, 满足: ,E,R, 称图G为R的关系图, 记作G,R,.,例如, A = 1, 2, 3, 4 , R = , , , , , 则R的关系图G,R,如下图所示.,1,2,3,4,18,作业：,P,49,6,P,50,10,19,