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

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

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

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

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

2.定义：设<x,y>，<u,v>是两个序偶，如果 x=u和y=v，则称<x,y>和<u,v>相等， 记作<x,y>=<u,v>. 3 .定义:有序3元组是一个序偶,其第一个元素也是个序偶。 有序3元组<< a,b>, c>可以简记成<a,b,c>。 但<a,<b,c>>不是有序3元组。 4.定义:有序n元组是一个序偶,其第一个元素本身是个有 序n-1元组,记作<<x1 , x2 , , xn-1>, xn >。且可以简记成 <x1 , x2 , , xn-1 , xn >。 5. 定义： <x1 , x2 , , xn>=<y1 , y2 ,· , yn > ( 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={<0,a>2<0,b>,<1,a>,<1,b>} BxA={<a0>,<b,0>,<a21><b,1>} A×A={<0,0>,<0,1>,<10>,<1,1> 可见A×BB×A 所以,集合的笛卡尔积运算不满足交换律

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