ch4二元关系及函数1二元关系的基本概念.ppt

例:A={1,2,3,4},A上的关系R={1,2,2,1,2,3,3,4,4,2,4,4}, R的关系矩阵: 关系图法（A是有穷集时） 集合A={x1，x2，…，xn}， B={y1，y2，…，ym}， R是A到B上的关系。 ①首先在平面上画上n个结点分别代表x1，…xn， 再画上m个结点分别代表y1，y2，…，ym。 ②如果xi, yj ∈ R ，则在xi到yj之间画上一 条从xi指向 yj的带箭头的直线 。 这样得到的图就是R的关系图。 例:A={1,2,3,4},B={a,b,c}，A到B的关系R={1,b,2,a,2,c,3,b,4,b}, R的关系图: A上关系R的关系图： 集合A={x1，x2，…，xn}，R是A上的关系 ①首先在平面上画上n个结点分别代表x1，…xn， ②如果xi, xj ∈ R ，则在xi到xj之间画上一 条从xi指向 yj的有向边 。 这样得到的图就是R的关系图。 例如：设 A={1，2，3，4}, A 上的关系 R={〈1,1〉,〈1,2〉,〈2,3〉,〈2,4〉, 〈4,2〉} R的关系图: 课堂练习： 集合A={1，2，3} 写出A上的恒等关系，全域关系，小于等于关系，整除关系，并画出关系图 4.2关系的运算 本节学习与关系有关的各种运算: 域 关系的逆、关系的合成 关系的幂 1.域 定义（域）关系R的定义域domR，值域ranR和域fldR分别是: domR = {x | ?y（〈x，y〉? R）} ranR = {y | ?x（〈x，y〉? R）} fldR = domR ? ranR 例: 下列关系都是整数Z上的关系，分别求出它们的定义域和值域 R1={〈x，y〉 | x，y ? Z∧x≤y} R2={〈x，y〉 | x，y ? Z∧y=2x } R3={〈x，y〉 | x，y ? Z∧|x|=|y|=3} 解: DomR1= RanR1=Z DomR2= Z,RanR2=（2z | z ? Z），即偶数集 DomR3= RanR3={-3，3} 2. 关系的逆、合成 定义： 设F，G为集合A上任意的关系，， 则F的逆记作F-1，F-1={〈x，y〉| yFx} F与G的合成记作FоG， FоG={〈x，y〉| ?z（xGz∧zFy）} 例:设A={1，2，3，4，5}， A上关系 R＝{1,2, 1,5,2,4,3,3} S＝{3,1,4,2,5,3} 求R-1, R○S, S○R 。 解: R-1 ＝{2,1,5, 1,4, 2 ,3,3} R○S ＝{3,2,3,5,4,4,5,3} S○R ＝{1,3,2,2,3,1} 例: 设F，G是N上的关系，其定义为 F={〈x，y〉| x，y ? N ∧ y=x2} G={〈x，y〉| x，y ? N ∧ y=x+1} 求G-1，FоG，GоF。 解 : G-1={〈y，x〉| y，x ? N ∧ y=x+1} ={〈x，y〉| y，x ? N ∧ x=y+1} ={〈x，y〉| y，x ? N ∧ y=x-1} ={〈1，0〉，〈2，1〉，… ，〈x+1，x〉，… } F ○ G ={x,y| $ z(xGz ∧ zFy)} ={x,y| $ z(x,z∈N∧z=x+1, z,y ∈N∧ y=z2} ={x,y| x,y∈N∧y=(x+1)2} G ○ F ={x,y| $ z(xFz ∧ zGy)} ={x,y| $ z(x,z∈N∧z=x2, z,y∈N∧ y=z +1} ={x,y| x,y∈N∧y=x 2 +1} 合成运算不是可交换的，即对任何关系F，G，一般说来FоG≠GоF Q A * 离散数学CH4二元关系和函数 回顾 用推理规则证明： |= ? A 证明： 设论域D={a , b , c}，求证： 第4章二元关系和函数 本章学习 1.集合的笛卡尔积 2.关系及其表示 3.关系的运算 4.关系的性质 5.关系的闭包 6.等价关系和偏序关系 7.函数的定义和性质 8.函数的复合和反函数 今日内容 集合的笛卡尔积 关系及其表示 关系的运算 笛卡尔乘积 定义：由两个元素x和y（允许x=y）按一定的顺序排列成的二元组叫做一个有序对（也称序偶），记做x,y，其中x是它的第一元素，y是它的第二元素。 平面直角坐标系中点的坐标就是序偶。 例如