离散数学第六章集合代数.ppt

《离散数学第六章集合代数.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章二元关系（重点）第二部分集合论第六章集合代数第八章函数（重点）1主要内容6.1集合的基本概念属于、包含、幂集、空集、文氏图等6.2集合的基本运算集合的初级运算：并、交、相对补、绝对补、对称差集合的广义并与广义交有穷集合元素的计数6.3集合恒等式集合运算的算律、恒等式的证明方法第六章集合代数26.1集合的基本概念1.集合定义集合没有精确的数学定义理解：由离散个体构成的整体称为集合，称这些个体为集合的元素常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、复数集合2.集合表示法枚举法----通过列出全体元素来表示集合谓词表示法----通过谓词概括集合元素的性质实例

2、：枚举法自然数集合N={0,1,2,3,…}谓词法S={x

3、x是实数，x21=0}3元素与集合1.集合的元素具有的性质无序性：元素列出的顺序无关相异性：集合的每个元素只计数一次确定性：对任何元素和集合都能确定这个元素是否为该集合的元素任意性：集合的元素也可以是集合2．元素与集合的关系隶属关系：或者3．集合的树型层次结构dA,aA4集合与集合集合与集合之间的关系：,=,⊈,,,定义6.1ABx(xAxB)定义6.2A=BABBA定义6.3ABABABA⊈Bx(xAxB)思考：和的定义注意和是不同层次的问题5空集、全集和

4、幂集1．定义6.4空集：不含有任何元素的集合实例：{x

5、xRx2+1=0}定理6.1空集是任何集合的子集。证对于任意集合A，Ax(xxA)T(恒真命题)推论是惟一的3.定义6.6全集E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集2.定义6.5幂集：P(A)={x

6、xA}实例：P()={},P({})={,{}}计数：如果

7、A

8、=n，则

9、P(A)

10、=2n.例如，A={1,2,3}则

11、P(A)

12、=23=866.2集合的运算初级运算集合的基本运算有定义6.7并AB={x

13、xAxB}交AB={x

14、xAxB}相对补A

15、B={x

16、xAxB}定义6.8对称差AB=(AB)(BA)定义6.9绝对补A=EA7文氏图集合运算的表示ABABABABABABABA–BAB~A8几点说明并和交运算可以推广到有穷个集合上，即A1A2…An={x

17、xA1xA2…xAn}A1A2…An={x

18、xA1xA2…xAn}ABAB=AB=AB=A9广义运算1.集合的广义并与广义交定义6.10广义并A={x

19、z(zAxz)}广义交A={x

20、z(zAxz)}实例{{1},{1,2},{1,2,3}}={1,2,3}{{1},{1

21、,2},{1,2,3}}={1}{{a}}={a}，{{a}}={a}{a}=a，{a}=a10关于广义运算的说明2.广义运算的性质(1)=，无意义(2)单元集{x}的广义并和广义交都等于x(3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算{A1,A2,…,An}=A1A2…An{A1,A2,…,An}=A1A2…An3.引入广义运算的意义可以表示无数个集合的并、交运算，例如{{x}

22、xR}=R这里的R代表实数集合.11运算的优先权规定1类运算：初级运算,,,，优先顺序由括号确定2类运算：广义

23、运算和运算，运算由右向左进行混合运算：2类运算优先于1类运算例1A={{a},{a,b}}，计算A(AA).解：A(AA)={a,b}({a,b}{a})=(ab)((ab)a)=(ab)(ba)=b12有穷集合元素的计数1.文氏图法2.包含排斥原理定理6.2设集合S上定义了n条性质，其中具有第i条性质的的元素构成子集Ai,那么集合中不具有任何性质的元素数为推论S中至少具有一条性质的元素数为13实例例2求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？定义以下集合：S={x

24、xZ1

25、x1000}A={x

26、xSx可被5整除}B={x

27、xSx可被6整除}C={x

28、xSx可被8整除}解得N=1000－(200+100+33+67)=600画出文氏图，然后填入相应的数字，解方法一：文氏图14实例方法二包含排斥原理

29、S

30、=1000

31、A

32、=1000/5=200,

33、B

34、=1000/6=166,

35、C

36、=1000/8=125

37、AB

38、=1000/lcm(5,6)=1000/33=33

39、AC

40、=1000/lcm(5,8)=