【集合论】二元关系 ( 定义域 | 值域 | 域 | 逆运算 | 逆序合成运算 | 限制 | 像 | 单根 | 单值 | 合成运算的性质 )

2023-03-28 18:01:20 浏览数 (2)

文章目录

  • 一、关系的定义域、值域、域
  • 二、关系的定义域、值域、域 示例
  • 三、关系的逆运算
  • 四、关系的逆序合成运算
  • 五、关系的限制
  • 六、关系的象
  • 七、单根
  • 八、单值
  • 九、合成运算的性质

一、关系的定义域、值域、域

R

是一个任意集合

定义域 ( Domain ) :

dom R = { x | exist y (xRy) }

存在

y

,

x

与

y

有

R

关系 ,

R

关系是一个集合 , 集合中的元素是有序对 ,

xRy

是

<x,y>

有序对 ;

R

中的有序对 , 第一个元素是

x

, 第二个元素是

y

, 那么可以将该

x

放入定义域中 ;

R

关系中所有的有序对的第一个元素拿出 , 构成一个定义域 ;

值域 ( Range ) :

ran R = { y | exist y (xRy) }
R

关系中所有的有序对的第一个元素拿出 , 构成值域 ;

域 ( Field ) :

fld R = dom R cup ran R

域 是 定义域 和 值域的并集 ;

二、关系的定义域、值域、域 示例

1.

R_1 = {a, b}
R_1

中没有有序对 , 因此其 定义域 , 值域为空 , 进而其 域 也为空 ;

dom R_1 = varnothing
ran R_1 = varnothing
fld R_1 = varnothing

2.

R_2 = { a, b, <c, d> , <e,f> }
dom R_2 = { c, e }
ran R_2 = { d, f }
fld R_2 = { c, d, e , f}

3.

R_3 = { <1,2>, <3, 4> , <5,6> }
dom R_3 = { 1, 3, 5 }
ran R_3 = { 2, 4, 6 }
fld R_3 = { 1, 2, 3, 4,5, 6}

三、关系的逆运算

任意集合

F , G

, 这里两个集合是关系 , 集合中的元素是有序对

逆运算 ( Inverse ) :

F^{-1} = { <x, y> | yFx }

将

F

关系中的所有有序对中的元素 , 前后调换方向 , 有序对中第一个元素变为第二个元素 , 第二个元素变为第一个元素 ;

如 : 将

yFx

, 是

<y, x>

有序对 , 变成

<x, y>

有序对 ;

四、关系的逆序合成运算

逆序合成 ( Composite ) :

FoG = { <x, y> | exist z ( xGz land zFy ) }

如果 关系

G

中有

<x,z>

有序对 , 关系

F

中有

<z, y>

有序对 , 就可以得到一个新的有序对

<x,y>

, 该新的有序对在 关系

F

和 关系

G

的合成 运算结果中 ;

这种合成是 逆序合成 , 先用

FoG

中的后面的

G

关系的有序对 , 然后再用 前者

F

中的有序对 ;

逆序合成 与之对应的是顺序合成 , 一般情况下使用逆序合成 , 其性质使用方便 ;

五、关系的限制

对于任意集合

F, A

, 可以定义

F

集合在

A

集合上的 限制 ( Restriction ) :

F upharpoonright A = { <x, y> | xFy land x in A }

解析 :

F

集合是一个关系 , 其元素是 有序对

A

集合是普通集合 , 其元素就是单纯的单个元素 ;

F

集合中的 有序对 元素中 , 如果 有序对的 第一个元素 在

A

集合中, 那么将这个有序对挑出来 , 放到一个新的集合中 , 这个新集合就称为

F

集合在

A

集合上的 限制 , 记作

F upharpoonright A

;

上述 限制 ( Restriction ) 是限制 有序对中的第一个元素 ;

如果想要 限制第二个元素 , 将

F

集合中的有序对中的 第二个元素属于

A

的集合的有序对挑出来 , 可以将

F

关系进行逆运算 , 然后 求

F^{-1}

的限制 ;

限制的结果仍然是一个关系 , 其集合中的元素是有序对 ;

六、关系的象

对于任意集合

F, A

, 可以定义

F

集合在

A

集合上的 像 ( Image ) :

F(A) = ran(F upharpoonright A)

即 ,

F

在

A

集合上的 限制 ( Restriction ) 的值域 ;

另一种表示方式 :

F [A] = { y | exist x ( x in A ) land xFy }

将

F

中的 有序对 挑出来 , 然后挑出有序对中第一个元素在

A

集合中的有序对 , 将上述 有序对的第二个元素挑出来 , 放入新的集合中 , 这个集合就 是

F

在

A

集合上的 像 ;

像 的结果不是一个关系 , 而是 符合特定要求的 有序对集合 中的有序对的第二个元素组成的集合 ;

七、单根

任意集合

F

, 单根 ( Single Rooted ) 定义 :

F

是单根的

Leftrightarrow
forall y ( y in ran F to exist ! x( x in domF land xFy ) )
Leftrightarrow
( forall y in ran F )( exist ! x in domF )(xFy)

任何一个

y

,

y

是有序对中的值域中的元素 , 有序对中与

y

对应的值

x

元素 , 即

<x, y>

构成一个有序对 , 该

x

存在并且唯一 ;

有序对

<x, y>

中每个

y

都对应着不同的

x

一些谓词公式说明 :

exist !

表示 唯一存在 ;

forall x ( (x in A to B(x) )

可以缩写为

(forall x in A)B(x)
exist x ( x in A land B(x) )

可以缩写为

(exist x in A)B(x)

八、单值

任意集合

F

, 单值 ( Single Value ) 定义 :

F

是单值的

Leftrightarrow
forall x ( x in dom F to exist ! y( y in ranF land xFy ) )
Leftrightarrow
( forall x in dom F )( exist ! y in ranF )(xFy)

任何一个

x

,

x

是有序对中的定义域域中的元素 , 有序对中与

x

对应的值

y

元素 , 即

<x, y>

构成一个有序对 , 该

y

存在并且唯一 ;

有序对

<x, y>

中每个

x

都对应着不同的

y

九、合成运算的性质

R_1, R_2, R_3

是三个集合 , 则有以下性质 :

(R_1 o R_2) o R_3 = (R_1 o ( R_2 o R_3 ))
F, G

是两集合 , 有以下性质 :

(F o G)^{-1} = G^{-1} o F^{-1}

合成运算的逆 等于 两个集合逆的合成 ;

field image range 集合

0 人点赞