离散数学集合

第二章集合（set)

集合的概念在现代数学中是一个非常重要的概念。本节主要介绍集合及其表示、集合的运算，序偶，集合的笛卡尔乘积。2023/2/41Zhengjin,CSU个体和集合之间的关系集合不能精确定义，只能直观描述：一个集合就是若干事物的全体。组成集合的每个事物叫做这个集合的元素。小写拉丁字母表示个体：a、b、c、d…大写拉丁字母表示集合：A、B、C、D…2023/2/42Zhengjin,CSU个体与集合之间的关系：属于关系。

对于某个个体a和某个集合A而言，a只有两种可能1）a属于A，记为aA，同时称a是A中的元素。2）a不属于A，记为aA，称a不是A中的元素。个体a属于A或者a不属于A，二者居其一且只居其一。

2023/2/43Zhengjin,CSU集合的表示法

(1)文字表示法用文字表示集合的元素，两端加上花括号。{在座的同学}{高等数学中的积分公式}

(2)元素列举法将集合中的元素逐一列出，两端加上花括号。{1，2，3，4，5}，{风，马，牛}{2，4，6，8，10，…}

2023/2/44Zhengjin,CSU(3)谓词表示法

{x︱p(x)}p表示x所满足的性质例如：{x︱x2=1}={1，-1}{y︱y是开区间(a，b)上的连续函数}2023/2/45Zhengjin,CSU（4）归纳定义法

用归纳法定义一个非空集合A时，包括以下三步：1)基本项（保证A不空)

已知某些元素属于A2)归纳项（生成规则）

给出一组规则，从A中的元素出发，依据这些规则所获得的元素，仍然都是A中的元素。（这是构造A的关键步骤）3）极小化（通常省略）如果集合S也满足（1）和（2），且SA，则S=A。这一点保证集合A的唯一性。

2023/2/46Zhengjin,CSU例1如果论域是整数集I，那么能被3整除的正整数集合S用归纳法可定义如下：（1）（基础）3S，（2）（归纳）如果xS和yS，则x+yS

2023/2/47Zhengjin,CSU集合的特殊情况1、不含任何元素的集合称为空集，记为φ2、含讨论问题所需全部元素的集合称为全集，记为∪

3、称含有有限个元素的集合为有限集合4、含有无限个元素的的集合称为无限集合或无限集5、集合A中元素的个数（或基数或集合的势）记为:|A|

提醒:一个集合也可以是别的集合的元素，如：{a，b，{a，b}}{a，b，φ，{{a，b}}}

2023/2/48Zhengjin,CSU集合与集合之间的关系

设A，B是两个集合1）若对于A中的每个元素x，都有x属于B，则称A包含在B中，记为:A

B。同时称A是B的子集。2）若A中的每个元素都属于B，且B中的每个元素都属于A，则称A等于B，记为A=B。

(A=B当且仅当AB且BA）

3)集合的包含关系具有传递性:即

若AB且BC，则AC2023/2/49Zhengjin,CSU子集的两种特殊情况（平凡子集）：1）空集是任一集合的子集。2）任何集合都是它自己的子集。2023/2/410Zhengjin,CSU例1：确定下列各命题的真假：(a)

(b)(c){}(d){}(e){a，b}{a，b，c，{a，b，c}}(f){a，b}{a，b，c，{a，b，c}}(g){a，b}{a，b，c，{a，b}}(h){a，b}{a，b，c，{a，b}}例2求出下列集合的全部子集：（a){，{}}

(b)

{{a，b}，{a，a，b}，{b，a，b}}2023/2/411Zhengjin,CSU集合上的运算定义2设A，B是两个集合1）A∩B={x︱xA∧xB}，称A∩B为A与B的交集，称∩为集合交运算。2）A∪B={x︱xA∨xB}，称A∪B为A与B的并集，称∪为集合并运算。3)A–B={x︱xA∧xB}，称A–B为A与B的差集例1设A={1，2，3，4，5}，B={2，5，7}，则A∪

B={1，2，3，4，5，7}A∩

B={2，5}A–B={1，3，4}2023/2/412Zhengjin,CSU

定理1

设U是全集，A，B，C是U的三个子集1）A∩A=A，A∪A=A2）A∩U=A，A∪U=U3）A∩=，A∪=A4）A∩B=B∩A，A∪B=B∪A5）(A∩B)∩C=A∩(B∩C)，(A∪B)∪C=A∪(B∪C)6）A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)

2023/2/413Zhengjin,CSU定理2设A，B，C为三个集合，则1）AA∪B，A∩BA；2）若AC且BC，则A∪BC；3）若CA且CB，则CA∩B。4)A-BA5)A-=A6)A∩(B-C)=(A∩B)-(A∩C)；定理3

设A，B为两个集合，则下面三式等价。1）AB2）A∪B=B3)A∩B=A图形表示：2023/2/414Zhengjin,CSU集合上的补运算(一元运算）

设U是全

集，A是U的子集。

~A={xxU∧xA}=U-A称~A是A关于U的补集，称~为补运算。例2设U={a，b，c，d，e}，A={c，d}，则~A=定理4

设U是全

集，A，B是U的子集。则1~(~

A)=A；2）若AB，则~

B~

A；3）若A=

B，则~

A=

~

B；4）~U=，~

=U。5)A∪~A=U，A∩~A=2023/2/415Zhengjin,CSU定理5

设A，B为两个集合，则1）~(A∪B)=~

A∩~B2）~(A∩B)=~A∪~B2023/2/416Zhengjin,CSU集合的环和（对称差）运算定义：设A，B是两个集合，

AB=(A-B)∪(B-A)

={x︱(xA∧xB)∨(xB∧xA)}称AB为A和B的环和，称为集合环和运算。由环和运算和并、差运算的定义知

AB=(A∪B)–(AB)例：设A={a，b，c，d，e}，B={a，b，c，f，g}，则

2023/2/417Zhengjin,CSU幂集定义：设A是集合，A的所有子集组成的集合称为A的幂集，记为：2A或p(A)。2A={xxA}

例1：如果A={a，b}，则2A={，{a}，{b}，{a，b}}例2：设A={，{}}，则2A={，{}，{{}}，{，{}}}

定理1设集合A是有限集合，A

=n，则2A=2A

定理2设A，B是两个集合。那么，A=B当且仅当2A=2B。2023/2/418Zhengjin,CSU有限集的计数原理设A和B都是有限集合，则以下公式成立:|A∪B|=|A|+|B|-|A

B||A

B|<=min(|A|，|B|)|

AB|=|A|+|B|-2|A

B||A-B|>=|A|-|B||A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1A2|-|A2A3|-|A1A3|+|A1A2A3|2023/2/419Zhengjin,CSU有限集计数原理P682023/2/420Zhengjin,CSU集合的广义并和广义交

定义6：如果集合C中的成员本身又都是集合，则集合C称为集类(或称为搜集)。

设C={A1，A2，A3，…An}(1)C的成员的并，记为：∪C，称为C的广义并∪C=A1∪A2∪…∪An（2）C的成员的交，记为：∩C，称为C的广义交∩C=A1∩A2∩…∩An例：设A={{1，2，4}，{3，4，5}，{4，6}}则A广义交：∩A={1，2，4}∩{3，4，5}∩{4，6}=ΦA的广义并：∪A={1，2，4}∪{3，4，5}∪{4，6}={1，2，3，4，5，6}2023/2/421Zhengjin,CSU数学归纳法对于以自然数为论域的xP(x)形式的归纳证明过程如下:第一数学归纳法(1)（基础）先证明P(0)是真。(2)（归纳)再证明n(P(n)

→P(n+1))是真即先假设“P(n)对任意取定的自然数n是真，再由此推出P(n+1)也真，一旦证明了P(n)

→P(n+1)对任意n是真，则用全称推广规则得n(P(n)

→P(n+1))再根据数学归纳法第一原理得出xP(x)。2023/2/422Zhengjin,CSU第二数学归纳法原理n[k[k<n

→P(k)]

→P(n)]

∴xP(x)证明过程:(1)首先证明P(0)为真。(2)证明:对任意n>0，如果P(k)对一切k<n成立，那么P(n)成立。数学归纳法2023/2/423Zhengjin,CSU集合的笛卡尔乘积

由任意两个元素x和y组成的集合{x，y}为偶集。因为{x，y}={y，x}，所以这种偶集只能叫无序偶集，简称无序偶。

有序偶:它不仅与含有的元素x，y有关，还与x，y出现的次序有关。这样的偶集称为有序偶，并记为：<x,y>

例如，用<x，y>表示平面直角坐标系下的横坐标为x且纵坐标为y的点时，则<x，y>和<y，x>在xy时就代表不同的点，因而就不相同。

2023/2/424Zhengjin,CSU定义1有序偶的集合定义：若x，y为任意两个元素，令<x，y>={{x}，{x，y}}称<x，y>为由x，y组成的二元序偶，简称有序偶或序偶。

提醒：此种定义显然体现了二元元素的有序性。但有序偶的定义不只一种，还有别的定义方法，只要能体现有序性就可以了用集合定义有序偶2023/2/425Zhengjin,CSU定理1<x，y>=<u，v>当且仅当x=u且y=v（根据序偶的定义即可得出。）定义2

设n是正整数，x1，x2，…，xn是任意的元素。若n=1，则令<x1>=x1

若n=2，则令<x1,x2>={{x1},{x1，x2}}

若n>2，则令

<x1,x2,…，xn>=<<x1,x2,…,xn-1>,xn>我们称<x1，x2，…，xn>为由x1，x2，…，xn

组成的n元序偶，并称每个xi为它的第i个分量。（这样就定义了n元序偶）2023/2/426Zhengjin,CSU定义3设n是正整数，A1，A2，…，An为n个任意集合。A1×A2×…×An={<x1，x2，…，xn>若1≤i≤n，则xi∈Ai}称A1×A2×…×An为A1，A2，…，An的n维笛卡尔乘积。

定义4设A，B是两个非空集合

A×B={<a，b>｜aA∧bB}(即所有第一元素在A中，第二元素在B中的序偶的集合)称A×B是A与B的叉积（笛卡儿积）集合。记:A×A=A2

2023/2/427Zhengjin,CSU（1）在A×B中，A称为前集，B称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记为A×A=A2。（2）规定A×Φ=Φ=Φ×B。若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。（3）由于偶对中的元素是有序的，因此一般地说A×B≠B×A。(除非A=B，或者A、B中至少有一个为空集)

2023/2/428Zhengjin,CSU例1

A={a，b，c}，B={0，1}A×B={<a，0>，<a，1>，<b，0>，<b，1>，<c，0>，<c，1>}B×A={<0，a>，<0，b>，<0，c>，<1，a>，<1，b>，<1，c>}A2={<a，a>，<a，b>，<a，c>，<b，a>，<b，b>，<b，c>，<c，a>，<c，b>，<c，c>}2023/2/429Zhengjin,CSU定理2：设A，B是两集合，则AB=A*B(即AB中元素的个数等于A中元素个数乘以B中元素个数)。定理3

设A，B，C，D是四个非空集合，那么A×B=C×D当且仅当A=C且B=D。20