离散数学-第1章-集合论.pptVIP

离散数学05三月2025电子科技大学计算机科学与工程学院

2025/3/5第一篇预备知识引进离散数学中的一些根本工具，包括集合、排列与组合、容斥原理与鸽笼原理等。尽管有些概念也许读者已经熟悉，但首先还是从集合、子集以及它们的运算开始论述。接着简单介绍计数问题的几种计数工具，包括排列与组合、容斥原理与鸽笼原理、离散概率以及递归关系等。这些背景知识正是我们对数学结构开始进行探索所需要的。

2025/3/5教学目标通过学习集合、排列与组合、容斥原理与鸽笼原理、离散概率以及递归关系等预备知识，使学生掌握学习本书其他各篇所必备的理论根底。讲授：集合论自学：排列与组合、容斥原理与鸽笼原理

集合论的历史康托尔朴素集合论策梅洛ZF公理集合论弗兰克尔斯科伦ZFS公理集合论

2025/3/51.0内容提要集合间的关系3集合的运算4集合的概念1集合的概念1集合的表示方法2集合的表示方法2无限集合5特殊集合5

2025/3/51.1本章学习要求重点掌握一般掌握了解11集合的概念及集合间关系2集合的表示3集合运算及定律4幂集P(A)31集合的递归指定法表示2了解无限集的基本概念21集合的归纳法表示2集合的对称差运算

2025/3/51.2集合一、集合的概念集合〔set〕由指定范围内的某些特定对象聚集在一起构成。指定范围内的每一个对象称为这个集合的元素(element)。中国所有真皮沙发的聚集指定范围特定对象

2025/3/5二、集合的记法通常用带(不带)标号的大写字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用带〔不带〕标号的小写字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。

2025/3/5固定的符号0,1,2,…自然数集合N…,-2,-1,0,1,2,…整数集合Zp/q,p,q是整数，且q≠0有理数集合Q实数集合R复数集合C

2025/3/5三、集合的表示方法集合是由它包含的元素完全确定的，为了表示一个集合，通常有：枚举法隐式法〔表达法〕归纳法递归指定文氏图

2025/3/51、枚举法〔显示法〕－－列出集合中全部元素或局部元素的方法叫枚举法例〔1〕A＝{a，b，c，d}〔2〕B={0,1,4,9,16,…,n2,…}适用场景：一个集合仅含有限个元素一个集合的元素之间有明显关系

2025/3/5枚举法的优缺点是一种显式表示法优点：具有透明性缺点：在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的角度看，显式法是一种“静态”表示法，如果一下子将这么多的“数据”输入到计算机中去，那将占据大量的“内存”。

2025/3/52、隐式法〔表达法〕通过刻画集合中元素所具备的某种特性来表示集合的方法称为表达法〔隐式法〕一般表示方法：A＝{x|P(x)}适用场景：一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画的共同特征其突出优点是原那么上不要求列出集合中全部元素，而只要给出该集合中元素的特性。代表元X所具有的性质P

2025/3/5例A={x|x是“discretemathematics”中的所有字母}；Z={x|x是一个整数}；S={x|x是整数，并且x2＋1=0}；Q+={x|x是一个正有理数}。

2025/3/53、归纳法归纳法是通过归纳定义集合，主要由三局部组成：第一局部：根底。指出某些最根本的元素属于某集合；第二局部：归纳。指出由根本元素造出新元素的方法；第三局部：极小性。指出该集合的界限。注意：第一局部和第二局部指出一个集合至少包括的元素，第三局部指出一个集合至多要包含的元素

2025/3/5例集合A按如下方式定义：〔1〕0和1都是A中的元素；〔2〕如果a,b是A中的元素，那么ab,ba也是A中的元素；〔3〕有限次使用(1)、(2)后所得到的字符串都是A中的元素。试指出其定义方式，并举出集合A中的3个元素。

2025/3/54、递归指定集合通过计算规那么定义集合中的元素例设a0＝1，ai+1＝2ai〔i?0〕定义S＝{a0，a1，a2，...}＝{ak|k?0}，试写出集合S中的所有元素。

2025/3/55、文氏图解法文氏图解法是一种利用平面上点的集合作成的对集合的图解。一般用平面上的圆形或方形表示一个集合。AA

2025/3/5四、集合与元素的关系元素与集合之间的“属于关系”是“明确”的。对某个集合A和元素a来说，a属于集合A，记为a?A或者a不属于集合A，记为a?A两者必