《离散数学讲义》PPT课件

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

1、第三章集合与关系3－1集合的概念和表示法离散数学1集合论起源：起源16世纪末，数学危机（理发师：只给那些不给自己理发的人理发，不给那些给自己理发的人理发）（理发师？属于那一类？）定义集合的方法在逻辑上来说，有矛盾1876-1908，cantor奠定了集合论基础(朴素集合论)20世纪初，zermole建立的公理化集合论，解决了悖论（公理化集合论）离散数学2离散数学31、集合概念及表示（1）集合①概念一般地说，把具有相同性质的一些东西，汇集成一个整体，就形成一个集合。例如：教室内的桌子；全国的高等学校；自然数的全体；直线上的点。②分类有限集：集合的元素个数是限的。无限集：集合的元素个数是无

2、限的。离散数学4（2）表示①集合：A～Z；元素（集合中的事物）：a～z。②I元素a属于集合A，记作：aAII元素a不属于集合A，记作：aA离散数学5③说明集合的方法I列举法：将某集合的元素列举出来。例如：A={a,b,c,d},D={桌子，灯泡，自然数，老虎}，C={2,4,6,…,2n}注意：集合的元素可以是一个集合。例如：S={a,{1,2},p,{q}}，q{q}，但qS。II叙述法：利用一些规则，来决定某一事物是否属于该集合。例如：S1={x

3、x是正奇数}S2={x

4、x是中国的省}S3={y

5、y=a或y=b}。另外，用P(x)表示任何谓词，则{x

6、P(x)}可表示集

7、合。离散数学62、集合相等外延性原理：两个集合是相等的，当且仅当它们有相同的成员。两个集合A和B相等，记作：A=B，两个集合不相等，则记作AB。离散数学7例如：设A是小于10的素数集合，即A={2,3,5,7}，设代数方程x4－17x3＋101x2－247x＋210＝0的所有根可组成集合B，则B={2,3,5,7}。又如：{1,2,4}={1,2,2,4}{1,2,4}={1,4,2}{1,3,5,…}={x

8、x是正奇数}但：{{1,2},4}{1,2,4}注意：集合没有次序之分，集合中的元素可以重复。离散数学83、子集（1）概念定义3-1.1设A、B是任意两个集合，假设A是每一个

9、元素是B的成员，则称A为B的子集，或A包含在B内，或B包含A。记作：AB，或BA。AB(x)(xAxB)例如：A={1,2,3}，B={1,2}，C={1,3}，D={3};则有：BA，CA，DA，DC。根据子集的定义，有：AA自反性(AB)(BC)(AC)传递性离散数学9（2）应用定理3-1.1集合A和B相等的充分必要条件是这两个集合互为子集。离散数学104、真子集定义3-1.3如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集。记作：AB。即：AB(AB)(AB)AB(x)(xAxB)(

10、x)(xBxA)离散数学115、空集（1）概念定义3-1.3不包含任何元素的集合是空集。记作：。＝{x

11、P(x)P(x)}，其中P(x)是任意谓词。注意：{}，但{}。离散数学12（2）性质定理3-1.2对于任意一个集合A，A。注意：I对于每一个非空集合A，至少有两个不同的子集：A和，即：AA和A。我们称A和为平凡子集。II一般来说，A的每一个元素都能确定A的一个子集，即若aA，则{a}A。离散数学136、全集定义3-1.4在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集。记作：E。(x)(xE)恒真。E＝{x

12、P(x)

13、P(x)}，P(x)任何谓词。注意：全集概念相当于论域设全集E={a,b,c}，可能的子集有：S0=,S1={a},S2={b},S3={c},S4={a,b},S5={a,c},S6={b,c},S7={a,b,c}。SiE(i=0,1,2,…,7)。注意：对于一个元素个数为n的全集E，其可能的子集个数为2n。离散数学147、幂集定义3-1.5给定集合A，有集合A的所有子集为元素组成的集合，称为集合A的幂集。记作：P(A)例如：A={a,b,c}P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}离散数学15（2）性质定理3-1.3如果有

14、限集合A有n个元素，则其幂集P(A)有2n个元素。离散数学16（3）编码引入一种编码，用来唯一地表示有限幂集的元素。例如：S＝{a,b,c}P(S)={Si

15、iJ}其中：J={i

16、i是二进制数且000≤i≤111}则：S011=S3={b,c},S110=S6={a,b}。一般地P(S)={S0,S1,…,S2n-1}即：P(S)={Si

17、iJ}其中：离散数学173－1习题作业P86（6）c）；（7）；（10）3－2集合的运算离散数学18离