( A B C) [ A (B C)]
[A (B C) (B C)] {A [(B C) (B C)]}
{A [(B C) (B C)]} [(A B C) (A B C)] 因为 A [(B C) (B C)]
离散数学教案
3、1 集合的基本概念
集合(set)(或称为集)就是数学中的一个最基本的概念。所谓集合,就就是指具有共同性
质的或适合一定条件的事物的全体,组成集合的这些“事物”称为集合的元素。
集合常用大写字母表示,集合的元素常用小写字母表示。若 A 就是集合, a 就是 A 的元
素,则称 a 属于 A ,记作 a A ;若 a 不就是 A 的元素,则称 a 不属于 A ,记作。若组成集合的元
素个数就是有限的,则称该集合为有限集(Finite Set),否则称为无限集(Infinite Set)。
常见集合专用字符的约定:
N —自然数集合(非负整数集)
幂集
Q —有理数集合( Q , Q )
F —分数集合( F , F ) C —复数集合 O —奇数集合
I (或 Z )—整数集合( I , I ) R —实数集合( R , R )
离散数学教案
学习目标: 1.深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价
类、商集、相容关系、(最大)相容类、偏序关系、极大元、极小元、上(下)界、 上(下)确界、最大(小)元、全序关系、良序关系等概念;
2.掌握集合的交、并、差、补、对称差的运算及其运算规律; 3.掌握关系的交、并、逆、复合运算、闭包运算及其性质; 4.掌握关系的矩阵表示与关系图; 5.深刻理解关系的自反性、反自反性、对称性、反对称性与传递性,掌握其 判别方法; 6.掌握集合的覆盖与划分的联系与区别; 7.掌握偏序关系的判别及其哈斯图的画法;会求偏序集中给定集合的n
(x y)n Cnk xk ynk k 0
x y 1
n
Cnn Cnk k 0
n
得
2n Cnk
k 0
故 P( A) 的元素个数就是 2n 。
人们常常给有限集 A 的子集编码,用以表示 A 的幂集的各个元素。具体方法就是: 设 A {a1, a2, , an} ,则 A 子集 B 按照含 ai 记1、不含 ai 记 0(i 1, 2, , n) 的规定依 次写成一个 n 位二进制数,便得子集 B 的编码。 例如,若 B {a1, an} ,则 B 的编码就是 100 01,当然还可将它化成十进制数。如果 n 4 ,那么这个十进制数为 9 ,此时特别记 B {a1, a4} 为 B9 。
定理 3、1、1 如果有限集 A 有 n 个元素,则其幂集 P( A) 有 2n 个元素。
证明 A 的所有由 k 个元素组成的子集数为从 n 个元素中取 k 个的组合数。
Cnk
n(n 1)(n 2) k!
(n k 1)
另外,因 A ,故 P( A) 的元素个数 N 可表示为
又因 令
N 1 Cn1 Cn2 Cnk
对称差的定义如图 3-1 所示。
由对称差的定义容易推得如下性质:
(1) A B B A (2) A A (3) A A (4) A B ( A B) ( A B) (5) (A B) C A (B C) 证明 (5) ( A B) C
图 3-1
[( A B) C] ( A B C)
3、2 集合的对称差运算
定义 3、2、1 设 A 、 B 就是两个集合,要么属于 A ,要么属于 B ,但不能同时属于 A 与
离散数学教案
B 的所有元素组成的集合,称为 A 与 B 的对称差集,记为 A B 。即
A B (A B) (B A) x x Ax B
例如,若 A {1, 2, c, d}, B {1,b,3, d},则 A B {2,c,b,3} 。
主要内容:
1.集合的基本概念及其运算 2.序偶与笛卡尔积 3.关系及其表示 4.关系的性质及其判定方法 5.复合关系与逆关系 6.关系的闭包运算 7.等价关系与相容关系 8.偏序关系 重点: 1.关系的性质及其判别; 2.关系的复合运算及其性质; 3.等价关系与等价类、等价关系与集合的划分的联系; 4.偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点: 1.关系的传递性及其判别; 2.等价关系的特性; 3.偏序关系的哈斯图的画法;偏序集中特异位置元素的求法。 教学手段: 通过多个实例的精讲帮助同学理解重点与难点的内容,并通过大量的练习使 同学们巩固与掌握关系的性质及其判别、关系的复合运算及其性质、等价关系 的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题: 习题 3、1:4,6;习题 3、2:3(8),4(12),6(m);习题 3、4:1 (2)、(4),3;习题 3、 5:1,4; 习 题 3 、 6:2,5,6; 习 题 3 、 7:2,5,6; 习 题 3 、 8:1(1)-(6); 习 题 3 、 9:3(2)、(4),4(3);习题 3、10:1 ,4,5。
{[(A B) (A B)] C} [(A B) (A B) C]
( A B C) ( A B C) {[(A B) ( A B)] C} 但 [( A B) ( A B)] C
={[( A B) A] [( A B) B]} C [( A A) ( A B) ( A B) (B B)] C [ ( A B) ( A B) ] C (A B C) (A B C) 故 (A B) C (A B C) (A B C) (A B C) (A B C) 又 A(B C)
脚标+与-就是对正、负的区分
P —素数集合 E —偶数集合
定义 3、1、1 对于每一个集合 A ,由 A 的所有子集组成的集合,称为集合 A 的幂集
(Power Set),记为 P( A) 或 2A .即 P(A) {B B A}。
例如: A {a,b, c}, P(A) {,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}。