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