离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
50-等价关系与划分
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
134 个评分
从本节课中
集合论：特殊关系及函数
与讲师见面
陈斌副教授
北京大学
[音乐] 嗨，欢迎回来。
那么我们上一节呢，我们提到了这个等价关系以及
这个等价类，而且呢说明了等价类之间，它们有一种
类似于这种切蛋糕，所以呢它是说等价类要么之间，它们之间呢是完全重复，
或者呢，说等价类之间呢不会共享任何的这个元素。
所以呢我们就把这个切蛋糕这件事情， 再进行一个型化，更准确的一个说法，
所以引入了这个概念，叫做划分。
那什么叫划分呢？划分呢是集合 A 的一个子集族， 所以呢划分它首先是一个集合族。
那么其次呢，它的每一个成员都是 A 的一个子集，所以呢它叫做子集族，
那么一般我们用 π 来代表这个划分。
那我们来看看它满足什么样的条件呢？首先，第一 叫做不空。
什么是不空呢？就是它的成员 不可能是一个空集。
也就是说任意的 B ，B∈ π ，那么蕴含呢 B ≠ ∅。
也就空集不能够作为子集族 π 的一个成员。
第二个呢是把这个 π 呢进行广义并，然后正好等于 A。
也就是说它的这个子集族的成员取
一个大的一个并集之后，它恰好要能够完整的覆盖这个 A。
所以呢，称作为不漏，不被漏掉 A 当中的任何 元素。
第三呢，是任何 B ，任何的 B' ， B 呢是 B' 都属于 π。
那么，而且呢 B 和 B' 是不相等的话，那么就意味着 B 和 B' 的交集是空集。
那么这就是第三个，叫做不交，也就是子集族它的这个子集之间 不会有任何的这个交集。
所以呢划分呢是适合于
具有如下三个性质的这个子集族，也就是不空，不漏，不交。
那么我们就把这个 π 当中的这个元素，也就是 A 的子集，就称之为一个划分的一个单元，这个单元。
那么我们特别约定，如果 A 是空集的话，那么就只有一个空划分，就是空集。
我们来看看一些划分的例子。
比如说 A 呢等于{ 1, 2, 3, 4 }， 那么第一个 π1 那就等于{{ 1 },
{ 2 }, { 3 }, { 4 }}，那么都是单元集。
那我们发现它有不空，它没有空集在里头；
不交，它们之间的交集为空；不漏，它们的这个并集正好等于 A。
然后 π2 = {{ 1, 3 }, { 2, 4 }}， { 1, 3 }和{ 2,
4 }，那这也是一个划分的例子， 它的每一个单元也都符合不空，不交，不漏的这个特性。
π3 = {{ 1, 3, 4 },
{ 2 }}， 那么这个划分里头呢就有两个单元，它有两个单元。
那么还有呢 π4 ，就是{{ 1, 2, 3, 4 }}，就是把这个 A 呢，整个的放在这儿。
那当然，它的单元数为 1 ，它也是不空，不交，不漏的。
那么我们来看看如果是{{ 1, 2 },
{ 4 }}，它是不是一个划分呢？ 那么显然不是，因为它虽然满足不空，不交，
但是呢它不满足不漏，它漏了一个元素 3
，对吧？ 那么这一题，{{ 1, 2, 3 }, { 2,
4 }}， 请你在题目当中来选择一下。
然后很明显呢就是我们如果把
这个划分单元和这个等价关系的这个等价类来进行一个对比， 我们就能够知道这个等价关系
R 的所有的等价类，如果把它做成一个集合的话， 那么就正好能够构成 A 的一个划分。
因为等价类它正好满足，每个等价类它至少都有一个元素吧， 就是自身，所以呢，它满足不空；
那么等价类之间呢，它不会有共享的元素，所以呢它也不交；
那么等价类会覆盖所有的 A 当中的元素，所以它也不漏。
所以呢 A 上的等价关系所包含的所有的等价类，把它收集在一起形成一个集合族，
那么它显然就能够构成 A 上的一个划分。
那么我们就把这种划分就称作为是 等价关系 R 所对应的一个划分。
那么这个呢定义就是这样，所有的 x ∈ A ， 那么 x 的等价类，
x 作为代表元素的等价类，把它们所有都放在一起， 那么这样的一个集合，它就是一个划分。
那么这个呢就是 等价关系 R 所对应的一个划分。
那么反过来，因为这个划分的单元它满足不空，不交，不漏 这些它们之间的关系。
那么显然呢它也类似于这个等价类，所以呢 A 上的一个划分
π ，它也会对应 A 上的一个等价关系 R。
那么这个呢就称之为划分 π 所对应的 等价关系。
那么这个呢定义为，说 R 等于然后{< x,
y >}，然后这个 x 呢，和 y 呢是都是属于同一个划分单元， 同一个划分单元。
那这样呢我们就明白了， 它属于同一个划分单元的话，那么在等价关系里面它就会属于同一个
等价类，对吧？那么所以呢有另外一种表达方式，就是把这个
划分单元，每一个划分单元进行这个笛卡尔积，
笛卡尔积以后得到的这个二元组，把它全部进行一个
广义并，给它并在一起，那这样呢也 能够得到一个等价关系。
那么我们就把这种 由划分 π 所推出来的等价关系就称之为划分所对应的 等价关系。
那么现在我们正过去有等价关系 对应的划分 π
，那么反过来也有 划分 π 所对应的等价关系，那么我们显然就会
有一个疑问，它们是不是一一对应的呢？那 这个表述就是这样，对应
π 的等价关系为 R 的话，那么当且仅当 R 对应
的划分正好为 π，这个呢就表示它们一一对应。
那我们的结论是， 对，确实是这样的，等价关系和划分是一一对应的。
我们可以来证明这一点。
首先呢我们来证明一个必要性，也就是 从左到右。
我们先假设这个对应 π 的这个等价关系为 R ，
那么这个 R 呢它显然也会对应一个划分
π ， 那么我们就把这个划分呢记作为 π'。
那么现在我们要证明这个 π 是等于 π' ， 如果能够得到证明，那么好，这个必要性就完成了。
那我们就从这个 A 当中取出任意一个元素小
a ，那么这个小 a ，既然 π 是这个 A 的划分，那么小
a 呢肯肯定会属于，因为不漏嘛， 它肯定就是属于 π 当中的一个单元，某一个单元。
那我们就把这个包含 a 的单元就称作为 B ，包含 a 的单元 B ，B 是属于 π 的。
那么 π' 既然也是一个划分，那么它肯定也有某一个单元包含 了
a ，那么我们就把这个包含了 a 的单元就记作为 π'。
接下来如果我们能够证明说 B 等于 B' 的话，
那么我们就可以证明说，因为 a 的这个任意性， 所以 π 是等于 π' 的。
我们现在来看看怎么证明 B 等于 B'。
B 等于 B' 呢是这样，我们从左半部开始。
左半部呢表示说 π 所对应的等价关系是 R ，所以呢
在 B 当中取出一个元素小 b ，那么它
肯定会有 aRb ，因为 a 也属于 B ，b 也属于 B ，所以会有 aRb。
那么右半部来看， R 所对应的这个划分是 π' ，
那么也就是说它这个 b 呢是属于
某一个 a 所在的这个等价类， b 属于
a 所在的等价类，那么就意味着 b 是属于 B' 的， 属于
B' ，然后呢中间呢有一个桥梁把它们搭在一起。
也就是既然有 aRb ，那么就说明呢 a 和 b
是在同一个等价类里边， 在这个 R 的这个等价类里。
所以呢有 b 属于 a 的等价类， a 在 R 当中的等价类。
所以这样呢给它搭在一起，那么全部都是逻辑等价。
所以呢我们就从 b ∈ B ，然后得到了 b ∈
B' ，因为呢 a 是任意的，所以呢我们说
π 等于 π' ，这样呢我们就证明了这个必要性。
接下来我们来看如何证明这个充分性。
也就是说我们假设 R 所对应的划分是 π ， 而 π
所对应的等价关系是 R' ，那么我们要证明 R = R'。
那么思路也是一样的，我们在 A 当中任意取出两个元素 a,
b ， 那当然这个虽然说是两个元素 a, b 啊，我们 并没有说这个 a,
b 肯定是不一样的，它也许是一样的，但是这个呢不影响我们的证明。
那么 a, b ，那么有 aRb 的话， 如果 aRb
的话，那么就等价于 b 呢是属于 a 的所在的等价类， a 所在的等价类。
那么既然这个 R 所对应的划分是 π 的话， 那么这个
a 所在的等价类呢必然是 π 的一个划分单元。
所以我们就会有存在 B ， B 是属于 π 的，然后 aR 呢等于
B ， 并且呢，小 b 是属于这个大 B ， 因为小 b 呢是在这个
aR 里面的， 对吧？那么我们把中间这个 aR
等于 B 给它这个做一个转换，
也就是说 a 作为代表元素的这个等价类既然等于这个划分单元了，
那么也很明显，这个 a 作为代表元素是属于这个 B 的，我们就把中间这个式子变成这个。
那么接下来我们就用刚才的条件，就是 π 所对应的等价关系是 R'。
那么既然π 所对应的等价关系是 R' ，而且呢 a 和 b ，小
a ， 小 b 都是属于 π 当中的 同一个划分单元，那么很显然它在
R' 当中 是具有 aR'b 的， 具有 aR'b。
所以呢那这一系列的这个逻辑等价下来， 我们就有了 aRb
是逻辑等价于 aR'b ， 那么这个呢就证明了说 R 是等于 R' 的。
