哈工大 集合与图论 讲义

《哈工大 集合与图论 讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一篇集合论集合论是德国数学家康托（Contor）在1874年建立的，它是现代数学的基础，当今数学中的每个对象本质上都是集合。有时我们说：“数学能嵌套在集合论中”其含义就是指数学的一些对象如数、函数、线、面等都可以用集合来定义。换句话说，数学的各个分支在本质上都是研究这种或那种对象的集合。例如：几何学是研究点、线、面的集合；数学分析是研究函数的集合；代数学是研究数的集合以及在此集合上有关运算的集合等。因此，我们把集合论作为现代各种数学的基础是有道理的、合适的。集合论也是计算机科学的重要工具。集合论在程序设计、数据结构、形式

2、语言、操作系统等计算机科学中，都有重要应用，成为计算机科学工作者必不可少的基础知识。计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的术语来描述和论证。集合论主要有以下几个特点：第一、第一、  它所研究的对象十分广泛。例如数、图形或其它任何客体作为对象。第二、第二、  因为它研究的对象是如此广泛，为了便于研究，就必须寻找对象的共性。而要做到这一点，就必须进行抽象。第三、第三、  在抽象化的基础上，可以用统一的方法来研究和处理集合论中的各种问题。总之，集合论的主要特点是研究对象的广泛性，分析思考问题的抽象性和处理问题

3、的统一性。正是这些特点，使我们便于用它来描述和研究离散对象及其关系。 第一章集合及其运算基本要求1.1.    掌握集合、子集、全集、空集和幂集等概念。熟悉常用的表示集合的方法以及用文氏图来表示集合的方法。能够判定元素与集合、集合与集合之间的关系；熟练掌握两个集合相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等。2.2.    熟练掌握集合之间的各种运算以及集合运算的基本等式，能够利用它们来证明更复杂的集合等式。3.3.    掌握余集与集合笛卡儿乘积的概念以及DeMorgan公式。4．掌握求解与有穷集合计数相

4、关的实际问题。 1.1必备知识和考试要点 1.1.1基本定义集合是一个不能精确定义的数学概念。一般地说，把一些确定的、可以区分的事物放在一起组成的一个整体称为集合，简称集。组成一个集合的每个事物称为该集合的元素，或简称一个元。若a是集合A的一个元素，就称a属于A，或称a在A中，记为aA。若a不是集合A的一个元素，就称a不属于A，或称a不在A中，记为aA。集合的概念很简单，但准确理解其含义却非易事，特别应注意下列几点：第一、第一、  集合的元素可以是任何的事物，既可以是具体的事物，也可以是抽象的事物；还可以是另外的集合，但构

5、成这个集合的元素决不能是这个集合的自身。第二、一个集合的每个元素是可以互相区分的。这意味着在集合中不会重复出现相同的元素。第三、组成一个集合的各个元素在该集合中是无次序的。第四、任一事物是否属于一个集合，回答是确定的。也就是说，对一个集合来说，任一事物或者是它的元素或者不是它的元素，二者必居其一且不可兼而有之，而且结论是确定的。今后，我们常用不同的大写的字母表示不同的集合，而且不的小写字母表示集合中不同的元素。但是因为某个集合的可能是令一个集合，所以这种约定不是绝对的。在本书规定用几种特定的字母表示几个常用的集合。约定：N

6、表示全体自然数组成的集合；I表示全体整数组成的集合；I+表示全体正整数组成的集合；Q表示全体有理数组成的集合；Q+表示全体正有理数组成的集合；R表示全体实数组成的集合；R+表示全体正实数组成的集合；C表示全体复数组成的集合；通常用两种方法表示一个集合。一种方法是外延表示法，即把集合中的全部元素一一列举出来，元素之间用逗号隔开，并把它们用花括号括起来。例1集合A中有五个元素1，2，3，4，5。则A={1，2，3，4，5}一般说来，一个集合仅含有少数的几个元素时才可用这种方法给出。即使是有限个但数量较大，原则上这种方法也是可行

7、的，然而实际上，很少能把全部的元素列出。不过当列出几个元素后就可以看出组成该集合的其他元素的规律时，也可采用此方法只列部分元素，其余用“…”表示。例2由26个小写英文字母组成的集合就可表示成{a，b，c，…，x，y，z}利用此方法可以表示含有无穷多个元素的集合。例3自然数集合N={1，2，3，…}用上述方法表示集合并不是永远可能的。例如，区间[0，1]中的所有实数之集就不能用这种方法给出。另一种方法是内涵表示法，即用集合中的元素的共性来刻画集合。例4上述集合A和N可以分别表示成A={x∣x是整数且1≤x≤5}，N={x∣x

8、是自然数}。例5所有的正偶数形成的集合可以表示成{x∣x=2n，nI+}例6[a，b]上的所有连续函数形成的集合可以表示成{f(x)∣f(x)在[a,b]上连续}。集合还有其他的表示方法，但上述两种方法是常用的。原则上能简单、准确而且易于被大家所公认的方法都是可以使用的。例如[0，1]区间上的所有实数构