离散数学[6]-集合论-关系基本概念

一、有序组

有序组

•  元素的有序组合如何从集合定义?
• 二元有序组，或者二元组(2-tuple)， 或者序偶(ordered pairs)
•  设a,b为任意对象，称集合族 {{a},{a,b}}为二元有序组，简记为 <a,b> 称a为<a,b>的第一分量，b为第二分量

“有序”的含义?

定理:

对于任意序偶<a,b>, <c,d>，<a,b>=<c,d>当且仅当a=c且b=d

• 充分性是显然的

• 证明必要性:设<a,b>=<c,d>，也就是

  {{a},{a,b}}={{c},{c,d}} ⇒∪{{a},{a,b}}=∪{{c},{c,d}} ⇒ {a,b}={c,d} 以及，{{a},{a,b}}={{c},{c,d}} ⇒ ∩{{a},{a,b}}= ∩{{c},{c,d}}  {a}={c} 综合两式，有a=c且b=d

  当a≠b时:<a,b>≠<b,a> 但{a,b}={b,a} 有序组{{a},{a,b}}的巧妙定义 利用元素和集合的两个不同层次实现 两个对象a,b的有序排列

n元有序组的定义

• n元有序组(n-tuple)<a1,…,an>

• 递归定义:

  n=2时，<a1,a2>={{a1},{a1,a2}} n>2时，<a1,…,an>=«a1,…,an-1>, an> ai称为n元组的第i分量

• 定理:对于任意n元组 <a1,…,an>=<b1,…,bn> 当且仅当 a1=b1,…,an=bn

二、 笛卡儿积

集合的一种运算

• 对任意集合A1,A2,…,An，A1×A2称作集合 A1，A2的笛卡儿积，定义如下:

  A1×A2 = {<u,v> | u∈A1,v∈A2} A1×A2×… ×An =(A1×A2×… ×An-1) ×An 例子:A={1,2}，B={a,b}，则: A×B等于{<1,a>, <1,b>, <2,a>, <2,b>} B×A等于{<a,1>, <a,2>, <b,1>, <b,2>}

笛卡儿积例子

• A×∅=∅×A=∅
•  R2={<x,y>|x,y是实数}，R2为笛卡儿平面
• R3为三维笛卡儿空间 笛卡尔是解析几何创始人，首次用三元组表示空间 中的点，统一了代数与几何
• 一般来说:
• A×B≠B×A(不满足交换律)
• A×(B×C) ≠(A×B)×C(不满足结合律)

笛卡儿积对集合运算的分配律

• 定理:设A,B,C为任意集合，$表示∪,∩或 -运算，那么:A×(B$C)=(A×B)$(A×C)， (B$C)×A=(B×A)$(C×A)

• 证明: A×(B∪C)=(A×B)∪(A×C)

  <x,y>∈A×(B∪C) ⇒ x∈A∧y∈(B∪C) ⇒ x∈A∧(y∈B∨y∈C) ⇒ (x∈A∧y∈B)∨(x∈A∧y∈C) ⇒(<x,y>∈A×B)∨(<x,y>∈A×C) ⇒ <x,y>∈(A×B)∪(A×C)

笛卡儿积的基数

定理:对于任意有限集合A1,…,An ，有 |A1×…×An|=|A1|…|An|

三、关系定义

关系的基本概念

• 关系是各个对象之间的联系和对应
• 最常见到是两组对象之间的联系和对应    例如：职员-部门的隶属关系
• 也有三组或者更多对象之间的联系和对应 供应商-工程-零件的供应关系
• 采用二元组或者多元组的集合来表示关系 ED={<张三,人事部>,<李四,销售部>,<王五,技术部 >} SPJ={<公司甲,大楼,水泥>,<公司甲,公路,水泥>,< 公司乙,大楼,钢筋>,<公司丙,公路,沥青>}

关系的定义

• R称为集合A1,A2,…,An-1到An的n元关系， 如果R是A1×A2×…×An的一个子集。当 A1=A2=…=An-1=An时，也称R为A上的n 元关系
• 如果R是A×B的一个子集，称R是A到B的二元关系，如果R是A×A的一个子集，则称R 是A上的二元关系
• 我们主要研究二元关系

关系的例子

• 自然数的相等关系 EN={<0,0>,<1,1>,<2,2>,…}(列举法)
• 整除关系D={<x,y>|x整除y}(描述法)

小于关系L:归纳法

〉 基础条款:<0,1>∈L
〉 归纳条款:若<x,y>∈L，则<x,y+1>∈L， <x+1,y+1>∈L
终极条款：略

几个特殊的二元关系

〉 空关系 ， A×B，称 为A到B 的空关系
〉 全关系A×B，笛卡儿积A×B是A到B 的全关系
〉 相等关系EA={<x,x>|x∈A}，称作A 上的相等关系

关系的几个概念

〉 定义:设R为A到B的二元关系(R A×B)
〉 xRy表示<x,y>∈R， ¬xRy表示<x,y>!R 〉 R的定义域domain:
〉 Dom(R)={x|x∈A∧ y(<x,y>∈R)}
〉 R的值域range:
〉 Ran(R)={y|y∈B∧ x(<x,y>∈R)} 〉 称A为R的前域，B为R的陪域

关系的表示法

集合表示法

〉 R={<x,y>|P(x,y)}
〉 适合于表示集合的几种方法均可，如前面的 关系例子
〉 关系图法
〉 前域和陪域都是有限集合
〉 一般的关系图，有向箭头表示元素之间存在 关系
〉 可以表示前域和陪域相同的关系图

前域和陪域不同的关系图

前域和陪域相同的关系图

关系矩阵法表示

〉 前域和陪域都是有限集合
〉 设关系R A×B，A={a1,...,am}， B={b1,...,bn}
〉 关系R的关系矩阵MR的定义: 〉 mij=1当且仅当aiRbj
〉 mij=0当且仅当¬aiRbj

关系矩阵例子

关系基本运算

运算基本定义

〉 关系相等
〉 如果关系R和S具有相同的前域和陪域，并且#x#y(xRy↔xSy)
〉 关系运算中的前域和陪域
〉 R A×B，A为前域，B为陪域
〉 参与关系运算的两个关系应该具有相同的前 域和陪域
这个条件不是本质的，因为总可以对关系的前域和 陪域做适当的扩充，使之满足条件

作为集合的关系运算

〉 〉 〉 〉 〉

R和S为A到B的二元关系，R,S A×B

并:R∪S={<x,y>|xRy∨xSy}
交:R∩S={<x,y>|xRy∧xSy}
差:R-S={<x,y>|xRy∧¬xSy}
补:R-=A×B-R={<x,y>| ¬xRy}
并不是全集U-R，而是全关系与R的差

对应的关系矩阵运算

〉 MR和MS为R、S的关系矩阵
〉 并:MR∪S=MR∨MS(矩阵对应分量做析取) 
〉 交:MR∩S=MR∧MS(矩阵对应分量做合取) 
〉 补:MS-=(MS)-(矩阵对应分量做否定)
〉 差:MR-S=MR∩S-=MR∧MS-

关系逆运算(converse)

〉 R~={<y,x>|xRy}，R A×B
〉 显然，R的逆关系是B到A的关系:R~B×A
〉 逆关系关系矩阵的运算:MR~=MRT，矩阵 转置
〉 逆运算例子
EA~=EA; ~= ;(A×B)~=B×A 自然数“小于<”关系的逆关系是“大于>” 自然数“小于<”关系的补关系是“大于或等于≥”

关系逆运算的性质

〉 R,S A×B，$代表并交差运算之一
〉 R~~=R(两次逆复原)
〉 R~-=R-~(逆的补等于补的逆)
〉 (R$S)~=R~$S~(对并交叉运算分配律)
〉 R S当且仅当R~ S~
〉 从矩阵转置角度来看，表现为转置运算不会 改变矩阵分量的值

关系合成运算

关系合成运算(composition)

R为A到B的二元关系，R A×B

〉 S为B到C的二元关系，S B×C
〉 R和S的合成关系R∃S定义为:
〉 R∃S={<x,z>|x∈A∧z∈C∧ y(y∈B∧xRy∧ySz)}
〉 简化形式: R∃S={<x,z>| y(xRy∧ySz)}
〉 R∃S A×C，是A到C的二元关系
〉 由于参与合成的第一个关系的陪域要等于第二个
关系的前域，所以合成关系不满足交换律

关系合成运算的例子

设EA是A上的相等关系，EB是B上的相等关系，R A×B

〉 EA∃R=R∃EB=R
〉 ∃R=R∃ =
〉 R∃R~=EA(A×B，B×A)
〉 {<x,x>| y(xRy∧yRx)}
〉 R~ ∃R=EB(B×A，A×B)
〉 {<y,y>| x(yRx∧xRy)}
〉 兄弟关系和父子关系的合成是“叔侄”关系

用关系图表示合成运算

用关系矩阵表示合成运算

〉 关系合成运算对应关系矩阵的乘法 
〉 将数乘换成合取，将数加换成析取 〉 设|A|=m，|B|=n，|C|=p，
〉 R A×B，S B×C，
〉 则MR=[rij]m*n， MS=[sij]n*p
〉 T=R∃S，有T A×C，
〉 MT=MR*MS=[tij]m*p
〉 其中tij=∨k=1..n(ri,k∧sk,j)(i=1,..,m;j=1,..,p)

合成运算的性质

R∃(S∪T)=(R∃S)∪(R∃T)(左分配律)

〉 (S∪T)∃R=(S∃R)∪(T∃R)(右分配律) 
〉 x(A(x)∨B(x))╞╡ xA(x)∨ xB(x)
〉 R∃(S∩T) (R∃S)∩(R∃T)
〉 (S∩T)∃R (S∃R)∩(T∃R)
〉 x(A(x)∧B(x))╞ xA(x)∧ xB(x)
〉 (R∃S)~=S~∃R~
〉 R∃(S∃T)=(R∃S)∃T(结合律，下页证明)

证明R∃(S∃T)=(R∃S)∃T

〉 <x,y>∈R∃(S∃T)
〉 u(<x,u>∈R∧<u,y>∈S∃T)
〉 u(<x,u>∈R∧ v(<u,v>∈S∧<v,y>∈T)) 
〉 xA(x)∧B╞╡ x(A(x)∧B)
〉 v u(<x,u>∈R∧<u,v>∈S∧<v,y>∈T) 
〉 v( u(<x,u>∈R∧<u,v>∈S)∧<v,y>∈T) 
〉 v(<x,v>∈R∃S∧<v,y>∈T)
〉 <x,y>∈(R∃S)∃T

关系的幂运算Rn

定义为自身的n次合成

〉 Rn=R∃...∃R(n个R合成)
〉 R0=EA
〉 幂运算的性质
〉 Rm ∃ Rn=Rm+n
〉 (Rm)n=Rmn
〉 可以把m看作参数，对n进行归纳法证明

幂关系有限定理

设集合A的基数为n，R是A上的二元关系， 则存在自然数i,j使得0≤i<j≤2n2，有Ri=Rj

〉 证明:
〉 R的任意次幂运算仍是A上的二元关系
〉 有限集A上不同的二元关系数量是有限的
〉 因为R A×A，而A×A子集的个数有限
〉 如果|A|=n，A上的二元关系的数量是2n2
〉 根据“鸽笼原理”，在0~2n2共计2n2+1 个R的幂关系中，一定有两个是相同的

关系基本特性

A上一些特殊性质的二元关系

〉 自反关系(reflexive)
〉 #x(x∈A→xRx)
〉 关系图:每个节点都有环
〉 关系矩阵:对角线全为1
〉 反自反关系(irreflexive)
〉 #x(x∈A→ ¬xRx)
〉 关系图:每个节点都没有环 〉 关系矩阵:对角线全为0

〉 对称关系(symmetric)
〉 #x#y(x,y∈A∧xRy→yRx)
〉 关系图:两个节点之间有边的就有反向边 〉 关系矩阵:对称矩阵
〉 反对称关系(antisymmetric)
〉 #x#y(x,y∈A∧xRy∧yRx→x=y)
〉 关系图:两个节点之间只能有一条单向边 〉 关系矩阵:ci,j=1(i≠j)时cj,i=0

〉 传递关系(transitive)
〉 #x#y#z(x,y,z∈A∧xRy∧yRz→xRz)
〉 关系图:如果有边v1v2,...,vn-1vn，则有边v1vn 〉 例子:
〉 设A={1,2,3}，R是A上的二元关系
〉 R={<1,1>,<1,3>,<2,2>,<3,3>}是自反的
〉 R={<1,3>,<3,1>}是反自反的，不是自反的 〉 R={<1,1>}不是自反，也不是反自反

特殊性质二元关系的例子

A上的空关系 是反自反的，不是自反的

〉 如果A= ，那么A上的空关系就是自反的， 同时也是反自反的 因为注意定义谓词的前件x∈A始终为假
〉 R={<1,3>,<3,1>,<1,2>,<1,1>}不是对 称的，也不是反对称的
〉 R={<1,2>,<2,1>}是对称的
〉 R={<1,2>,<3,1>}是反对称的
〉 A上的相等关系EA既是对称的，又是反对称 的

R={<1,2>,<2,3>,<1,3>,<3,3>} 是 传 递 的 ， 但R- {<1,3>}不是传递的

〉 空关系 是传递的，R={<1,2>,<1,3>}也是传递的， 因为它们使得传递定义的前件为假
〉 所有非空集合上的: 空关系都是反自反、对称、反对称、传递的; 全关系是自反，对称，传递的; 相等关系是自反，对称，反对称，传递的;
〉 整数集合上的整除关系是自反、反对称、传递的;
〉 三角形的相似关系、全等关系都是自反、对称、传递的

关系特性定理

关系特性的一些定理

R自反当且仅当EA R

〉 R反自反当且仅当EA∩R
〉 R对称当且仅当R R~
〉 设R对称，则:
〉 <x,y>∈R <y,x>∈R <x,y>∈R~ 〉 设R R~，则:
〉 xRy xR~y yRx，所以R对称

R反对称当且仅当R∩R~ EA

〉 设R反对称，则:
〉 <x,y>∈R∩R~ <x,y>∈R∧<x,y>∈R~ 〉 <x,y>∈R ∧<y,x>∈R x=y
〉 <x,y>∈EA
〉 设R∩R~ EA，由<x,y>∈R ∧<y,x>∈R 〉 <x,y>∈R ∧<x,y>∈R~
〉 <x,y>∈ R∩R~ <x,y>∈EA
〉 x=y，所以R是反对称

R传递当且仅当R2 R

〉 设R传递:
〉 <x,y>∈R2
〉 u(xRu ∧uRy) u(xRy) <x,y>∈R
〉 设R2 R:
〉 xRy ∧yRz xR2z xRz，所以R传递

关系基本特性的运算封闭性

具有某特性的关系，在运算后，运算结果是否保持这个特性，称为运算封闭性

〉 所有5个特性对交运算封闭，即如果R1、R2都具有某个特性，则R1∩R2仍具有 这个特性:
〉 例证:对称性，xR1∩R2y xR1y ∧xR2y yR1x ∧yR2x yR1∩R2x
〉 自反、反自反、对称性对并运算封闭
〉 例证:自反性，xR1x xR1x ∨xR2x xR1∪R2x(并不要求R2具有特性)
〉 反自反、对称、反对称对差运算封闭
〉 例证:反对称:xR1-R2y∧yR1-R2x xR1y∧yR1x x=y
〉 实际上，只要R1反对称，任何R2，R1-R2都是反对称的

关系基本特性的运算封闭性

对称性对补运算封闭

〉 xR-y，假设¬yR-x，那么yRx，即xRy，和已知矛盾，所以有yR-x
〉 所有5个特性对求逆运算均封闭
〉 例证:传递，xR~y ∧ yR~z
〉 yRx ∧zRy zRx xR~z
〉 自反对合成运算封闭，其它性质对合成运算 均不封闭:
〉 xR1x ∧xR2x xR1∃R2x

参考资料

北京大学地球与空间科学学院 陈斌

https://www.coursera.org/learn/dmathgen/supplement/MGstj/ke-jian