【Discrete|二元关系【Discrete|Mathematics】

主要内容

1. 有序对与卡氏积
2.二元关系（包括空关系，恒等关系，全域关系等）及其表示（关系矩阵，关系图）
3. 关系的五种性质（自反性，反自反性，对称性，反对称性，传递性）
4.二元关系的幂运算
5.关系的三种闭包（自反闭包，对称闭包，传递闭包）
6. 等价关系和划分（包括等价类，商集，划分块等）
7. 偏序关系（包括哈斯图，最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界等）

学习要求

1.掌握：有序对及卡氏积的概念及卡氏积的性质
2.掌握：二元关系，A到B的二元关系，A上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系在集合上的限制，集合在关系下的象等概念，3掌握关系的定义域、值域、逆、合成、限制、象等的主要性质
3.掌握：关系矩阵与关系图的概念及求法
4.掌握：集合A上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质
5.掌握：A上二元关系的n次幂的定义及主要性质
6.掌握A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法
7.掌握：等价关系、等价类、商集、划分、等概念，以及等价关系与划分之间的对应
8.掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念

==========================

有序对与笛卡儿积基本概念
【【Discrete|二元关系】定义7.1 由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作，其中x是它的第一元素，y是它的第二元素。
有序对具有以下性质：

1．当x≠y时，≠。
2．=的充分必要条件是x=u且y=v。

这些性质是二元集{x,y}所不具备的。例如当x≠y时有{x,y}={y,x}。原因在于有序对中的元素是有序的，而集合中的元素是无序的。
例7.1 已知=<5,2x+y>，求x和y。
解由有序对相等的充要条件有
x+2=5
2x+y=4
解得x=3,y=-2。
定义7.2 设A，B为集合,用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。笛卡儿积的符号化表示为A×B={|x∈A∧y∈B}
例如，设A={a,b}, B={0,1,2}，则
A×B={,,,,,}
B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
由排列组合的知识不难证明，如果|A|=m,|B|=n,则|A×B|=m^n。
二元关系基本概念
定义7.3 如果一个集合满足以下条件之一：

（1）集合非空，且它的元素都是有序对
（2）集合是空集

则称该集合为一个二元关系，记作R。二元关系也可简称为关系。对于二元关系R，如果∈R，可记作xRy；如果R，则记作xy。
例如R1={<1,2>,}，R2={<1,2>,a,b}。则R1是二元关系，R2不是二元关系，只是一个集合，除非将a和b定义为有序对。根据上面的记法可以写1R12，aR1b，aR1c等。
定义7.4 设A，B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系，特别当A=B时则叫做A上的二元关系。
例如A={0,1}，B={1,2,3}，那么R1={<0,2>}，R2=A×B，R3=，R4={<0,1>}
等都是从A到B的二元关系，而R3和R4同时也是A上的二元关系。
集合A上的二元关系的数目依赖于A中的元素数。如果|A|=n，那么|A×A|=n2， A×A的子集就有个。每一个子集代表一个A上的二元关系，所以A上有个不同的二元关系。例如|A|=3，则A上有=512个不同的二元关系。
关系表示法
例7.4 设A={1,2,3,4}，下面各式定义的R都是A上的关系，试用列元素法表示R。
(1) R={|x是y的倍数}
(2) R={|(x-y)2∈A}
(3) R={|x/y是素数}
(4) R={|x≠y}
解　(1) R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}
(2) R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,<2,3>,<1,2>}
(3) R={<2,1>,<3,1>,<4,2>}
(4) R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}
给出一个关系的方法有三种:集合表达式，关系矩阵和关系图。例7.4中的关系就是用集合表达式来给出的。对于有穷集A上的关系还可以用其他两种方式来给出。
设A={x1,x2,…,xn},R是A上的关系。令

则

是R的关系矩阵，记作MR。
关系的运算基本概念

定义域、值域、域、逆关系
关系的基本运算有七种，分别定义如下：
定义7.6 设R是二元关系。
(1) R中所有的有序对的第一元素构成的集合称为R的定义域，记为domR。形式化表示为：domR={x|y(∈R)}
(2) R中所有有序对的第二元素构成的集合称为R的值域，记作ranR。形式化表示为 ranR={y|x(∈R)}
(3) R的定义域和值域的并集称为R的域，记作fldR。形式化表示为fldR=domR∪ranR
例7.5 设R={<1,2>,<1,3>,<2,4>,<4,3>}，则
domR={1,2,4}
ranR={2,3,4}
fldR={1,2,3,4}

定义7.7 设R为二元关系，R的逆关系，简称R的逆，记作R-1,其中R-1={|∈R} 运算的性质
下面考虑这些基本运算的性质。
定理7.1 设F是任意的关系，则
(1)(F-1)-1=F
(2)domF-1=ranF，ranF-1=domF

证　(1)任取，由逆的定义有
∈(F-1)-1∈F-1∈F。
所以有(F-1)-1=F。
(2)任取x,
x∈domF-1y(∈F-1)y(∈F)x∈ranF
所以有domF-1=ranF。
同理可证 ranF-1=domF。
定理7.2 设F，G，H是任意的关系，则
(1)(FG)H=F(GH)
(2)(FG)-1=F-1G-1

证 (1)任取,
∈(FG)H
t(∈FG∧(t,y)∈H)
t(s(∈F∧∈G)∧∈H)
ts(∈F∧∈G∧∈H)
s(∈F∧t(∈G∧∈H))
s(∈F∧∈GH)
∈F(GH)
所以(FG)H=F(GH)

（2）任取,
∈(FG)-1
∈FG
t(∈F∧(t,x)∈G)
t(∈G-1∧(t,y)∈F-1)
∈G-1F-1
所以（FG）-1=F-1G-1。
关系幂
在右复合运算的基础上可以定义关系的幂运算。
定义7.10 设R为A上的关系，n为自然数，则R的n次幂定义为：
（1） R0={|x∈A}=IA
（2） Rn+1=RnR
由以上定义可知，对于A上的任何关系R1和R2都有
R10=R20=IA
也就是说，A上任何关系的0次幂都相等，都等于A上的恒等关系IA。此外对于A上的任何关系R都有R1=R，因为
R1=R0R=IAR=R
给定A上的关系R和自然数n，怎样计算Rn呢？若n是0或1，结果是很简单的。下面考虑n≥2的情况。如果R是用集合表达式给出的，可以通过n-1次右复合计算得到Rn。如果R是用关系矩阵M给出的，则Rn的关系矩阵是Mn，即n个矩阵M之积。与普通矩阵乘法不同的是，其中的相加是逻辑加，即
1+1=1,1+0=0+1=1,0+0=0
如果R是用关系图G给出的，可以直接由图G得到Rn的关系图G'。G'的顶点集与G相同。考察G的每个顶点xi，如果在G中从xi出发经过n步长的路径到达顶点xj，则在G'中加一条从xi到xj的边。当把所有这样的便都找到以后，就得到图G'。
幂运算的性质
下面考虑幂运算的性质。
定理7.6 设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。
证 R为A上的关系，对任何自然数k，Rk都是A×A的子集。又知|A×A|=n2，|P(A×A)|=，即A×A的不同子集仅个。当列出R的各次幂R0，R1，R2，…，，…，必存在自然数s和t使得Rs=Rt。
该定理说明有穷集上只有有穷多个不同的二元关系。当t足够大时Rt必与某个Rs(s定理7.7 设R是A上的关系，m,n∈N，则
(1)RmRn=Rm+n
(2)(Rm)n=Rmn

证(归纳法)
(1) 对于任意给定的m∈N,施归纳于n。若n=0，则有
RmR0=RmIA=Rm=Rm+0
假设R4Rn=Rm+n，则有
RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1 ，
所以对一切m,n∈N有RmRn=Rm+n。
(2) 对于任意给定的m∈N,施归纳于n。若n=0，则有
(Rm)0=IA=R0=Rm×0
假设(Rm)n=Rmn，则有
(Rm)n+1=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)
所以对一切m,n∈N有(Rm)n=Rmn。

(未完成......请关注下节内容.)

关于Discrete Mathematics更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.