[计算机硬件及网络]第1章 集合代数

《[计算机硬件及网络]第1章 集合代数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章集合代数集合理论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念——集合（sets）出发，定义数及其运算，进而发展到整个数学。集合理论产生于16世纪末。当时，只是由于微积分学的需要，人们仅对数集进行了研究。19世纪末，即1876一1883年间，康托尔（GeorgCantor1845一1918年,德国数学家）对任意元素的集合进行了系统的研究。康托尔被公认为集合理论的创始人。[1]人们称康托尔开创的集合理论为朴素集合论，因为他没有对集合论作完全公理化的描述，从而导致了理论的不一致（产生了悖论）。为弥补朴素集合理论的不足，本世纪初出现

2、了各种公理化集合论体系,为数学奠定了一个良好的基础。更有意义的是，从此集合基本概念不断深入人心，被广泛地应用于数学理论和其他学科的基础研究和实际应用中，集合论的原理和方法成为名副其实的数学基本技术。基于本书的教学目的，以“集合代数”为标题的本章，主要讨论集合基本概念和集合运算。它与第二章在一起，被视为全书学习所必备的最基本的数学知识和工具，在以后讨论的内容中将不断地运用它们。因此，本章将不涉及公理化集合论体系。事实上，集合不仅可用来表示数及其运算，更可以用于非数值信息及离散结构的表示和处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织

3、和查询都很难用传统的数值计算来处理，但可以用集合运算来实现。集合论被广泛应用在计算机科学中，如数据结构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、CAD等，这也是本章学习集合理论基础知识的目的。1.1集合的概念与表示1.1.1集合及其元素在中学的数学课程中,大家对集合及其元素的意义已经有所了解,因此，下面我们做些简要的回顾。集合是由确定的、互相区别的、并作整体识别的一些对象组成的总体。严格地说这不是集合的定义，因为“总体”只是“集合”一词的同义反复。实际上，在集合论中，集合是一个不作定义的原始概念（就像几何学中

4、的点、线、面等概念）。不过，上述关于集合概念的描述，有益于对它的内涵和外延作直观的理解和认识。例1.1（1）“北洋大学全体学生”为一集合，组成这一集合的对象是北洋大学的学生。（2）“全体正整数”为一集合，其组成对象是正整数。（3）“本书中所有汉字”的集合，其组成对象是本书的汉字。（4）“获1988年诺贝尔文学奖的作家”构成一个集合，尽管它只有一个对象——埃及作家纳吉布•马夫兹。“获2002年诺贝尔生理学或医学奖的科学家”构成一个集合，它包括英国科学家悉尼•布雷内,美国科学家罗伯特•霍维茨,英国科学家约翰•苏尔斯顿三名成员。（5）“解放军理工大学

5、所有学员队”的集合，其组成对象是学员队，而不是学员，因为集合中对象是整体识别的，尽管学员队又是学员的集合。（6）“好书的全体”不构成集合，因为难以对每一本书的好坏作出确定的判断。（7）“方程x(x2-2x+1)=0的所有根”组成一个集合，它只有一个对象0和一个（而不是两个）对象1，因为集合中对象是相互区别的。（8）“方程x2+x+1=0的根”组成一个集合。当在复数域上讨论时，它由两个对象组成；而当在实数域上讨论时，它不含有任何对象，是一个特定集合。组成集合的对象称为集合的成员或元素（members）请注意，这里“对象”的概念是相当普遍的，可以是

6、任何具体的或抽象的客体，还可以又是集合，因为人们有时以集合为其讨论的对象，而又需涉及它们的一个总体——以集合为其元素的集合。例如，例1.1（5）的集合，以学员队集体为其元素；又如集合{1，{1，2}，{1}，2}，数1，2是它的成员，集合{1}和{1，2}也是它的成员。因此，尽管集合与其成员是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。因此必须注意，a不同于{a}，前者为一对象a，后者为仅含该对象a的单元素集合；同样，{a}≠{{a}}，{{a}}是仅含{a}的单元素集。64通常用大写拉丁字母A，B，C等表示集合，用小写字母a,

7、b,c等表示集合的元素。但是，由上可知，这种表示形式不是绝对的。a作为A的元素时，并不排斥a作为集合的可能性。同样，集合A也可能是别的集合的元素。元素对于集合的隶属关系是集合理论的另一基本概念。当对象a是集合A的成员时，称a属于A，记为a∈A当对象a不是集合A的成员时，称a不属于A，记为aÏA对任何对象a和任何集合A，或者aÎA或者aÏA,两者恰居其一。这正是集合论对其元素的“确定性”要求。1.1.2集合的表示集合的表示方式主要有以下三种：（l）列举法：表示一个集合A时，将A中元素—一列举，或列出足够多的元素以反映A中成员的特征，其表示形如A＝

8、｛a1，a2，…，an｝或A=｛a1，a2，a3,…｝（2）描述法；表示一个集合A时，将A中元素的特征用一个性质来描述，其表示形式如A=｛x

9、P(x)