离散数学_九章:关系(1)

简介: 离散数学_九章:关系(1)

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


传递关系的幂是该关系的子集

相关文章
|
算法 Android开发 Python
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
62 0
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
|
5月前
|
存储 算法 数据挖掘
螺旋矩阵 II:从理论到实践的五种算法解析
螺旋矩阵 II:从理论到实践的五种算法解析
|
算法
Plant(快速幂+数学分析(没想到吧,数学无处不在))
Plant(快速幂+数学分析(没想到吧,数学无处不在))
67 0
|
机器学习/深度学习 数据库
离散数学_九章:关系(2)
离散数学_九章:关系(2)
108 1
|
机器学习/深度学习 人工智能 语音技术
离散数学_九章:关系(5)
离散数学_九章:关系(5)
241 0
|
人工智能
离散数学_九章:关系(3)(一)
离散数学_九章:关系(3)(一)
127 0
|
机器学习/深度学习 移动开发
离散数学_九章:关系(4)(二)
离散数学_九章:关系(4)(二)
146 0
|
Python
离散数学_九章:关系(6)(一)
离散数学_九章:关系(6)(一)
111 0
离散数学_九章:关系(4)(一)
离散数学_九章:关系(4)(一)
98 0
|
数据可视化
离散数学_九章:关系(6)(二)
离散数学_九章:关系(6)(二)
345 0