第4章二元关系和函数v2汇编.ppt

第4章 二元关系和函数 4.1 集合的笛卡尔积和二元关系 2 笛卡尔积 例1 笛卡尔积的性质(1) 性质1：对于任意集合A，A??=?，??A=? 笛卡尔积的性质(2) 笛卡尔积的性质(3) 性质5 对于任意集合A，B，C，若C??，则 3 二元关系 A到B的不同的关系共有多少？ 如|A|=m, |B|=n, |A?B|=mn, 而关系是A?B的子集,根据幂集个数的结论,A?B的子集共有2mn,所以,A到B的关系共有 ? 个。 集合A上的三种特殊关系： 关系的三种表示方法： 第2节 关系的运算 例1 1、关系的集合类运算 2、复合关系 复合关系的补充说明 关系的n次幂 3 逆关系 逆关系的性质 第4.3节 关系的性质 2、反自反性 3、对称性 定义 设R是A上的关系，?x, y∈A, 4、反对称性 5、传递性 定义 设R是A上的关系,?a,b,c∈A,如果a,b∈R, b,c∈R,则必有a,c∈R,则称R为A上的传递关系, 或称R具有传递性。 下边R1、R3、R4、R5、R8均是传递的关系。 几种特殊关系的性质 第4节 关系的闭包 怎样求出给定集合的闭包 练习 4.5 等价关系和偏序关系 2 等价类的概念 X的等价类 R为非空集合A上的等价关系，?x∈A ，令 [x]R={y|y? A且 xRy}， 称[x]R为x关于R的等价类，简称为x的等价类。记作[x] 或 。 3 等价类的性质 设R为非空集合A上的等价关系， ?x，y∈A,则 4 商集 5 集合的划分 设A是一个非空集合,?={A1, A2,... ,An}, Ai?A (i=1,2,...,n),如果满足: 二 偏序关系的概念 2 可比的概念 3 全序关系的概念 4 哈斯图 偏序集的关系图,可以简化为哈斯图,其简化规则为: 5 覆盖的概念 6 偏序集上的特殊元 2)设(A,≤)是偏序集,B?A，?y∈A. 4.6函数的定义 4 5 函数的性质 6 几种特殊的函数(1) 几种特殊的函数(2) (4)特征函数:设A为一个集合, B?A,子集B的特征函数XB是A→E={0，1}的映射,定义为: XB=1,a∈B; XB=0,a∈A-B 4.7 函数的复合和反函数 复合函数的性质 3 反函数的定义和性质 （1） [x] 非空； （2）如果xRy?[x]=[y]； （4）所有等价类的并集就是A. （3） ——设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记作A/R.即 A/R={[x]R|x∈A}. 例 X={1,2,3}, A1={{1,2,3}}, A2={{1},{2},{3}}, A3={{1,2},{3}}, A4={{1,2},{2,3}}, A5={{1},{3}} 是划分的是哪个？ 等价关系 集合的划分 A/R ？ Ai?Φ , A1∪A2∪...∪An =A (i=1,2,..., n), Ai?Aj=Φ ,(i?j,1≤i,j≤n) 则称A是X的划分。每个Ai均称为划分块。 1 设R是非空集A上的关系,如果R具有自反性,反对称性和传递性,则称R是A上的偏序关系,或称半序关系, 例1 设集合A＝{a,b,c},A上的关系R＝{a,a,a,b,a,c,b,b,b,c,c,c},从关系图来验证R是偏序关系。 问：常见的偏序关系有哪些？ 把关系R记作≤,如果a,b∈≤,则记作a≤b,读作“a小于等于b” 定义 设R为非空集合A上的偏序关系， 其中，xy读作x”小于” y。 定义 1) 设R是A上的偏序关系,若?a, b∈A,a与b都是可比的, 则称R为A上的全序关系,或称线序关系。 2) 集合A和A的偏序关系≤一起称为偏序集,记作A,≤。 (1)所有结点的自回路均省略; (2)省略所有弧上的箭头, 如果a≤b,则a画在b的下方。 (3) a到b有边,b到c有边,则a到c的边必须省略。 设〈A，≤〉为偏序集。?x，y ∈A，如果xy且不存在z∈ A使得xzy，则称y覆盖x。 a c d b b是a的覆盖 1）设(A,≤)是偏序集,B?A,若?b∈B 则┑?x∈B,使bx,称b为B的极大元. 使得?x∈B,均有b≤x,则称b为B的最小元. 则┑?x∈B,使xb，称b为B的极小元. 使得?x∈B,均有x≤b,则称b为B的最大元. 若?x (x∈B→x≤y)成立，则称y为B的上界。 若?x (x∈B→y≤x)成立，则称y为B的下界。 令C={y|y为B的上界},则称C中的最小元为B的最小上界（或上确界）。 令D={y|y为B的下界},则称C中的最大元为B的最大