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

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

1、用集合表示关系


关系是序偶的集合,所以描述集合能用的方法一般都可以描述关系,比如枚举满足关系的所有序偶,比如叙述满足关系的性质。


前面的例子都是用集合表示关系,这里不赘述


2、用矩阵表示关系


矩阵表示关系

有限集之间的关系可用0-1 矩阵表示:


假设 R 是从 A = { a1, a2,…,am } 到 B = { b1, b2,…,bn } 的关系,则A×B上的所有关系可以用一个 m×n的长方形 0-1 矩阵 来表示。


关系R由矩阵 MR = [ mij ] 表示,其中

当 ai 与 bj 相关时,表示 R 的 0-1 矩阵的 (i, j) 项是1,如果ai 与 bj 无关系,则是0


📘例1:

假设 A = { 1, 2, 3 },B = { 1, 2 }。令 R 为 A 到 B 的关系,如果 a∈A,b∈B 且 a > b,则 R 包含 (a, b)。表示 R 的矩阵是什么(假设元素的顺序与递增的数值顺序相同)?


由题意得,R = { (2, 1), (3, 1), (3, 2) },因此矩阵为:


📘例2:

设 A = { a1, a2, a3 },B = { b1, b2, b3, b4, b5 }。哪些有序对在下面的矩阵所表示的关系 R 中?


因为 R 是由 mij = 1 的有序对 (ai, bj) 构成的,所以

R = { (a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5) }


⭐集合上的关系矩阵

表示定义在一个集合上的关系的矩阵是一个方阵,可以用这个矩阵确定关系是否有某种性质


R 自反时

R 是自反的,当且仅当 MR 的主对角线上的所有元素都等于1

❗ 注意:非主对角线上的元素可以是 0 或 1



R 对称时

R 是对称关系,当且仅当 若mij = 1 则 mji = 1


换句话说:R 是对称关系,当且仅当 MR = (MR)T


(沿主对角线对称)


R 反对称时

R 是反对称关系,当且仅当 i ≠ j 时,mij = 0 或 mji = 0(至少有一个得是0)

📘例:

假设集合上关系 R 由下图矩阵表示,R 是自反的、对称的和反对称的吗?

判断自反:因为这个矩阵中所有的对角线元素都等于1,所以 R 是自反的。

判断对称:由于 MR 是对称的,所以 R 是对称的。

判断反对称:因为 m1,2 和 m2,1 都是1,所以 R 不是反对称的


⭐确定关系合成的矩阵

确定关系合成的矩阵:已知两个关系的关系矩阵,求这两个关系矩阵的合成矩阵

本质是关系矩阵的布尔积,理解上可以直接把两个矩阵相乘(注意顺序,A×B和B×A不一样),0仍是0,大于等于1的写成1

相关文章
|
7月前
|
自然语言处理
数学基础从高一开始1、集合的概念
数学基础从高一开始1、集合的概念
73 0
|
7月前
|
机器学习/深度学习 算法 搜索推荐
普林斯顿算法讲义(四)(4)
普林斯顿算法讲义(四)
157 2
|
7月前
|
算法 数据可视化 Java
普林斯顿算法讲义(二)(3)
普林斯顿算法讲义(二)
78 0
|
7月前
|
人工智能 算法 搜索推荐
普林斯顿算法讲义(一)(4)
普林斯顿算法讲义(一)
160 0
|
7月前
|
人工智能 算法 数据可视化
普林斯顿算法讲义(二)(1)
普林斯顿算法讲义(二)
94 0
|
7月前
|
人工智能 算法 Java
普林斯顿算法讲义(四)(2)
普林斯顿算法讲义(四)
117 0
|
7月前
|
存储 人工智能 算法
普林斯顿算法讲义(一)(3)
普林斯顿算法讲义(一)
66 0
|
机器学习/深度学习 数据库
离散数学_九章:关系(2)
离散数学_九章:关系(2)
115 1
离散数学_九章:关系(4)(一)
离散数学_九章:关系(4)(一)
107 0
离散数学_九章:关系(3)(二)
离散数学_九章:关系(3)(二)
91 0