离散数学 第2篇 关系.ppt

离散数学 西安交通大学 电子与信息工程学院 计算机系 离散数学 第二章 关系 (relation) §1 . 集合的叉积　n元组 §2 .关系 §3 .关系的表示　关系的性质 §4 .关系的运算 §5. 等价关系 §6. 半序关系 离散数学 §1 . 集合的叉积　n元组 定义1. 叉积，笛卡尔积 (cross product , Cartesian product(1637)) 　 n个集合A1， A2，? ，An的 n 维叉积定义为 =A1 × A2 × ? × An ={(a1, a2, ?, an): ai? Ai(1?i ? n)} ； 　 离散数学 n 维叉积A1 × A2 × ? × An的每个元素(a1, a2, ?, an)都称为一个n元组（n-tuple）；即，叉积是元组的集合； 每个n元组(a1, a2, ?, an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变； n 称为该叉积及其元组的维数； 两个元组相等?它们的维数相同且对应的分量相等。即 (a1, a2, ?, an)= (b1, b2, ?, bm) ? n=m ? (?i?N)(1?i ? n)(ai = bi)； 注：笛卡尔(1596-1650 )，法国数学家， 1637年发表《方法论》之一《几何学》，首次提出坐标及变量概念。这里是其概念的推广。 离散数学 定义2. ? 二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a? A ?b?B} ； 其元素——二元组(a, b)通常称为序偶或偶对(ordered pair) ； 二元组(a, b)的第一分量上的元素a称为前者；第二分量上的元素b称为后者； 二重叉积的A? B第一集合A称为前集；第二集合B称为后集。 离散数学 例1 . A={ a,b,c }, B={0,1} A×B={(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)} B×A={(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)} 例2 . A={张三,李四}，B={白狗,黄狗} A×B={(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)} B×A={(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)} 离散数学 一般地说，关于叉积和元组我们有： (1) (a, b)? (b, a)； (2) A×B ? B × A ； (3) 二元组不是集合，因为二元组中的分量计较顺序, 而集合中的元素是不讲顺序的。 (4) 我们也可用二元组来递归的定义n元组如下： 　　　(a,b,c)=((a,b),c) ? ? ? (a1, a2, ?, an-1 , an)= ((a1, a2, ?, an-1) , an) 离散数学 (5) 这样，我们也就可用二重叉积来递归的定义n维叉积如下： 　　 A×B×C=(A×B)×C 　　 ? ? ? A1×A2× ?×An-1×An= (A1×A2× ?×An-1)×An 离散数学 (6) 利用(5)所给的定义，我们可以递归的定义集合的叉积幂如下： 　　　　　A2= A×A A3 = A2 ×A ? An = An-1 ×A (7)我们规定空集?与任何集合A的叉积是空集? 。 即 A×? = ? = ?×A 　由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的。 离散数学 定理1. 设A,B,C,D是四个非空的集合。那么 　　　　A×B = C×D ? A = C ? B = D 　。 [证]. 　 ?)：（采用逻辑法）对任何的元素a,b (a,b)?A×B ?(a,b)?C×D (条件： A = C ? B = D ） 所以　 A×B = C×D 。 离散数学 　 ?)：（采用逻辑法）对任何的元素a,b a?A?b?B