重庆邮电大学理学院：《图论及其应用》课程PPT教学课件_第1章 预备知识——集合、关系、函数、复杂度

第一部分预备知识 集合、关系、函数、复杂度

第一部分 预备知识 集合、关系、函数、复杂度

对于从事计算机科学工作的人们来说,集合 论是必不可少的基础知识。例如程序设计语言、 数据结构、形式语言等都离不开子集、幂集 集合的分类等概念。集合成员表和范式在逻辑 设计、定理证明中也都有重要应用。 本部分从集合的直观概念出发,介绍了集合 论中的一些基本概念和基本理论

对于从事计算机科学工作的人们来说，集合 论是必不可少的基础知识。例如程序设计语言、 数据结构、形式语言等都离不开子集、幂集、 集合的分类等概念。集合成员表和范式在逻辑 设计、定理证明中也都有重要应用。 本部分从集合的直观概念出发，介绍了集合 论中的一些基本概念和基本理论

集合论是研究集合的一般性质的数学 分支,它研究集合不依赖于组成它的事物 的特性的性质。集合论总结出由各种对象 构成的集合的共同性质,并用统一的方法 来处理。 集合论的特点是研究对象的广泛性,集 合是各种不同对象的抽象,这些对象可以 是数或图形,也可以使任意其它事务

集合论是研究集合的一般性质的数学 分支，它研究集合不依赖于组成它的事物 的特性的性质。集合论总结出由各种对象 构成的集合的共同性质，并用统一的方法 来处理。 集合论的特点是研究对象的广泛性，集 合是各种不同对象的抽象，这些对象可以 是数或图形，也可以使任意其它事务

集合的基本概念 例: 1.二十六个英文字母可以看成是一个集合; 2.所有的自然数看成是一个集合; 3.重庆邮电大学计算机学院2010级的本科学生可以看 成是一个集合 4.这间教室中的所有座位可以看成是一个集合

1. 二十六个英文字母可以看成是一个集合； 2. 所有的自然数看成是一个集合； 3. 重庆邮电大学计算机学院2010级的本科学生可以看 成是一个集合； 4. 这间教室中的所有座位可以看成是一个集合。 例: 集合的基本概念

集合的元素 组成一个集合的那些对象或单元称为这 个集合的元素。通常,用小写的英文字母a, b,c,表示集合中的元素。元素可以是单个 的数字也可以是字母,还可以是集合。 如:A={a,c,b};B={a},{b},(c}

组成一个集合的那些对象或单元称为这 个集合的元素。通常，用小写的英文字母a, b, c,…表示集合中的元素。元素可以是单个 的数字也可以是字母，还可以是集合。 如：A={a,c,b} ; B={{a},{b},{c}} 集合的元素

元素与集合的属于关系: 设A是一个集合,a是集合A中的元素,元素与 集合的关系: 属于∈;不属于g 若a是集合A中的元素记为a∈A,读作a属于A; 若a不是集合A中的元素,则记为agA,读作a不 属于A。 例如:A是正偶数集合,则2∈A,4∈A, 6∈A;而1gA,3乐A,19运A

元素与集合的属于关系： 设A是一个集合，a是集合A中的元素，元素与 集合的关系： 属于∈； 不属于  若a是集合A中的元素记为aA，读作a属于A； 若a不是集合A中的元素，则记为aA，读作a不 属于A。 例如：A是正偶数集合，则2A，4A， 6A；而 1A，3A，19A

特别注意 集合并不决定于它的元素展示方法。集合的元素 被重复或重新排列,集合并不改变,即{a,a,b,C,d }={a,b,c,d} ②集合的元素可以是具体事物,可以是抽象概念,也 可以是集体,如一本书,一支笔;集合{1,2,3}可以 是集合B={一本书,一支笔,{1,2,3}的元素。特别 地,以集合为元素的集合称为集合族或集合类如 A={1,2,3},{8,9,6}。 ③集合中元素之间可以有某种关联,也可以彼此毫 关系

特别注意： ① 集合并不决定于它的元素展示方法。集合的元素 被重复或重新排列，集合并不改变，即{a, a ,b, c, d, c}= { a, b, c, d}。 ②集合的元素可以是具体事物，可以是抽象概念，也 可以是集体，如一本书，一支笔；集合{1,2,3}可以 是集合B={一本书，一支笔，{1,2,3}} 的元素。特别 地，以集合为元素的集合称为集合族或集合类如 A={{1,2,3}, { 8,9,6}}。 ③集合中元素之间可以有某种关联，也可以彼此毫 无关系

集合的元素数 有限集A中所含元素的个数称为集合的 元数。记作:|A 如:A={1,3,2,4,5,9}则|A|=6 设A是所有英文字母组成的集合,则 A|=26。特别,|φ|=0

有限集A 中所含元素的个数称为集合的 元数。记作：| A | 如： A ={1,3,2,4,5,9} 则 | A |= 6； 设A是所有英文字母组成的集合，则 A=26。特别， |  |=0 集合的元素数

集合的表示法 列举法列元素法):将集合中的元素一一列举 或列出足够多的元素以反映集合中元素的特征, 例如:V={a,b,c,d,e}或 B={1,2,3,4,56,}。 描述法谓词表示法):将集合元素的条件或性 质用文字或符号在花括号内竖线后面表示出来。 A={x关于x的一个命题P}; 如:B={x0<x<10};B={xx=a2,a是自然数}

➢列举法(列元素法) ：将集合中的元素一一列举， 或列出足够多的元素以反映集合中元素的特征， 例如：V={a, b, c, d, e} 或 B={1,2,3, 4, 5,6,……}。 ➢描述法(谓词表示法) :将集合元素的条件或性 质用文字或符号在花括号内竖线后面表示出来。 A={x|关于x的一个命题P}; 如：B={x|0<x<10}; B= {x|x=a2 ,a是自然数}。 集合的表示法

>文氏图 用一个大的矩形表示全集,在矩形内画一些圆 其它的几何图形,来表示集合,有时也用一些点来表 示集合中的特定元素。 例如:集合A={a,b,c,de},用文氏图表示如下:

E A a e ➢文氏图 用一个大的矩形表示全集，在矩形内画一些圆或 其它的几何图形，来表示集合，有时也用一些点来表 示集合中的特定元素。 例如：集合A={a,b,c,d,e} ，用文氏图表示如下: d c b