离散数学PPT电子教案-第06章_二元关系.ppt

第三篇 二元关系 第6章 二元关系 6.0 内容提要 6.1本章学习要求 第三篇 二元关系 关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。 关系是日常生活以及数学中的一个基本概念, 例如: 兄弟关系, 师生关系, 位置关系, 大小关系, 等于关系, 包含关系等。 6.2 二元关系 6.2.1 序偶与笛卡尔积 N重有序组 笛卡尔乘积 例6.2.3 设A={a}, B={b,c}, C=Φ, D={1,2}, 请分别写出下列笛卡儿积中的元素。 (1) A×B, B×A; (2) A×C, C×A; (3) A×(B×D), (A×B)×D。 解 根据笛卡儿积的定义，有 (1) A×B={a,b,a,c}, B×A={b,a,c,a}; (2) A×C=Φ, C×A=Φ; (3) A×(B×D) = {a,b,1,a,b,2,a,c,1,a,c,2}; (A×B)×D = {a,b,1,a,b,2,a,c,1,a,c,2}。 注意 由例6.2.3我们可以看出： （1）笛卡儿积不满足交换律, 即 A×B ? B×A; （2）A×B=Φ 当且仅当 A=Φ或者B=Φ； （3）笛卡儿积不满足结合律, 即 A×(B×D) ? (A×B)×D ； （4）对有限集A,B，有 |A×B|=|B×A|=|A|×|B|。 两个定理 定理6.2.1 设A,B,C是任意三个集合，则 （1）A×(B∪C) = (A×B)∪(A×C)； （2）(B∪C)×A = (B×A)∪(C×A)； （3）A×(B∩C) = (A×B)∩(A×C)； （4）(B∩C)×A = (B×A)∩(C×A)。 n个集合的笛卡尔集 定义6.2.6 设A1,A2,…,An是n个集合，称集合 A1×A2×…×An = {a1,a2,…,an| ai∈Ai, i∈{1,2,3,…,n}} 为集合A1,A2,…,An的笛卡儿积 当A1=A2=…=An=A时，有A1×A2×…×An=An。 6.2.2 二元关系的定义 定义6.2.7 设A,B为两个非空集合，称A×B的任何子集R为从A到B的二元关系，简称关系。 如果 A＝B，则称R为A上的二元关系。 例6.2.4 假设A={a,b}, B={c,d}, 试写出从A到B的所有不同关系. 解 因为A={a,b},B={c,d}，所以 A×B={a,c,a,d,b,c,b,d}。 于是A×B的所有不同子集为： 0–元子集：Φ； 1–元子集: {a,c}, {a,d}, {b,c}, {b,d}； 2–元子集: {a,c,a,d}, {a,c,b,c}, {a,c,b,d}, {a,d,b,d}, {a,d,b,d}, {b,c,b,d}; 例6.2.4 解（续） 3–元子集： {a,c,a,d,b,c}, {a,c,a,d,b,d}, {a,c,b,c,b,d}, {a,d,b,c,b,d}； 4–元子集： {a,c,a,d,b,c,b,d}。 其中, A称为R的前域, B称为R的后域。D?A, C?B 满足: D＝{x|x,y?R}, C＝{y|x,y?R}。称D为R的定义域，记为D＝domR；称C为R的值域, 记C＝ranR;并称 fldR＝D∪C 为R的域。 例6.2.5 求定义在Z上关系的定义域、值域和域。 （1）R1={x,y|(x,y∈Z)∧{y=x2}}； （2）R2={x,y|(x,y∈Z)∧{|x|=|y|=7}}。 解（1）domR1=Z, ranR1={0,1,4,9,…,n2,…} fldR1=Z； （2）domR2={7,–7}, ranR2={7,–7}, fldR2={7,–7}。 练习: P190 1(1)(3) 1. 给定集合: A={1,7}, B={0,3,5}, C={1,2}. (1) 写出A对B的关系 , =, ?, 并确定dom, ran, fld; (3) 写出A对C的关系 , =, ?, 并确定dom, ran, fld。 解 (1) R={1,3,1,5}, R==?, R? =R; dom R={1}, ranR={3,5},fldR={1,3,5}; 定义6.2.8 (n元关系) 设A1,A2,…,An为n个非空集合, 称 A1×A2×…×An的任意子集R为以