离散基础及数学 11

1离散数学第三章集合数理逻辑--回顾6个逻辑联接词最小完备运算集命题变元、命题公式永真式、永真蕴含代入规则、替换规则永真、永假、可满足对偶三个原理/定理范式基本和、基本积、极小项、极大项析取、合取主析取、主合取命题的翻译推理四规则P规则T规则CP规则F规则2026/9/142/84回顾个体、谓词、量词全称量词、存在量词自由变元、约束变元谓词公式、谓词公式的解释（赋值）含量词的等价式和永真蕴含式量词转化律(德摩根律)扩张及收缩律（命题常量与谓词的运算）量词分配律（全称与存在量词）二阶谓词全称与存在量词位置转换的规律谓词公式的翻译全称量词存在量词2026/9/143/84推理规则约束变元改名自由变元代入取代规则替换规则量词的增删规则全称特指（UniversalSpecialization）存在特指（Existentialspecialization）存在推广（existentialgeneralization）全称推广（universalgeneralization）范式前束范式斯科林范式人工智能回顾2026/9/144/84集合论的创立与康托尔的遭遇

19世纪末期，数学界出现了一件引人注目的事情。一位名叫康托尔（G.Cantor，1845－1918）的德国数学家提出一种令人费解的古怪理论----集合论。它的内容是如此与常识格格不入，以致于一出世就引起了一场轩然大波。2026/9/145/84

自从17世纪牛顿和莱布尼茨）创立微积分理论体系之后，在近一二百年时间里，微积分理论一直缺乏一个严格的逻辑基础。它的一些基本概念的表述，还有某些混乱和自相矛盾之处。从19世纪开始，柯西、魏尔斯特拉斯等人进行了微积分理论严格化的工作。他们建立了极限理论，并把极限理论的基础归结为实数理论。那么，实数理论的基础又该是什么呢？康托尔试图用集合论来作为实数理论，以至整个微积分理论体系的基础。2026/9/146/84

出于这一目的，康托尔用集合的观点重新考察各种数量关系，特别是无穷数量关系。他发现，无穷集合有着有穷数量关系所不具备的性质。比如，在无穷集合领域，所有整数和所有偶数之间是一一对应的，所有有理数和所有整数之间是一一对应的，平面上所有的点和线段上所有的点是一一对应的，……概言之，在无穷的世界里，整体的所有元素和部分的所有元素之间可以是一一对应的。另外，无穷集合并不都是相等的，比如所有实数和所有有理数之间就不是一一对应的。因而，无穷集合是有大小的。集合论用“基数”这个概念来表示无穷集合间的区别。

那么，有没有一个最大的集合呢？康托尔通过研究，否定了这个想法。因为每个已知集合的所有子集所构成集合，其基数都大于已知集合的基数。既然没有最大的基数，当然也没有最大的集合。无穷世界里的这些性质，初看起来，真是令人头晕目眩。2026/9/147/84

康托尔的研究成果发表之后，马上遭致当时一些赫赫有名的数学家的激烈攻击。德国数学家克隆尼克是这些人中言辞最激烈、攻击时间最长的一个。

克隆尼克比康托尔年长22岁。他主张，除非一种数学对象能够用有限步骤从自然数中构造出来，否则不能认为它在数学上是存在的。他有一句“名言”：“上帝创造了自然数，其余的一切才是人做的工作”。因此，他否认无理数的存在，也否认极限理论的意义。虽然康托尔是他的学生，但由于集合论的内容同他的主张大相径庭，所以克隆尼克简直到了不能容忍的程度。他认为，康托尔关于超限数的研究，是一种非常危险的数学疯病。克隆尼克的影响还使康托尔的学术论文一再延误发表日期。2026/9/148/84

除了克隆尼克之外，还有一些著名数学家也对集合论发表了反对意见。

法国数学家彭加勒说：“我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西”。他把集合论当作一个有趣的“病理学的情形”来谈，并且预测说：“后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了”。

德国数学家魏尔认为，康托尔关于基数的等级观点是雾上之雾。

菲利克斯．克莱因也不赞成集合论的思想。

数学家H．A．施瓦兹原来是康托尔的好友，但他由于反对集合论而同康托尔断交。2026/9/149/84

尽管有希尔伯特等著名数学家赞同他的集合论，尽管他的集合论事实上已取得巨大的成功，仍未能使康托尔感到欣慰和满足。

从1884年春天起，即在他40岁的时候，他患了严重的忧郁症，极度沮丧，神态不安。不过，在精神病发作的间歇阶段，康托尔仍然顽强地坚持集合论的研究。而且当每次从精神病发作中恢复过来的时候，他都感到自己的脑子变得格外清晰。他在集合论方面许多非常出色的成果，都是在精神病发作的间歇时期获得的。然而，长期的精神折磨所造成的危害毕竟是不容忽视的。由于健康状况逐渐恶化，1918年，他在哈勒大学附属精神病院去世。

2026/9/1410/84公理化集合论的建立

到二十世纪初集合论已得到数学家们的赞同。数学家们为一切数学成果都可建立在集合论基础上的前景而陶醉了。他们乐观地认为从算术公理系统出发，借助集合论的概念，便可以建造起整个数学的大厦。在1900年第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣布“……数学已被算术化了。今天，我们可以说绝对的严格已经达到了。”

然而这种自得的情绪并没能持续多久。不久，集合论有漏洞的消息迅速传遍了数学界。这就是1902年罗素得出的罗素悖论。2026/9/1411/84

罗素构造了一个所有不属于自身（即不包含自身作为元素）的集合R。现在问R是否属于R？

如果R属于R，则R满足R的定义，因此R不应属于自身，即R不属于R；另一方面，如果R不属于R，则R不满足R的定义，因此R应属于自身，即R属于R。这样，不论何种情况都存在着矛盾。

这一仅涉及集合与属于两个最基本概念的悖论如此简单明了以致根本留不下为集合论漏洞辩解的余地。绝对严密的数学陷入了自相矛盾之中。这就是数学史上的第三次数学危机。2026/9/1412/84

1908年，策梅罗提出公理化集合论，后经改进形成无矛盾的集合论公理系统，简称ZF公理系统。原本直观的集合概念被建立在严格的公理基础之上，从而避免了悖论的出现。这就是集合论发展的第二个阶段：公理化集合论。与此相对应，在1908年以前由康托尔创立的集合论被称为朴素集合论。公理化集合论是对朴素集合论的严格处理。它保留了朴素集合论的有价值的成果并消除了其可能存在的悖论，因而较圆满地解决了第三次数学危机。

2026/9/1413/84主要内容集合的概念与表示方法集合的基本运算包含与排斥原理2026/9/1414/842026/9/1415/84集合是由某些特殊对象汇集在一起构成的。一般来说这些对象具有某种共同的性质。组成集合的那些个体称为集合的元素。全体中国人全部整数全国的高校全部叫李明的人用大写字母表示集合（如A），小写字母表示集合中的事物（如a）若个体a是集合中A的元素，记作“a∈A”若个体a不是集合中A的元素，记作“aA”3.1集合的概念及其表示一、集合和元素2026/9/1416/84一、集合和元素注意：集合中的元素也可以是集合。2026/9/1417/84二、集合的表示方法（1）枚举法：把集合中的元素写在一个花括号内，元素间用逗号隔开。

例如：A={2,a,b,9},B={4,5,6,7,8}（2）构造法：构造法又叫谓词法。如果P(x)是表示元素x具有某种性质P的谓词，则所有具有性质P的元素构成了一个集合，记作A={x|P(x)}。例如：集合B可以表示成B={a|a∈N且4≤a≤8}D={2x∣x∈Z且x≤50},即D={0,2,4,6,…,98,100}2026/9/1418/84二、集合的表示方法几个常见的集合的表示符号：N：所有正整数的集合。Z：所有非负整数的集合。R：所有实数的集合。I：所有整数的集合。Q：所有有理数的集合。P：所有素数的集合。Nm：从1到m，这m个正整数的集合。Zm：从0到m-1，这m个非负整数的集合。2026/9/1419/84小插曲公务员考试、公司招聘的可能题目：23,29,31,37.下一个数是什么？3,5,8,13,21,()………..2026/9/14数列的通项公式--谓词20/84三、集合的外延和内涵符合某个概念R的那些客体的集合A，叫作该概念R的外延；集合A中诸客体共有的本质属性P(x)，叫作该概念R的内涵。

外延：所有人的集合人内涵：人所共有的本质属性（外貌、思想等）一个概念的外延越大，则内涵越小。（人，黄种人）外延性原理：两个集合相等，当且仅当它们有相同的元素。记作A=B

2026/9/1421/84四、集合的基数集合A中不同元素的个数叫集合A的基数，记作#A或|A|。例如：A={2,3,4},#A=3，A为有限集.

A={x|x∈Z},#A无穷大，A为无限集.，#S=4.五、空集不包含任何元素的集合为空集，记作

。例如：A={x|x∈R且x2+8=0}=

注意：与的区别2026/9/1422/84六、集合之间的关系1.集合的相等

定义：若A、B是两个集合，当且仅当A、B两集合恰恰有完全相同的成员时，称A、B两集合相等，记作A=B。例如：设A={x|x∈N

且

x能整除24}，

B={1,2,3,4,6,8,12,24}

则

A=B

注意：1.集合中不考虑重复元素。例如：{1,2,3}={1,2,2,3}.2.集合中不考虑元素的排列顺序。例如：{1,2,3}={3,2,1}.3.{1,2,3}{1,{2,3}}.2026/9/1423/84六、集合之间的关系2.集合的包含

定义：设有集合A、B，如果A的每一个元素都是B的元素，则称A是B的子集或B是A的包含集，记或。例如：可以得出

注意：若，则有2026/9/1424/84集合的包含关系应具有以下性质：(1)对任意集合A，都有(2)对任意集合A，都有(3)对任意集合A、B，(4)对任意集合A、B、C，若，那么证明:(1)（反证法）假设是假，则至少有一个元素x，使得且，然而这与空集不包含任何元素相矛盾，所以以上假设不成立，即为真。A的平凡子集2026/9/14六、集合之间的关系25/84六、集合之间的关系3.集合的真包含定义：如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则A称为B的真子集，或A真包含于B，记作。

例如：设A={0，1}，B={0，1，2}，C={0}

则2026/9/1426/84七、全集定义：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E。举例：全集的概念相当于论域，如在初等数论中，全体整数组成了全集。UAAB2026/9/1427/84八、幂集定义：给定集合A，由集合A的所有子集为元素组成的集合称为集合A的幂集，记为。例：设A={a}

1个元素的子集：{a}则0个元素的子集：

设B={a,b}

1个元素的子集：{a},{b}

2个元素的子集：{a,b}则0个元素的子集：

设C={a,b,c}

1个元素的子集：{a},{b},{c}2个元素的子集：{a,b},{a,c},{b,c}

3个元素的子集：{a,b,c}则0个元素的子集：；2026/9/1428/84九、幂集定理：如果有限集合A有n个元素，则它的幂集有2n个元素。证明：A的所有k个元素组成的子集数为从n个元素中取k个的组合数。

另外，因为，因此的总数N可表示为因为令x=y=1，得故集合A的幂集的元素个数为2n2026/9/1429/84幂集的编码表示以S={a,b,c}为例说明可得2026/9/1430/84离散数学

大连理工大学软件学院

陈志奎博士、教授、博士生导师

办公室：综合楼405，Tel：62274392

实验室：综合楼一楼，

Mobile/p>

Email:zkchen@

zkchen00@

QQ：1062258606

2026/9/1431/84回顾集合的定义集合的描述内涵与外延集合的基数集合间的关系相等包含、真包含全集补集子集、幂集运算子集的二进制描述32/843.2集合的运算定义：由集合A和B的所有公共元素所组成的集合，称为集合A和B的交集。记作一、相交运算例如：

设A={a,b,c,d},B={d,f,a},C={e,f,g}则可以看出AB2026/9/1433/84一、相交运算证明：若则，对任一，则且，即且，故，因此。集合的交运算具有如下性质：AB2026/9/1434/84一、相交运算类推至多个集合的情况，集合的交运算仍满足结合律。假设有n个集合A1,A2,…An，那么这些集合的交集可表示为：2026/9/1435/84二、联合运算（集合的并）定义：由集合A和B的所有元素组成的集合称为A和B的并集，记作AB例如设A={a,b,c},B={c,d,f},C={b,e}那么可以看出2026/9/1436/84二、集合的并集合的并运算具有如下性质：注意：假设有n个集合A1,A2,…An，那么这些集合的并集可表示为：2026/9/1437/84二、集合的并2026/9/1438/84二、集合的并证明：对于任意的x，若由x的任意性可知(a)成立。同理可以证明(b)。2026/9/1439/84二、集合的并2026/9/1440/84二、集合的并2026/9/1441/84交集、并集的思考题

老师讲完交集、并集的概念之后，提问学生：

（1）设A={x│x是参加百米赛跑的同学}，B={x│x是参加跳高比赛的同学}，求A∩B．

（2）设A={x│x是红星农场的汽车}，B={x│x是红星农场的拖拉机}，求A∪B．一学生答道：（1）中A∩B={x│x是参加百米障碍赛的同学}．

（2）中A∪B={x│x是红星农场的联合收割机}．2026/9/1442/84三、差分运算（集合的补）定义：设A,B是两个集合，所有属于A而不属于B的元素组成的集合，称为A和B的差集或B对A的相对补集。记作A-B绝对补集：B对E的相对补集叫做绝对补集，简称补集，记作~BAB

A-BA~A43/84三、差分运算（集合的补）例：设A是小于10的素数集合，B是奇数集合，求A-B。解：A={2,3,5,7}B={1,3,5,7,9}

A-B={2}例：设U=I(I是整数集合)

解：44/84三、差分运算（集合的补）集合的差分运算还具有如下性质：A~A45/84三、差分运算（集合的补）定理3.2-4：设A,B为任意两个集合，则下列关系式成立。46/84三、差分运算（集合的补）定理3.2-5：设A,B为任意两个集合，则下列关系式成立。证明:(b)设，即且，因为则必有，故有，即为。设，则且，即

且或者，显然只能与成立。即。47/84三、差分运算（集合的补）定理3.2-6：设A,B,C为任意三个集合，则下列关系式成立。证：因此，48/84三、差分运算（集合的补）49/84四、对称差分运算定义：设A、B为任意两个集合。属于A但不属于B的所有元素和属于B但不属于A的所有元素的并集，称为A和B的对称差集，记作。例如：A={1,2,3}B={3,2,4}

则={1,4}ABE50/84四、对称差分运算集合的对称差分运算满足如下性质：ABE51/84四、对称差分运算52/84四、对称差分运算53/84四、对称差分运算上述证明结果可以通过以下文氏图清楚看出。EABCBACE54/843.3集合定律55/843.3集合定律56/843.3集合定律57/84证明:(39)转化为假设为假，证明为假。由为假可知，和均__为假，即并且为真，也就是为真，使得为假。58/843.4包含排斥原理集合的运算，可用于有限个元素的技术问题。集合的基数：集合所含元素的个数。集合A的基数用|A|或#A表示。设A1,A2是有限集合，用|A1|,|A2|分别表示它们的基数，那么可以推出：59/843.4包含排斥原理定理3.4-1：设A1,A2是有限集合，|A1|,|A2|为其基数，则60/843.4包含排斥原理例3.4.1：假设在10名青年中有5名是工人，7名是学生，其中兼具有工人与学生双重身份的青年有三名，问既不是工人又不是学生的青年有几名？解：设工人的集合为W，学生的集合为S，则根据题设应有：

因此既不是工人又不是学生的青年有1人61/843.4包含排斥原理包含排斥原理在三个有限集和上的推广：62/84例3.4.2

求1到1000之间（包含1和1000在内）既不能被5和6，也不能被8整除的数有多少个？解：设

用

表示有穷集P中的元素数，

表示小于等于x的最大整数，

表示

的最小公倍数，则有63/84根据包含排斥原理，所求的元素数为64/843.4包含排斥原理例3.4.3：某工厂装配30辆汽车，可供选择的设备是收音机﹑空气调节器和对讲机。已知其中15辆汽车有收音机﹑8辆有空气调节器，6辆有对讲机，而且其中有3辆这三种设备都有。我们希望知道有几辆汽车没有提供任何设备。解：设A1，A2和A3分别表示配有收音机﹑空气调节器和对讲机的汽车集合，因此由题设知

因为得65/843.4包含排斥原理把包含排斥原理推广到n个集合。定理3.4-2：设A1,A2,…,An为n个有限集合，它们的基数分别为|A1|,|A2|,…,|An|，可得：66/84证明：设S为全集，由德·摩根定律可得

因此，由此，原定理可变为67/84应用数学归纳法对上式进行证明，当n=2

时，证明

若

，有

，则

成立。若

，有

于是

，则68/84因此当n=2

时，

成立。假设69/84成立，则，70/8471/84因此定理得证。72/843.4包含排斥原理例3.4.4：求1到250之间能被2，3，5和7中任何一个整除的整数个数。解：设A1表示1到250之间能被2整除的整数集合，A2表示能被3整除的整数集合，A3表示能被5整除的整数集合，A4表示能被7整除的整数集合。|x|

表示小于或等于x的最大整数。73/843.4包含排斥原理于是有74/84例3.4.5:某系有100个学生至少要学法、德、英三种语言中的一种。现在这100个学生中有42人学法语，45人学德语，65人学英语，15人学法语和德语，20人学法语和英语，25人学德语和英语。问同时学三种语言的有多少?仅学英语的有多少?

75/84解:令A,B,C分别表示学法语、德语、英语学生的集合。则

|A|=42,|B|=45,|C|=65,|A∩B|=15,|A∩C|=20,|B∩C|=25,|A∪B∪C|=100。

由容斥原理得：

|A∪B∪C|=(|A|+|B|+|C|)-(|A∩B|+|A∩C|+|B∩C|)+|A∩B∩C|

所以|A∩B∩C|=|A∪B∪C|-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|)=8

仅学英语的人数为：

|C|-|A∩C|-|B∩C|+|A∩B∩C|=2876/84例3.4.6求欧拉函数的值。欧拉函数

表示

中与

n互素的数的个数。例如

，因为与12互素的数有1,5,7,11。下面利用包含排斥原理给出欧拉函数的计算公式。解：给定正整数

n

，

为n

的素因子分解式，令那么77/84下面计算等式右边的各项，根据包含排斥原理例如，。78/843.5应用与拓展PointNe与DeepSets用于三维几何的集合学习

在三维计算机视觉与自动驾驶领域，激光雷达采集的数据通常以点云形式呈现——即三维空间中一组无序的坐标点。从数学上看，一个包含若干点的点云就是一个集合，其中每个元素代表一个三维坐标。关键难点在于：点云是无序的，交换任意两点的索引不改变点云所表示的物体形状。传统深度学习方法要求输入具有规则网格结构，因此必须先将点云转换为体素或多视图图像，这导致数据冗余且破坏了集合的本质特性。DeepSet理论为这一问题提供了严格的数学基础。Zaheer等人在2017年证明：任何定义在有限集合上的置换不变函数，都可以分解为两个部分的组合——首先是对每个元素独立进行变换，然后是对所有变换结果进行对称聚合。这一结论直接对应集合论中的基本性质：集合由其元素唯一确定，与枚举顺序无关。

79/842026/9/14PointNet是这一理论在工程上的首个成功落地。其架构严格遵循DeepSets的分解形式：首先通过共享的多层感知机对每个点独立提取特征；随后使用对称池化层（最大池化或求和池化）聚合所有点的信息，得到全局特征向量。该过程保证了无论输入点以何种顺序排列，网络输出的特征表示保持不变。后续的PointNet++进一步引入了分层集合学习，通过在最优度量空间内递归地对点集进行嵌套划分，对应于集合论中子集族与覆盖的概念，从而捕获局部几何结构与多尺度上下文。在工具层面，PointNet的官方实现基于TensorFlow，而PyTorchGeometric等现代图神经网络库已将其封装为标准的卷积层，支持端到端的点云分类、分割与检测任务。从理论到工程的映射关系十分清晰：集合的无序性通过置换不变的网络架构得以保持，而集合元素数量的可变性则通过共享权重与池化操作天然处理。80/842026/9/14粗糙集理论用于可解释特征选择

在机器学习的数据预处理阶段，特征选择旨在从高维数据中剔除冗余与无关属性，以降低计算复杂度并提升模型泛化能力。与第一章所述基于MaxSAT的约束优化方法不同，粗糙集理论提供了另一种基于集合近似与不可分辨关系的数学框架，其最大优势在于无需先验知识，完全从数据本身的集合结构出发进行推理。粗糙集由Pawlak于1982年提出，其核心概念直接建立在集合论基础之上。给定信息表，其中行代表对象，列代表属性，粗糙集通过不可分辨关系将样本划分为等价类——即具有完全相同属性值的样本被视为不可区分的整体。对于任意决策类别，粗糙集用下近似（肯定属于该类别的样本集合）与上近似（可能属于