《离散数学 二元关系》由会员分享，可在线阅读，更多相关《离散数学 二元关系（141页珍藏版）》请在金锄头文库上搜索。
1、第四章 二元关系主要内容：关系的概念及表示方法 关系的性质关系的运算:关系的复合，求逆关系，关系的闭包。三种关系: 等价关系，相容关系， 次序关系。 Date1一、序偶与有序n元组1.定义:由两个对象x、y组成的序列称为有序二元 组，也称之为序偶，记作；称x、y分别为 序偶的第一，第二元素。注意，序偶与集合x,y不同： 序偶：元素x和y有次序； 集合x,y：元素x和y的次序无关紧要。4-1 序偶与集合的笛卡尔积Date22.定义：设，是两个序偶，如果x=u和y=v则称和相等，记作=。3 .定义：有序3元组是一个序偶,其第一个元 素也是个序偶。 有序3元组, c可以简记成 ， 但不是有序3元 组
2、。 Date34.定义：有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,记作, xn。且可以简记成。5. 定义=( x1= y1) ( x2= y2) ( xn= yn)Date4例如“斗兽棋”的16颗棋子， 豹猫虎象狮狗鼠虎象狮豹狼鼠猫狗狼设：A=红,蓝B=象,狮,虎,豹,狼,狗,猫,鼠 每个棋子可以看成一个序偶，斗兽棋可记成集合AB ： , , , , Date51.定义:设A、B是集合，由A的元素为第一元素，B 的元素为第二元素组成序偶的集合，称为A和B 的笛卡尔积，记作AB，即AB=|xAyB例1 设A=0,1，B=a,b，求AB ， BA， AA 。解： AB=,BA=,A
3、A=, 可见 ABBA 所以，集合的笛卡尔积运算不满足交换律。Date6v另外 (AB)C=,c|AB cCA(BC)=|aA BC,因 不是有序三元组,所以(AB)CA(BC)。故也不满足结合律。2.性质1) 如果A、B都是有限集，且|A|=m, |B|=n，则 |AB |=mn。 证明：由笛卡尔积的定义及排列组合中的乘法 原理，直接推得此定理。2) A=B= Date73) 对和满足分配律。设A,B,C是任意集合，则 A(BC)= (AB)(AC)； A(BC)= (AB)(AC)； (AB)C= (AC)(BC)； (AB)C= (AC)(BC)；证明 ：任取A(BC) xA yBC x
4、A(yByC) ( xA yB)(xAyC)ABAC (AB)(AC) 所以式成立。（其余可以类似证明）Date84) 若C, 则 AB(ACBC) (CACB) 证明：充分性： 设AB，求证 ACBC任取AC xAyC xByC (因AB)BC 所以, ACBC。必要性：若C, 由ACBC 求证 AB 取C中元素y, 任取 xAxAyC ACBC (由ACBC )xByC xB 所以, AB。所以 AB(ACBC)类似可以证明 AB (CACB)。Date95) 设A、B、C、D为非空集合，则ABCDACBD 证明：首先,由ABCD 证明ACBD任取xA，任取yB，所以 xAyBABCD (
5、由ABCD )xCyD 所以, ACBD。其次, 由AC，BD 证明ABCD任取AB xAyB xCyD (由AC，BD)CD 所以, ABCD 证毕。Date106)约定 (A1A2)An-1)An)=A1A2An 特别 AAA = An v设R是实数集合，则R2表示笛卡尔坐标平面，R3表示三维空间，Rn表示n维空间。3. 应用1)令A1=x|x是学号 A2=x|x是姓名 A3=男,女A4=x|x是出生日期 A5=x|x是班级 A6 =x|x是籍贯 则A1A2A3 A4A5 A6中一个元素：这就是学生档案数据库的一条信息，所以学生的档 案就是A1A2A3 A4A5 A6的一个子集。Date1
6、12) 令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z 是英文字母表一个英文单词可以看成有序n元组：如 at=, boy=, data=, computer=于是可以说：atA2 ,boyA3,dataA4,computerA8,所以英文词典中的单词集合可以看成是AA2An 的一个子集。作业 P105 Date124-2 关系及其表示法相关 按照某种规则，确认了二个对象或多个 对象之间有关系，称这二个对象或多个对象是相 关的。例1： 大写英文字母与五单位代码的对应关系R1:令=A,B,C,D,Z=30,23,16,22,21是五单
7、位代码集合=11000, 10011, 01110, 10010, 10001R1=,.,Date13例2：令=1,2,3,4, A中元素间的关系R2 ： R2= , , ,AA关系的定义定义1: 设A、是集合，如果AB，则称R是一 个从A到B的二元关系。如果 RAA，则称R是A上 的二元关系。二元关系简称为关系。定义2: 任何序偶的集合，都称之为一个二元关系 。如:R=,基本概念基本概念Date148R xRy 也称之为x与y有关系。 后缀表示中缀表示8R xRy 也称之为x与y没有关系。例3. R是实数集合，R上的几个熟知的关系x2+y2=4=xyv 从例3中可以看出关系是序偶(点)的集合
8、( 构成线、面)。Date15关系的定义域与值域 定义域(domain)：设RAB，由所有R的第 一个元素组成的集合，称为R的定义域。记作dom R，即 dom R=x|y(R) 值域(range)：设RAB，由所有R的第二 个元素组成的集合，称为R的值域。记作ran R，即 ran R=y|x(R) 令： R1= , , , , , dom R1 =1,2,3,4ran R1 =1,2,3,4Date16 枚举法：即将关系中所有序偶一一列举出，写在大括号内。 如R = , , , , , , , 。 谓词公式法：即用谓词公式表示序偶的第一元素与第二元素间 的关系。例如 R=|xR时，从x到y
9、引一条有向弧(边 )。这样得到的图形称为R的关系图。关系的表示方法关系的表示方法Date17例 设A=1,2,3,4,B=a,b,c, R1 AB,R2 AA，R1 = ,R2 = ,R2 :3214AB abc1234R1 :R1 、R2的关系图如下：Date18 矩阵表示法：设A=a1, a2, , am，B=b1, b2, , bn是个有限 集， RAB，定义R的mn阶矩阵 MR=(rij)mn，其中1 若R0 若R(1im,1jn)rij=例：R1= , R2= ,1 0 1 0 1 0 1 0 0 0 0 1431 2 3 4a b c上例中 MR1 =MR2=1 0 0 1 0 0
10、 1 01 1 0 01 0 0 1441 2 3 41 2 3 4Date19 空关系：因为AB，(或AA)，所以也是一个从 A到B(或A上)的关系，称之为空关系。即无任何元素的关系，它的关系图中只有结点,无 任何边；它的矩阵中全是0。 完全关系(全域关系) ：AB(或AA)本身也是一个从A到B(或A上) 的关 系，称之为完全关系。即含有全部序偶的关系。它的矩阵中全是1。三个特殊关系三个特殊关系Date20 A上的恒等关系IA：IAAA,且IA =|xA为A上的恒等关系。 例如例如 A=1,2,3, 则IA =, A上的、完全关系及IA的关系图及矩阵如下： 1 1 1 1 1 1 1 1 1
11、33MAA=1。2。31。2。31。2。3 AA IAMIA =1 0 0 0 1 0 0 0 1330 0 0 0 0 0 0 0 033M=Date21v 由于关系就是集合，所以集合的、-、 和运算对关系也适用。 例如 A是学生集合，R是A上的同乡关系，S是A上 的同姓关系，则 RS：或同乡或同姓关系 RS：既同乡又同姓关系 R-S ：同乡而不同姓关系 RS：同乡而不同姓,或同姓而不同乡关系 R：不是同乡关系, 这里R=(AA)-R作业 P109 、c)d)关系的集合运算关系的集合运算Date22v本节中所讨论的关系都是集合A中的关系。 v关系的性质主要有：自反性、反自反性、对称性 、反对
12、称性和传递性。 一. 自反性 定义:设R是集合A中的关系，如果对于任意xA都 有R (xRx)，则称R是A中自反关系。即 R是A中自反的关系x(xAxRx)例如：在实数集合中,“”是自反关系，因 为，对任意实数x，有x x. 4-3 关系的性质Date23v从关系有向图看自反性:每个结点都有环。 v从关系矩阵看自反性：主对角线都为1。 令A=1,2,3，确定以下八个关系中哪些是自反的？1。2。3 R21 。2。3 R11。2。3 R31 。2。3 R41。2。3 R51 。2。3R61。2。3R71。2。3R8Date24二.反自反性 定义：设R是集合A中的关系，如果对于任意的 xA都有R ，
13、则称R为A中的反自反关系。即 R是A中反自反的x(xAR) v 从关系有向图看反自反性:每个结点都无环。 v 从关系矩阵看反自反性：主对角线都为0。 如 实数的大于关系，父子关系是反自反的。 注意：一个不是自反的关系，不一定就是反自反 的，如前边R6、R7非自反,也非反自反。Date25R2、R5、 R8、均是反自反关系。1。2。3 R21 。2。3 R11。2。3 R31 。2。3 R41。2。3 R51 。2。3R61。2。3R71。2。3R8观察下图：Date26三.对称性 定义:R是集合A中关系,若对任何x, yA,如果有 xRy,必有yRx,则称R为A中的对称关系。R是A上对称的xy
14、(xAyAxRy) yRx) v从关系有向图看对称性:在两个不同的结 点之间，若有边的话，则有方向相反的两 条边。 v从关系矩阵看对称性：以主对角线为对 称的矩阵。 例 邻居关系和朋友关系是对称关系。Date271。2。3 R21 。2。3 R11。2。3 R31 。2。3 R41。2。3 R51 。2。3R61。2。3R71。2。3R8R3、R4、 R6 、 R8均是对称关系。Date28四.反对称性 定义:设R为集合A中关系,若对任何x, yA,如果有 xRy,和yRx,就有x=y,则称R为A中反对称关系 。RR是A上反对称的xy(xAyAxRyyRx) x=y)xy(xAyAxyxRy)y x) (P112) v 由R的关系图看反对称性：两个不同的
