离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
34-集合基本概念
Loading...
Do curso por Peking University
离散数学概论 Discrete Mathematics Generality
144 classificações
Na lição
集合论：集合代数
Conheça os instrutores
陈斌副教授
北京大学
[音乐] 好，欢迎回来。
接下来我们来介绍这个集合的一些基本的概念， 首先我们看什么是集合？那么集合的英文叫
set ， 它呢是作为整体识别的、 确定的相互区别的一些对象的总体。
所以呢 集合是一个总体，是一些对象的总体。
而这里头的几个关键的概念 一个呢是整体识别，所以呢它就不会再被分割。
然后呢，第二个呢是确定也就是说这些对象是 属于或者不属于整体，它是确定的而不是模糊的。
第三呢这些对象是相互区别的。
也就是说这些对象呢它们不会相同，而是呢总会有区别的地方，它能够
以某种形式把它区分开。
那么比如说集合的例子， 比如说北京大学的全体学生，那么就只有可以构成一个集合，
而组成的对象呢就是学生。
比如说全体自然数 0 ，1 ，2 ，3 ，4 ，5 ，6 等等等
一直到后边，那么这个组成的对象呢就是每一个自然数。
那么，
像北京大学的全体学生也可以作为集合的例子，它是组成对象是学生。
全体的自然数 0 ，1 ，2 那么它组成对象就是每一个自然数。
也可以呢是方程 x 平方减 2x 加 1
等于 0 的根， 那么它也可以组成一个集合。
那么这个呢组成的对象 就是 1 ，当然你说这是 1
而不是两个 1 ， 这不是说重根的两个 1 ，因为 1 和 1
之间它是不能区分开， 所以呢它的这个集合的组成对象就是只有一个 1。
还有呢像 x 平方加 x 加 1 等于 0 它的实数根，
那么如果讨论负数的话，那当然这个组成对象呢是两个不同的负数。
如果你讨论实数，那么这个呢就是一个没有任何组成对象的一个集合，
因为这个方程没有实数解，
那么所以呢这种没有任何组成对象的集合呢，我们后面还会看到它是一个特殊的这个集合。
我们把组成集合的对象就称之为成员（member）或者叫做元素。
那么元素呢实际上是可以任何的 可以是任何的具体或者抽象的这些事物，都可以是。
那么当然元素也可以是集合， 那么集合的记号呢用两个花括号给它括在一起，比如说，
一个几个 A ，它的包含的三个自然数 1 ，2 ，3 那么用花括号给它括起来。
或者呢一个集合 S ，它的包含了三个元素， 那么第一个呢是
1 ，第二个呢是 10 ，第三个呢 它是一个由 2 ，3
所构成的集合， 所以呢它有是三个成员，其中两个呢是自然数，
第三个它是一个集合，所以它这是一个混合式的这种集合。
也可以这个花括号里边什么都没有， 也可以定义出一个集合来。
那么这样的元素 和集合之间它存在着一种隶属的关系，
我们说如果对象 a 是集合 A 的成员 的话，那么我们就称之为 a 是属于 A 的。
那么有一个记号像一个 叉子一样的记号 ∈ 对吧？这个 a ∈ A。
那么如果 a 不是集合 A 的成员的时候呢，就称之为 a ∉ A。
那么记作于 a ∈ A 前面加一个否定的词"非"。
当然也可以发明一种新的符号，就是在这个 ∈
符号上 加一个斜杠啊 ∉。
那么规定集合的方式呢大概来讲有三种， 列举法、 描述法和归纳法。
那么列举法呢是把所有的元素都进行列举， 比如说
1 ，2 ，3 把它列举出来用括号括起来， 比如说 a1
，a2 一直到 an 那么它有一个下标的也可以把它括起来。
那么描述法呢是把这个集合当中的元素的特征 用一个谓词公式的形式把它描述出来，
那么一般的式子就是这样 A 等于 x | Px ，或者说
x ：P ( x ) ，那么这个就意味着说 的表示说
x ∈ A ，当且仅当 Px 成立的时候
Px 为真，这个时候呢这是符合描述法。
那么第三种呢是归纳法，归纳法呢我们后面 有一个章节专门来说明它。
那么实际上呢我们前面 已经用了归纳法做了一些定义，比如说定义了数理逻辑当中的命题公式啊，
定义了个体项啊这些都是用归纳法。
那个典型的那个三句话，第一句第二句第三句，三句话的那种定义 就称之为归纳定义。
那么 一些集合规定的例子，比如说｛0 ，1
｝这样的集合 的我们用列举法来描述了，当然我们也可以用
描述法来同时来描述它，可以变成 x ，然后 x 等于
0 吸取上 x 等于 1 ，对吧？像这个自然数集合 你可以用列举法
0 ，1 ，2 ，3 ，4 ，5 ，6 … 那么也可以用描述法 x 然后 x 是自然数。
比如说 I ＋ ，比如说 1 ，2 ，3 … 这个正整数集合也可以用描述法来进行描述。
像这个 Nn 就是前 n 个自然数 0 一直到 n
－ 1 ， 那么可以用列举法，那么也可以用描述法来描述
x | 然后 x ∈ N ，这个 x 是自然数并且
x 大于等于 0 小于 n ，就是在 0 和 n
之间，但是并不包含 n 这样的一个描述。
那当然前 n 个自然数集合的集合
就是｛0 ｝然后的集合，｛0，1 ｝的集合，｛0 ，1 ，2 ｝的集合，｛0
，1 ，2 ，3 ｝ 的集合，那么也可以用描述法描述成 x
等于 Nn ， 这个 n 呢是一个下角标，而且 n 呢 ∈ 正整数集合。
那这样呢就是前 n 个自然数集合的集合， 所有的前
n 个，前一个自然数，前两个自然数，前三个自然数
这个所有的集合所构成的集合，那么当然也可以简单的就写成 Nn
，然后 n 呢是一个正整数。
刚才我们称作在 一个特殊的集合就是花括号里边什么都没有了，
那么我们把这种没有任何元素的这种特殊的集合就称之为空集， 叫做空集。
空集呢有一个特殊的记号就是希腊字母 φ。
那么空集呢，它可以实际上也可以用描述法来定义，
我们只需要把这个谓词公式写成一个矛盾式，也就是一个永假式就可以了。
那么第二个概念呢叫称之为有限集。
那么我们把空集和只含有有限多个元素的集合，就称之为有限集。
那么否则呢就称之为无限集。
当然无限集，什么是无限集这要直接去定义还是 并不容易定义的。
第三个是基数的概念， 我们把有限集合当中成员的个数称之为集合的基数。
当然了只要是有限集合，那么它的这个成员的个数
它肯定是一个自然数对吧？空集成员个数是 0。
那么如果只包含有一个那么它的基数呢 就是 1
，2 ，3 ，4 ，只要是有限集合那么它的基数呢肯定是一个自然数。
但是呢无线集合的基数那就复杂了，那么这个呢不在我们
这个课程的范围之内，大家如果有兴趣可以找参考书来看一看。
那么集合的基数它有一个记号，就在集合的两边画上 |。
就是 | A | 就叫做 A 的基数。
下面呢是集合论的三大基本的原理，
就是阐述了集合是一个什么样的一个概念，集合的性质是什么？
那么这三个呢基本的原理称作 为外延公理、 概括公理和正规公理。
那么外延公理呢是表明说两个集合什么 时候才称作为是相等的，是相同的集合。
它是说两个集合 A 和 B 相等 当且仅当它们具有相同的元素，这个时候呢就称为相等。
我们实际上可以用一个谓词公式来记录它来表示它。
也就是说 A 等于 B 就是相等啊， A 等于 B 双向蕴含
任意的 x ，x ∈ A 双向蕴含 x ∈ B。
这个呢就是外延公理的具体的定义。
那当然，在这个定义下，我们就会发现像(0,1)构成的集合和(1,0)构成的集合
那么它是同一个集合，它们是相等的
那实际上都可以用同一个谓词来来描述它，就是x=0 v x=1。
那么，外延公理呢，就是说明了它定义的 所定义的集合相等，就说明了集合元素的一个无序性
它本身是没有排序的，所以呢你是(0,1)还是(1,0)是无关系的 以及呢集合表示形式的一个不唯一性
既然是无序，那当然就是不唯一，那不唯一的同时，你实际上还可以有
其他的这个谓词公式来确定它，只要它们 满足说具有相同的元素就可以了
那么第二个呢是称之为概括公理 概括公理就是说对于任何的个体域U
任何一个谓词公式P，都能够确定任何一个以该域中的对象作为元素的一个集合S
那么把它记为S={xIx∈U
∧P(x)}也就使得P为真，同时呢x也要乘这个U'iii' 这就是一个个体域。
这个概括公理呢就规定了集合成员的一个确定性，确定性
因为谓词公式它有真值的话，真值的它是确定，非真即假，有排中律
那么所以呢，在概括公理之下，我们也 可以给出空集的这个定义，也就是说我们只需要把P(x)
记为永假式，我们就可以得到一个空集
第三个是所谓的正规公理
正规公理是说并不存在一个集合A1,A2,A3，使得说
A1它 的成员是A2，A2的成员是A3，然后以至于无穷
那么直观来说呢就是这个集合是有限可分的 个体域的元素呢就是一个"基本粒子"
个体域当中的元素就不能够在是一个集合，那要不然就无从进
那么正规公理呢确立了这个元素和集合的一个不同层次性 也就是说集合呢不能够是自己的成员
那么也就排除了像A=，然后 {A}作为元素的集合这样的一个"病态"集合
而很多悖论呢都是从这个"病态"集合变出来的 那么康托尔的朴素集合论当中
实际上并没有考虑到个体域的概念 也就是我们刚才说的这个抽象原理，在概括公理当中的这个抽象原理
它呢定义了这个抽象原理是这样的：S={xIP(x)}
那么这个罗素悖论的描述，它实际上可以直接的写成一个谓词
谓词Q(x)，我们定义一个Q(x)定义为x不属于x
当然，这个当然很奇怪，本来呢属于 这个'iii'的这个概念，它的左边应该是一个元素，右边是一个集合
那么现在呢，他把x摆在了同一个位置上 它既摆在元素的层次上，又摆在了集合的层次上
那么就形成了这样的一个谓词 然后我们用这个谓词呢实际上可以定义一个集合B
既然是抽象原理嘛，我们可以定义一个B，B呢就是{xIQ(x}
那么接下来，定义了这一个谓词和相应的集合之后
如果我们来判断Q(B)的真值的话，那么就出现麻烦了
什么麻烦呢？那么Q(B)既然它是一个命题
那么它的真值非真即假，对吧？但是如果说，我们说Q(B)是真的话
那么也就意味着B这个B呢会属于这个集合
因为Q(x)为真，那么这个x呢就会属于这个集合，所以B就会属于B
但是按照Q(x)本身的定义 如果B属于B的话，那么就应该是Q(B)是为假，对吧
从Q(B)为真，推到了Q(B)为假，这就自相矛盾了
那么反过来又怎么样呢？如果Q(B)为假，那么按照
这个集合的定义，那么它就不属于这个集合
不属于集合就是B不属于B，但是B如果属于B你按照谓词的定义来
说，那应该是Q(B)为真，那这样呢就出现了很多的麻烦
所以呢这是悖论产生的这个根源。
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.
