离散数学第三章集合的基本概念和运算知识点总结

集合论部分

第三章、集合的基本概念和运算

3.1 集合的基本概念集合的定义与表示

集合与元素

集合 没有精确的数学定义

理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员 集合的表示

列元素法 A={ a, b, c, d }

谓词表示法 B={ x | P(x) }

B 由使得 P(x) 为真的 x 构成常用数集

N, Z, Q, R, C 分别表示自然数、整数、有理数、

实数和复数集合，注意 0 是自然数.

元素与集合的关系：隶属关系

属于 ，不属于

实例

A={ x | x R x2-1=0 }, A={-1,1}

1 A, 2 A

注意：对于任何集合 A 和元素 x (可以是集合)，

x A和 x A 两者成立其一，且仅成立其一.

集合之间的关系

包含（子集） A B x (x A x B)

不包含 A B x (x A x B)

相等 A = B A B B A

不相等 A B

真包含 A B A B A B

不真包含 A B

思考： 和 的定义

注意 和 是不同层次的问题

空集 不含任何元素的集合

实例 {x | x2+1=0 x R} 就是空集

定理 空集是任何集合的子集

A x (x x A) T

推论 空集是惟一的.

证 假设存在 1和 2，则 1 2 且 1 2，因此 1= 2

全集 E

相对性

在给定问题中，全集包含任何集合，即 A (A E )

幂集定义 P(A) = { x | x A }

实例

P( ) = { }，

P({ }) = { ,{ }}

P({1,{2,3}})={ ,{1},{{2,3}},{1,{2,3}}}

计数

如果 |A| = n，则 |P(A)| = 2n

3.2 集合的基本运算

集合基本运算的定义

并 A B = { x | x A x B }

交 A B = { x | x A x B }

相对补 A B = { x | x A x B }

对称差 A B = (A B) (B A)

= (A B) (A B)

绝对补 A = E A

文氏图（John Venn）

关于运算的说明

运算顺序： 和幂集优先，其他由括号确定

并和交运算可以推广到有穷个集合上，即

A1 A2 …An= {x | x A1 x A2 … x An}

A1 A2 …An= {x | x A1 x A2 … x An}

某些重要结果

A B A

A B A B= （后面证明）

A B= A B=A

命题演算法证 X Y：任取 x ， x X …

例3 证明A B P(A) P(B)

任取x

x Y

x P(A) x A x B x P(B)

任取x

x A {x} A {x} P(A) {x} P(B)

{x} B x B

包含传递法证 X Y：找到集合T 满足 X T 且 T Y，从而有X Y 例4 A B A B

证 A B A

A A B

所以 A B A B

利用包含的等价条件证 X Y：

例5 A C B C A B C

证 A C A C=C

B C B C=C

(A B) C=A (B C)=A C=C

(A B) C=C A B C

命题得证

反证法证 X Y：欲证X Y, 假设命题不成立，必存在 x 使得 x X 且 x Y. 然 后推出矛盾.

例6 证明 A C B C A B C

证 假设 A B C 不成立，

则 x (x A B x C)

因此 x A 或 x B，且 x C

若 x A, 则与 A C 矛盾；

若 x B, 则与 B C 矛盾.

利用已知包含式并交运算：由已知包含式通过运算产生新的包含式X Y X Z Y Z, X Z Y Z

例7 证明 A C B C A C B C A B

证 A C B C， A C B C

上式两边求并，得

(A C) (A C) (B C) (B C)

(A C) (A C) (B C) (B C)

A (C C) B (C C)

A E B E

A B

命题演算法证明X=Y：任取 x ，

x X … x Y

x Y … x X

或者

x X … x Y

例8 证明 A (A B)=A （吸收律）

证 任取x,

x A (A B) x A x A B

x A (x A x B) x A

等式替换证明X=Y：不断进行代入化简，最终得到两边相等

例9 证明A (A B)=A （吸收律）

证 (假设交换律、分配律、同一律、零律成立)

A (A B)

=(A E) (A B) 同一律

=A (E B) 分配律

=A (B E) 交换律

=A E 零律

=A 同一律

反证法证明X=Y：假设 X=Y 不成立，则存在 x 使得 x X且x Y，或者存在 x 使得 x Y且x X，然后推出矛盾.

例10 证明以下等价条件

A B A B=B A B=A A B=

(1) (2) (3) (4) 证明顺序：

(1) (2), (2) (3), (3) (4), (4) (1)

(1) (2)

显然B A B，下面证明A B B.

任取x，

x A B x A x B x B x B x B

因此有A B B. 综合上述（2）得证.

(2) (3)

A=A (A B) A=A B

（将A B用B代入)

(3) (4)

假设A B , 即 x A B，那么x A且x B. 而

x B x A B.

从而与A B=A矛盾.

(4) (1)

假设A B不成立，那么

x (x A x B) x A B A B

与条件（4）矛盾.

集合运算法证明X=Y：由已知等式通过运算产生新的等式

X=Y X Z=Y Z, X Z=Y Z，X-Z=Y-Z

例11 证明A C=B C A C=B C A=B

证 由 A C=B C 和 A C=B C 得到

(A C)-(A C)=(B C)-(B C)

从而有 A C=B C

因此

A C=B C (A C) C =(B C) C

A (C C) =B (C C) A =B A=B

3.3 集合中元素的计数

集合的基数与有穷集合

集合 A 的基数：集合A中的元素数，记作 cardA

有穷集 A： cardA=|A|=n，n为自然数.

有穷集的实例：

A={ a,b,c}, cardA=|A|=3；

B={ x | x2+1=0, x R}, cardB=|B|=0

无穷集的实例：

N, Z, Q, R, C 等

包含排斥原理：定理 设 S 为有穷集，P1, P2, …, Pm 是 m 种性质， Ai 是 S 中具有性质 Pi 的元素构成的子集，i=1, 2,

…, m.则 S 中不具有性质 P1, P2, …, Pm 的元素数为

证明要点：任何元素 x，如果不具有任何性质，则对等式右边计数贡献为１，否则为０

证 设 x不具有性质 P1, P2, … , Pm ,

x Ai , i = 1, 2, … , m

x Ai Aj , 1 i < j m

…

x A1 A2 … Am ,

x 对右边计数贡献为

1 0 + 0 0 + … + ( 1)m · 0 = 1

例1 求1到1000之间（包含1和1000在内）既不能被 5 和6 整除，也不能被 8 整除的数有多少个？

解：S ={ x | x Z, 1 x 1000 },

如下定义 S 的 3 个子集 A, B, C：

A={ x | x S, 5 | x }，

B={ x | x S, 6 | x }，

C={ x | x S, 8 | x }

对上述子集计数：

|S|=1000,

|A|= 1000/5 =200, |B|= 1000/6 =133，

|C|= 1000/8 =125,

|A B|= 1000/30 =33, |B C| = 1000/40 =25,

|B C|= 1000/24 =41,

|A B …… 此处隐藏：1777字，全部文档内容请下载后查看。喜欢就下载吧 ……