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

一、有序组

有序组

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

“有序”的含义?

定理:

对于任意序偶<a,b>, <c,d>,<a,b>=<c,d>当且仅当a=c且b=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},{a,b}}的巧妙定义 利用元素和集合的两个不同层次实现 两个对象a,b的有序排列

n元有序组的定义

  • n元有序组(n-tuple)
  • 递归定义:

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

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

二、 笛卡儿积

集合的一种运算

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

    A1×A2 = { | 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×∅=∅×A=∅
  •  R2={|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)

    ∈A×(B∪C) ⇒ x∈A∧y∈(B∪C) ⇒ x∈A∧(y∈B∨y∈C) ⇒ (x∈A∧y∈B)∨(x∈A∧y∈C) ⇒(∈A×B)∨(∈A×C) ⇒ ∈(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}(描述法)

小于关系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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学