4.5 等价关系

  • 「等价关系」 使用符号 \equiv 表示任意一个等价关系,并且:

    1. xxx \equiv x。关系 \equiv 是自反的。
    2. 如果 xyx \equiv y,那么 yxy \equiv x。关系 \equiv 是对称的。
    3. 如果 xyx \equiv yyzy \equiv z,那么 xzx \equiv z。关系 \equiv 是传递的。

      集合 SS 上的关系 \equiv,称为 SS 上的等价关系,当且仅当它在 SS 上是对称的、自反的、传递的。

  • 『确定等价性』 可以使用等价关系将集合 SS 划分为等价类,SS 的两个元素 xxyy 属于同一等价类,当且仅当 xyx \equiv y。例如,有 12 个编号为 0 至 11 的数有如下等价关系: 04,31,610,89,74,68,35,211,110 0 \equiv 4, 3 \equiv 1, 6 \equiv 10, 8 \equiv 9, 7 \equiv 4, 6 \equiv 8, 3 \equiv 5, 2 \equiv 11, 11 \equiv 0 那么,作为关系 \equiv 的自反性、对称性和传递性的结果,能够将这 12 个数划分成下列等价类: {0,2,4,7,11};{1,3,5};{6,8,9,10} \{0, 2, 4, 7, 11\}; \{1, 3, 5\}; \{6, 8, 9, 10\} 确定等价类的算法分两个阶段。第一个阶段,读入并存储等价对 <i,j><i, j>。第二个阶段,从 00 开始,找到所有形如 <0,j><0, j> 的等价对,其中,00jj 属于同一等价类。利用传递性,所有形如 <j,k><j, k> 的等价对说明 kk00 属于同一等价对。按照这种方式继续,直到找到(或标记、输出)含有 00 的所有等价类为止。然后继续。

results matching ""

    No results matching ""