离散数学第三章集合的基本概念和运算知识点总结
时间:2025-04-04
时间:2025-04-04
集合论部分
第三章、集合的基本概念和运算
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 中具有 …… 此处隐藏:1507字,全部文档内容请下载后查看。喜欢就下载吧 ……
下一篇:体育组计划2012-2013