二元关系

这是一篇关于二元关系的思维导图，包含关系的性质、关系的闭包、等价关系与划分、二元关系等。

二元关系

• 关系的性质
  • 自反
    • R在A上自反："x( xÎA®<x,x>ÎA ) R在A上反自反："x( xÎA®<x,x>ÏA )
    • R在A上自反ÛIAÍR R在A上反自反ÛRÇIA=Æ
  • 对称
    • R在A上对称："x"y( x,yÎAÙ<x,y>ÎR®<y,x>ÎR ) 出现<x,y>必然要出现<y,x> R在A上反对称："x"y( x,yÎAÙ<x,y>ÎRÙ<y,x>ÎR®x=y ) 除对角线外，出现<x,y>必然不存在<y,x>
    • R在A上对称ÛR=R^-1 R在A上反对称ÛRÇR^-1ÍIA
  • 传递
    • R在A上传递："x"y"z( x,y,zÎAÙ<x,y>ÎRÙ<y,z>ÎR®<x,z>ÎR ) 要么不存在xyz的传递关系，一旦存在xy,yz则必须要出现xz
    • R在A上传递ÛR°RÍR
• 关系的闭包
  • 闭包：添加最少的有序对使原关系成为特殊关系
  • 自反闭包 r(R)：r(R)=RÈR0 矩阵：Mr=M+E（E为单位矩阵，对角线为1，其余为0） 关系图：在每个顶点处加一个环
  • 对称闭包s(R)：s(R)=RÈR^-1 矩阵：Ms=M+M'（M'为转置矩阵，即对称矩阵） 关系图：补全单边
  • 传递闭包：t(R)=RÈR^2ÈR^3È…… 矩阵：Mt=M+M^2+M^3+…… 关系图：把所有可以从一个点到另一个点之间有向连接（不论路径长短）
  • 定理：7.11 R是自反/对称/传递的Ûr(R)/s(R)/t(R)=R 7.12 R1ÍR2，r/s/t(R1)Ír/s/t(R2) 7.13 (1)R是自反的，s(R)和t(R)也是自反的 （2）R是对称的，r(R)和t(R)也是对称的 （3）R是传递的，r(R)也是传递的（传递性可能在对称过程中丢失，<1,3>是传递的，对称之后<1,3>.<3,1>不是传递的）
• 等价关系与划分
  • 等价关系
    • 定义：R是A上的等价关系ÛR是自反，对称，闭包的 <x,y>ÎR，称x等价于y，记作x~y
    • 等价类：R为A上的等价关系，"xÎA，[x]R={y| yÎAÙxRy } 称为x关于R的等价类，简称x的等价类，记作[x]或x （x的等价类是A中所有与x具有等价关系R的元素集合）
    • 模n等价关系：x~yÛxºy(mod n) x整除n的余数和y整除n的余数相等
    • 商集：R为A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集 A/R={[x]R|xÎA}
    • 定理： 7.14 R是A上的等价关系 （1）"xÎA，[x]是A的非空子集 （2）"x,yÎA,若xRy,则[x]=[y] (3)"x,yÎA，若xR\y,则[x]与[y]不交 （4）È{[x]|xÎA}=A
  • 划分
    • A的子集族p（pÍP(A)）是子集的集合 （1）ÆÏp （2）"x"y( x,yÎpÙx¹y®xÇy=Æ ) 元素集合之间无交集 （3）Èp=A 元素集合的总和为全集 则称p是A的一个划分，p中的元素为A的划分块
• 偏序关系
• 关系的运算
  • 关系运算
    • 定义域：R中所有有序对的第一元素构成的集合 domR={x|$y (<x,y>ÎR) }
    • 值域：R中所有有序对的第二元素构成的集合 ranR={y|$x (<x,y>ÎR) }
    • 域：R的定义域和值域的并集 fldR=domRÈranR
    • 逆关系 R^-1={<x,y>|<y,x>ÎR}
    • 右复合：G对F的右复合 F°G={<x,y>|$t (<x,t>ÎFÙ<t,y>ÎG) }
    • R在A上的限制 RéA={<x,y>| xRyÙxÎA } (除去R中第一元素不是A的)
    • A在R下的像 R[A]=ran(RéA) （第一元素是A的有序对的值域）
    • 运算法则：逆运算优先于其他运算；关系运算优先于集合运算
  • 关系定理
    • 7.1 （1）F^-1^-1=F （2）domF^-1=ranF，ranF^-1=domF 7.2 (1)(F°G)°H=F°(G°H) (2)(F°G)^-1=G^-1°F^-1 7.3 R°I=I°R=R 7.4 (1)F°(GÈH)=F°GÈF°H (2)(GÈH)°F=G°FÈH°F (3)F°(GÇH)ÍF°GÇF°H (4)(GÇH)°FÍG°FÇH°F 对于有限个关系也成立 7.5 （1）Fé(AÈB)=FéAÈFéB (2)F[AÈB]=F[A]ÈF(B) (3)Fé(AÇB)=FéAÇFéB (4)F[AÇB]ÍF[A]ÇF[B]
  • 幂运算R^n
    • 定义：R^0=IA R^n+1=R^n°R
    • 计算：集合表达式 关系矩阵：矩阵乘法（a*b） 关系图：如果R的关系图G中从xi出发经过n步长的路径到达xj，则在R^n的关系图G'中加一条从xi到xj的边
    • 定理 7.6 A为n元集，R是A上的关系，则存在自然数s和t，使得R^s=R^t （R^k是A*A的子集有限，R^k可以有无穷个，必然存在两个R的不同次幂相等） 7.7 (1)R^m°R^n=R^m+n (2)(R^m)^n=R^mn (归纳法：先验证n=0时是否成立，在验证假设已知条件成立下n+1是否成立) 7.8 （1）R^s+k=R^t+k (2)R^s+kp+i=R^s+i，其中p=t-s (3)S={R^0,R^1,……，R^t-1},对于任意的qÎN有R^qÎS (0£i£p-1)
• 二元关系
  • 二元关系（关系）
    • 定义：（1）集合为空集 （2）集合非空，且它的元素都是有序对 对于二元关系R，<x,y>ÎR , 记作xRy ; <x,y>ÏR，记作xR\y
    • A,B为集合，A*B的任何子集所定义的二元关系称作从A到B的二元关系， 当A=B时称作A上的二元关系 |A|=n，|A*A|=n^2，A*A的子集有2^n^2
  • 常见关系
    • 空关系：空集Æ是A*A的子集，称作A上的空关系 全域关系E：E={<x,y>|xÎAÙyÎA}=A*A 恒等关系I：I={<x,x>|xÎA} 小于等于关系L：L={<x,y>|x,yÎA,x£y} 整除关系D：D={<x,y>|x,yÎA,x|y}(x整除y) 包含关系RÍ：R={<x,y>|x,yÎA,xÍy}
  • 关系的表示
    • 集合表达式 R={<1,1>,<1,2>,……}
    • 关系矩阵 M=| 横行x,竖行y |，如果xRy,则对应位置为1；若xR\y,则对应位置为0
    • 关系图 A中有n个元素，则有n个顶点。若xRy，则连接x到y（有向线段）
• 有序对与笛卡儿积
  • 有序对（序偶）
    • 定义：由两个元素按照一定顺序排列成的二元组（与二元集不同），记作<x,y>，其中x是第一元素，y是第二元素
  • 笛卡儿积
    • 定义：A,B两集合，以A中元素为第一元素，B中元素为第二元素构成有序对，所有这样有序对构成的集合叫做A和B的笛卡儿积，记作A*B
    • 符号化表示：A*B={<x,y>|xÎAÙyÎB}
    • 性质： 1.A*Æ=Æ Æ*A=Æ 2.不满足交换律和结合律 3.对并和交满足分配律 4.AÍCÙBÍD Þ A*BÍC*D（反之则不成立，当A或B一者为空集时，另一个不满足前式的包含关系）
• 恒等关系I：I={|xÎA