离散数学作业
作业6 ——等价关系
1. 设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。
（1）R∩S （2）R∪S （3）r (R-S)
（4）R- S （5）R◦S （6）R2
解：(1),(6)正确，其余错误。
2. R是集合A上的二元关系， a,b,c ,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。
分析: 需要证明两部分:
(1)已知R是自反和循环的，证明:R是一等价关系
(2)已知R是一等价关系, 证明R是自反和循环的.
证明：（1）先证必要性。只需要证明R是对陈的和传递的。
任取(x,y)∈R。因为R是自反的，所以(y,y)∈R。由R是循环的可得(y,x)∈R，即R是对陈的。
任取(x,y)，(y,z)∈R。因R是循环的，所以(z,x)∈R。由R对称性得(x,z)∈R，即R是传递的。
（2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)∈R，下证(z,x)∈R。由于R是传递的，所以(x,z)∈R。又由R是对称的得(z,x)∈R。所以R是循环的。
3. 设|A|=n，在A上可以确定多少个不同的等价关系？
解：2n!/((n+1)n!n!)
4. 给定集合S={ 1 , 2 , 3, 4, 5 }，找出S 上的等价关系R ，此关系R 能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。
解：{(1,2),(2,1),(4,5),(5,4)}S R I =⋃
5. 设A={1，2，3，4，5}。R 是集合A 上的二元关系，其关系矩阵如下图所示。求包含R 的最小等价关系和该等价关系所确定的划分。
⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0010001000
000000101000001R
M 分析: 可以证明tsr(R)是包含R 的最小等价关系.
解：包含R 的最小等价关系的矩阵表示如下：
100000
1010001010
101000101⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭
上述等价关系确定的划分为{{1},{2,4},{3,5}}.
6. 自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个
求解传递闭包的具体实例，并可清晰讲解算法整体实现过程。
7. （选做题）设R 与S 是A 上的等价关系，证明：
（1）R S 是A 上的等价关系，iff R S=S R ；
（2）R ∪S 是A 上的等价关系，if R S ⊆S 且 S R ⊆R.
分析: iff 是if and only if 的缩写, 是当且仅当的意思.
证明：（1）先证必要性。任取(x,z)∈R S ，则存在y 使得xRy,ySz 。因为R 与S 是A 上的等价关系，所以R 与S 是对陈的，即yRx,zSy,所以
(z,x) ∈S R 。因此，R S ⊆S R 。
任取(x,z)∈S R ，则存在y 使得xSy,yRz 。由R 与S 是对陈的得ySx,zRy ，即(z,x) ∈R S 。又因为R S 是对陈的，所以(x,z) ∈R S ，即S R ⊆ R S 。
综上R S=S R ，必要性得证，下面证充分性。 因为I A ⊆R ，I A ⊆S ，所以I A ⊆R S ，即R S 是自反的。 任取(x,z)∈R S ，则存在y 使得xRy,ySz 。由R 与S 是对陈的得yRx,zSy ，即(z,x)∈S R 。因为R S=S R ，所以(z,x)∈R S ，即R S 是对陈的。
因为
222()()()()()R S R S R S R S R S R R S S
R S R S ====⊆
所以R S 是传递的。
综上，R S 是等价关系，充分性得证。
（2） 因为I A ⊆R ，I A ⊆S ，所以I A ⊆R ∪S ，即R ∪S 是自反的。 由111()R S R S R S ---⋃=⋃=⋃得，R ∪S 是对陈的。 由2()()()()()()()
R S R S R S R R S S R S S R R S S R R S ⋃=⋃⋃=⋃⋃⋃⊆⋃⋃⋃⊆⋃ 得 R ∪S 是传递的。
综上，R ∪S 是等价关系。
