Skip to content

离散数学基础:关系

思维导图

关系

笛卡尔积

定义

A×B={a,b|aAbB}

性质

笛卡尔积运算不满足交换律
笛卡尔积运算不满足结合律
笛卡尔积运算对集合交有分配律
笛卡尔积运算对集合并有分配律

二元关系

描述

集合AB的二元关系是笛卡尔积A×B的子集
集合A上的二元关系是集合A到自己的二元关系

定义

RA×B
RA×A

描述

ab有关系R
a R b
a,bR
ab没有关系R
a  b
a,bR

备注:本课程的关系只考察二元关系

空关系

定义

全关系

定义

A×B

恒等关系

or 对角关系

定义

ΔA={<a,a>|aA},  A

关系矩阵

自反关系

定义

aA, <a,a>∈R

关系矩阵

ΔAR

反自反关系

定义

aA, <a,a>∉R

关系矩阵

ΔAR=

对称关系

定义

a,bA, a,bR<b,a>∈R

关系矩阵

R=R1

反对称关系

定义

a,bA, (a,bR)(<b,a>∈R)a=b

关系矩阵

RR1ΔA

备注

传递关系

定义

a,b,cA, (a,bR)(<b,c>∈R)<a,c>∈R

关系矩阵

RR1R

等价关系

定义

R是自反的、对称的、传递的

等价类

  • 描述

-

a所在的等价关系R的等价类,简称a的等价类
  • 定义

-

[a]R={xA|<a,x>∈R}

代表

b[a]R,则称b为等价类[a]R的一个代表

商集

  • 描述

-

集合A关于等价关系R的商集是集合A的所有等价类构成的集合
  • 定义

-

A/R={[a]R|aA}
  • 基本性质

-

商集是一个集合族且是A的划分其中每一个元素都是等价类每个等价类都是这个划分的一个划分块

偏序关系

定义

R是自反的、反对称的、传递的

符号

经典例子

  • 数集上的 小于或等于关系、大于或等于关系

  • 集合的子集关系

    • 整数集上的整除关系

可比

(ab)(ba)

不可比

(a⪯̸b)(b⪯̸a)

覆盖

b覆盖a(ab)!c(accb)

极大元

aA的极大元bA(abb=a)

极小元

aA的极小元bA(bab=a)

最大元

aA的最大元bA(ba)

最小元

aA的最小元bA(ab)

偏序集

定义

(A,)  or  abbreviated as A

全序

or 线序

定义

偏序集A的任意两个元素都可比,则这个偏序集是全序或线序

关系举例-幂集上的:

真包含关系

  • 反自反、反对称、传递

恒等关系

  • 自反、对称、反对称、传递

全关系

  • 自反、对称、传递

空关系

  • 反自反、对称、反对称、传递