复合关系、逆关系

1、1,第二部分 集合论,主要内容 集合 3-1 集合的概念和表示法 3-2 集合的运算 3-4 序偶与笛卡尔积 3-5 关系及其表示 3-6 关系的性质 3-7 复合关系和逆关系 3-8 关系的闭包运算 3-9 集合的划分与覆盖,3-10 等价关系与等价类 3-11 3-12 序 函数 4.1 函数的基本概念 4.2 复合函数与逆函数,2,第一部分 数理逻辑,上节内容回顾,3-5 关系及其表示 3-5. 1 关系 关系：序偶的集合 定义域、值域、域 3-5. 2 一些特殊关系 空关系、恒等关系、全域关系 关系的交并补差还是关系 3-5. 3 关系的表示 序偶集合形式 关系矩阵mr 关系图gr,3

2、-4 序偶和笛卡尔积 序偶的概念和表示 =,z ,z 笛卡尔积 ab=|xayb 不满足交换律、结合律 与、 满足分配率,3,第二部分 集合论,主要内容 集合 3-1 集合的概念和表示法 3-2 集合的运算 3-4 序偶与笛卡尔积 3-5 关系及其表示 3-6 关系的性质 3-7 复合关系和逆关系 3-8 关系的闭包运算 3-9 集合的划分与覆盖,3-10 等价关系与等价类 3-11 相容关系 3-12 序关系 函数 4.1 函数的基本概念 4.2 复合函数与逆函数,1） 自反性(reflexivity) （2） 反自反性( irreflexivity) （3） 对称性(symmetry) （

3、4） 反对称性( antisymmetry) （5） 传递性(transitivity,3-6 关系的性质,自反性,反自反性,对称性,反对称性,传递性,需要指出,从x到y的关系r是xy 的子集，即rxy， 而xy （xy）（xy） 所以r （xy）（xy） 令z= xy，则rzz 因此，我们今后通常限于讨论同一集合上的关系,第二部分 集合论,需要注意：关系和运算,关系：= 不相交 朋友 同学 父子 运算：,自反性,反自反性,对称性,反对称性,传递性,自反性reflexivity：设r为定义在a上的二元关系，即raa, 如果对于每一个xa，有xrx (r)，则称二元关系r是自反的。 r在a上是自

4、反的 (x)( xa xrx) r在a上是非自反的 (x)( xa r)。 定理： r是自反的 ia r mr主对角线上的元素全为1 gr的每个顶点处均有自环,第二部分 集合论,自反性,反自反性,对称性,反对称性,传递性,自反性(举例)： 恒等关系、全域关系 实数： = ：|x,y都是实数且xy 几何图形： 三角形的全等：|ab、相似 数理逻辑： 、：|pq 、|pq是重言式 集合论： ：|a b,第二部分 集合论,第二部分 集合论,自反性,反自反性,对称性,反对称性,传递性,反自反性irreflexivity：设raa, 如果对于每一个xa，有r，则称二元关系r是反自反的。 r在a上是反自反

5、的 (x)(xa r )。 r在a上是非反自反的 (x)( xa xrx) 定理： r是反自反的 iar= mr主对角线上的元素全为0 gr的每个顶点处均无自回路（无环,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反自反性(举例)： 空关系 实数： 、|x,y都是实数且x|pq是重言式 中“”取 、 、 时 集合论： 、 ：|a b 注意：非自反不一定是反自反的。 即存在有关系既不是自反的也不是反自反的,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,对称性symmetry：设raa, 如果对于每个x,ya，每当 xry，就有

6、 yrx，则称集合a上的关系r是对称的。 r在a上对称 (x)(y)(xayaxryyrx). r非对称 (x)(y)(xayaxryyrx) 定理： r是对称的 mr是对称的 gr的任何两个顶点之间若有边, 则必有两条方向相反的有向边,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,对称性(举例)： 空关系、恒等关系、全域关系 实数：、= ：|x,y都是实数且x=y 几何图形：三角形的全等：|ab、相似 数理逻辑： |pq是重言式 中“”取 、 、 时 集合论：、不相交 ：|ab= 整数：同余 人之间的关系：同学关系、朋友关系、邻居关系,第二

7、部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性antisymmetry：设raa,如果对于每个x,ya,每当 xry和yrx，必有x=y，则称集合a上的关系r是反对称的。 r是反对称的 (x)(y)(xaya xry yrx x=y ) (x)(y)(xaya xy xry yrx ). r非反对称 (x)(y)(xa ya xry yrx xy) 定理：r是反对称的 在mr中, xixj(ij rij=1rji=0) 在gr中, xixj(ij), 若有有向边, 则必没有,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对

8、称性,反对称性,传递性,反自反性,反对称性(举例)：空关系 实数：、|p q是重言式 集合论： ：|a b 人之间的关系：父与子关系 整数：整除关系：|x,y都是整数且x|y 注意：非对称不一定反对称；可能有某种关系即是对称的又是反对称的。例如：a=1,2,3, s=, s在a上即是对称的又是反对称的。 n=, n在a上即不是对称的又不是反对称的,第二部分 集合论,恒等关系,、,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,传递性transitivity：设raa, 如果对于任意的x,y,za, 每当xry，yrz时就有xrz，称关系r在a上

9、是传递的。 r在a上是传递的 (x)(y)(z)(xayazaxryyrzxrz) r非传递(x)(y)(z)(xayazaxry yrzxrz)。 定理：r是传递的 在gr中, xi xj xk(ijk), 若有有向边和, 则必有,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,传递性(举例)：空关系、恒等关系、全域关系 实数：、|x,y都是整数且x|y 几何图形：三角形的全等：|ab、相似 数理逻辑： 、：|pq是重言式 集合论：、 ：|a b 人之间的关系：同姓、同性别,自反性与反自反性是相互矛盾的，不能同时成立 对称性

10、和反对称性不矛盾、可以同时成立,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,例1：在 n = 1,2, 上： 、 ： |xnynxy 自反,反对称,传递 、|xnynx|xnynx|y (整除关系) 自反,反对称,传递 in=|xnynx=y (恒等关系) 自反,对称,反对称,传递 en=|xnyn=nn (全域关系) 自反,对称,传递,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,思考： 左边的论述是否完全正确？ 有没有不严谨的地方,

11、例2：判断以下关系所具有的性质。 a=a,b,c r1=, r2=, r3=, r4=, r5=, r6=, r7,第二部分 集合论,反对称,传递,反对称,自反,对称,传递,对称,自反,反对称,传递,反自反，对称，反对称 ，传递,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,第二部分 集合论,xa,有r,xa,有r,若r 则r,若r,且xy, 则 r,若r 且r 则r,iar,ria,r=rc,rrcia,rrr,主对角线元素全是1,主对角线元素全是0,矩阵是对称矩阵,若rij1, 且ij, 则rji0,m2中1位置, m中

12、相应位置都是1,每个顶点都有环,每个顶点都没有环,两点之间有边, 是一对方向相反的边,两点之间有边,是一条有向边,点xi到xj有边, xj 到xk有边, 则xi到xk也有边,设 a=1,2,3，下面分别给出集合a上三个关系的关系图，试判断它们的性质,2）非自反，也不是反自反，非对称，反对称， 可传递,3）是自反的，对称的，可传递的，不是反自反，也不是反对称,解 （1）是自反的，非对称，不是反对称，不可传递,小结: 本节介绍了关系的基本性质及其判别方法,作业,第二部分 集合论,p113 (3) (6,p109 (2) (5) b) d,21,第二部分 集合论,主要内容 集合 3-1 集合的概念和

13、表示法 3-2 集合的运算 3-4 序偶与笛卡尔积 3-5 关系及其表示 3-6 关系的性质 3-7 复合关系和逆关系 3-8 关系的闭包运算 3-9 集合的划分与覆盖,3-10 等价关系与等价类 3-11 相容关系 3-12 序关系 函数 4.1 函数的基本概念 4.2 复合函数与逆函数,3-7.1 复合关系 3-7.2 逆关系 3-7.3 关系的运算性质 3-7.4 关系矩阵与关系图,3-7 复合关系和逆关系,复合关系,逆关系,运算性质,矩阵与图,运算性质,复合 (composite)关系: 设r为x到y的关系，s为从y到z的关系，则rs称为r和s的复合关系，表示为： rs= | xxzz

14、(y)(yyrs). 定义（屈婉玲版）：二元关系r, s的右复合运算 rs = ( | y (r s),复合关系,逆关系,矩阵与图,b=离散数学, 高等数学, 大学物理, 大学英语, 体育课,c=吃饭, 睡觉, 打豆豆, 变成豆豆,a=周一上午, 周二下午, 周三下午，周四上午，周五下午,rs,复合关系,逆关系,运算性质,矩阵与图,社交的六度分割原理： 地球上任何两个人之间的间隔不超过6个人,第二部分 集合论,a=地球上的人；r=|x,y a, 且x与y认识,rr2r3r4r5r6=aa,你隔壁老王家孩子的同学的同事的亲戚的朋友认识特朗普,复合关系,逆关系,运算性质,矩阵与图,逆(invers

15、e)关系 : 设r是x到y的二元关系，则从y到x的二元关系rc (r-1)定义为： rc = |r. 整数集合上的“”关系的逆关系是“”关系。 人群中的父与子关系的逆关系是子与父关系。 容易看出(rc) c=r,第二部分 集合论,复合关系,逆关系,运算性质,矩阵与图,第二部分 集合论,rs = sr, ,栗子： r = , , , s = , , , , ,rc,利用图示（不是关系图）方法求复合关系,复合关系,逆关系,运算性质,矩阵与图,28,关系运算的性质1,设f是任意的关系, 则 (1) (fc)c=f (2) domfc= ranf, ranfc= domf,证 (1) 任取, 由逆的定

16、义有 (fc)c fc f. 所以有(fc)c=f,2) 任取x, xdomfc y(fc) y(f) xranf 所以有 domfc=ranf. 同理可证 ranfc=domf,29,设f, g, h是任意的关系, 则 (1) 结合律：(fg)h = f(gh) (2) (fg)c = gcfc,1)证 任取, (fg)h t (fgh) t ( s (fg)h) t s (fgh) s (ft (gh) s (fgh) f(gh) 所以 (fg)h = f(gh,关系运算的性质2,30,性质2证明,2) (fg)c = gcfc 证 任取, (fg)c fg t (fg) t (gcfc)

17、 gc fc 所以 (f g)c = gc fc,31,关系运算的性质3,设r为a上的关系, 则 ria= iar=r,证任取 ria t (ria) t (rt=y) r r r ya r ia ria 同理可证 iar=r,32,关系运算的性质4,分配率：f,g,h为任意关系，则 (1) f(gh) = fgfh (2) (gh)f = gfhf (3) f(gh) fgfh (4) (gh)f gfhf,3)证 任取, f(gh) t (fgh) t (fgh) t (fg)(fh) t (fg)t (fh) fgfh fgfh 所以有 f(gh) fgfh 注意：复合运算对并满足分配律

18、，对交满足“弱”分配律,gh,h,gh,fh,33,推广,分配率的结论可以推广到有限多个关系 r(r1r2rn) = rr1rr2rrn (r1r2rn)r = r1rr2rrnr r(r1r2 rn) rr1rr2 rrn (r1r2 rn)r r1rr2r rnr,34,关系运算的性质5,1) (r1 r2) c= r1 c r2 c (2) (r1r2) c= r1 c r2 c (3) (ab)c= ba (4) (r)c = rc, 这里r ab-r (5) (r1-r2)c = r1c - r2c,35,关系的幂运算,定义：设 r 为 a 上的关系, n为自然数, 则 r 的 n

19、次幂定义为： (1) r0 = | xa = ia (2) rn+1 = rnr 注意： 对于a上的任何关系 r1 和 r2 都有 r10 = r20 = ia 对于a上的任何关系 r 都有 r1 = r,关系矩阵的性质,1) mrc= (mr)t. ( t表示矩阵转置) (2) mr1 r2 = mr1mr2 (表示布尔乘法, 其中加法使用逻辑, 乘法使用逻辑,逆关系关系图的性质,关系 rc 的图形是将关系r图形中弧的箭头方向反置,复合关系,逆关系,运算性质,矩阵与图,例题: 设 a=a,b,c, r1=, r2=, 用mr1, mr2确定mr1c , mr2c, mr1r1, mr1r2, mr2r1, 从而求出它们的集合表达式,复合关系,逆关系,运算性质,矩阵与图,1 1 0 1 1 0 mr1= 1 0 1 mr1c= 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 mr2= 0 0 1 mr2c= 1 0 0 0 0 0 1 1 0 0 1 1 mr1r