电子工业出版社：计算机类本科规划教材《离散数学》课程教学资源（PPT课件讲稿）第3章 集合

第3章集合 第3章集合 31集合的基本概念 3,2集合的运算 33集合恒等式 34集合的覆盖与划分 35笛卡尔积 返回总目录

第3章 集合 第3章 集合 3.1 集合的基本概念 3.2 集合的运算 3.3 集合恒等式 3.4 集合的覆盖与划分 3.5 笛卡尔积 返回总目录

第3章集合 第3章集合 3.1集合的基本概念 些确定的、能区分的对象的全体是集合,通常用大 写的英文字母表示。组成集合的对象叫做集合的元素或成 员,常用小写的英文字母表示 集合的元素必须是确定的。所谓确定的,是指任何 个对象是不是集合的元素是明确的、确定的,不能模棱两 可 集合的元素又是能区分的,能区分的是指集合中的元 素是互不相同的。如果一个集合中有几个元素相同,算做 个。例如集合1,2,3,3}和1,2,3}是同一集合

第3章 集合 第3章 集 合 3.1集合的基本概念 一些确定的、能区分的对象的全体是集合，通常用大 写的英文字母表示。组成集合的对象叫做集合的元素或成 员，常用小写的英文字母表示。 集合的元素必须是确定的。所谓确定的，是指任何一 个对象是不是集合的元素是明确的、确定的，不能模棱两 可。 集合的元素又是能区分的，能区分的是指集合中的元 素是互不相同的。如果一个集合中有几个元素相同，算做 一个。例如集合1,2,3,3和1,2,3是同一集合

第3章集合 集合的元素是任意的对象,对象是可以独立存在的具体 的或抽象的客体。它可以是独立存在的数、字母、人或其它 物体,也可以是抽象的概念,当然也可以是集合。例如集合 1,2,13}1,2}的元素3}和1,2}就是集合 集合的元素又是无序的,即1,2,3}和3,1,2}是同一集合 设S是集合,a是S的一个元素,记为a∈S,读做"a属于 ”,也可读做“a在S中”。如果a不是S的元素,记为agS, 读做“a不属于S”,也可读做“a不在S中”。 例如 ①26个英文字母组成一个集合,任一英文字母是该集 的元素 ②直线上的所有点组成实数集合R,每一个实数是集合R 的元素 ③陕西科技大学全体学生组成一个集合,该校的每一个 学生是这个集合的元素

第3章 集合 集合的元素是任意的对象，对象是可以独立存在的具体 的或抽象的客体。它可以是独立存在的数、字母、人或其它 物体，也可以是抽象的概念，当然也可以是集合。例如集合 1,2,3,1,2的元素3和1,2就是集合。 集合的元素又是无序的，即1,2,3和3,1,2是同一集合。 设S是集合，a是S的一个元素，记为aS，读做“ a属于 S”，也可读做“ a在S中”。如果a不是S的元素，记为aS， 读做“ a不属于S ”，也可读做“ a不在S中” 。 例如： ①26个英文字母组成一个集合，任一英文字母是该集合 的元素。 ②直线上的所有点组成实数集合R，每一个实数是集合R 的元素。 ③陕西科技大学全体学生组成一个集合，该校的每一个 学生是这个集合的元素

第3章集合 3.1.1集合的表示法 集合有三种表示法。 第一种表示法是列举法:在花括号“}”中列举出 该集合的元素,元素之间用逗号隔开 例如: 1.2345 =1,2,3, =0,1,-1,2,2,…} STF 第二种表示法是描述法:用谓词界定集合的元素 例如 Q=x|x是有理数 R=1x|x是实数 C=x|x是复数 A-x|xe1∧0<x∧x<5

第3章 集合 3.1.1集合的表示法 集合有三种表示法。 第一种表示法是列举法：在花括号“”中列举出 该集合的元素，元素之间用逗号隔开。 例如： I5 =1,2,3,4,5 I+ =1,2,3, … I =0,1,-1,2,-2, … S=T,F 第二种表示法是描述法：用谓词界定集合的元素。 例如： Q=x | x是有理数 R=x | x是实数 C=x | x是复数 A=x | x I∧0＜x∧x＜5

第3章集合 若用P(x)表示x是有理数,那么Q又可表示为: Ox P(x) 般地说,集合可用描述法表示为: x|A(x)}其中,A(x)是谓词 显然,当a∈S时,则A(a)为真;反之,当4(a)为真,则 a∈S。即a∈S的充分必要条件是A(a)为真 在中学的教科书中将自然数定义为: N=12.3.…} 这是对的。在离散数学中,认为自然数是由0开始的,即 N=0.1,2,3.…} 我们把这种由0开始的自然数集叫做扩展的自然数集。 离散数学中使用扩展的自然数集。本书的自然数集是指扩 展的自然数集

第3章 集合 若用P(x)表示x是有理数，那么Q又可表示为： Q=x | P(x)  一般地说，集合可用描述法表示为： S=x | A(x)  其中，A(x)是谓词 显然，当aS 时，则A(a)为真；反之，当A(a)为真，则 aS。即aS的充分必要条件是A(a)为真。 在中学的教科书中将自然数定义为： N=1,2,3, … 这是对的。在离散数学中，认为自然数是由0 开始的，即 N=0,1,2,3, … 我们把这种由0 开始的自然数集叫做扩展的自然数集。 离散数学中使用扩展的自然数集。本书的自然数集是指扩 展的自然数集

第3章集合 具有有限个元素的集合叫有限集,否则叫无限集。有 狠集元素的个数称为该集合的基数,也叫集合的势。有限 集A的基数记为 例如:设A=ab,c,A是有限集,A的基数A=3 无限集也有基数的概念。无限集的基数比有限集的基 数要复杂的多,本书将在53节中介绍 扩展的自然数集N=0,1,2,3,…}是无限集。整数集合Ⅰ、 有理数集合Q、实数集合R和复数集合C都是常见的无限集

第3章 集合 具有有限个元素的集合叫有限集，否则叫无限集。有 限集元素的个数称为该集合的基数，也叫集合的势。有限 集A的基数记为|A|。 例如：设 A=a,b,c，A 是有限集，A的基数|A|=3。 无限集也有基数的概念。无限集的基数比有限集的基 数要复杂的多，本书将在5.3节中介绍。 扩展的自然数集N=0,1,2,3, …是无限集。整数集合I、 有理数集合Q、实数集合R和复数集合C都是常见的无限集

第3章集合 3.12子集和集合的相等 定义3.1.1设A,B是任意的集合,当A的每一元素都 是B的元素时,则称A是B的子集,也称A包含在B内或B包 含A。记为AcB或BA。 当A不是B的子集时,记为A实B。 AB用谓词公式表示为:AcB>(x)x∈A→x∈B) AgB用谓词公式表示为:AgB>(丑x)(x∈A∧x≠B) 例如:设A=1},B=1,2},C=1,2,3}则 Aca acB, BcC, Acc C B 可以证明,集合的包含有下列性质: ①自反性。即对任意集合A,AcA ②传递性。即对任意集合A、B、C,当AcB和BcC 时,AcC

第3章 集合 3.1.2子集和集合的相等 定义3.1.1 设A，B是任意的集合，当A的每一元素都 是B的元素时，则称A是B的子集，也称A包含在B内或B包 含A。记为AB或BA。 当A不是B的子集时，记为A⊈B。 AB用谓词公式表示为：AB(x)(xA→xB) A⊈B用谓词公式表示为： A⊈B(x)(xA∧xB) 例如：设A=1，B=1,2，C=1,2,3 则 AA AB，BC，AC C⊈B 可以证明，集合的包含有下列性质： ①自反性。即对任意集合A，AA。 ②传递性。即对任意集合A、B、C，当AB和BC 时，AC

第3章集合 定义3.1.2设A,B是集合,如果AcB且BcA,则称A 与B相等。记为A=B。如果A与B不相等,记为A≠B。 集合相等也可用谓词公式表示为 A=B(Vx)(x∈A→x∈B)∧(Vx)(x∈B→x∈A) (Vx)(x∈Ax∈B 例如:设A=1,2},B=1,12},C=2,1}则 A=C,A≠B 由集合相等的定义可以看出,集合相等有下列性质: ①自反性:即对任意集合A,A=A ②对称性:即对任意集合A、B,当A=B时,B=A。 ③传递性:即对任意集合A、B、C,当A=B和B=C时 A=C

第3章 集合 定义3.1.2 设A，B是集合，如果AB且BA，则称A 与B相等。记为A=B。如果A与B不相等，记为A≠B。 集合相等也可用谓词公式表示为： A=BAB∧BA (x)(xA→xB)∧(x)(xB→xA) (x)(xA↔xB) 例如：设 A=1,2，B=1, 2，C=2,1 则 A=C，A≠B 由集合相等的定义可以看出，集合相等有下列性质： ①自反性: 即对任意集合A，A=A。 ②对称性: 即对任意集合A、B，当A=B时，B=A。 ③传递性: 即对任意集合A、B、C，当A=B和B=C时， A=C

第3章集合 定义3.1.3设A,B是集合,如果A∈B且A≠B,则称A是 B的真子集。记为A(x)x∈A∈B)∧(3x)(x∈B∧xgA) 例如:设A=a},B=1ab},C=abc}则 acb, BcC, AcO A a 又如,自然数集是整数集合的真子集,也是有理数集 和实数集合的真子集,即Ncl,NcQ,NCR

第3章 集合 定义3.1.3 设A，B是集合，如果AB且A≠B，则称A是 B的真子集。记为AB。如果A不是B的真子集，记为AB。 真子集用谓词公式表示为： ABAB∧A≠B (x)(xA→xB)∧(x)(xB∧xA) 例如：设 A=a，B=a,b，C=a,b,c 则 AB，BC，AC AA 又如，自然数集是整数集合的真子集，也是有理数集 合和实数集合的真子集，即NI，NQ，NR

第3章集合 定义3.14不包含任何元素的集合叫空集。记为必。 空集可以表示为 =x|P(x)∧-P(x)}其中,P(x)为任意谓词 空集是不包含任何元素的集合,所以,0 定理3.1.1空集是任意集合的子集。 证明:设A是任意集合。对任意对象x,由空集的定义 知,x∈⑧为假,由条件联结词的定义知,x∈⑧→x∈A为真。 根据全称推广规则有 (x)(x∈→→x∈A) 为真,故cA

第3章 集合 定义3.1.4 不包含任何元素的集合叫空集。记为。 空集可以表示为： =x | P(x)∧P(x)  其中，P(x)为任意谓词 空集是不包含任何元素的集合，所以，||=0。 定理3.1.1 空集是任意集合的子集。 证明：设A是任意集合。对任意对象x，由空集的定义 知，x为假，由条件联结词的定义知，x→xA为真。 根据全称推广规则有 (x)( x→xA) 为真，故A