定义7.1 由两个元素 x 和 y，按照一定的顺序组成的二元组称为有序对，记作.

有序对性质:

(1) 有序性  （当xy时）

(2) 与相等的充分必要条件是

= x=uy=v.

定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，且

AB = {| xAyB}.

笛卡儿积性质：

(1) 不适合交换律

AB BA (AB, A, B)

(2) 不适合结合律

(AB)C A(BC) (A, B, C)

(3) 对于并或交运算满足分配律

A(BC) = (AB)(AC) (BC)A = (BA)(CA)

A(BC) = (AB)(AC) (BC)A = (BA)(CA)

(4) 若 A 或 B 中有一个为空集，则 AB 就是空集.

A = B = 

(5) 若 |A| = m, |B| = n, 则 |AB| = mn

例题：

AC = BD是否推出 A=B,C=D? 为什么？

不一定.反例如下：

A={1}，B={2}, C = D = , 则AC = BD但是A B.

定义7.3 如果一个集合满足以下条件之一：

(1) 集合非空, 且它的元素都是有序对

(2) 集合是空集

则称该集合为一个二元关系, 简称为关系，记作R.

定义7.4

设A,B为集合, A×B的任何子集所定义的二元关系叫做从A到B的二元关系, 当A=B时则叫做A上的二元关系.

定义7.5 设 A 为集合,

(1) 是A上的关系，称为空关系

(2) 全域关系 EA = {| x∈A∧y∈A} = A×A

恒等关系 IA = {| x∈A}

小于等于关系 LA = {| x,y∈A∧x≤y}, A为实数子集

整除关系 DB = {| x,y∈B∧x整除y}, A为非0整数子集

包含关系 R = {| x,y∈A∧xy}, A是集合族.

关系的表示

1. 关系矩阵

若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的

关系，R的关系矩阵是布尔矩阵MR = [ rij ] mn, 其中

rij = 1 < xi, yj> R.

2. 关系图

若A= {x1, x2, …, xm}，R是从A上的关系，R的关系图是GR=, 其中A为结点集，R为边集. 如果属于关系R，在图中就有一条从 xi 到 xj 的有向边.

注意：

关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）

关系图适合表示有穷集A上的关系

关系的基本运算

定义7.6 关系的定义域、值域与域分别定义为

domR = { x | y (R) }

ranR = { y | x (R) }

fldR = domR  ranR

定义7.7 关系的逆运算

R1 = { | R }

定义7.8 关系的合成运算

RS = { | y (R  S) }

定义7.9 设R为二元关系, A是集合

(1) R在A上的限制记作 R↾A, 其中

 R↾A = { | xRy∧x∈A }

(2) A在R下的像记作R[A], 其中

 R[A]=ran(R↾A)

说明：

R在A上的限制 R↾A是 R 的子关系，即 R↾A R

A在R下的像 R[A] 是 ranR 的子集，即 R[A] ranR

R↾ = 

R[] = 

定理7.1 设F是任意的关系, 则

(1) (F1)1=F

(2) domF1= ranF, ranF1= domF

定理7.2 设F, G, H是任意的关系, 则

(1) (FG)H = F(GH)

(2) (FG)1 = G1F1

定理7.3 设R为A上的关系, 则

  RIA= IAR=R

定理7.4

(1) F(GH) = FG∪FH (2) (G∪H)F = GF∪HF

(3) F(G∩H) FG∩FH (4) (G∩H)F GF∩HF

只证 (3) 任取,

 ∈F(G∩H)

t (∈F∧∈G∩H)

 t (∈F∧∈G∧∈H)

 t ((∈F∧∈G)∧(∈F∧∈H))

 t (∈F∧∈G)∧t (∈F∧∈H)

 ∈FG∧∈FH

 ∈FG∩FH

所以有 F(G∩H) FG∩FH

定理7.4 的结论可以推广到有限多个关系

R(R1∪R2∪…∪Rn) = RR1∪RR2∪…∪RRn

(R1∪R2∪…∪Rn)R = R1R∪R2R∪…∪RnR

R(R1∩R2∩ … ∩Rn) RR1∩RR2∩ … ∩RRn

(R1∩R2∩ … ∩Rn)R R1R∩R2R∩ … ∩RnR

定理7.5 设F 为关系, A, B为集合, 则

(1) F ↾(A∪B) = F ↾A∪F ↾B

(2) F [A∪B] = F [A]∪F [B]

(3) F ↾(A∩B) = F ↾A∩F ↾B

(4) F [A∩B] F [A]∩F [B]

定义7.10

设 R 为 A 上的关系, n为自然数, 则 R 的 n 次幂定义为：

(1) R0 = { | x∈A } = IA

(2) Rn+1 = RnR

注意：

对于A上的任何关系 R1 和 R2 都有 R10 = R20 = IA

对于A上的任何关系 R 都有 R1 = R

如何计算R的n次幂呢（n≧2）？

1、关系矩阵的布尔乘法

与线性代数中的矩阵乘法公式相比，只要把矩阵乘法公式中的数乘改为合取，把数加改为析取，就得到了关系矩阵的布尔乘法公式。

2、关系图

几次幂就是走几步能不能到。

定理7.6 设 A 为 n 元集, R 是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.

证 R 为A上的关系,

列出 R 的各次幂

必存在自然数 s 和 t 使得 Rs = Rt

定理7.7 设 R 是 A上的关系, m, n∈N, 则 【归纳法】

(1) RmRn = Rm+n

(2) (Rm)n = Rmn

定理7.8 设R 是A上的关系,

若存在自然数 s, t (sy | y∈A∧xRy}

定理7.14 设R是非空集合A上的等价关系, 则

(1) xA, [x]是A的非空子集

(2) x,yA, 如果 xRy, 则 [x] = [y]

(4) ∪{[x] | xA}=A

证 (1) 由定义, xA有[x]A. 又x[x], 即[x]非空.

(2) 任取 z, 则有

 z∈[x]  ∈R ∈R

R∧R R R

从而证明了z∈[y]. 综上所述必有 [x][y]. 同理可证 [y][x]. 这就得到了[x] = [y].

(4) 先证∪{[x] | xA} A. 任取y,

y∪{[x] | xA} x(xA∧y[x])

y[x]∧[x] A yA

从而有∪{[x] | x∈A} A

再证A ∪{[x] | x∈A}. 任取y,

yA y[y]∧yA y∈∪{[x] | xA}

从而有∪{[x] | x∈A} A成立.

综上所述得∪{[x] | xA} = A.

定义7.17 设 R 为非空集合A上的等价关系, 以 R 的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = {[x]R | x∈A}

实例 设 A={1,2,…,8}，A关于模3等价关系R的商集为

A/R = {{1,4,7}, {2,5,8}, {3,6}}

定义7.18 设A为非空集合, 若A的子集族π(π P(A))满足:

(1) π

(2) xy(x,yπ∧x≠y→x∩y=)【两两不交】

(3) ∪π = A

则称π是A的一个划分, 称π中的元素为A的划分块.

根据等价类的性质以及划分的定义，显然有下面的结论：

（1）商集就是A的一个划分，等价类就是划分块。

（2）给定集合A上的一个等价关系R决定了A的一个划分，并且不同的等价关系将对应于不同的划分。

（3）给定集合A的一个划分确定该集合上的一个等价关系。

定义4.17 设R为非空集合A上的关系，如果R是自反的和对称的，则称R为A上的相容关系。

根据该定义，相容关系有以下三个性质：

（1）所有的等价关系都是相容关系。

（2）相容关系的关系矩阵主对角线全为1且是对称矩阵。

（3）相容关系的关系图每一个节点上都有环，且每两个不同节点间如果有边，一定有方向相反的两条边。

相容关系的图形表示中，每个环不必画出，两个元素之间方向相反的有向边用一条无向边替代，这样的图称为相容关系的简化关系图。

定义4.18 设R是非空集合A上的相容关系，集合C A，若对任意的x, yC都有xRy成立，则称C是由相容关系R产生的相容类。

如果R是A上的相容关系, C是由相容关系R产生的相容类,从定义可看出:

（1）相容类C一定是A的子集。

（2）因为相容关系R是自反的，即xA， 有xRx，所以{x}是由相容关系R产生的一个相容类，即A中的任何元素组成的单元素集是由相容关系R产生的一个相容类。

定义4.19 设R是非空集合A上的相容关系，C是R产生的相容类。如果它不是其他任何相容类的真子集，则称C为最大相容类，记为CR。

根据定义4.19，最大相容类CR具有如下的性质：

（1）CR中任意元素x与CR中的所有元素都有相容关系R。

（2）A - CR中没有一个元素与CR中的所有元素都有相容关系R。

利用相容关系的简化关系图求最大相容类的方法：

（1）最大完全多边形的顶点构成的集合是最大相容类。

（2）孤立点构成的集合是最大相容类。

（3）如果一条边不是任何完全多边形的边，则它的两个端点构成的集合是最大相容类。

定理4.20 设R是非空有限集合A上的相容关系，C是R产生的相容类，那么必存在最大相容类CR，使得CCR。

定义4.20 设A是非空集合，若A的子集族满足以下条件：

（1）

（2）

则称为集合A的一个覆盖。

定理4.21 设A是有限集合，R是A上的相容关系，由R产生的所有最大相容类构成的集合是A的覆盖，叫作集合A的完全覆盖，记为CR(A)。

定理4.22 给定集合A的覆盖{A1, A2,... ,An}，则由它确定的关系R= A1A1A2A2... AnAn是A上的相容关系。

定理4.23 集合A上的相容关系R与完全覆盖CR(A)存在一一对应。

定义7.19

偏序关系：非空集合A上的自反、反对称和传递的关系，记作≼. 设≼为偏序关系, 如果 ∈≼, 则记作 x ≼ y, 读作x"小于或等于"y.

定义7.20 设 R 为非空集合A上的偏序关系,

(1) x, y∈A, x与y可比  x ≼ y∨y ≼ x

(2) 任取元素 x 和 y, 可能有下述几种情况发生：x ≺ y (或 y ≺ x), x＝y, x与y不是可比的

定义7.21 R 为非空集合A上的偏序关系, x,y∈A, x与y都是可比的，则称R为全序（或线序）

定义7.22 x,y∈A, 如果 x≺y 且不存在 z∈A 使得 x≺z≺y, 则称 y覆盖x.

定义7.23 集合A和A上的偏序关系≼一起叫做偏序集, 记作.

哈斯图: 利用偏序关系的自反、反对称、传递性进行简化的关系图

特点：

(1) 每个结点没有环

(2) 两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前

(3) 具有覆盖关系的两个结点之间连边

偏序集的哈斯图的画法如下：

（1）用"°"表示A中的每一个元素；

（2）x, yA，若xy| y为B的下界}, D的最大元为B的最大下界或下确界

性质：

(1) 下界、上界、下确界、上确界不一定存在

(2) 下界、上界存在不一定惟一

(3) 下确界、上确界如果存在，则惟一

(4) 集合的最小元是其下确界，最大元是其上确界；反之不对.

关系性质的证明方法

1. 证明R在A上自反

任取x,

xA  ……………………..….…….  R

前提 推理过程 结论

2. 证明R在A上对称

任取，

R  ……………………………….  R

前提 推理过程 结论

3. 证明R在A上反对称

任取，

RR  ……………………..  x = y

前提 推理过程 结论

4. 证明R在A上传递

任取,，

RR  ……………………..  R

前提 推理过程 结论

关系等式或包含式的证明方法

数学归纳法（主要用于幂运算）

证明中用到关系运算的定义和公式, 如：

基本要求

熟练掌握关系的三种表示法

能够判定关系的性质（等价关系或偏序关系）

掌握含有关系运算的集合等式

掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念

计算A´B, dom R, ranR, fldR, R-1, R°S , Rn , r(R), s(R), t(R)

求等价类和商集A/R

给定A的划分p，求出p 所对应的等价关系

求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界

掌握基本的证明方法

证明涉及关系运算的集合等式

证明关系的性质、证明关系是等价关系或偏序关系7和