集合的划分与覆盖-集合与关系-离散数学.pptx

集合的划分与覆盖,第1页,对集合进行讨论时，常把一个集合化分成若干个子集加以讨论如：图书馆的图书，要分成许多类存放，学校的学生要按照专业分成许多班，…即对集合的元素划分 知识点： 划分基本概念 覆盖基本概念,第2页,,,,,,,,,,,例：集合的覆盖,第3页,,,例：集合划分(分类),,,,,第4页,,一、集合的划分与覆盖的定义,定义3-9.1 覆盖：设A是一个非空集合，S={S1, S2,. ,Sn}, (1)SiΦ，SiA (i=1,2,.,n)， (2) S1∪S2∪.∪Sn =A (i=1,2,., n) 则称S是A的覆盖 设S={S1, S2,. ,Sn}是A一个覆盖, 且 SiSj=Φ (ij,1≤i,j≤n)，则称S是A的划分 划分块(类):每个Si均称为这个划分的一个划分 块(类)举例,例 A={1,2,3}，S1={{1,2,3}}，S2={{1},{2},{3}}， S3={{1,2},{3}}， S4={{1,2},{2,3}}, S5={{1},{3}} 是集合X的覆盖的有： 是集合X的划分的有：,划分一定是覆盖；但覆盖不一定是划分划分：,S1, S2 ,S3 ,S4 。

S1, S2 ,S3集合的划分不是唯一的第5页,A={1,2,3}，可构造多少个A的划分？,思考题,第6页,,例：4个元素的集合可构造多少个划分？ 解: 4=1+1+1+1,有1种; 4=4,有1种; 4=1+3对应 种不同的划分; 4=2+2对应 种不同的划分; 4=1+1+2对应 种不同的划分; 故4个元素的集合总共有 1+1+4+3+6=15 种不同的划分第7页,,,,,,,,,,,,,,,,,,,,,,,,,4个=1个+3个对应 种不同的划分;,4个=2个+2个对应 种不同的划分;,4个=1个+1个+2个对应 种不同的划分;,例、4个元素的集合共有多少个划分?,第8页,最小划分：划分块最少的划分即只有一个划分 块的划分，这个划分块就是X本身 最大划分：划分块最多的划分即每个划分块里 只有一个元素的划分 例： A={1,2,3}， S1={{1,2,3}}，S2={{1},{2},{3}}，S3={{1,2},{3}}， S4={{1,2},{2,3}}, S5={{1},{3}} S1,S2,S3是一种划分，其中S1是最小划分，S2是最大划分。

二、最小划分与最大划分,第9页,例 X是工大学生集合, A和B都是X的划分： A={H,N},HX, NX, H={河南人},N={非河南人} B={M,W},MX, WX, M={男生},W={女生} C={H∩M, H∩W, N∩M, N∩W } 称C是X的交叉划分H,N,三、交叉划分,,,M,W,,,,,,,H ∩M,H ∩W,N∩M,N∩W,第10页,定义3-9.2：若A={A1, A2,. ,Am}与B={B1,B2,.,Bn}都是集合X的划分，则其中所有的AiBj，组成的集合C，称为C是A与B两种划分的交叉划分 即{ A1,A2,. ,Am}与{B1,B2,.,Bn}的交叉划分是 C={A1B1,A1B2,.,A1Bn, A2B1,A2B2,.,A2Bn ,., AmB1,AmB2,.,AmBn},作业：第130页 (1),第11页,。