离散数学二元关系.

计算机科学学院刘芳2019/12/201第7章二元关系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系和划分7.7偏序关系计算机科学学院刘芳2019/12/2027.1有序对与笛卡尔积7.1.1有序对的定义7.1.2集合的笛卡尔积7.1.3有序n元组和n阶笛卡尔积计算机科学学院刘芳2019/12/2037.1.1有序对的定义定义7.1：两个元素x,y组成的有序序列＜x,y＞，称为一个有序对（序偶、二元组）。例：直角坐标系中点的坐标＜x,y＞日期的表示：＜y,m＞计算机科学学院刘芳2019/12/2047.1.1有序对的定义性质：当x≠y时，＜x，y＞≠＜y，x＞＜x，y＞＝＜u，v＞x＝u∧y＝v例7.1：x＋2,4＝5,2x＋y，求x,y。解：∵x＋2＝5,2x＋y＝4∴x＝3,y＝2计算机科学学院刘芳2019/12/2057.1.2集合的笛卡尔积定义7.2：集合A与B的笛卡儿乘积A×B＝｛＜x,y＞|x∈A∧y∈B}例：设A＝{a,b}，B＝{0，1，2}，C＝φ，计算A×B，B×A，A×C，A×A。解：A×B＝{＜a,0＞,＜a,1＞,＜a,2＞,＜b,0＞,＜b,1＞,＜b,2＞}B×A＝{＜0,a＞,＜0,b＞,＜1,a＞,＜1,b＞,＜2,a＞,＜2,b＞}A×C＝φA×A＝{＜a,a＞,＜a,b＞,＜b,a＞,＜b,b＞}（A×A可记作A2）例7.2：A={1，2},求P(A)A。计算机科学学院刘芳2019/12/2067.1.2集合的笛卡尔积集合的笛卡儿积的性质：性质1：若|A|＝m,|B|＝n,则|AB|＝mn性质2：对任意集合A，有：A×φ＝φ×A＝φ性质3：一般地A×B≠B×A，即笛卡儿乘积不满足交换律。问题：什么情况下A×B＝B×A？（A＝B∨A＝φ∨B＝φ）什么情况下A×B≠B×A？（A≠B∧A≠φ∧B≠φ）计算机科学学院刘芳2019/12/2077.1.2集合的笛卡尔积例3：设A＝{a，b}，B＝{1，2，3}，C＝{p，q}，计算(A×B)×C，A×(B×C)。解：(A×B)×C＝{＜a,1,p＞,＜a,1,q＞,＜a,2,p＞,＜a,2,q＞,＜a,3,p＞,＜a,3,q＞,＜b,1,p＞,＜b,1,q＞,＜b,2,p＞,＜b,2,q＞,＜b,3,p＞,＜b,3,q＞}。计算机科学学院刘芳2019/12/2087.1.2集合的笛卡尔积A×(B×C)＝{＜a,1,p＞,＜a,1,q＞,＜a,2,p＞,＜a,2,q＞,＜a,3,p＞,＜a,3,q＞,＜b,1,p＞,＜b,1,q＞,＜b,2,p＞,＜b,2,q＞,＜b,3,p＞,＜b,3,q＞}集合的笛卡儿积的性质性质4：一般地(A×B)×C≠A×(B×C)，即集合的笛卡儿积不满足结合律。性质5：AC∧BDA×BC×D计算机科学学院刘芳2019/12/2097.1.2集合的笛卡尔积性质6：笛卡儿积对∪、∩运算满足分配律A×（B∪C）＝（A×B）∪（A×C）A×（B∩C）＝（A×B）∩（A×C）（A∪B）×C＝（A×C）∪（B×C）（A∩B）×C＝（A×C）∩（B×C）计算机科学学院刘芳2019/12/20107.1.2集合的笛卡尔积证明：A×（B∪C）＝（A×B）∪（A×C）证：任取＜x，y＞＜x，y＞∈A×（B∪C）x∈A∧y∈B∪Cx∈A∧（y∈B∨y∈C）（x∈A∧y∈B）∨（x∈A∧y∈C）（＜x，y＞∈A×B）∨（＜x，y＞∈A×C）＜x，y＞∈（A×B）∪（A×C）所以，A×（B∪C）＝（A×B）∪（A×C）成立。计算机科学学院刘芳2019/12/20117.1.2集合的笛卡尔积证明：（A∩B）×C＝（A×C）∩（B×C）证：任取＜x，y＞＜x，y＞∈（A∩B）×Cx∈（A∩B）∧y∈Cx∈A∧x∈B∧y∈C（x∈A∧y∈C）∧（x∈B∧y∈C）（＜x，y＞∈A×C）∧（＜x，y＞∈B×C）＜x，y＞∈（A×C）∩（B×C）所以，（A∩B）×C＝（A×C）∩（B×C）成立。计算机科学学院刘芳2019/12/20127.1.3有序n元组和n阶笛卡尔积定义：n个元素x1，x2，…，xn组成的有序序列,记做：＜x1,x2,…,xn＞称为n重组（n元序偶、n元组）。约定:＜x1，x2，…,xn-1,xn＞=＜x1，x2，…,xn-1,xn＞性质：＜x1,x2,…,xn＞＝＜y1,y2,…,yn＞xi＝yi(i=1,2,…,n)计算机科学学院刘芳2019/12/20137.1.3有序n元组和n阶笛卡尔积定义4.4：集合A1、A2、……、An的笛卡儿乘积A1×A2×…×An＝{＜x1，x2，…，xn＞|xi∈Aii＝1,2,…,n}注意：A1×A2×……×An－1×An＝（A1×A2×……×An－1）×An一般地：若A1＝A2＝……＝An＝A时，上式简记为：An计算机科学学院刘芳2019/12/20147.2二元关系7.2.1二元关系的基本定义7.2.2二元关系的表示计算机科学学院刘芳2019/12/20157.2.1二元关系的基本定义关系数的＞,＝,＜关系;V＝IR;计算机程序的输入与输出联系；数据库的数据特性联系等。集合论为刻划这种联系提供了一种数学模型关系(Relation)。计算机科学学院刘芳7.2.1二元关系的基本定义定义7.3如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.例如：R＝{1,2,a,b}S＝{1，2,3,4}.2019/12/2016计算机科学学院刘芳2019/12/20177.2.1二元关系的基本定义例:(1)R＝{x,y|x,yN,x＋y＜3}＝{0,0,0,1,0,2,1,0,1,1,2,0}(2)C＝{x,y|x,yR,x2＋y2＝1}(3)R＝{x,y,z|x,y,zR,x＋2y＋z＝3}(4)5元关系的实例—数据库实体模型员工号姓名年龄性别工资301302303…张林王晓云李鹏宇…504347…男女男…160012501500…计算机科学学院刘芳2019/12/20187.2.1二元关系的基本定义定义7.4设A,B为集合,RA×B，称R为A到B的二元关系；RA×A，称R为A上的关系。例：若A＝{a,b},B＝{1},则：（1）写出A到B的所有二元关系。（2）写出A上的所有二元关系。计算机科学学院刘芳2019/12/20197.2.1二元关系的基本定义一般地：若|A|＝m,|B|＝n|A×B|＝mn,A×B的子集有2mn个,从A到B有2mn个不同的二元关系.R＝φ，称R为空关系；R＝A×B，称R为全域关系若|A|＝n|A×A|＝n2,A×A的子集有2n2个,A上有2n2不同的二元关系.R＝φ，称R为A上空关系R＝A×A，称R为A上的全域关系，记做EA;R＝{x,x|x∈A}，称R为A上的相等关系，记做IA;计算机科学学院刘芳2019/12/20207.2.1二元关系的基本定义常见的几种特殊的二元关系≤≥＜＞＝|集合之间的关系：＝≠计算机科学学院刘芳2019/12/20217.2.2二元关系的表示1.集合表示法2.关系矩阵(matrixofrelation)设A＝{a1,a2,…,am}，B＝{b1,b2,…,bn}，R是A到B的一个二元关系，令：1211112122122212RnnnmmmmnbbbarrrMarrrarrr10ijijiaRbraR其中jb称：MR为R的关系矩阵。计算机科学学院刘芳2019/12/20227.2.2二元关系的表示例1：设A＝{a,b,c},B＝{0,1,2,3},R＝{a,1,b,2,c,0},写出MR。0001c0100b0010a3210MR＝计算机科学学院刘芳2019/12/20237.2.2二元关系的表示例2：设A＝{1,2,3,4},A上的关系R＝{1,1,1,2,2,3,2,4,4,2},写出MR。123411100200113000040100MR＝计算机科学学院刘芳2019/12/20247.2.2二元关系的表示例3设A＝{1,2,3,4},A上的二元关系R＝{x,y|x≥y},写出MR。123411000211003111041111MR＝计算机科学学院刘芳2019/12/20257.2.2二元关系的表示3.关系图R为A到B的二元关系；以A∪B的每个元素为一个结点，对每个x,y∈R，均连一条从结点x到y的有向边，得到一个有向图，称为R的关系图，记为GR。计算机科学学院刘芳2019/12/20267.2.2二元关系的表示例1设A＝{a,b,c},B＝{0,1,2,3},R＝{a,1,b,2,c,0},画出GR。abc0123计算机科学学院刘芳2019/12/20277.2.2二元关系的表示例2设A＝{1,2,3,4},A上的二元关系R＝{x,y|x≥y},画出GR。1243计算机科学学院刘芳2019/12/20287.2.2二元关系的表示练习：A＝{a,b,c,d},R＝{a,a,a,b,a,c,b,a,d,b},求R的关系矩阵MR和关系图GR。0010000000010111计算机科学学院刘芳2019/12/20297.2.2二元关系的表示关系的表示方法关系R的集合表达式关系矩阵MR关系图GR三者均可以唯一相互确定。计算机科学学院刘芳2019/12/20307.3关系的运算7.3.1关系的定义域、值域和域7.3.2关系的逆7.3.3关系的右复合7.3.4关系运算的性质7.3.5关系的幂计算机科学学院刘芳2019/12/20317.3.1关系的定义域、值域和域定义7.6：dom（R）={x|y（xRy）}ran（R）={y|x（xRy）}fld（R）=dom（R）∪ran（R）例：设R＝{＜a,1＞,＜b,2＞,＜a,3＞}计算dom（R）,ran（R）,域fld（R）计算机科学学院刘芳2019/12/20327.3.2关系的逆运算定义7.7关系R的逆关系R-1={y,x|xRy}例：R＝{a,1,b,2,c,0},则：R-1＝{1,a,2,b,0,c}问题：已知MR，如何计算MR-1?已知GR，如何计算GR-1?计算机科学学院刘芳2019/12/20337.3.3关系的右复合定义7.8关系F,G的右复合{,|()}FGxytxFttGy关系复合的求解方法集合表达式图示法关系矩阵计算机科学学院刘芳2019/12/20347.3.3关系的右复合例：R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}法1：R∘S=S∘R={1,3,2,2,2,3}{1,2,1,4,3,2,3,3}法2：利用图示方法求合成计算机科学学院刘芳2019/12/20357.3.3关系的右复合法3：关系矩阵相乘的方法一般地：设:A={a1,a2,…,am}B={b1,b2,…,bp}C={c1,c2,…,cn}R是A到B的一个二元关系，S是B到C的一个二元关系，RοS是A到C的一个二元关系，计算机科学学院刘芳2019/12/20367.3.3关系的右复合则：MR＝(rij)m×pMS＝(sij)p×nMRοS＝(tij)m×n1()(1,1)ikkjpijktrsimjn：其中计算机科学学院刘芳