离散数学第四章二元关系和函数知识点总结

集合论部分

第四章、二元关系和函数

集合的笛卡儿积与二元关系有序对

定义由两个客体x 和y，按照一定的顺序组成的

二元组称为有序对，记作

实例：点的直角坐标(3,4)

有序对性质

有序性 （当x y时）

与 相等的充分必要条件是= x=u y=v

例1 <2, x+5> = <3y4, y>，求x, y.

解 3y 4 = 2, x+5 = y y = 2, x = 3

定义一个有序n (n3) 元组 是一个

有序对，其中第一个元素是一个有序n-1元组，即

= < , x n>

当n=1时, 形式上可以看成有序 1 元组.

实例 n 维向量是有序 n元组.

笛卡儿积及其性质

定义设A,B为集合，A与B 的笛卡儿积记作A B，即A B ={ | x A y B }

例2 A={1,2,3}, B={a,b,c}

A B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,

<3,a>,<3,b>,<3,c>}

B A ={,,,,,,

, ,}

A={}, P(A)A={<,>, <{},>}

性质：

不适合交换律A B B A (A B, A, B)

不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律

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)

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

A=B=

若|A|=m, |B|=n, 则 |A B|=mn

证明A(B C)=(A B)(A 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)

所以有A×(B∪C) = (A×B)∪(A×C).

例3 (1) 证明A=B C=D A C=B D

(2) A C=B D是否推出A=B C=D 为什么

解 (1) 任取

A C x A y C

x B y D B D

(2) 不一定. 反例如下：

A={1}，B={2}, C=D=, 则A C=B D 但是A B.

二元关系的定义

定义设A,B为集合, A×B的任何子集所定义的二元

关系叫做从A到B的二元关系, 当A=B时则叫做A上

的二元关系.

例4 A={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, |A×A|=n2, A×A的子集有个. 所以A上有

个不同的二元关系.

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

设A 为任意集合，

是A 上的关系，称为空关系

E

, I A 分别称为全域关系与恒等关系，定义如下：

A

E

={|x∈A∧y∈A}=A×A

A

I

={|x∈A}

A

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

E

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

A

I

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

A

小于等于关系L A, 整除关系D A, 包含关系R定义：

L

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

A

D

={| x,y∈B∧x整除y},

B

B Z*, Z*为非0整数集

R={| x,y∈A∧x y}, A是集合族.

类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.

例如A = {1, 2, 3}, B ={a, b}, 则

L

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

A

D

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

A

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

R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

二元关系的表示

表示方式：关系的集合表达式、关系矩阵、关系图

关系矩阵：若A={a1, a2, …, a m}，B={b1, b2, …, b n}，R是从A到B的关系，R 的关系矩阵是布尔矩阵M R = [ r ij ] m n, 其中r ij= 1 < a i, b j> R.

关系图：若A= {x1, x2, …, x m}，R是从A上的关系，R的关系图是G R=, 其中A为结点集，R为边集.如果属于关系R，在图中就有一条从x i到x j 的有向边.

注意：A, B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系

A={1,2,3,4},

R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},

R的关系矩阵M

和关系图G R如下：

R

关系的运算

基本运算定义：定义域、值域和域

dom R = { x | y (R) }

ran R = { y | x (R) }

fld R = dom R ran R

例1 R={<1,2>,<1,3>,<2,4>,<4,3>}, 则

dom R={1, 2, 4}

ran R={2, 3, 4}

fld R={1, 2, 3, 4}

逆与合成

R1 = { | R}

R°S = | | y (RS) } 例2 R={<1,2>, <2,3>, <1,4>, <2,2>}

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

R1={<2,1>, <3,2>, <4,1>, <2,2>}

R°S ={<1,3>, <2,2>, <2,3>}

S°R ={<1,2>, <1,4>, <3,2>, <3,3>}

定义 F 在A上的限制

F?A = { | xFy x A}

A 在F下的像

F[A] = ran(F?A)

实例R={<1,2>, <2,3>, <1,4>, <2,2>}

R?{1}={<1,2>,<1,4>}

R[{1}]={2,4}

R?=

R[{1,2}]={2,3,4}

注意：F?A F, F[A] ran F

基本运算的性质

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

(1) (F1)1=F

(2) dom F1=ran F, ran F1=dom F

证 (1) 任取, 由逆的定义有

∈(F 1) 1 ∈F 1 ∈F

所以有 (F1)1=F

(2) 任取x,

x∈dom F 1 y(∈F1)

y(∈F) x∈ran F

所以有dom F1= ran F. 同理可证 ran F1 = dom F.

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

(1) (F°G)°H=F°(G°H)

(2) (F°G)1= G1°F 1

证 (1) 任取,

(F°G)°H t(∈F°G∧∈H) t (s(∈F∧∈G)∧∈H)

t s (∈F∧∈G∧∈H)

s (∈F∧t (∈G∧∈H))

s (∈F∧∈G°H)

∈F°(G°H)

所以 (F°G)°H = F°(G°H)

(2) 任取,

∈(F°G)1

∈F°G

t (∈F∧(t,x)∈G)

t (∈G1∧(t,y)∈F1)

∈G1°F1

所以 (F°G)1 = G1°F1

幂运算

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

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

(2) R n+1 = R n°R

注意：

对于A上的任何关系R1和R2都有

R 10 = R

2

0 = I

A

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

R1 = R

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

证R为A上的关系, 由于|A|=n, A上的不同关系只有个.

当列出R 的各次幂

R0, R1, R2, …, , …,

必存在自然数s 和t 使得R s=R t.

定理4 设R 是A 上的关系, m, n∈N, 则

(1) R m°R n=R m+n

(2) (R m)n=R mn

证用归纳法

(1) 对于任意给定的m∈N, 施归纳于n.

若n=0, 则有

R m°R0=R m°I

=R m=R m+0

A

假设R m°R n=R m+n, 则有

R m°R n+1=R m°(R n°R)=(R m°R n)°R=R m+n+1 ,

所以对一切m, n∈N有R m°R n=R m+n.

(2) 对于任意给定的m∈N, 施归纳于n.

若n=0, 则有

(R m)0=I A=R0=R m×0

假设 (R m)n=R mn, 则有

(R m)n+1=(R m)n°R m=(R mn)°R m=R mn+m=R m(n+1)

所以对一切m,n∈N有 (R m)n=R mn.

关系的性质

自反性

反自反性

定义设R为A上的关系,

(1) 若x(x∈A→R), 则称R在A上是自反的.

(2) 若x(x∈A→R), 则称R在A上是反自反的.实例：

反关系：A上的全域关系E A, 恒等关系I A

小于等于关系L A, 整除关系D A

反自反关系：实数集上的小于关系

幂集上的真包含关系

例1 A={1,2,3}, R1, R2, R3是A上的关系, 其中R

＝{<1,1>,<2,2>}

1

R

＝{<1,1>,<2,2>,<3,3>,<1,2>}

2

R

＝{<1,3>}

3

R

自反,

2

R

反自反,

3

R

既不是自反也不是反自反的

1

对称性

反对称性

定义设R为A上的关系,

(1) 若x y(x,y∈A∧∈R→∈R), 则称R为A上对称的关系.

(2) 若x y(x,y∈A∧∈R∧∈R→x=y), 则称R为A上的反对称关系.

实例：

对称关系：A上的全域关系E A, 恒等关系I A和空关系

反对称关系：恒等关系I A，空关系是A上的反对称关系.

例2 设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系,

其中

R

＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}

1

R

＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}

3

R

对称、反对称.

1

R

对称，不反对称.

2

R

反对称，不对称.

3

R

不对称、也不反对称.

4

传递性

定义设R为A上的关系, 若x y z(x,y,z∈A∧∈R∧∈R→∈R),

则称R是A上的传递关系.

实例：

A上的全域关系E

,恒等关系I A和空关系

A

小于等于关系, 小于关系，整除关系，包含关系，

真包含关系

例3 设A＝{1,2,3}, R1, R2, R3是A上的关系, 其中

R

＝{<1,1>,<2,2>}

1

R

＝{<1,2>,<2,3>}

2

R

＝{<1,3>}

3

R

和R3 是A上的传递关系

1

R

不是A上的传递关系

2

关系性质的充要条件

设R为A上的关系, 则

(1) R在A上自反当且仅当I A R

(2) R在A上反自反当且仅当R∩I A=

(3) R在A上对称当且仅当R=R 1

(4) R在A上反对称当且仅当R∩R1I A

(5) R在A上传递当且仅当R R R

证明模式证明R在A上自反

任取x,

x A……………..….……. R

前提推理过程结论

例4 证明若I A R ，则 R在A上自反.

证任取x,

x A I

R

A

因此R 在A 上是自反的.

证明模式证明R在A上对称

任取

R……………..….……. R

前提推理过程结论例5 证明若R=R1 , 则R在A上对称.

证任取

R R1 R

因此R 在A 上是对称的.

证明模式证明R在A上反对称

任取

RR………..………. x=y

前提推理过程结论例6 证明若R∩R1I A , 则R在A上反对称.

证任取

R R R R1

R∩R1 I A x=y

因此R 在A 上是反对称的.

证明模式证明R在A上传递

任取，

RR…..………. R

前提推理过程结论

例7 证明若R R R , 则R在A上传递.

证任取，

R R R R R

因此R 在A 上是传递的.

关系的闭包

闭包定义

定义设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R, 使得R满足以下条件：

（1）R是自反的（对称的或传递的）

（2）R R

（3）对A上任何包含R的自反（对称或传递）关系R有R R. 一般将R 的自反闭包记作r(R), 对称闭包记作s(R), 传递闭包记作t(R).

闭包的构造方法

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

(1) r(R) = R∪R0

(2) s(R) = R∪R1

(3) t(R) = R∪R2∪R3∪…

说明：

对于有穷集合A (|A|=n) 上的关系, (3)中的并最多不超过R n. 若R是自反的，则r(R)=R; 若R是对称的，则s(R)=R; 若R是传递的，则t(R)=R. 设关系R, r(R), s(R), t(R)的关系矩阵分别为M, M r, M s 和M t , 则

M

= M + E

r

M

= M + M’

s

M

= M + M2 + M3 + …

t

E 是和M 同阶的单位矩阵, M’是M 的转置矩阵.

注意在上述等式中矩阵的元素相加时使用逻辑加.

设关系R, r(R), s(R), t(R)的关系图分别记为G, G r, G s, G t , 则G r, G s, G t 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新边：考察G的每个顶点, 如果没有环就加上一个环，最终得到G r . 考察G的每条边, 如果有一条x i 到x j 的单向边, i≠j, 则在G中加一条x j 到x i 的反方向边，最终得到G s. 考察G的每个顶点x i, 找从x i 出发的每一条路径，如果从x i 到路径中任何结点x j 没有边，就加上这条边. 当检查完所有的顶点后就得到图G

.

t

等价关系和偏序关系

定义设R 为非空集合上的关系. 如果R 是自反的、对称的和传递的, 则称R 为 A 上的等价关系. 设R 是一个等价关系, 若∈R, 称x 等价于y, 记做x～y.

实例设A={1,2,…,8}, 如下定义A上的关系R：R = { | x,y∈A∧x≡y(mod 3) }其中x≡y(mod 3) 叫做x 与y 模3相等, 即x 除以3的余数与y 除以3的余数相等.

验证模 3 相等关系R 为A上的等价关系, 因为

x∈A, 有x ≡ x(mod 3)

x, y∈A, 若x ≡ y(mod 3), 则有y ≡ x(mod 3) x, y, z∈A, 若x ≡ y(mod 3), y ≡ z(mod 3), 则有x≡z(mod 3)

自反性、对称性、传递性得到验证

定义设R为非空集合A上的等价关系, x∈A，令[x]R = { y | y∈A∧xRy }

称 [x]R 为x 关于R 的等价类, 简称为x 的等价类, 简记为[x].

实例A={ 1, 2, … , 8 }上模 3 等价关系的等价类：

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}

等价类的性质：

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

(1) x∈A, [x] 是A的非空子集.

(2) x, y∈A, 如果x R y, 则 [x]=[y].

(3) x, y∈A, 如果x y, 则 [x]与[y]不交.

(4) ∪{ [x] | x∈A}=A，即所有等价类的并集就是A. A={ 1, 2, … , 8 }上模 3 等价关系的等价类：

[1]=[4]=[7]={1,4,7}，

[2]=[5]=[8]={2,5,8}，

[3]=[6]={3,6}

以上3 类两两不交，

{1,4,7}{2,5,8}{3,6} = {1,2, (8)

定义设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} }

A关于恒等关系和全域关系的商集为：

A/I

= { {1},{2}, … ,{8}}

A

A/E

= { {1, 2, … ,8} }

A

集合的划分：

定义设A为非空集合, 若A的子集族π(πP(A)) 满足下面条件：

(1) π

(2) x y (x,y∈π∧x≠y→x∩y=)

(3) ∪π=A

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

例1 设A＝{a, b, c, d},

给定π1,π2,π3,π4,π5,π6如下：

π

= { {a, b, c}, {d} }，π2= { {a, b}, {c}, {d} }

1

π

= { {a}, {a, b, c, d} }, π4= { {a, b}, {c} }

3

π

= { ,{a, b}, {c, d} }, π6= { {a, {a}}, {b, c, d} }

5

则π1和π2是A的划分, 其他都不是A 的划分.

为什么

等价关系与划分的一一对应

商集A/R 就是A 的一个划分

不同的商集对应于不同的划分

任给A 的一个划分π, 如下定义A 上的关系R：

R = { | x,y∈A∧x 与y 在π的同一划分块中}

则R 为A上的等价关系, 且该等价关系确定的商集就是π. 例2 给出A＝{1,2,3}上所有的等价关系

求解思路：先做出A的所有划分, 然后根据划分写

出对应的等价关系.

例3 设A={1, 2, 3, 4}，在A A上定义二元关系R：

<,>R x+y = u+v，

求R 导出的划分.

解A A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>,<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>, <4 ,4>}

根据 的x + y = 2,3,4,5,6,7,8 将A A划分成7个等价类：

(A A)/R={ {<1,1>}, {<1,2>,<2,1>},

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

{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>},

{<3,4>, <4,3>}, {<4,4>} }

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

实例

集合A上的恒等关系I A 是A上的偏序关系.

小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系.

x与y 可比：设R为非空集合A上的偏序关系,

x,y A, x与y可比x?y ∨y?x.

结论：任取两个元素x和y, 可能有下述情况：

x?y (或y?x), x＝y, x与y不是可比的.

全序关系：

R为非空集合A上的偏序, x,y A, x与y 都是可比的，则称R 为全序（或线序）

实例：数集上的小于或等于关系是全序关系

整除关系不是正整数集合上的全序关系

覆盖：设R为非空集合A上的偏序关系, x, y∈A, 如果x ?y且不存在z A 使得x ?z ?y, 则称y 覆盖x.

实例：{ 1, 2, 4, 6 }集合上的整除关系,

2 覆盖 1,

4 和 6 覆盖 2.

4 不覆盖 1.

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

实例：整数集和小于等于关系构成偏序集，幂集P(A)和包含关系构成偏序集.

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

特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边

偏序集的特定元素

定义设为偏序集, B A, y∈B.

(1) 若x(x∈B→y?x) 成立, 则称y 为B 的最小元.

(2) 若x(x∈B→x?y) 成立, 则称y 为B 的最大元.

(3) 若x (x∈B∧x ?y) 成立, 则称y 为B的极小元.

(4) 若x (x∈B∧y ?x) 成立, 则称y 为B的极大元.

特殊元素的性质

对于有穷集，极小元和极大元必存在，可能存在多个.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是极小元；最大元一定是极大元.

孤立结点既是极小元，也是极大元.

定义设为偏序集, B A, y A.

(1) 若x(x∈B→x?y) 成立, 则称y 为B的上界.

(2) 若x(x∈B→y?x) 成立, 则称y 为B的下界.

(3) 令C＝{y | y为B的上界}, 则称C的最小元为B的最小上界或上确界.

(4) 令D＝{y | y为B的下界}, 则称D的最大元为B的最大下界或下确界.特殊元素的性质

下界、上界、下确界、上确界不一定存在

下界、上界存在不一定惟一

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

集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.

函数的定义和性质

函数定义：定义设F 为二元关系, 若x∈dom F 都存在唯一的y∈ran F 使xFy 成立, 则称F 为函数. 对于函数F, 如果有xFy, 则记作y=F(x), 并称y 为F 在x 的值.

例1 F1={,,}

F

={,}

2

F

是函数, F2不是函数

1

函数相等：定义设F, G为函数, 则

F =

G F G∧G F

如果两个函数F 和G 相等, 一定满足下面两个条件：

(1) dom F = dom G

(2) x∈dom F = dom G 都有F(x) = G(x)

实例函数

F(x)=(x21)/(x+1), G(x)=x1

不相等, 因为 dom F dom G.

定义设A, B为集合, 如果

f 为函数

dom f = A

ran f B,

则称f 为从A到B的函数, 记作f：A→B.

实例

f：N→N, f(x)=2x 是从N 到N 的函数

g：N→N, g(x)=2也是从N 到N 的函数

定义所有从A 到B 的函数的集合记作B A,

读作“B上A”，符号化表示为

B A ={ f | f：A→B }

计数：

|A|=m, |B|=n, 且m, n>0, |BA|=n m.

A=, 则B A=B={}.

A≠且B=, 则B A=A= .

例2 设A = {1, 2, 3}, B = {a, b}, 求B A.

解B A = {f0, f1, … , f7}, 其中

f

={<1,a>,<2,a>,<3,a>}, f1={<1,a>,<2,a>,<3,b>} 0

f

={<1,a>,<2,b>,<3,a>}，f3={<1,a>,<2,b>,<3,b>}

2

f

={<1,b>,<2,a>,<3,a>}，f5={<1,b>,<2,a>,<3,b>}

4

f

={<1,b>,<2,b>,<3,a>}, f7={<1,b>,<2,b>,<3,b>} 6

定义设函数f：A→B, A1A.

A

在f 下的像：f(A1) = { f(x) | x∈A1 }

1

函数的像f(A)

本文来源：https://www.bwwdw.com/article/yene.html