2.5覆盖与划分描述.ppt

定义 若{A1,A2,…,Ar}与{B1,B2,…,Bs}是同一集合A的两种划分，则其中所有Ai∩Bj≠Φ组成的集合，称为是原来两种划分的交叉划分。 例子 所有生物X={P,A}，其中P表示植物集合，A表示动物集合 所有生物X={E,F}，其中E表示史前生物，F表示史后生物 交叉划分Q 设{A1,A2,…,Ar}与{B1,B2,…,Bs} 是同一集合X的两种划分，则其交叉划分亦是原集合的一种划分。 证明方法 根据划分的定义，分步骤证明 定义 给定X的任意两个划分{A1,A2,…,Ar}和{B1,B2,…,Bs}，若对任一Aj,均有Bk使Aj ? Bk，则称{A1,A2,…,Ar}为{B1,B2,…,Bs}的加细。 真加细 任何两种划分的交叉划分，都是原来各划分的一种加细。 证明：(从定义出发) 设{A1,A2,…,Ar}和{B1,B2,…,Bs}的交叉划分为T，对T中的任意元素Ai∩Bj必有Ai∩Bj?Ai和Ai∩Bj?Bj，故T是原划分的加细。 覆盖 划分 细分 Thank you 授课教师：程文刚 wgcheng@ncepu.edu.cn 关系的运算 集合基本运算 复合运算 逆运算 闭包运算 定义 设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则R?S称为R和S的复合关系，表示为 R?S={x,z?x∈A∧z∈C∧?y (y∈B∧x,y∈R∧y,z∈S)} 计算方法 根据定义：只考虑R值域与S定义域之间的交集 矩阵乘法（布尔） 定理4.2.1 设R?A?A，则R?IA=IA?R=R 证明方法：互为子集。 定理4.2.2 若R?A?B，S,T?B?C，W?C?D，则 ① R?(S∪T)=R?S∪R?T ② R?(S∩T) ? R?S∩R?T ③ (S∪T)?W=S?W∪T?W ④ (S∩T)?W ? S?W∩T?W 定理4.2.3 若R?A?B，S?B?C，T?C?D，则(R?S)?T=R?(S?T) 定义 设R是集合A上的二元关系，n?N，R的n次幂记为Rn，定义为： (1) R0=IA (2) Rn+1=Rn?R 定理4.2.4 若R?A?A，且m, n?N，则 (1) Rm?Rn=Rm+n， (2) (Rm)n=Rmn。 定理4.2.5 令R?A?A，且|A|=n，则存在i和j，使得Ri=Rj，其中0≤ij≤2n2。 定理4.2.6 令R?A?A，若存在i和j，ij，使得Ri=Rj。且d=j-i，则 (1) 对任意k≥0,Ri+k=Rj+k。 (2) 对任意k,m≥0，Ri+md+k=Ri+k。 (3) 设S={R0,R1,R2,···,Rj-1}，对?n?N，有Rn?S。 定义 设R是从集合A到集合B的二元关系，如果将R中每序偶的第一元素和第二元素的顺序互换，所得到的集合称为R的逆关系，记为R-1，即 R-1={y,x?x,y∈R} 由定义可知，?-1=?，(A?B)-1=B?A 特别地,A上恒等关系,全域关系,空关系的逆关系都是自身 定理4.2.7 若R?A?B，S?B?C，则(R?S)-1=S-1?R-1 定理4.2.8 令R，S?A?B，则 ① (R-1)-1=R ② D (R-1)=R (R)， R(R-1)=D (R) ③ (R∪S)-1= R-1∪S-1 ④ (R∩S)-1= R-1∩S-1 ⑤ (R-S)-1= R-1-S-1 ⑥ R?S?R-1?S-1 定理 设R为X上的二元关系，则 a) R是对称的，当且仅当R=R-1; b) R是反对称的，当且仅当R∩R-1 ?IX 定义 设R是A上的二元关系，R的自反（对称、传递）闭包是关系R1，则 ① R1是自反的（对称的、传递的） ② R?R1 ③ 对任何自反的（对称的、传递的）关系R2，若R?R2，则R1?R2。 R的自反、对称和传递闭包分别记为r(R)、s(R)和t(R)。 定理4.2.10 设R是X上的二元关系，那么 a) R是自反的，当且仅当r(R) =R; b) R是对称的，当且仅当s(R)=R; c) R是传递的，当且仅当t(R) =R。 定理 设R是集合X 上的二元关系，则 r(R)=R∪Ix 定理 设R是集合X上的二元关系，则 s(R)=R∪Rc 定理 设R是集合X上的二元关系，则 t (R)= =R∪R2 ∪R3 ∪… 定理 设X是含有n个元素的集合,R是X上的二元 关系,则存在一个正整数k=n,使得 t(R)=R∪R2∪R3∪…Rk 从本定理可