离散数学-集合论-关系的闭包、等价关系与划分和偏序关系（9）

系统管理员 2024-03-29 14:37 18阅读 0赞

### 关系的闭包、等价关系与划分和偏序关系 ###

### 1 关系的闭包 ###

定义:设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R’,使得R‘满足以下条件：  
（1）R’是自反的（对称的或传递的）  
（2） R ⊆ R ’ R\\sube R’ R⊆R’  
（3）对A上任何包含R的自反（对称或传递）关系R’'，有 R ′ ⊆ R ′ ′ R'\\sube R'' R′⊆R′′,R的自反闭包记作 r ( R ) r(R) r(R),对称闭包记作 s ( R ) s(R) s(R),传递闭包记作 t ( R ) t(R) t(R)。  
一般将R的自反闭包记作 r ( R ) r(R) r(R),对称闭包记作 s ( R ) s(R) s(R)  
,传递闭包记作 t ( R ) t(R) t(R)。  
定理：设R为A上的关系，则有：  
（1） r ( R ) = R ∪ R 0 r(R)=R∪R^0 r(R)=R∪R0  （ R 0 = I A ） （R^0=I\_A） （R0=IA）  
（2） s ( R ) = R ∪ R − 1 s(R)=R∪R^\{-1\} s(R)=R∪R−1  
（3） t ( R ) = R ∪ R 2 ∪ R 3 ∪ ⋅ ⋅ ⋅ ⋅ t(R)=R∪R^2∪R^3∪···· t(R)=R∪R2∪R3∪⋅⋅⋅⋅  
例如：给定A=\{1，2，3，4\}和A上的关系R=\{<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>\}，求R的自反闭包、对称闭包和传递闭包。  
解：  
 r ( R ) r(R) r(R)=R∪ I A I\_A IA  
=\{<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>\}∪\{<1,1>,<2,2>,< 3,3>.<4,4>\}  
=\{<1,1>,<2,2>,< 3,3>.<4,4>,<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>\}  
 s ( R ) s(R) s(R)=R∪ R − 1 R^\{-1\} R−1  
=\{<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>\}∪\{< 3,1>,<4,1>,< 3,2>,<4,2>,<4,3>\}  
=\{< 3,1>,<4,1>,< 3,2>,<4,2>,<4,3>,<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>\}  
 t ( R ) t(R) t(R)= R ∪ R 2 R∪R^2 R∪R2  
=\{<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>\}∪\{<1,4>,<2,4>\}  
=\{<1,3>,<1,4>,<2,3>,<2,4>,< 3,4>,<2,4>\}

![在这里插入图片描述][cd79dbf6f7b042eb8d5ebc569ecc19a0.png]

### 2 等价关系和划分 ###

定义1：等价关系  
设R为非空集合A上的关系，如果R是**自反的、对称的和传递的**，则称R为A上的**等价关系**，设R是一个等价关系，若<x,y>∈R，称x等价于y，记作x~y。  
![在这里插入图片描述][e633e031d08047d0b96bc2eddf571c1b.png]

定义2：等价类  
设R为非空集合A上的等价关系， ∀ x \\forall x ∀x∈A，令  
 \[ x \] R = （ y ∣ y ∈ A ∧ x R y \[x\]\_R=（y|y∈A\\land xRy \[x\]R=（y∣y∈A∧xRy  
称\[x\]\_R为关于R的等价类，简称为x的等价类，简记\[x\]或 x ˉ \\text\{\\=\{x\}\} xˉ。  
![在这里插入图片描述][13bca12e04aa4d40a28f49212c93ddfa.png]  
定义3：商集  
设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的**商集**，记作A/R，即：  
 A / R = \[ x \] R ∣ x ∈ A A/R=\{\[x\]\_R|x∈A\} A/R=\[x\]R∣x∈A  
![在这里插入图片描述][95dc1a728669467fa384e5b014e0defa.png]  
定义4：集合的划分  
![在这里插入图片描述][4aff9cffdd8143f898b96a5e217a4853.png]  
![在这里插入图片描述][88fb94c0d1fc467f82d74915e21cee78.png]

### 3 偏序关系 ###

![在这里插入图片描述][f758c00f10034c209897df2135ae1e8d.png]  
![在这里插入图片描述][89e75866ea2e4ca3bd2523f19dfdae87.png]  
![在这里插入图片描述][f506d0f6139546bc822f90b361b0696d.png]  
![在这里插入图片描述][57ba862db9ad4f0b8a02f124de0eed40.png]  
![在这里插入图片描述][aa2bfabc15464189af625935c2ca269e.png]  
![在这里插入图片描述][00f7d5353edd4bd098693780b5e6f19e.png]  
![在这里插入图片描述][1a3a5fdb41a84c549f2ab4b6af9d9f1e.png]  
![在这里插入图片描述][6517f679aee54793900d065ed1cd193e.png]

[cd79dbf6f7b042eb8d5ebc569ecc19a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/83e65abd6ea24c4d9bc1059bd4e688e0.png
[e633e031d08047d0b96bc2eddf571c1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c4eb05cef1854d78a2ec36720e276fd1.png
[13bca12e04aa4d40a28f49212c93ddfa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/05aa4f19621e4e77979e9cb00eeb8f57.png
[95dc1a728669467fa384e5b014e0defa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/051a9c6084ca406aa53a22ca5e323feb.png
[4aff9cffdd8143f898b96a5e217a4853.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/42575c0207404569879de9df21bc5bfd.png
[88fb94c0d1fc467f82d74915e21cee78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/1961f5fd5c8745bfa837d87f04dc6a1f.png
[f758c00f10034c209897df2135ae1e8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/9240e7f79a30453482dafdefccac3866.png
[89e75866ea2e4ca3bd2523f19dfdae87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ad1b082db75f48a4ad7a364cca7839e8.png
[f506d0f6139546bc822f90b361b0696d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c6e871d2f2574303a91772709e6c83ac.png
[57ba862db9ad4f0b8a02f124de0eed40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/e8b54bf652c247faaa49279a3f7415da.png
[aa2bfabc15464189af625935c2ca269e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/a8ec0317fe2a49d387f34edf668a20cf.png
[00f7d5353edd4bd098693780b5e6f19e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/8fdafe0956e34bc1926646da2d07bf0c.png
[1a3a5fdb41a84c549f2ab4b6af9d9f1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/91498a2687224589ace589c7fa31e64c.png
[6517f679aee54793900d065ed1cd193e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/f67444692edb44fc9842538c45b94164.png