集合的概念与表示法.ppt

第3章集合
集合的概念与表示法
集合的运算与性质
集合的划分与覆盖
排列与组合
归纳原理
容斥原理和抽屉原理
递推关系
集合论在命题逻辑中的应用
7/28/2017
集合的概念与表示法
集合的概念
集合作为数学的一个基本而又简单的原始概念,是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合,集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合,用小写字母(如a、b)表示集合中的元素。
给定一个集合A和一个元素a,可以判定a是否在集合A中。如果a在A中,我们称a属于A,记为a∈A。否则,称a不属于A,记为aA。
例如,某大学计算机系的全体学生、所有自然数等都是集合。
7/28/2017
由集合的概念可知,集合中的元素具有确定性、互异性、无序性和抽象性的特征。其中:
(1)确定性是指:一旦给定了集合A,对于任意元素a,我们就可以准确地判定a是否在A中,这是明确的。
(2)互异性是指:集合中的元素之间是彼此不同的。即集合{a,b,b,c}与集合{a,b,c}是一样的。
(3)无序性是指:集合中的元素之间没有次序关系。即集合{a,b,c}与集合{c,b,a}是一样的。
(4)抽象性是指:集合中的元素是抽象的,甚至可以是集合。如A={1,2,{1,2}},其中{1,2}是集合A的元素。
7/28/2017
集合是多种多样的,我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数,记为|A|。当|A|有限时,称A为有限集合;否则,称A为无限集合。
下面将本书中常用的集合符号列举如下:
N:表示全体自然数组成的集合。
Z:表示全体整数组成的集合。
Q:表示全体有理数组成的集合。
R:表示全体实数组成的集合。
Zm:表示模m同余关系所有剩余类组成的集合。
7/28/2017
集合的表示法
表示一个集合通常有两种方法:列举法和谓词表示法。
1. 列举法(或枚举法)
列举法就是将集合的元素全部写在花括号内,元素之间用逗号分开。例如:A={a,b,c},B={0,1,2,3,…}。
列举法一般用于有限集合和有规律的无限集合。
2. 谓词表示法(或描述法)
谓词表示法是用谓词来概括集合中元素的属性。通常用{x|p(x)}来表示具有性质p的一些对象组成的集合。例如:{x|1≤x≤6∧x为整数}为由1、2、3、4、5、6组成的集合。
下面讨论集合之间的关系。
7/28/2017
集合的包含与相等
包含与相等是集合间的两种基本关系,也是集合论中的两个基本概念。两个集合相等是按照下述原理定义的。
外延性原理两个集合A和B是相等的,当且仅当它们有相同的元素。记为A=B。
例如,若A={2,3},B={小于4的素数},则A=B。
设A和B为两个集合,若对于任意的a∈A必有a∈B,则称A是B的子集,也称A包含于B或B包含A,记作AB。如果B不包含A,记作AB。B包含A的符号化表示为:
ABx(x∈A→x∈B)。
例如,若A={1,2,3,4},B={1,2},C={2,3},则BA且CA,但CB。
7/28/2017
集合A和B相等当且仅当这两个集合互为子集。即:A=BAB∧BA。
证明若A=B,则A和B具有相同的元素,于是x(x∈A→x∈B)、x(x∈B→x∈A)都为真,即AB且BA。
反之,若AB且BA,假设A≠B,则A与B元素不完全相同。不妨设有某个元素x∈A但xB,这与AB矛盾,所以A=B。
这个定理非常重要,是证明两个集合相等的基本思路和依据。
7/28/2017
设A、B和C是三个集合,则:
(1)AA。
(2)AB∧BCAC。
证明(1)由定义显然成立。
(2)AB∧BCx(x∈A→x∈B)∧x(x∈B→x∈C)x((x∈A→x∈B)∧(x∈B→x∈C))x(x∈A→x∈C)AC。
设A和B是两个集合,若AB且B中至少有一个元素b使得bA,则称A是B的真子集,也称A真包含于B或B真包含A,记作AB。否则,记作AB。B真包含A的符号化表示:
7/28/2017
ABx(x∈A→x∈B)∧x(x∈B∧xA)。
若两个集合A和B没有公共元素,我们说A和B是不相交的。
例如,若A={a,b,c,d},B={b,c},则B是A的真子集,但A不是A的真子集。
需要指出的是,∈与表示元素和集合的关系,而、与=表示集合和集合的关系。
例如,若A={0,1},B={0,1,{0,1}},则AB且AB。
设A、B