东北大学：《离散数学》课程教学资源（PPT课件讲稿）第四章 二元关系

第四章二元关系 二元关系是一个很重要的概念,它在很多数学领域中 都有应用,在计算机科学的如下理论都离不开关系 逻辑设计、数据结构、编译原理、软件工程 数据库理论、计算理论、算法分析、操作系统等 本章主要介绍: 关系的概念及表示方法 关系的性质 关系的运算:关系的复合,求逆关系,关系的闭包 三种关系:等价关系,相容关系,次序关系

第四章 二元关系 二元关系是一个很重要的概念，它在很多数学领域中 都有应用，在计算机科学的如下理论都离不开关系 ： 逻辑设计、 数据结构、 编译原理、 软件工程 数据库理论、 计算理论、 算法分析、 操作系统等 本章主要介绍： 关系的概念及表示方法 关系的性质 关系的运算:关系的复合, 求逆关系, 关系的闭包. 三种关系: 等价关系，相容关系, 次序关系

4-1序偶与集合的笛卡尔积 实际上“序偶”概念以前已经用过。例如,用序 偶表示平面直角坐标系中一个点(a,b)。设x表示 上衣,y表示裤子,(x,y)可以表示一个人的着装 序偶与有序n元组 1.定义:由两个对象x、y组成的序列称为有序二 元组,也称之为序偶,记作;称x、y分 别为序偶的第一,第二元素。 注意,序偶与集合{x,y}不同: 序偶:元素x和y有次序; 集合{x,y}:元素x和y的次序是无关紧要的

4-1 序偶与集合的笛卡尔积 实际上“序偶”概念以前已经用过。例如，用序 偶表示平面直角坐标系中一个点(a,b)。设x表示 上衣,y表示裤子,(x,y)可以表示一个人的着装。 一.序偶与有序n元组 1.定义:由两个对象x、y组成的序列称为有序二 元组，也称之为序偶，记作；称x、y分 别为序偶的第一，第二元素。 注意，序偶与集合{x,y}不同： 序偶：元素x和y有次序； 集合{x,y}：元素x和y的次序是无关紧要的

2.定义:设〈x,y>,是两个序偶,如果 x=u和y=V, 则称和相等, 记作〈x,y>= 3定义:有序3元组是一个序偶,其第一个元素也是个序偶 有序3元组,C>可以简记成。 但不是有序3元组。 4定义:有序n元组是一个序偶,其第一个元素本身是个有 序n-1元组,记作,x2>。且可以简记成 X1.X X 5.定义:= (x1=y1)入(X2=y2)∧∧(Xn=yn

2.定义：设，是两个序偶，如果 x=u和y=v，则称和相等， 记作=. 3 .定义:有序3元组是一个序偶,其第一个元素也是个序偶。 有序3元组, c>可以简记成。 但>不是有序3元组。 4.定义:有序n元组是一个序偶,其第一个元素本身是个有 序n-1元组,记作, xn >。且可以简记成 。 5. 定义： = ( x1= y1 ) ( x2= y2 ) ( xn= yn )

集合的笛卡尔积 例如“斗兽棋”的16颗棋子 象)(狮)(虎)(豹)(狼)(狗)(猫)(鼠 象)(狮)(虎)(豹)(狼)(狗)(猫)(鼠 可看成是由两种颜色的集合A和8种动物的集合B组成的。 A={红,蓝} B={象狮虎豹狼狗猫,鼠} 每个棋子可以看成一个序偶,斗兽棋可记成集合AxB: 红狮>,红,虎>红豹>红狼>红猫>, 蓝狮>,蓝,豹>,蓝狗>蓝,鼠>}

二.集合的笛卡尔积 例如“斗兽棋”的16颗棋子， 可看成是由两种颜色的集合A和8种动物的集合B组成的。 A={红,蓝} B={象,狮,虎,豹,狼,狗,猫,鼠} 每个棋子可以看成一个序偶，斗兽棋可记成集合AB ： { ,,,,,,,, ,,,,,,,} 象 狮 虎 豹 狼 狗 猫 鼠 象 狮 虎 豹 狼 狗 猫 鼠

1定义:设A、B是集合,由A的元素为第一元素, B的元素为第二元素组成序偶的集合,称为A 和B的笛卡尔积,记作A×B,即 AxB={xyX∈A∧y∈B} 例1设A={0,1},B={ab},求AxB,BxA, A×A。 解:A×B={2,,} BxA={,,} A×A={,,, 可见A×BB×A 所以,集合的笛卡尔积运算不满足交换律

1.定义:设A、B是集合，由A的元素为第一元素， B的元素为第二元素组成序偶的集合，称为A 和B的笛卡尔积，记作A×B，即 AB={|xA∧yB} 例1 设A={0,1}，B={a,b}，求AB ， BA， AA 。 解： AB={,,,} BA={,,,} AA={,,,} 可见 A×B≠B×A 所以，集合的笛卡尔积运算不满足交换律

另外 (A×B)×C={c>ab>∈ AXB AC∈C} Ax(BxC){>a∈A入∈BxC}, 因不是有序三元组, 所以(AXB)XC≠A×(B×C 故x也不满足结合律 2.性质 1)如果A、B都是有限集,且A=m,|Bn,则 A×Bmn 证明:由笛卡尔积的定义及排列组合中的乘法原 理,直接推得此定理 2)A×=①×B=①

另外 (AB)C={,c>|AB cC} A(BC)={>|aA BC}, 因 >不是有序三元组, 所以(AB)CA(BC)。 故也不满足结合律。 2.性质 1) 如果A、B都是有限集，且|A|=m, |B|=n，则 |AB |=mn. 证明：由笛卡尔积的定义及排列组合中的乘法原 理，直接推得此定理。 2) AΦ=ΦB=Φ

3)×对U和∩满足分配律。 设A,BC是任意集合,则 (1)A×(B∪C)=(A×B)∪(A×C); (2)Ax(B∩C)=(A×B)∩(A×C); (3)(A∪B)XC=(AXC)∪(B×C); (4)(A∩B)xC=(A×C)n(B×C 证明(1):任取∈Ax(BUC) 台X∈A~y∈B∪C分X∈A∧(y∈BVy∈C) 台(X∈ANy∈B)V(X∈Ay∈C 冷冷∈A×BV∈A×C 台∈(AxB)∪(AxC)所以()式成立。 其余可以类似证明

3) 对∪和∩满足分配律。 设A,B,C是任意集合，则 ⑴ 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) 证明⑴ ：任取A(B∪C) xA yB∪C xA (yB∨yC) ( xA yB)∨(xAyC) AB∨AC (AB)∪(AC) 所以⑴式成立。 其余可以类似证明

4若C≠①,则 A∈B冷(A×CcB×C)冷( CXACCXB) 证明:必要性:设AcB,求证 AxCcBXC 任取∈AxC分x∈Ay∈C →X∈BNy∈C(因AcB) 台∈BxC所以,AxC≤B×C 充分性:若C西Φ,由 AXCcBXO求证AcB 取C中元素y任取x∈A→X∈Ay∈C ∈A×C →∈BxC(由 AxCcBXO) 台→X∈BNy∈C→X∈B所以,AcB 所以AcB台→( AXCcBXC) 类似可以证明AB台> CxACCxB)

4)若C,则 AB(ACBC) (CACB). 证明: 必要性： 设AB，求证ACBC 任取AC xAyC xByC (因AB) BC 所以, ACBC. 充分性： 若C, 由ACBC 求证 AB 取C中元素y, 任取 xAxAyC AC BC (由ACBC ) xByCxB 所以, AB. 所以 AB(ACBC) 类似可以证明 AB (CACB)

5)设A、B、C、D为非空集合,则 A×B∈A×B →∈CXD(由A× BECXD) >X∈CNy∈D所以,A≌C∧B∈A×B ∈A×B分X∈Ay∈B →x∈ CAyED(由AcC,BD) 台xxy>∈C×D所以, AXBCCXD证毕

5) 设A、B、C、D为非空集合，则 ABCDAC∧BD. 证明: 首先,由ABCD 证明AC∧BD. 任取xA，任取yB，所以 xAyB A×B C×D (由ABCD ) xCyD 所以, AC∧BD. 其次, 由AC，BD. 证明ABCD 任取A×B A×B  xAyB  xCyD (由AC，BD) C×D 所以, ABCD 证毕

6)约定 (…(A1×A2)××An21)XAn)=A1×A2××An 特别AxAx.×A=A 设R是实数集合,则R2表示笛卡尔坐标平面, R3表示三维空间,R表示n维空间 3应用 1)令A1={xx是学号}A2={xx是姓名}A3={男,女} A:={xx是出生日期}A5={xx是班级}A6={xx是籍贯} 则A1XA2×A3×AxA×A6中一个元素: <001,王强,男,1981:02:16,计2001-1,辽宁 这就是学生档案数据库的一条信息,所以学生 的档案就是AA2XA3×A4×A×A的一个子集

6)约定 (…(A1A2 )…An-1 )An )=A1A2…An 特别 AA…A = An 设R是实数集合，则R2表示笛卡尔坐标平面， R3表示三维空间，Rn表示n维空间。 3.应用 1)令A1={x|x是学号} A2={x|x是姓名} A3={男,女} A4={x|x是出生日期} A5={x|x是班级} A6 ={x|x是籍贯} 则A1A2A3 A4A5 A6中一个元素： 这就是学生档案数据库的一条信息，所以学生 的档案就是A1A2A3 A4A5 A6的一个子集。 n 个