资源描述：
《电子科技大学离散数学第01章-集合论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、离散数学电子科技大学信息与软件工程学院08九月2021第一篇预备知识引进离散数学中的一些基本工具，包括集合、排列与组合、容斥原理与鸽笼原理、离散概率以及递归关系等。尽管有些概念也许读者已经熟悉，但首先还是从集合、子集以及它们的运算开始论述。接着简单介绍计数问题的几种计数工具，包括排列与组合、容斥原理与鸽笼原理、离散概率以及递归关系等。这些背景知识正是我们对数学结构开始进行探索所需要的。2021/9/8教学目标通过学习集合、排列与组合、容斥原理与鸽笼原理、离散概率以及递归关系等预备知识，使学生掌握学习本书其他各篇所必备的理论基础。2021/9/8第1
2、章集合论集合论是现代数学的基础，几乎与现代数学的各个分支都有着密切联系，并且渗透到所有科技领域，是不可缺少的数学工具和表达语言。集合论的起源可以追溯到16世纪末期，为了追寻微积分的坚实基础，开始时，人们仅进行了有关数集的研究。1879～1884年，康托尔(GeorgCantor)发表了一系列有关集合论研究的文章，奠定了集合论的深厚基础，以后策墨罗(Zermelo)在1904～1908年列出了第一个集合论的公理系统，并逐步形成公理化集合论。2021/9/8集合论集合不仅可以表示数、而且还可以象数一样进行运算，更可以用于非数值信息的表示和处理，如数据的
3、增加、删除、排序以及数据间关系的描述；有些很难用传统的数值计算来处理，但可以用集合运算来处理。集合论在程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能等领域都得到了广泛的应用，并且还得到了发展。本章对集合论本身及其公理化系统不作深入探讨，主要是介绍集合、子集的基本概念及相关性质；集合间的各种运算和它们满足的运算性质；有限集、无限集以及粗糙集的基本概念。2021/9/81.0内容提要集合间的关系3集合的运算4集合的概念1集合的概念1集合的表示方法2集合的表示方法2无限集合5特殊集合52021/9/81.1本章学习要求重点掌握一般掌握了
4、解11集合的概念及集合间关系2集合的表示3集合运算及定律4幂集P(A)31集合的递归指定法表示2了解无限集的基本概念21集合的归纳法表示2集合的对称差运算2021/9/81.2集合一、集合的概念集合（SET）是由指定范围内的满足给定条件的所有对象聚集在一起构成的。指定范围内的每一个对象称为这个集合的元素(element)中国所有真皮沙发的聚集指定范围特定对象2021/9/8二、集合的记法通常用带(不带)标号的大写字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用带（不带）标号的小写字母a、b、c、...、a1、b1
5、、c1、...、x、y、z、...表示元素。2021/9/8固定的符号0,1,2,…自然数集合N…,-2,-1,0,1,2,…整数集合Zp/q,p,q是整数，且q≠0有理数集合Q实数集合R复数集合C2021/9/81.2.1集合的表示方法集合是由它包含的元素完全确定的，为了表示一个集合，通常有：枚举法隐式法（叙述法）归纳法递归指定文氏图2021/9/81、枚举法（显示法）－－列出集合中全部元素或部分元素且能看出其他元素规律的方法叫枚举法例1.2.1（1）A＝{a，b，c，d}（2）B={0,1,4,9,16,…,n2,…}适用场景：一个集合仅含有限
6、个元素一个集合的元素之间有明显关系2021/9/8枚举法的优缺点是一种显式表示法优点：具有透明性缺点：在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的角度看，显式法是一种“静态”表示法，如果一下子将这么多的“数据”输入到计算机中去，那将占据大量的“内存”。2021/9/82、叙述法（隐式法）通过刻画集合中元素所具备的某种特性来表示集合的方法称为叙述法（隐式法）一般表示方法：A＝{x
7、P(x)}适用场景：一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画的共同特征其突出优点是原则上不要求列出集合中全部元素，而只要
8、给出该集合中元素的特性。代表元X所具有的性质P2021/9/8例1.2.2A={x
9、x是“discretemathematics”中的所有字母}；Z={x
10、x是一个整数}；S={x
11、x是整数，并且x2＋1=0}；Q+={x
12、x是一个正有理数}。2021/9/83、归纳法归纳法是通过归纳定义集合，主要由三部分组成：第一部分：基础。指出某些最基本的元素属于某集合；第二部分：归纳。指出由基本元素造出新元素的方法；第三部分：极小性。指出该集合的界限。注意：第一部分和第二部分指出一个集合至少包括的元素，第三部分指出一个集合至多要包含的元素2021/9/8例1
13、.2.3集合A按如下方式定义：（1）0和1都是A中的元素；（2）如果a,b是A中的元素，则ab,ba也是A中的元素；（3）
