《离散数学]》PPT课件.ppt

《《离散数学]》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集合论由于集合论的语言适合于描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、排队论、开关理论，形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数，以及集合的基数问题。集合论第三章集合与关系§1集合的概念和表示法§2集合的运算§4序偶与笛卡尔积§5关系及其表示§6关系的性质§7复合关系和逆关系§8关系的闭包运算§9集合的划分和覆盖§10等价关系与等价类§11相容关系§12序关系§1集合的概念和表示法1、集合与元素（1）集合：就是把人们直观

2、的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。讨论：①一些不同的确定的对象之全体。例：1000以内的素数的集合；这个班里高个子学生的集合；（不是集合）②元素（成员）：组成集合的各个对象。③符号：用大写英文字母表示集合，用小写英文字母或其它符号表示元素。集合：A，B….元素：a，b….§1集合的概念和表示法④元素与集合间的关系：若a是集合S中的元素，则可写成aS；若b不是集S合中的元素，则可写成bS。⑤集合S的基数(势)：S中的元素个数。用

3、S

4、表示。⑥有限集合：集合的基数（元素）是有限的

5、。无限集合：集合的基数（元素）是无限的。§1集合的概念和表示法⑦本书中常用集合符:Im(m≥1)有限个正整数的集合{1,2,3……m}Nm(m≥0)有限个自然数的集合{0,1,2……m}以上是有限集合,下面是无限集合：N自然数集合{0,1,2……}I+正整数集合{1,2,3……}I整数集合{……-1,0,1,2……}P素数集合{大于1的正整数，只能被1和自己整除}Q有理数集合{i/j.i、j均为整数且j≠0}R实数集合{有理数、无理数}C复数集合{a+bi，a、b可为实数}§1集合的概念和表示法(2)集合的

6、表示方法:(a)枚举法(列举法)把集合的元素列于花括号内。例：命题的真假值组成的集合：S={T,F}自然数0,1,2,3,4五个元素的集合：P={0,1,2,3,4}(b)谓词公式描述法所有集合均可用谓词公式来表示：S={x

7、p(x)}§1集合的概念和表示法例：大于10的整数的集合：S1={x

8、xI∧x>10}偶整数集合：S2={x

9、y(yI∧x=2y)}有限个元素集合：S3={1,2,3,4,5}={x

10、xI∧(1≤x≤5)}S4={F,T}={x

11、x=T∨x=F}S5={1,4}={x

12、(x²-

13、5x+4=0)}(c)同一集合可以用多种不同的形式表示。(d)集合也可作为某一集合的元素。例：S={a,{1,2},p,{q}}§1集合的概念和表示法(3)三个特殊集合：空集、全集合、集合族《定义》如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用E表示。E={x

14、p(x)∨p(x)}p(x)为任何谓词公式《定义》不拥有任何元素的集合称为空集（或称零集），用表示={x

15、p(x)∧p(x)}={}注意：≠{}前者是空集，是没有元素的集合；后者是以作为元素的集合。§1集合的概

16、念和表示法《定义》集合中的元素均为集合，称这样的集合为集合族。例A={{a}，{b}，{c、d}}2、集合之间的关系《公理》给定二个集合A和B，当且仅当A和B具有同样的元素（成员），则A和B才是相等的，记作A=B并规定：（A=B）x(xA↔xB)例：{a,b,c}={b,a,a,c,c}§1集合的概念和表示法例：{a,b,c}={b,c,a}例：设P={{1,2},4}，Q={1,2,4}，则PQ《定义》设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A是B的子集，或者说A包含

17、于B，或者说B包含A，记作AB，或者BA。并规定：ABBAx(xA→xB)§1集合的概念和表示法例：A1={1,2,3}A2={0}A3={1,2,3,0}B={1,2,3,0}则A1、A2、A3均为B的子集合，并记为A1B，A2B，A3B《定义》设A、B是任意二个集合，若AB且A≠B，则称A是B的真子集，记作AB（A真包含于B）并规定：AB（AB∧A≠B）§1集合的概念和表示法注意：区分“”和“”的关系：“”关系是指集合和该集合中元素之间的关系。例：S={a,{b}

18、,c}则aS，{b}S，cS而“”关系是指二个集合之间的关系。例：S1={a,b}S2={a,b,1,2}则S1S2若A不包含于B，则也可表示成AB《定理》设E是全集，A是一个集合，则一定有AE。§1集合的概念和表示法《定理》设A、B是任意二个集合，当且仅当AB和BA才有A=B。证明：(ⅰ)充分性：（A=B）（AB∧BA）(A=B)x(xA→xB∧xB→xA)x(xA→x