离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
37-集合族及运算
Loading...
Do curso por Peking University
离散数学概论 Discrete Mathematics Generality
144 classificações
Na lição
集合论：集合代数
Conheça os instrutores
陈斌副教授
北京大学
[音乐] 嗨，你好，欢迎回来。
接下来呢我们来讨论 一种特殊的集合，就是称之为集合族。
那什么是集合族？就是如果一个集合 C
当中呢，它的每个元素 都是集合的话，那么也就是说由集合所构成的集合，
我们就把这种，特意的把这种集合，单提出来进行讨论，称为集合族。
那么集合族呢，它因为是一系列的集合， 所以呢它可能可以表示成这种
下标的形式，就是它的每一个元素，它可能会带下标。
那么比如说这样，C =｛Sd｝，C 等于S下标d。
d 呢是属于另外一个集合，大 D。
那么我们可以把所有的下标收集在一起， 收集到一起，成为这个大
D ，我们就把这个下标组成的集合，就称之为集合族的 标志集。
那么标志集呢 它可以是，比如说可以是自然数，也可以是自然数的一个子集，
那么当然也可以是一些连续的符号。
我们来看看集合族和一些标志集的例子。
比如说，由0构成的集合，0，1构成的集合， 由0，1，2构成的集合点点点。
那这个呢，因为它所有的 元素都是集合，所以呢这样的 C 是一个集合族。
但是呢，它并没有列成下标的形式，所以呢它没有这个标志集。
但是如果我们可以定义大N，小n，这个小n作为下标，
那么把这个大N，小n定义为前n个自然数， 也就是从0，1，2一直到n－1，
那么这样呢，这个C就可以表示成 大N，然后小n，然后n是一个正整数。
也就是说，它是第一个呢是N1 = {0}； N2 = {0，1}；N3 = {0，1，2}。
那么这样呢，这个 C 它就有了一个标志集，而这个标志集呢，就是正整数集合。
像这样，C =
{Sa，Sb，Sc}， 那么这个呢，我们就可以把它的下标收集在一起，把它放在一起，成为一个集合，
那么把这个集合称之为d，这个标志集呢就是集合d，
就是它的内容呢，就是 a，b，c。
那么当然，特别典型的，
如果把一个集合它的所有的子集放在一起，也就是它的幂集，
我们前面有说过，这个集合的幂集运算，它得到的是一个集合。
那么这个集合呢，显然是一个集合族。
因为它的每一个成员，都是A的一个子集，它把A所有的子集放在一起， 所以呢它这个幂集显然是一个集合族。
那么考虑到集合， 基于集合的基本的运算，再考虑到这个集合族本身
的特有的特点，也就是说它每一个元素都是集合， 那么我们可以把集合的基本运算，并和交运算
进行一个扩展，扩展成为一个叫做广义并和广义交。
这个专门针对集合族这种特殊的集合的。
那么所谓的广义并呢，就是把集合族，它的当中的包含的所有的集合 做一个大的并集，这就叫广义并。
那广义并的记号呢，是把这个并集这个运算符，放在C的前面， 这就叫广义并了。
这有点类似于我们对一个数列进行 连加连乘的那样的一个符号，比如像∑啊，
大 ∏啊，大 ∏是连乘我们知道，这样的符号呢 比较类似。
那么广义并的这个定义呢，是这样的， 它是这样的一些个体，我们要注意它是
个体，从个体域来的个体的集合。
所以呢，它就不再是这个集合的集合啦。
所以呢它是这样的一些个体，存在 S， S
呢是属于 C，也就是C当中的一个元素，就是一个集合了。
那这个 x 呢，是属于 S 的，所以就是把
C 当中的所有的集合，它的那个的花括号全部都打破，
然后呢把这些打破以后的所有的个体， 所有的成员收集在一起，去掉重复得到的集合，这就是广义并。
相对呢就有广义交。
广义交呢就是把集合 族当中所包含的所有的集合，进行一个交集，
求它们公共的，所有集合的公共的元素。
那么它的定义呢，也是这样，把这个交这个运算放在 C 的前面。
然后它是任意的 Ｓ ，Ｓ 只要是属于C的，那么这个
x 都会属于这个 Ｓ ， 也就是所有 C
当中集合公共的那些 元素。
那么广义并和广义交呢， 可以退化成这个的普通的，这个并和交运算。
如果说 C 恰好就是包含两个集合 A，B，
那么 C 就等于 AB 组成的集合，这么一个集合族的话， 那么
C 的广义并那么就是 A 并 B，，C 的广义交就是 A 交 B。
那么如果带有标志集的话， 比如说
C 呢是 A ，然后它的下标是 d ， 小 d 呢来自于这个大
D ，这么有一个有标志集的情况下， 我们可以按照像
∑， ∑我们知道是从比如说有 连加的话，会从比如说
n＝1 然后加到 n ， 或者 1 加到 k。
或者连乘，n 呢从 1 连乘一直连乘到
100， 那么这样的一个写法，我们可以把这个
标志集写在这个 广义并或者广义交的这个符号的下面， 小 d
属于大 D，然后写上 Ad 这样的一个形式。
那么这个两个形式都是有的。
那么这个呢分别 适用于说有标志集和没有标志集的情况。
我们来看看几个集合族运算的这个例子，广义交和广义并的例子。
首先第一个这个集合族是刚才我们比较熟悉的， ｛0｝，｛0，1｝，｛0，1，2｝这前n个自然数那么构成的这么一个大的一个集合族。
如果对它做这个广义并的话，那么显然它就得到的是 全体的自然数。
如果做广义交，那么就是每一个集合中的公共元素， 公共元素呢只有
0 ，所以它 广义并呢是 0 的集合，就是自然数 0 所构成的集合。
如果 C 是一个这样的一个有限集， 是｛1｝，｛1，2｝和｛1，3，5｝这三个集合所构成的，
那么它们的这个广义并就是｛1，2，3，5｝对吧， 那么它们的广义交就是
1 所构成的集合， 这就是广义并和广义交这两个运算的例子。
那么根据广义并和广义交的定义，我们可以推出一些关于它们运算的一些性质。
那么第一，我们来看一个例子， 任意的集合
A 和集合族 C 来说， 如果 A 交上 C
的广义并， 那么它是等于说把 A 放到这个
C 里边去， 跟 C 的每一个成员做交，然后再做广义并。
这个呢，相当于一种分配律的形式，对吧，它是满足 分配律的。
如果 A 并上 C 的这个广义交， 那么它就相当于把这个
A 呢跟 C 当中的每一个元素，每一个集合进行一个并集，然后呢再做广义交。
这也是符合分配律的形式。
但如果是差运算，就不一样了，不如我们预期的那样， 如果
A 差上这个 C 的广义交，那么 它相当于
A 对每一， C 当中的每一个集合 进行，做一个差集。
但是这个时候，广义交呢就要把它 这个底朝天，把它变成一个广义并。
所以呢，A 差上 C 的广义并也是一样， 就相当于 A 差上
C 当中的每一个元素，然后呢再做广义交。
这个呢，我们在证明的过程当中，如果需要证明的话， 我们实际上也可以预想到，它跟德摩根律是有关系的。
然后接下来是一个补的运算。
那么补的运算呢，跟差运算是一致的。
所以我们也可以预期说，C 的广义并如果求补的话，
就等于说 C 的每一个元素都求补，然后再做一个广义交。
那反过来也是，C 的广义交做求补，那就等于说
C 的每一个元素做求补， 最后呢把它们做这个广义并，就是交变成并，并变成交。
从这个运算性质呢， 我们可以来进行一个证明。
做一个证明，这个证明呢就是A插上C的广义并，
他等于A和C当中的每一个元素进行 额，进行差运算，然后呢再做这个广义交。
那么这里头呢会用到这个德摩根律，我们来看看。
那么我们利用这个集合相等的这个定义，就是外延公理。
就是只要你要证明任何一个左边这个集合当中的元素，
都是，同时呢也是右边这个集合当中的这个元素，他们是逻辑等价的话， 那么就说明这两个集合它是相等的。
所以呢我们从左边A减去A插上C的广义并当中提取出一个元素
X，那么进行 分裂，那么它会分成：
X呢属于A，这是差运算的定义。
X属于A，并且合取上X不属于后边的这个， 不属于这个C的广义并。
所以， 这是第一条呢，逻辑等价是用到了差运算， 它的这个定义。
然后接着呢，我们前面这个不变，把后边的这个 还原，用这个广义并的这个定义来进行还原。
那还原是什么呢？既然是广义并，那么就是存在S，S属于C，
合取上X属于S，那么既然是不属于，那就在前面加一个否定 连接词，否定连接词。
然后接下来呢，就把这个否定词用德摩根律，然后深入到里边去。
深入到里边去了以后呢，就量词就要变号，变号，从存在量词变成全称量词。
然后呢把这个合取变成析取，对吧？然后S属于C变成S不属于C，
X属于S就变成X不属于S。
然后接下来，把这个任意S，
这个量词进行狭域的扩展，扩展到整个的这个式子。
当然这个对于合取来讲，是 可以的。
因为第一个X属于A呢，它并不包含有自由变元S， 所以它可以扩展出来。
这个也是一个等价式，对吧？这是一个等价式。
然后接着同时我们再利用这个 合取对析取的分配率， 啊分配率。
然后变成了X属于A，然后合取上S不属于C，
然后X属于A合取上X不属于S，然后它们之间用析取连接起来。
然后呢我们再用这个蕴涵等价式
把这个析取变成一个蕴涵式，析取变成蕴涵式。
析取变成蕴涵式之后，这个前件呢，它应该是一个否定。
所以呢我们就把它变成了， X不属于A，然后析取上S属于C。
合取变析取了，因为它做了一个否定。
那么后面呢？ 后面就不变。
后面我们把它还原成一个差运算。
X属于A又X不属于S，那它就是属于A减去S，对吧？
然后接下来呢，我们再把它进行一个还原。
还原成什么呢，这是一个蕴涵的等价，就是一个逻辑等价。
逻辑等价，我们记下来一个公式：A析取B蕴涵C那就
相当于，A蕴涵C并且B蕴涵C，对吧？所以呢把它这个拆开。
所以就变成了：X不属于A，然后蕴涵着X属于A减去S，
然后呢同时呢，是S属于C，然后蕴涵着X属于A减去S。
然后我们来看看这个合取连接词连接的这两个公式。
那么前面这个公式呢，是前件是X不属于A，
那可是我们的条件是X属于A，所以呢它应该是一个假，它永远为假。
前件既然为假，那么整个蕴涵式就为真。
那对于一个合取式来说， 那么为真的我们可以把它给划掉，划掉，划掉呢只剩下后面这块。
就是S属于C蕴涵着X属于A减S。
那么这个呢按照广义交的这个定义，
那么它就是：A减S， 这个集合族的广义交。
那么我们最终就得到了X属于A减S， S是属于C的这么一个集合族的广义交。
所以呢，我们通过一步一步的，有1，2，3，4，5，6，7，8，
有8步这样的逻辑等价，最终呢证明了这个两个集合是相等的。
这也证明了这个广义并和广义交它运算的性质当中的一个，对吧？
接下来我们来看另外一个运算： 就是幂集运算跟这个集合族的运算，它们有什么样的性质？
那么这个呢就是并集，广义并。
它说对于任何的集合A，A的幂集，它是一个集合族啦，那么它的广义并呢等于A。
这个其实很容易理解，那既然是 幂集，额，是集合族的所有的成员做一个大的并集。
那至少说这里头一个最大的集合， 包含最多元素的集合，就是ρ(A)里的，就有A嘛。
那么A和它所有子集的这个并集，那当然还是它自己。
当然我们可以来进行一个证明，还是用这个谓词 逻辑的形式来进行证明。
那么它也还是我们同样用这个等价的形式，
从这个ρ(A)幂集的广义并当中提取出一个元素来， S，X。
那么这个广义并就 变成了存在S，然后呢S属于ρ(A)，并且呢X属于S，是吧？
那么既然S是属于ρ(A)的， 就也就是说，它是，这个S是ρ(A)的一个子集。
所以呢，变成了S是包含于A。
那既然有这个X属于S，而S又包含于A，
那么从这个，它实际上就等价于，X就是A当中的一个成员，
对吧？所以呢从上面直接变成了下，下面这个了。
那我们再观察这个，在X属于A里头压根就没有 这个S的什么事儿，所以呢实际上就可以把这个存在量词给它抛弃掉，
那么自然就是X属于A了。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
