东北大学：《离散数学》课程教学资源（PPT课件讲稿）第三章 集合论基础

第二篇集合论 主要包括如下内容: 集合论基础 二元关系 函数

第二篇 集合论 主要包括如下内容： 集合论基础 二元关系 函数

第三章集合论基础 本章主要介绍如下内容: 基本概念及集合的表示方法 集合间的关系 特殊集合 集合的运算 大包含排斥原理

第三章 集合论基础 本章主要介绍如下内容： 基本概念及集合的表示方法 集合间的关系 特殊集合 集合的运算 ＊包含排斥原理

3-1基本概念 1.集合与元素 集合是个最基本的概念。 集合:是由确定的对象(客体构成的集体。用 大写的英文字母表示 这里所谓“确定”是指:论域内任何客体, 要么属于这个集合,要么不属于这个集合,是 唯一确定的。 元素:集合中的对象,称之为元素 ∈:表示元素与集合的属于关系。 例如,N表示自然数集合,2∈N,而1.5不属于N 写成(1.5∈N,或写成1.5N

3-1 基本概念 1.集合与元素 集合是个最基本的概念。 集合：是由确定的对象(客体)构成的集体。用 大写的英文字母表示。 这里所谓“确定”是指：论域内任何客体， 要么属于这个集合，要么不属于这个集合，是 唯一确定的。 元素：集合中的对象，称之为元素。 ∈：表示元素与集合的属于关系。 例如，N表示自然数集合，2∈N，而1.5不属于N 写成(1.5∈N), 或写成 1.5N

2.有限集合与无限集合 这里对有限集合与无限集合只给出朴 素的定义,以后再给出严格的形式定义 有限集合:元素是有限个的集合 如果A是有限集合,用A表示A中元素 个数。例如,A={1,2,3},则A=3 无限集合:元素是无限个的集合 对无限集合的所谓‘大小’的讨论,以 后再进行

2. 有限集合与无限集合 这里对有限集合与无限集合只给出朴 素的定义，以后再给出严格的形式定义。 有限集合：元素是有限个的集合。 如果A是有限集合，用|A|表示A中元素 个数。例如，A={1,2,3}, 则|A|=3。 无限集合：元素是无限个的集合。 对无限集合的所谓‘大小’的讨论，以 后再进行

3集合的表示方法 列举法:将集合中的元素一一列出,写 在大括号内。 例如,N={1,2,34,}A={a,b,c,d} 描述法:用句子(或谓词公式)描述元素 的属性。 例如,B={xx是偶数} C={xx是实数且2X≤5 一般地,A={xP(x)},其中P(x)是谓词公 式,如果论域内客体a使得P(a)为真,则 a∈A,否则a∈A

3.集合的表示方法 列举法：将集合中的元素一一列出，写 在大括号内。 例如，N={1,2,3,4,……} A={a,b,c,d} 描述法：用句子(或谓词公式)描述元素 的属性。 例如，B={x| x是偶数} C={x|x是实数且2≤x≤5} 一般地，A={x|P(x)}, 其中P(x)是谓词公 式，如果论域内客体a使得P(a)为真，则 a∈A，否则aA

4.说明 ()集合中的元素间次序是无关紧要的,但是必须是可以 区分的,即是不同的。例如A={ab,c,a},B={c,b,a,}, 则A与B是一样的。 (2对集合中的元素无任何限制,例如令 A={人,石头,1,B},B={,{}} (3本书中常用的几个集合符号的约定: 自然数集合N={1,2,3,} 整数集合I,实数集合R,有理数集合Q (4)集合中的元素也可以是集合,下面的集合的含义不同: 如 a: 张书记 党支部(只有一个书记) {a}:分党委(只有一个支部 {{a}}:党委(只有一个分党委) {a}:市党委(只有一个党委)

4. 说明 ⑴集合中的元素间次序是无关紧要的，但是必须是可以 区分的，即是不同的。例如A={a,b,c,a}，B={c,b,a,}， 则A与B是一样的。 ⑵对集合中的元素无任何限制，例如令 A={人，石头，1，Ｂ}, B={Φ,{Φ}} ⑶本书中常用的几个集合符号的约定： 自然数集合N= {1,2,3,……} 整数集合I，实数集合R，有理数集合Q ⑷集合中的元素也可以是集合，下面的集合的含义不同： 如 a： 张书记 {a}: 党支部(只有一个书记) {{a}}： 分党委(只有一个支部) {{{a}}}： 党委 (只有一个分党委) {{{{a}}}}： 市党委(只有一个党委)

32集合间的关系 被包含关系(子集)c 1定义:A、B是集合,如果A中元素都是 B中元素,则称B包含A,A包含于B, 也称A是B的子集。记作AcB。 文氏图表示如右下图 例如,N是自然数集合, a)B R是实数集合,则NR 谓词定义: A∈Bx∈B)

3-2 集合间的关系 一.被包含关系(子集)  1.定义：A、B是集合，如果A中元素都是 B中元素，则称B包含A，A包含于B， 也称A是B的子集。记作AB。 文氏图表示如右下图。 例如，N是自然数集合， R是实数集合，则NR 谓词定义： ABx(x∈A→x∈B) A B

2.性质: (1)有自反性,对任何集合A有AcA。 (2)有传递性,对任何集合A、B、C,有 AcB且BC,则AcC。 (3)有反对称性,对任何集合A、B,有 AcB且BcA,则A=B

2. 性质： ⑴有自反性，对任何集合A有AA。 ⑵有传递性，对任何集合A、B、C，有 AB且 BC ，则AC。 ⑶有反对称性，对任何集合A、B，有 AB且 BA ，则A=B

相等关系 1.定义:A、B是集合,如果它们的元素完 全相同,则称A与B相等。记作A=B 定理:A=B,当且仅当AcB且BcA。 证明:充分性,已知AcB且BcA,假 设AB,则至少有一个元素a,使得a∈A而 a∈B;或者a∈B而agA。如果a∈A而 agB,则与AcB矛盾。如果a∈B而agA, 则与BcA矛盾。所以A=B 必要性显然成立,因为如果A=B,则必 有AcB且BcA

二. 相等关系 1. 定义：A、B是集合，如果它们的元素完 全相同，则称A与B相等。记作A=B。 定理：A=B，当且仅当AB且BA。 证明：充分性，已知AB且BA，假 设A≠B，则至少有一个元素a,使得a∈A而 aB；或者a∈B而aA。如果a∈A而 aB，则与AB矛盾。如果a∈B而aA， 则与 BA矛盾。所以A=B。 必要性显然成立，因为如果A=B，则必 有AB且 BA

谓词定义: A=BX∈B)x(X∈B→>X∈A) 冷X(Xx∈A→>X∈B)∧(X∈B→>x∈A) 冷Vx(x∈A>x∈B) 2.性质 (1)有自反性,对任何集合A,有A=A (2)有传递性,对任何集合A、B、C,如果 有A=B且B=C,则A=C (3)有对称性,对任何集合A、B,如果有 A=B,则B=A

谓词定义： A=BABBA x(x∈A→x∈B)x(x∈B→x∈A) x((x∈A→x∈B)(x∈B→x∈A)) x(x∈Ax∈B) 2. 性质 ⑴有自反性，对任何集合A，有A=A。 ⑵有传递性，对任何集合A、B、C，如果 有A=B且 B=C ，则A=C。 ⑶有对称性，对任何集合A、B，如果有 A=B，则B=A