关系

定义：设A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样的序偶组成的集合，称为笛卡尔积（直积）记作A×B 。

关系

• 1.序偶
  • 定义1.具有固定次序的两个客体组成一个序偶，表示两个客体之间的关系；记作<x,y> X是第一元素，y是第二元素，讲究次序
  • 定义2.n元组是一个序偶，其第一个元素是一个n-1元组，记作<<x1,x2，xn-1>,xn>
  • 推广：三元组<<x,y>,z>是一个序偶，其第一个元素本身也是一个序偶。也可记作<x,y,z> 不可记作<x,<y,z>第一元素可以是多个，第二元素只能是一个。
• 2.笛卡尔积
  • 结论：|A|=m；|B|=n；则|A×B|=mn 笛卡尔积运算不满足交换律和结合律 笛卡尔积运算对于交和并满足左右分配律A×(BUC)=(A×B)U(A×C)
  • N个集合笛卡尔积：n元组
  • 定义：设A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样的序偶组成的集合，称为笛卡尔积（直积）记作A×B A=a b c B=1 2 A×B={<a,1><a,2><b,1><b,2><c,1><c,2>}
• 3.定义
  • • 由序偶出发：任一序偶的集合确定了一个二元关系R，R中任一序偶<x,y>可记作<x,y>∈R或 xRy Eg、大于关系：R={<x,y>|x,y∈N且x>y}
  • 设X和Y是任意两个集合，直积X×Y的子集R称作X到Y的二元关系。 若X=Y，则称R为X上的二元关系。 X×Y={<a,1><a,2><b,1><b,2><c,1><c,2>}
• 4.关系的域
  • 设R为二元关系，由<x,y>∈R的所有x构成的集合domR称为R的前域。由<x,y>∈R的所有y构成的集合domR称为R的值域。R的前域和值域构成R的域，记作FLD R 。
• 5.定理：若R和S是从集合x到y的两个关系，则rs的交并补差仍是x到y的关系
• 6.关系的性质
  • 对称性
    • R 在X上对称  (x)(y)(x属于X∧yX∧xRy→yRx)
  • 自反性
    • R 在X上自反  (x)(x属于X→xRx)
  • 反对称
    • R 在X上反对称  (x)(y)(x属于X∧y属于X∧xRy∧yRx→x=y)
  • 反自反
    • R 在X上反自反  (x)(x属于X→属于R)
  • 传递性
    • R 在X上传递  (x)(y)(z)((x属于X∧y属于X∧z属于X∧xRy∧yRz)→xRz)
  • 关系的矩阵表示
    • 对称性
      • 关于对角线"\"对称
    • 自反性
      • 对角线"\"bool值全为真
    • 反对称
      • 非主对角线"\"上的每个"1"对称点都是"0"
    • 反自反
      • 主对角线全是0
• 7.复合关系
  • 定义：设 R 为X到Y的关系，S 为Y到Z的关系，则 R○S 称 为 R 和 S 的复合关系，表示为 R○S 。
  • 从 R 和 S，求 R○S，称为关系的合成运算
  • 前个关系中序偶的第二元素和后个关系中序偶的第一元素 一致
  • 规律
    • 不满足交换律
    • 满足结合律
• 8.逆关系
  • 定义：设 R 为X到Y的二元关系，如将 R 中每一序偶的元 素顺序互换，所得到的集合称为 R 的逆关系。记作 Rc 。（把x和y调换位置）Rc = {<y,x>|<x,y>∈R}
  • 逆关系的性质
  • 关系的n次幂
    • 设 R 是A上的二元关系，n为自然数，R 的n次幂记 为 Rn，定义为： (1) R∧0 = IA； (2) R∧(n+1) = R∧n○Rc //IA=<x,x>(A上的恒等关系）
    • 性质
      • 由定义可以看出，A上的任何二元关系的0次幂都相等， 等于A上的恒等关系IA。 由定义还可以看出： R1 = R0○R = IA○R = R R2 = R1○R = R○R R3 = R2○R = (R○R)○R
    • 复合关系和逆关系的结合
      • 定理
        • 定理: 设 R是A到B的关系，S是B到C的关系， 则 (R○S) c = S c○Rc
      • 注意
        • 子主题
          • 复合关系的逆等于它们逆关系的反复合 而 (R○S) c≠ Rc○S c 因 Rc是B到A的关系，S c是C到B的关系