离散数学及其应用 本科 何中胜02　集合论.ppt

《离散数学及其应用 本科 何中胜02　集合论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2篇　集合论集合论集合论是现代各科数学的基础，它是德国数学家康托（GeogCantor,1845～1918）于1874年创立的1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合

2、论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。第3章集合与关系3.1集合的概念和表示法3.2集合的运算3.3集合的计数3.4序偶与笛卡尔积3.5关系及其表示第3章集合与关系－＞3.1集合的概念和表示法一般地说，把具有共同性质的或满足一定条件的事物汇集成一个整体，就形成一个集合。例如：教室内的桌椅、图书馆的藏书、自然数的全体、直线上的所有点等，均分别构成一个集合

3、，而同学、高等学校、每个自然数、直线上的点等分别是所对应集合的元素。通常用大写英文字母表示集合的名称，用小写英文字母表示组成集合的“事物”，即元素。若元素a属于集合A，记作aA，也称集合A包含a，或a在A之中，或a是A的成员；若元素a属于集合的元素，记作aA，也称集合A不包含a，或a不在A之中，或a不是A的成员。若一个集合包含的元素个数是有限的，则称该集合为有限集，否则称为无限集。第3章集合与关系－＞3.1集合的概念和表示法集合的方法通常有两种：列举法和描述法。列举法是指将集合中所有元素都列举出来，或

4、者列出足够多的元素以反映集合中成员的特征，并把它们写在大括号里。例如：A＝｛a,b,c,d｝，B＝{课桌，灯泡，自然数，老虎}，C＝｛1,2,3,···｝，D={a,a2,a3,···}。从方法的定义中可以看出，列举法必须把元素的全体尽列出来，不能遗漏任何一个，并且集合中的元素没有顺序之分且不重复。而描述法是指利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合。如果我们用谓词P(x)表示一个集合中的元素x所具有的属性，则任一集合可表示为｛x

5、P(x)｝，其中竖线“

6、”前写的是元素的一般表示

7、，右边写出元素应满足（具有）的属性。含义为该集合中的元素x具有属性P。设集合A＝｛x

8、P(x)｝，如果P(a)为真，则aA，否则aA。例如：第3章集合与关系－＞3.1集合的概念和表示法本书中用如下专用字母表示常见的集合：N——自然数的集合（包含0）；Nm——小于m的自然数集合，即{0,1,…,n-1}；I(或Z)——整数的集合；I+(或Z+)——正整数的集合；I_（或Z_）——负整数的集合；R——实数的集合；R+——正实数的集合；R_——负实数的集合；Q——有理数的集合；C——复数的集合。第3章集合与

9、关系－＞3.1集合的概念和表示法集合间的关系定义3.1.1设A，B为任意两个集合，则有：（1）对于每个aA皆有aB，那么称A为B的子集或B包含A，也称B为A的母集，记作AB或BA。即：ABx(xAxB)可等价地表示成：ABx(xBxA)。（2）若AB且A≠B，则称A为B的真子集或B真包含A，记作AB或BA。即：ABx(xAxB)x(xBxA)（3）若AB且BA，则称A和B相等，记作A=B；否则，称A和B不相等，并记作A≠B。即：A=B(A

10、B)(BA)第3章集合与关系－＞3.1集合的概念和表示法例题3.1.1设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则NQRC，｛1｝N，｛1,1.2,9.9｝Q，｛2,｝R。也有NQRC，｛1｝N，｛1,1.2,9.9｝Q，｛a,b｝{a,b,c,d}。注意符号“”和“”在概念上的区别，“”表示元素与集合间的“属于”关系，“”表示集合间的“包含”关系。集合间的包含关系“”具有下述性质：定理3.1.1设A，B是任意的集合，则（1）A

11、A，称为自反性；（2）若AB且BC，则AC，称传递性；证明：（1）由集合间包含关系的定义直接得证。（2）对任意xA，由AB可知，一定有xA，又由BC可知，一定有xC，因此AC。第3章集合与关系－＞3.1集合的概念和表示法定义3.1.2不包含任何元素的集合是空集(EmptySet)，记作。　　　即={x

12、P(x)P(x)}，P(x)是任意谓词。定理3.1.2对于任意一个集合A，有A。且空集是惟一的