中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第二部分 集合论 第三章 集合代数

第二部分集合论 集合论是研究集合一般性质的数学分支，创始人是 康托尔(G.Cantor1845-1918)。现代数学中，每个对 象（数，函数等）本质上都是集合，即可以用某种集 合来示义，数学的各个分支本质上都是在研究某一 种对象集合的性质，集合论的特点是研究对象的广 泛性，是计算机科学的基础理论表达工具。 1128

1/28 第二部分 集合论 • 集合论是研究集合一般性质的数学分支，创始人是 康托尔(G.Cantor 1845-1918)。现代数学中，每个对 象(数，函数等)本质上都是集合，即可以用某种集 合来示义，数学的各个分支本质上都是在研究某一 种对象集合的性质，集合论的特点是研究对象的广 泛性，是计算机科学的基础理论表达工具

第三章集合代数 3.1集合的基本概念 ·1.集合的定义 集合是现代数学中最重要的基本概念之一。我们知 道，在任何一个数学理论中，不可能对其中的每 个概念都严格定义，这样的概念一般为数学理论 中的原始概念，而称其余的概念为它的派生概念 如欧几里得几何学中，“点”和“线”是原始概 念，而“三角形”和“圆”则为派生概念。今天 我们介绍的“集合”也是一个不能严格定义的原 始概念。但是为了理解上的方便，我们仍然给 个不严格的定义。 2/28

2/28 第三章 集合代数 3.1集合的基本概念 • 1.集合的定义 集合是现代数学中最重要的基本概念之一。我们知 道，在任何一个数学理论中，不可能对其中的每 个概念都严格定义，这样的概念一般为数学理论 中的原始概念，而称其余的概念为它的派生概念。 如欧几里得几何学中，“点”和“线”是原始概 念，而“三角形”和“圆”则为派生概念。今天 我们介绍的“集合”也是一个不能严格定义的原 始概念。但是为了理解上的方便，我们仍然给一 个不严格的定义

3.1集合的基本概念 定义3.1：任何被称为“成员”或“元素”的 对象的聚集称为集合(Set)。 例如：自然数的全体N,有理数的全体Q,实 数的全体R,复数的全体C,整数的全体Z, 都是集合。 通常情况下，用带（或不带）下标的大写英文字 母表示集合，而用带（或不带）下标的小写英 文字母表示集合的元素或成员。 3/28

3/28 3.1 集合的基本概念 •定义3.1：任何被称为“成员”或“元素”的 对象的聚集称为集合(Set)。 例如：自然数的全体N，有理数的全体Q，实 数的全体R，复数的全体C，整数的全体Z， 都是集合。 通常情况下，用带(或不带)下标的大写英文字 母表示集合，而用带(或不带)下标的小写英 文字母表示集合的元素或成员

3.1集合的基本概念 ·2.集合的表示 集合是由它所包含的元素完全确定的，有多 种方法来表示一个集合。 (1).枚举法：当一个集合仅有有限个元素或元 素之间有明显的关系时，采用列出集合中全 部元素或部分元素的方法，叫枚举法。 例：A={1,2,3,4},B={a,b,c,x,y,Z,N ={0,1,2,3,.…}。 这种方法实际上是一种显示表示法，优点是 具有透明性，缺点是当集合中元素比较多时 会占据大量内存。 4/28

4/28 3.1 集合的基本概念 • 2.集合的表示 集合是由它所包含的元素完全确定的，有多 种方法来表示一个集合。 (1).枚举法：当一个集合仅有有限个元素或元 素之间有明显的关系时，采用列出集合中全 部元素或部分元素的方法，叫枚举法。 例：A={1,2,3,4}，B={a, b, c, …x, y, z}，N ={0,1,2,3, …}。 这种方法实际上是一种显示表示法，优点是 具有透明性，缺点是当集合中元素比较多时 会占据大量内存

3.1集合的基本概念 (2).描述法：一般用谓词来概括集合中元素的 特性，由谓词P(x)所定义的集合常记为： A={XP(x)}。 例：B={x|x∈R∧x2-1=0}。 谓词表示法是一种隐式表示法，所表示的集 合元素可以是很少的或无穷多个，从计算机 的角度来看，是种“动态”的表示法，不用 占据大量内存 (3).文氏图法(Venn):文氏图解法是一种利用 平面上的点的集合作成的对集合的图解，一 般用平面上的圆形或方形表示一个集合。 5/28

5/28 3.1 集合的基本概念 (2).描述法：一般用谓词来概括集合中元素的 特性，由谓词P(x)所定义的集合常记为： A={x |P(x)}。 例：B={x | x ∈R ∧x 2 -1=0}。 谓词表示法是一种隐式表示法，所表示的集 合元素可以是很少的或无穷多个，从计算机 的角度来看，是种“动态”的表示法，不用 占据大量内存。 (3).文氏图法(Venn)：文氏图解法是一种利用 平面上的点的集合作成的对集合的图解，一 般用平面上的圆形或方形表示一个集合

3.1集合的基本概念 •3.集合与元素的关系 元素和集合之间的关系是“隶属关系”，即 “属于”或“不属于”， “属于”记作∈， 不属于记作生。 例：A={a,{b,c,{d},a∈A, {b,c} ∈A,b走A。 ·例3-1：在一个很偏僻的孤岛上，住着 一些人家， 岛上只有一个理发师，该理 发师专给那些并且只给那些自己不刮脸 的人刮脸。那么该给这位理发师刮脸？ 6/28

6/28 3.1 集合的基本概念 • 3.集合与元素的关系 元素和集合之间的关系是“隶属关系”，即 “属于”或“不属于”，“属于”记作∈， 不属于记作。 例：A={a，{b，c}，{{d}}}，a ∈A， {b，c} ∈A，b  A。 •例3-1：在一个很偏僻的孤岛上，住着 一些人家，岛上只有一个理发师，该理 发师专给那些并且只给那些自己不刮脸 的人刮脸。那么该给这位理发师刮脸？

3.1集合的基本概念 在离散数学中，我们仅讨论界限清楚无二义 性的元素与集合的隶属关系，即元素a要么 属于集合A,要么不属于集合A,两者必居 其 ·4.集合的特性 (1).确定性：即a∈A或aA,两者必居其一 且仅居其一； (2).互异性：集合中相同的元素被视为同一元 素，即：{1,1,2,2}与{1,2}相同； 3)无序性：集合中的元素顺序并不重要，如 {1,2,3,4}与{2,3,4,1}相同。 7128

7/28 3.1 集合的基本概念 在离散数学中，我们仅讨论界限清楚无二义 性的元素与集合的隶属关系，即元素a要么 属于集合A，要么不属于集合A，两者必居 其一。 • 4.集合的特性 (1).确定性：即a∈A或a  A，两者必居其一 且仅居其一； (2).互异性：集合中相同的元素被视为同一元 素，即：{1，1，2，2}与{1，2}相同； (3).无序性：集合中的元素顺序并不重要，如 {1，2，3，4}与{2，3，4，1}相同

3.1集合的基本概念 ·5.集合之间的关系 ·定义32：设A,B是两个集合，如果B中的每个元 素都是A中的元素，则称B是A的子集合，简称子 集(Subset),这时也称B被A包含，或A包含B,记 作BCA,或A三B,称“∈”或“2”为包含关系 (Inclusion Relation)。如果B不被A包含，则记作 BdA。 例：NcZcQ∈R∈C,但ZdN; A={1,2,3,4,B={1,2,C={2,3},D={2,3} B,C,DCA;CCD;DEC;BC,D;C,DB; AB,C,D 对任意的集合A,都有ACA。 8/28

8/28 3.1 集合的基本概念 • 5.集合之间的关系 • 定义3.2：设A，B是两个集合，如果B中的每个元 素都是A中的元素，则称B是A的子集合，简称子 集(Subset)，这时也称B被A包含，或A包含B，记 作BA，或AB，称“  ”或“  ”为包含关系 (Inclusion Relation)。如果B不被A包含，则记作 BA。 例：N  Z  Q  R  C, 但ZN ; A={1，2，3，4}，B={1，2}，C={2，3}，D={2，3}， 则 B,C,DA; CD; DC; BC,D; C,DB; AB,C,D 对任意的集合A，都有AA

3.1集合的基本概念 定义3.3：设A,B为集合，如果AcB且BcA,则称 A与B相等，记作A=B,如果A与B不相等，则记作 AB。 相等的符号化表示为：A=B台ACBABCA 例：A={xk∈N,且x≤4}，B={0,1,2,3,4}则 A=B。 ·定义3.4：设A,B为集合，如果BcA且B≠A,则称 B是A的真子集Proper Subset),记作BcA,称 “c”为真包含关系(Properly Inclusion Relation), 如果B不是A的真子集，则记作B丈A 9/28

9/28 3.1 集合的基本概念 • 定义3.3：设A，B为集合，如果AB且BA，则称 A与B相等，记作A=B，如果A与B不相等，则记作 A≠B。 相等的符号化表示为：A=BABBA 例：A={x|x∈N，且x≤4}，B={0，1，2，3，4}则 A=B。 • 定义3.4：设A，B为集合，如果BA且B≠A，则称 B是A的真子集(Proper Subset)，记作BA，称 “  ”为真包含关系(Properly Inclusion Relation)， 如果B不是A的真子集，则记作BA

3.1集合的基本概念 这时或者BA,或者B=A,符号化表示为： BCA→BcA∧B≠A 例：NCZCOCRCC,但NtN, {0,1}，,{2,3} 是{0,1,2,3}的真子集，但{1,4不是。 ·定义3.5：不含任何元素的集合叫做空集 (Empty Set),记作Q。空集符号化表示为： ⑦={xkx。 例：设A={xx∈RAx2+1=0},是方程x2+1=0的实 数解集，而该方程无实数解，所以A=①。 10/28

10/28 3.1 集合的基本概念 这时或者 ，或者B=A，符号化表示为： 例： ，但 ，{0,1}，{2,3} 是{0,1,2,3}的真子集，但{1,4}不是。 •定义3.5：不含任何元素的集合叫做空集 (Empty Set)，记作○。空集符号化表示为： ○={x |x ≠x}。 例：设 ，是方程 的实 数解集，而该方程无实数解，所以A= ○。 N  Z  Q  R  C N  N B  A B  A B  A B  A {x | x R x 1 0} 2 A =   + = 1 0 2 x + =