离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
35-子集合
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
137 个评分
从本节课中
集合论：集合代数
与讲师见面
陈斌副教授
北京大学
[音乐] 嗨，欢迎回来。
那么这一节呢， 我们开始讲述这个集合之间的一种新的关系，称之为子集。
那么我们在上一节呢，通过公理定义了集合两个集合之间怎么样能够称之为相等，
也就是说它只要包含有相同的元素，两个集合就相等。
那么这个呢就定义了集合的一种无序性，它所包含的元素的无序性。
那么接下类我们来看看这种新的集合之间的关系。
如果A的每一个元素都是B的元素的话
那么我们就把这个集合A称之为集合B的一个子集 叫做子集合。
我们可以用一阶谓词逻辑 来定义这个子集这么一个关系。
我们可以说任意x，x呢只要属于A，那么就必定蕴涵着x属于B，
如果这个成立的话，那么A是B的子集 那么有一个记号，一个喇叭口，下面画一个等号
那么就记作A包含于B，这样呢，我们就得到了集合论里头的两个基本的关系，
就是元素和集合之间的隶属关系和集合与集合之间的一种 包含关系，就是子集关系。
我们来看看几个子集的例子 啊。
首先这个a,b它所构成的集合，那么 它是a,b,c,d四个元素所构成集合的子集，这个没问题
第二个，a,b,c三个元素所构成的集合 那么它是自身的子集，那么按照定义也没有问题，
因为按照定义呢，自身的每个元素当然也都是自身的每一个元素了，
第三这个，a,b,c所构成的集合，单单一个a
出来，那么它就只有隶属关系，而不是子集关系，那我们要记住
子集呢是集合之间的一种关系，你单个的这个元素它是构不成这样的关系的。
但是这个呢也是两个集合，a,b所构成的集合和右边
a,b以及c,d所构成的集合，它们有子集关系吗？ 虽然它们是两个集合，但是它没有子集的关系，因为
右边这个集合呢，它实际上是由两个元素构成的 只不过这两个元素呢，每个元素都是集合而已
所以呢，左边这个a,b所构成的集合是右边的一个成员，它是隶属于它
而不是它的一个子集。
那当然，有的时候呢，隶属关系和包含关系会同时成立， 那么这就需要
一个巧妙的一个构造 怎么样一个巧妙构造呢？就是你要让这个集合，既是另一个集合的成员
又是另一个集合的子集，那么它们所包含的 这个元素又要相同的话，那么这就需要有一个巧妙的构造。
比如说这个例子，一个1构成了一个 只有包含有一个元素的集合和另外一个集合，
它是两个成员，一个成员呢是元素1，另一个成员呢是集合，1的集合
那这两个是不一样的，1和1的集合是不一样的东西
那么这两个集合之间，它们就既是隶属关系又是包含关系了。
这个有时候呢会特别有用，我们会用到这些巧妙的构造。
我们下面来通过一些定理，来看看子集这个关系的一些性质。
第一个定理是说，对于任意的两个集合A,B，那么A=B
两个集合相等，当且仅当A是B的子集
而且呢B也是A的子集，也就是说如果两个集合互为子集合的话 那么这两个集合就是相等的。
那么而且呢特别 的对于任意的集合A，它跟自身就有这个
子集的关系，刚才我们通过一个例子，像abc那个例子已经，就已经看到了。
我们可以用通过这个子集的这个和相等的这个定义 来进行证明。
好，我们下面来看看，那么A=B，那么根据公理
根据外延公理就可以知道，它是任意x只要x属于A就双向蕴涵x属于B
那么这样的这个用双向蕴含拆开 它就有两个单向蕴含，对吧，两个蕴含
那么就是任意x，那么x属于A单向蕴含x属于B 然后并且呢合取上x属于B
蕴涵着x属于A，这是双向蕴涵的 这个性质。
然后这时候呢我们把这个 这个任意x，这个量词的这个辖域给它分开，
这个是谓词公式里边的永真式，这是没有问题的。
任意x，x属于A蕴涵着x属于B，然后合取上任意x，x属于B 蕴涵x属于A。
那么从这呢，我们发现它正好符合 子集合的这个定义，所以呢那就是左边就是A是B的子集
然后右边是B是A的子集 那这样呢，一路下来都是逻辑等价，那么最终呢我们就证明了说A=B，
那么就等价于A是B的子集，同时B是A的子集。
那么定理2是说：如果A,B,C都是任意集合的话
那么如果有A是B的子集 B又包含于C，那么就会有A包含于C。
也就是说子集这个关系呢，它是可以传递的，它是可以传递的
那么我们实际上可以用这个逻辑蕴涵式I6这个
在命题逻辑里头的这个I6这个逻辑蕴涵式，这个逻辑蕴涵式呢是 意味着这个A蕴涵B，并且又，又B蕴涵C
那么它逻辑蕴涵于A蕴涵C，这个来证明它。
因为子集它是由蕴涵这个连接词来定义的。
所以我们 用这个I6这个逻辑蕴涵式，是一定很容易能够证明这个定理二的。
第三个定理，是说对于任意的集合A，A
都是这个全集，就是整个个体域，全总域的子集。
那当然了，全总域那也就说它包含了我们考虑的所有的个体，
所有的个体，那么既然都所有的个体的话，那么所以呢
在A当中的任何的元素，x隶属于U 这个是永真的，永真的。
那么根据这个子集合的定义 x属于A蕴涵着x属于U，那么
不管这个x属于A成立不成立，反正x属于U是永远成立的
那么我们知道这一个蕴涵式，只要后件为真，
那么它整个式子它就一定为真，前件是真是假已经是不要紧了。
所以呢这整个式子也是恒真，所以我们就能够得到A是U的子集， 这当然很明显的事情。
但是呢我们可以通过 这个蕴涵式来进行证明。
第四个定理，是说对于任何的集合A
这个空集都是任何集合这个A的子集 空集都是它的子集。
那么这里呢也可以通过 这个子集的这个关系式来表达
它的定义，就是x属于空集蕴涵着x属于A
那么因为空集当中不包含有任何的元素 所以呢x属于空集它是永假。
那么既然永假，我们知道，一个蕴涵式， 它的前件为假，那么它就整个蕴涵式就为真。
而不管这个后件是真是假，它都是为真的。
定理五是说，空集呢是唯一的 也就是说如果有存在两个空集
我们称之为这个空集1，空集2 那么根据上面刚刚证明的定理，定理四，
那么既然它是一个空集，空集1，就是∅1是空集的话
那么不管后边这个∅2是什么，那么它都会有∅1是∅2的 这个子集。
那么反过来再用，因为∅2是有一个空集， 所以呢它也是∅1的子集。
那么它们互为子集的话，那么根据定理一，那么它们就是两个就是相等的。
所以呢，我们得到结论，如果有两个空集的话，那么它必然是同一个集合。
第六个定理， 是说子集的个数。
假设呢A是一个有限的集合 A的基数是n，也就是说它包含的这个成员数量为n的话
那么A的子集的个数是2的n次幂，这么多个 那么我们可以通过这个组合数学的方法来证明
我们来分析A的子集有哪些。
那么第一，它是不包含有任何元素的 当然空集是所有的这个集合的子集，所以第一空集。
也就是说从 Cn0从n个当中提取出0个，就什么，1个元素都不选 那这个时候呢它是1个。
那么只包含有A当中1个元素的子集 那么就是从n个当中挑出1个来，那么就是Cn1个
只包含有两个的，就是Cn2个。
那么最终呢， 包含A当中所有元素的这个子集，那么就是A本身了，就是从A
的n个元素当中选出n个元素，那只有一种选法，就是它自己，所以就是一个
那么这样呢，把这些所有的从Cn0 Cn1一直加到，累加到Cnn
那么我们根据组合数学的这个结论能得到它是2的n次方，它正好等于2的n次方
所以这样呢，我们就完成了这个证明。
那么比如说，1,2 这个两个元素的集合，它的子集有哪些呢？有空集
有1构成的集合，有2构成的集合，还有呢1,2构成 的集合，它一共有4个，所以它有2²，有4个
当然包含有3个元素的集合，那么它的子集呢就一共有8个这么多
那么接下来，
如果说A是B的一个子集，并且呢A≠B的话，
就是它们B当中有这个包含了一些A所没有的这个元素的话，那么就记作为
A是B的一个真子集，这就是真子集。
那当然空集是所有非空集合的真子集。
当然空集呢也是自身的子集，但只不过是它是，它并不是真子集而已。
那接下来我们来看看一些判断，看看你掌握了这个子集关系没有。
第一，空集是自身的子集。
这是对的，我们要记住， 空集是任何集合的子集。
那么第二，空集是空集的元素。
那当然这是错的，因为空集当中不包含有任何的元素。
第三，空集是由空集构成的集合的子集。
这个别的不管，我们只要看到空集是某一个元素的子集那么，某一个集合的子集，我们
立马就要判断，它是对的，所以它肯定是对的。
当然，右边这个集合呢 它其实不是空集，它是由空集这个集合，它包含了一个元素 它的一个集合。
第三，空集隶属于由空集构成的这个集合。
诶，那当然对了，因为这个右边这个集合呢，它只有一个元素，它的元素就是空集。
最后，如果A是B的子
隶属于B，而且呢B又隶属于C，那么会不会有A隶属于C呢？
我们说子集的关系是传递的，如果A包含于B，B包含于C，那么一定会有A包含于C。
那么这个隶属关系有没有这个传递性呢？
你来，请你来在题目当中来告诉我吧。
