9.1关系及其性质
1、二元关系
设A和B是集合,一个从 A 到 B 的二元关系是A×B的子集。 (序偶集合的子集)
🐳换句话说,一个从A到B的二元关系是集合R,其中每个有序对的第一个元素取自A而第二个元素取自B。
我们使用记号 aRb表示(a, b)∈R,aR b表示(a, b)∉R。当(a, b)属于R时,称a与b有关系R。
📘例:设 A = { 0, 1, 2 }, B = { a, b }
{ (0, a), (0, b), (1, a), (2, b) }是一个从 A 到 B 的关系。
我们可以用图或表格来表示从集合 A 到集合 B 的关系:
2、集合A上的关系
集合A上的关系是从A到A的关系。
🐳换句话说,集合A上的关系是从A到A的关系
📘例:设 A = { a, b, c }
那么R = { (a, a), (a, b), (a, c) }是 A 上的关系
3、n元素集合 有多少个关系?
A上的关系和 A × A 的子集是一回事
➡所以可以直接计数 A × A 的子集。
因为当 A 是 n 元素集合时 A × A 有 n2 个元素,所以 A × A 的子集有 2m (m = n2)
📘例:设 B = { b }
那么B上的二元关系共有2个:R1 = ∅,R2 = { (b, b) }
📘例:设 C = { a, b, c }
那么C上的二元关系共有29 = 512个
4、关系的性质
1. 自反(Reflexivity)
若对每个元素a∈A有(a,a)∈R,那么定义在集合A上的关系R称为自反的 记作aRa,a是A中任意一个元素
用符号表示:(集合A上的关系)R 是自反的,当且仅当 ∀x(x∈A⟶ (x, x)∈R )
(这里的论域是A中所有元素的集合。)
📘例:
以下关于整数的关系是自反的:
R1 = { (a, b) | a ≤ b },
R3 = { (a, b) | a = b 或 a = – b },
R4 = { (a, b) | a = b }。
以下关系不是自反的:
R2 = { (a, b) | a > b }(注意3 ≯ 3),
R5 = { (a, b) | a = b + 1 }(注意3 ≠ 3 + 1),
R6 = { (a, b) | a + b ≤ 3 }(注意4 + 4 ≰ 3)。
2. 对称(Symmetry)
对于任意 a, b∈A,若只要 (a, b)∈R 就有 (b, a)∈R,则称定义在集合 A 上的关系 R 为对称的。
用符号表示:R 是对称的,当且仅当 ∀x∀y ( (x, y)∈R ⟶ (y, x)∈R )
📘例:
以下关于整数的关系是对称的:
R3 = { (a, b) | a = b 或 a = – b },
R4 = { (a, b) | a = b },
R6 = { (a, b) | a + b ≤ 3 }。
以下不是对称的:
R1 = { (a, b) | a ≤ b }(反例:3 ≤ 4,但4 ≰ 3),
R2 = { (a, b) | a > b }(反例:4 > 3,但 3 ≯ 4),
R5 = { (a, b) | a = b + 1 }(反例:4 = 3 + 1,但3 ≠ 4 + 1)。
3. 反对称(Antisymmetry)
对于任意 a, b∈A,若 (a, b)∈R 且 (b, a)∈R,一定有 a = b,则称定义在集合 A 上的关系 R 为反对称的。
用符号表示:R 是反对称的,当且仅当 ∀x∀y( (x, y)∈R ∧ (y, x)∈R ⟶ x = y )
📘例:
以下关于整数的关系是反对称的:
R1 = { (a, b) | a ≤ b },
R2 = { (a, b) | a > b },
R4 = { (a, b) | a = b },
R5 = { (a, b) | a = b + 1 }。
以下关系不是反对称的:
R3 = { (a, b) | a = b 或 a = – b }(反例: (1, – 1) 和 (–1, 1) 都属于R3),
R6 = { (a, b) | a + b ≤ 3 }(反例: (1, 2) 和 (2, 1) 都属于R6)。
💻对称与反对称的概念不是对立的,因为一个关系可以同时有这两种性质或者两种性质都没有。
一个关系如果包含了某些形如(a,b)的有序对,其中a≠b,则这个关系就不可能同时是对称的和反对称的。
4. 传递(Transitivity)
若对于任意 a, b, c∈A,(a, b)∈R 并且 (b, c)∈R 则 (a, c)∈R,那么定义在集合 A 上的关系 R 称为传递的。
用符号表示:R 是传递的,当且仅当∀x∀y∀z( (x, y)∈R ∧ (y, z)∈R ⟶ (x, z)∈R)
📘例:
以下关于整数的关系是可传递的:
R1 = { (a, b) | a ≤ b },
R2 = { (a, b) | a > b },
R3 = { (a, b) | a = b 或 a = – b },
R4 = { (a, b) | a = b }。
下面的句子不是可传递的:
R5 = { (a, b) | a = b + 1 }
(反例:(3, 2) 和 (4, 3) 都属于R5,但不属于 (3, 3)),
R6 = { (a, b) | a + b ≤ 3 }
(反例:(2, 1) 和 (1, 2) 都属于R6,但不属于 (2, 2))。
5、关系的组合
因为从A到B的关系是 A×B 的子集,所以可以按照两个集合组合的任何方式来组合两个从A到B的关系。
给定两个关系R1和R2,我们可以使用基本的集合操作将它们组合起来,形成新的关系,如 R1 ∪ R2、R1 ∩ R2、R1 − R2 和 R2 − R1
除了常见的并∪、交∩、差 - 、异或⊕,还有一种新的组合方式:
关系的合成
设R1 是集合 A 到集合 B 的关系,R2 是集合 B 到集合 C 的关系。
R2 和 R1 的合成是 A 到 C 的关系,其中如果 (x, y) 是 R1 的成员,(y, z) 是 R2的成员,那么 (x, z) 则是 R1 ∘ R2 的成员。
(R1 ∘ R2 表示R1 和 R2 的合成)
关系的幂
由两个关系合成的定义可以递归定义关系R的幂
设R为A上的二元关系,则关系R的n次幂Rn可归纳定义为:
基础步骤:R1 = R
归纳步骤:Rn+1 = Rn ∘ R
传递关系的幂是该关系的子集