离散数学 二元关系与函数.ppt

第4章 二元关系与函数;4.1 集合的笛卡儿积和二元关系;一、有序对; 在日常生活和实际工作中，“关系”这个词的含义如： 父子关系，夫妻关系，同学关系，师生关系等。 下面采用集合论的观点来描述这类关系。 如集合A={a,b,c,d,e}, 其中a,b,c,d,e是五个人， a是b的父亲，c是d的父亲，c又是e的父亲。 现将这5个人中所有符合父子关系的两个人，用有序 对：(a,b),(c,d),(c,e)来表示，如果以这些有序对作为 元素构成集合，即R={(a,b), (c,d), (c,e)} 那么R就完 整地描述了a,b,c,d,e中的父子关系。称R为集合A上的一 个关系(父子关系)。这种有序对仅由两个元素组成的关 系称为二元关系。;又如两个集合A和B中的元素之间的关系： A={a,b,c,d} B={x,y,z} 假设A中元素a,b,c,d表示4位大学生，B中元素x,y,z 表示3种不同的专业；如果a,b是x专业的学生，c是y 专业的学生，d是z专业的学生。则有序对： (a,x),(b,x),(c,y),(d,z)就表示这4位大学生和所学 专业的关系。 由这些有序对作为元素所构成的集合R，即 R={(a,x),(b,x),(c,y),(d,z)} 称R为A到B上的二元关系。; 注： 1、从数学角度来看，关系是一个集合，它的 元素是有序对； 2、一般情况下有序对中的两个元素是不可随 意交换的。如R中(a,b)表示a是b的父亲， 而(b,a)表示b是a的父亲,它不属于R。 ;有序 n 元组;二、笛卡尔乘积;特别地，当A=B 时，A×A 称为集合A 上的 笛卡尔乘积，也可简写作A2。;2、笛卡尔积的性质; 3、n阶笛卡儿积 定义：设A1，A2，…，An (n≥2) 是集合，则称 A1×A2×…×An 为它们的n阶笛卡儿积。 特别地 A?A?…?A = An。 设R是实数集合，则R2表示笛卡尔坐标平面， R3表示三维空间，Rn表示n维空间。 应用 令A1={x|x是学号} A2={x|x是姓名} A3={男,女} A4={x|x是出生日期} A5={x|x是班级} A6 ={x|x是籍贯} 则A1?A2?A3 ?A4?A5 ?A6中一个元素： 001，王强，男，1981:02:16，计2001-1，辽宁 这就是学生档案数据库的一条信息，所以学生 的档案就是A1?A2?A3 ?A4?A5 ?A6的一个子集。;三、二元关系的定义;定义 A和B是两个集合，R是笛卡尔乘积 A×B 的子集，则称R 为从A到B的一个二元关系。;思考：设 A={0,1}, B={1,2,3}, 若R1={0,2}, R2=A×B, R3=?, R4={0,1}. 试判断哪些是从A到B的二元关系，哪些是从A上的二元关系？; 对于任意集合，空集总是它的子集，另外这个集合本身也是它 的子集，通常称这两种子集为平凡子集。 ; 又设Ｒ１是Ａ上的二元关系，对于Ａ中任意元素a 、b， 当a+b是奇数时，(a,b)∈R1，显然， R1是Ａ上的空关系。;定义 设IA是A上的二元关系且满足 IA= ，则称 IA为A上的恒等关系。;例 A={1，2，3，4，5，6，7}， R是A上的二元关系， 对于A中元素a , b，当它们被3除后余数相同， 则 (a,b) ∈R （R也称为模3 同余关系），求R。;例 A={a,b,c,d,e} ，其中a、b、c、d、e分别表示5位大学生， a、b、c都姓张，d 和e 都姓王；如果两位大学生姓氏相同， 则认为他们是相关的，求描述同姓氏的二元关系R。;四、关系的表示方法;2.矩阵表示法;思考： 写出集合A=｛1 , 2 , 3 , 4 ｝上的恒等关系、 空关系、 全域关系和小于关系的关系矩阵。;如A={1,2,3,4}, 而R={1,1,1,2,2,3,2,4,4,2}, 则R的关系矩阵MR和关系图GR如下：