第2章 集合与序列

第2章集合与序列

1集合论的产生:

1876～1883年间，康托（GeorgeCantor1845～1918年,德国数学家）对任意元素的集合进行了系统的研究。康托被公认为集合理论的创始人。

2.1集合的定义和运算22.1.1集合的定义一、集合（sets）的概念

集体

集合

组成集合的事物（也称个体）叫做该集合的元素（elements）。例如：

计算机系2011级全体同学；全体自然数；方程x2-1＝0的解；抽象成数学概念3二、集合的表示集合----用大写字母A,B,…等标识。元素----用小写字母a,b,…等标识。记法：若个体a是集合A的元素,则记为a∈A,读作“a属于A”;否则，记为a

A,读作“a不属于A”。4【定义】没有任何元素的集合叫空集(emptyset),记为

。【定义】当我们所讨论的集合都是某一集合的子集时,这某一集合就称为全集(universalset),并用E表示。5表示一个集合的方法通常有以下三种:

1.列举法。如：

A=｛0,1,2,3｝。自然数集N用列举法表示是｛0,1,2,3,…｝。

根据所列元素,容易判断N中的其余元素6

2.描述法：说明集合A中的元素x应满足的条件。记为：

A＝{x|x满足的条件}

如:大于0小于1的实数集合：{x|(0<x<1)且x∈R};所有正奇数的集合：{x|x＝2y+1且y∈N}。73.递归法(递推法)数列常常用递归定义。【例】斐波那契数列:f1=1,f2=1,fn=fn-1+fn-2，n=3,4,…8罗素悖论：Questions在一个僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？解：设C＝{x|x是不给自己刮脸的人}

b是这位理发师

如果这位理发师不自己刮脸,即b

C，则

b

C；

如果这位理发师自己刮脸,即b

C，则

b

C。

b

C或b

C都不能成立9【定义】集合A中元素的个数称为A的基（基数,

cardinality），也称为长度，记作|A|。当|A|是有限数时,集合A称作有限集,否则称为无限集。显然,|

|＝0。10定义2.1.1设A、B是两个集合，E是全集，则A和B的并集(union)

A∪B、A和B的交集(intersection)

A∩B、A的补集(complement)分别定义如下：

A∪B＝｛x|x∈A或x∈B｝A∩B＝｛x|x∈A且x∈B｝

＝｛x|x

A且x∈E｝三、集合的运算

11直观地表示集合间关系的文氏图：注：文氏(JohnVenn),1834-1923,英国逻辑学家。

注意：文氏图只能帮助我们形象地理解复杂的集合关系,一般不作为一种证明方法。

12定义2.1.2设A、B是两个集合，A与B的差集(difference)A－B定义为:

A－B＝｛x|x∈A且x

B｝13设A＝{a,e,f},B＝{a,f,g,h}则：

A－B＝______B－A＝_______

A－B=B－A。?14由定义或文氏图都容易得到下面的公式:A－B＝A∩

1542算法2.1.1：求两个集合交集的算法。A1645234BC12452364依次扫描A、B中的元素，若相同，则把其添加到C中紧凑存储方式下的集合运算的实现216算法2.2.1：求两个集合交集的算法。FindIntersection(setA,setB)//求出集合A和B的交集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度for(i=0;i<iALength;i++){

for(j=0;j<iBLength;j++)if(A[i]==B[j]){

C[k]=A[i];//添加交集元素到交集C中k++;break；}}ReturnC;//集合C就是A与B的交集}1742算法2.2.2：求两个集合并集的算法。A1245234BC152364把A中的元素加到C中，再扫描B，把其不再A中的元素加入C。421563618算法2.1.2：求两个集合并集的算法：FindUnion(setA,setB)//求出集合A和B的并集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度C=B；//用集合C存储集合的并集，把B中的元素赋值到C中iCLength=iBLengthfor(i=0;i<iALength;i++){bFind=false;for(j=0;j<iBLength;j++)//循环1if(A[i]==B[j]){bFind=true;//A[i]为公共元素；break；//跳出循环1}ifnotbFind//A[i]不是公共元素；{C[iClength+1]=A[i];//把A[i]加入到集合C中；iClength=iClength+1;}}ReturnC;//集合C就是A与B的并集}19算法2.2.2：求两个集合减法的算法。A1245234B234删除在B中出现的A的元素。41562620算法2.2.3：集合减法运算算法。FindDeference(setA,setB)//求出集合A-B的差集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度for(i=0;i<iBLength;i++){for(j=0;j<iALength;j++)if(A[j]==B[i]){A=A-A[j]；//从集合A中去掉元素A[j]Break；}}ReturnA;//集合A就是A与B的差集}21假定全集E是有限的。首先为E的元素任意规定一个顺序，例如d1，d2，…，dn，于是可以用长度为n的位串(布尔型数组)表示E的子集A：如果di属于A，则位串中第i位是1；如果di不属于A，则位串中第i位是0。二、非紧凑存储方式下的集合运算的实现22例令E={1，2，3，4，5，6，7，8，9，10}，而且E的元素从小到大排序，即di=i。问：表示E中所有奇数的子集、所有偶数的子集和不超过5的整数的子集的位串是什么?解表示E中所有奇数的子集即{1，3，5，7，9}的位串，其第1、3、5、7、9位为1，其他位为0，即

1010101010

(位串分成长度为5的两段以便阅读)23类似地，E中所有偶数的子集即{2，4，6，8，10}，由位串

0101010101表示。E中不超过5的所有整数的集合即{1，2，3，4，5}，由位串

1111100000

表示。24用位串表示集合便于计算集合的补集、并集、交集和差集。1）要从表示集合的位串计算它的补集的位串，只须简单地把每个1改为0，每个0改为1。即按位取反。25例我们已经知道集合{1，3，5，7，9}的位串是1010101010它的补集的位串是什么?解用0取代1，用1取代0，即可得到此集合的补集的位串

0101010101

这对应着集合{2，4，6，8，10}。26要得到两个集合的并集和交集的位串，我们可以对表示这两个集合的位串按位做布尔运算：2）并集的位串是两个集合位串的按位或：只要两个位串的第i字位有一个是1，则并集的位串的第i位是1，当两个字位都是0时为0。3）交集的位串是两个集合位串的按位与：当两个位串的第i字位均为1时，交集的位串第i位为1，否则为0。27

例集合{1，2，3，4，5}和{1，3，5，7，9}的位串分别是1111100000和1010101010。用位串找出它们的并集和交集。解这两个集合的并集的位串是

1111100000

1010101010=1111101010它表示的集合是{1，2，3，4，5，7，9}。这两个集合的交集的位串是

1111100000

1010101010=1010100000它表示的集合是{1，3，5}。28

例集合A={1，2，3，4，5}和B={1，3，5，7，9}的位串分别是1111100000和1010101010。试用位串求差集A－B

。解利用公式A－B＝A∩

292.结合律

A∪(B∪C)＝(A∪B)∪C

A∩(B∩C)＝(A∩B)∩C1.交换律

A∪B＝B∪A

A∩B＝B∩A3.分配律

A∩(B∪C)＝(A∩B)∪(A∩C)

A∪(B∩C)＝(A∪B)∩(A∪C)2.1.3集合运算的性质

304.德·摩根定律5.

A－B＝A∩

德·摩根(DeMorgan,1806-1871)生于印度,英国数学家。主要贡献:数学归纳法,极限的定义,符号逻辑由4和5可得：6.

A－(B∪C)＝(

A－B

)∩(

A－C

)

A－(B∩C)＝(

A－B

)∪(

A－C

)通过这些性质，可以看出实现同一集合运算有不同算法。31例2.1.1：集合A表示班级男生集合，B是离散数学考试及格的同学，C是数据结构考试及格的同学。求出至少有一门考试不及格的男同学。分析：(A-B)表示离散数学考试不及格的男同学;(A-C)表示数据结构考试不及格的男同学;至少有一门考试不及格的男同学可以表示为：(A-C)∪(A-B)根据摩根定律可知：(A-C)∪(A-B)=A-(B∩C)32//找出至少有一门考试不及格的男同学//A表示班级男生集合//B是离散数学考试及格的同学//C是数据结构考试及格的同学FindMaleNotPass（setA，setB，setC）{//求出B与C的交集 setD=FindIntersection(B,C)；//A-(B∩C)FindDeference(setA,setD)//求出集合A-D}33利用前面公式,可以证明集合恒等式。

【例】对任意集合A,B,C,证明:(A－B)－C＝A－(B∪C)

342.2序列与串一、序列序列：是考虑了元素顺序的一个列表，与集合相比，序列中允许元素重复。序列元素：用下标法标注元素在序列中的位置。如序列S：2，4，6，8，…,2n则s1=2，s2=4，s3=6，…序列长度：一个序列中元素的个数。子序列：从一个序列中去掉一些元素，余下的元素组成了一个新的序列，称为原序列的子序列。35判定一个序列T是不是另一个序列S的子序列算法：判定原则：T中的元素是否在S中按次序出现。例：S12345678T1139T2173T3137√××36isSubsequence(S,T)//判定序列T是不是序列S的子序列{n=iSLength;//序列S的长度m=iTLength;//序列T的长度ifm>nreturnfalse;i=1;j=1;while((i<=m)and(j<=n)){if(ti=sj)//字符匹配i=i+1;j=j+1；}ifi=m+1returntrue;//T是S的子序列returnfalse;}S246783T473j=1i=1j=2i=2j=3j=4i=3j=5j=6i=4>mj=737二、字符串长度有限的字符序列又称字符串，字符串T的长度记作：|T|。两个字符串可以执行连接运算“+”，字符串S和字符T的连接运算如下：S=“abcdefg”T=“hijklmn”S+T=“abcdefghijklmn”。T+S=“hijklmnabcdefg”。38字符串中子串的概念，在计算机编程语言中的概念和数学中的子序列的概念有所不同。如果字符串的子序列是由原字符串中连续的元素构成的，则该子序列称为原字符串的子串。如S=“abcdefg”,则子串为：“abc”，“cde”，“efg”等“bdf”虽然是S的子序列，但不是S的子串。思考：子串判定的算法392.3矩阵一、矩阵相加的算法MatrixSum(MatrixA,MatrixB){for(i=0;i<m;i++)for(j=0;j<n;j++)aij=aij+bijreturnA;}40二、矩阵相乘的算法MatrixMulti(MatrixA,MatrixB){for(i=0;i<m;i++)for(j=0;j<l;j++){cij=0;for(k=0;k<n;k++)cij=cij+aik×bkj}returnC;}41容斥原理如果已知|A|和|B|,能否求出|A∪B|和|A∩B|?|A∪B|、|A∩B|和|A|、|B|之间的关系是什么?三个集合及以上的情况又如何?Questions容斥原理回答了上述问题。42

【定理】对任意两个有限集A和