离散数学 二元关系

离散数学二元关系第1页，共12页，2023年，2月20日，星期二2

有序对的性质：1）有序性<x,y><y,x>（当xy时）2）<x,y>与<u,v>相等的充分必要条件是<x,y>=<u,v>x=uy=v例4.1<2,x+5>=<3y4,y>，求x,y.解3y4=2,x+5=y

y=2,x=3

§4.1二元关系的概念1.有序对/序偶：由两个元素x和y按一定顺序排成的组合。记作：<x，y>。其中x称作第一个元素；y称作第二个元素。第2页，共12页，2023年，2月20日，星期二3

注：<x1,<x2,x3,…,xn>>≠<x1,x2,…,xn>实例：1.空间直角坐标系中的坐标

<3，5，－6>是有序三元组2.图书馆记录<书类别，书号，书名，作者，出版社，年份>是一个有序六元组.2.有序n元组：一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

<<x1,x2,…,xn-1>,xn>=

<x1,x2,…,xn>。我们将来的研究重点为有序二元组，即有序对/序偶第3页，共12页，2023年，2月20日，星期二4例4.2A={1,2,3},B={a,b,c},C=

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}AA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}AC=CA=3.笛卡儿积：设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对.所有这样的有序对组成的集合叫做

A与B的笛卡儿积记作AB,即AB={<x,y>|xAyB}。第4页，共12页，2023年，2月20日，星期二5笛卡儿积的性质：1.不适合交换律ABBA(AB,A,B)2.若A或B中有一个为空集，则AB就是空集.

AB=BA=

3.若|A|=m,|B|=n,则|AB|=mn

4.不适合结合律(AB)CA(BC)(A,B)例：A={1},B={2},C={3}AB={<1,2>},(AB)C={<<1,2>,3>}={<1,2,3>}BC={<2,3>},A(BC)={<1,<2,3>>}{<1,2,3>}第5页，共12页，2023年，2月20日，星期二6二元关系：集合中两个元素之间的某种关系例4.3甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x胜y.它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.例4.4有A、B、C3个人和四项工作G1、G2、G3、G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2.

那么，人和工作之间的对应关系可以记作

R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2>}它表示了集合{A,B,C}到工作{G1,G2,G3,G4}之间的关系第6页，共12页，2023年，2月20日，星期二如<x,y>∈R,可记作xRy；如果<x,y>R,则记作xRy实例：R1={<1,2>,<a,b>},R2=

,R3={<1,2>,3,4}，R4={<x,y>|x∈N∧y∈Z}R1,R2,R4是二元关系；R3不是二元关系。4.

二元关系：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.第7页，共12页，2023年，2月20日，星期二85.从A到B的关系与A上的关系设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做

A上的二元关系.例4.5A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.

计数：|A|=n,|B|=m,|A×B|=n×m,A×B的子集有个.所以A到B上有个不同的二元关系.|A|=n,|A×A|=

,A×A的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有512个不同的二元关系.

第8页，共12页，2023年，2月20日，星期二9设A为任意集合，是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},则

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

注：{<1,1>}≠IA;{<2,2>}≠IA6.A上的特殊关系第9页，共12页，2023年，2月20日，星期二10小于等于关系LA,整除关系DA,包含关系R定义：

LA={<x,y>|x,y∈A∧x≤y},AR，R为实数集合

DB={<x,y>|x,y∈A∧x整除y},BZ*,Z*为非0整数集

R={<x,y>|x,y∈P(A)∧xy},P(A)是集合A的幂集.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.6.A上的特殊关系第10页，共12页，2023年，2月20日，星期二11例4.6A={1,2,3},B={a,b},则

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

P(B)={,{a},{b},{a,b}},则B上的包含关系是R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{