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

* *

集合论部分 第四章、二元关系和函数

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

定义 由两个客体 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作 实例：点的直角坐标(3,?4) 有序对性质

有序性 ? （当x? y时）

与 相等的充分必要条件是= ? x=u ? y=v 例1 <2, x+5> = <3y? 4, y>，求 x, y. 解 3y? 4 = 2, x+5 = y ? y = 2, x = ? 3 定义 一个有序 n (n?3) 元组 是一个 有序对，其中第一个元素是一个有序 n-1元组，即 = < , xn> 当 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, 那么 R1, R2, R3, R4是从 A 到 B

的二元关系, R3和R4同时也是 A上的二元关系. 计数

* *

3=?, R4={<0,1>}. R* *

|A|=n, |A×A|=n2, A×A的子集有 个. 所以 A上有 个不同的二元关系.

例如 |A|=3, 则 A上有=512个不同的二元关系. 设 A 为任意集合，

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

EA, IA 分别称为全域关系与恒等关系，定义如下： EA={|x∈A∧y∈A}=A×A IA={|x∈A} 例如, A={1,2}, 则

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

小于等于关系 LA, 整除关系DA, 包含关系R?定义：

LA={| x,y∈A∧x≤y}, A?R，R为实数集合 DB={| x,y∈B∧x整除y}, B?Z*, Z*为非0整数集 R?={| x,y∈A∧x?y}, A是集合族.

类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 例如 A = {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>}

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

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

* *

<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 二元关系的表示

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

关系矩阵：若A={a1, a2, …, am}，B={b1, b2, …, bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = [ rij ] m?n, 其中 rij = 1? < ai, bj> ?R.

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

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

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

R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R的关系矩阵MR和关系图GR如下：

4.2 关系的运算

基本运算定义：定义域、值域 和 域 domR = { x | ?y (?R) } ranR = { y | ?x (?R) } fldR = domR ? ranR

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

domR={1, 2, 4}