离散习题讲解（9）

她来听我的演唱会......

问题：

对于以下集合 $ {1, 2, 3, 4} $ 上的每个关系，判断它是否是反射的（reflexive），对称的（symmetric），反对称的（antisymmetric），以及传递的（transitive）。

$ {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} $
$ {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} $
$ {(2, 4), (4, 2)} $
$ {(1, 2), (2, 3), (3, 4)} $
$ {(1, 1), (2, 2), (3, 3), (4, 4)} $
$ {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)} $

解答与解释：

a) $ {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} $

反射性 (Reflexive)：反射性要求对于每个元素 $ x {1, 2, 3, 4} $，都有 $ (x, x) $ 在关系中。这里缺少 $ (1, 1) $ 和 $ (4, 4) $，所以不反射。
对称性 (Symmetric)：如果 $ (a, b) $ 存在，则 $ (b, a) $ 也应当存在。这里 $ (2, 3) $ 存在，但是 $ (3, 2) $ 也在，所以对称。
反对称性 (Antisymmetric)：如果 $ (a, b) $ 和 $ (b, a) $ 同时存在，且 $ a b $，则不反对称。这里有 $ (2, 3) $ 和 $ (3, 2) $，且 $ 2 $，所以不反对称。
传递性 (Transitive)：如果 $ (a, b) $ 和 $ (b, c) $ 存在，则 $ (a, c) $ 也应存在。检查后，发现没有违反传递性。所以是传递的。

结论：传递性。

b) $ {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} $

反射性 (Reflexive)：所有元素 $ {1, 2, 3, 4} $ 的对角元素 $ (x, x) $ 存在，所以是反射的。
对称性 (Symmetric)：每对存在的 $ (a, b) $ 都有对应的 $ (b, a) $，所以是对称的。
反对称性 (Antisymmetric)：对于 $ (1, 2) $ 和 $ (2, 1) $，虽然它们对称，但 $ 1 $，所以不反对称。
传递性 (Transitive)：如果 $ (a, b) $ 和 $ (b, c) $ 存在，则 $ (a, c) $ 也应该存在，这里没有违反传递性。

结论：反射的、对称的、传递的。

c) $ {(2, 4), (4, 2)} $

反射性 (Reflexive)：缺少 $ (1, 1) $, $ (3, 3) $, $ (4, 4) $，所以不反射。
对称性 (Symmetric)：有 $ (2, 4) $ 和 $ (4, 2) $，满足对称性。
反对称性 (Antisymmetric)：有 $ (2, 4) $ 和 $ (4, 2) $，且 $ 2 $，所以不反对称。
传递性 (Transitive)：没有违反传递性。

结论：对称的。

d) $ {(1, 2), (2, 3), (3, 4)} $

反射性 (Reflexive)：缺少 $ (1, 1) $, $ (2, 2) $, $ (3, 3) $, $ (4, 4) $，所以不反射。
对称性 (Symmetric)：有 $ (1, 2) $，但没有 $ (2, 1) $，所以不对称。
反对称性 (Antisymmetric)：没有 $ (a, b) $ 和 $ (b, a) $ 同时出现，所以是反对称的。
传递性 (Transitive)：有 $ (1, 2) $ 和 $ (2, 3) $，应该有 $ (1, 3) $，但没有，因此不是传递的。

结论：反对称的。

e) $ {(1, 1), (2, 2), (3, 3), (4, 4)} $

反射性 (Reflexive)：每个元素的对角元素都存在，因此是反射的。
对称性 (Symmetric)：每个元素的对角元素的对称关系也成立，因此是对称的。
反对称性 (Antisymmetric)：没有出现 $ (a, b) $ 和 $ (b, a) $ 同时存在且 $ a b $，因此是反对称的。
传递性 (Transitive)：没有违反传递性。

结论：反射的、对称的、反对称的、传递的。

f) $ {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)} $

反射性 (Reflexive)：缺少 $ (1, 1) $, $ (2, 2) $, $ (3, 3) $, $ (4, 4) $，所以不反射。
对称性 (Symmetric)：不对称。
反对称性 (Antisymmetric)：$ (1, 3) $ 和 $ (3, 1) $ 存在，且 $ 1 $，所以不反对称。
传递性 (Transitive)：检查后没有违反传递性，但有多个不同的关系，因此不满足。

结论：没有这些属性。

总结：

传递的
反射的、对称的、传递的
对称的
反对称的
反射的、对称的、反对称的、传递的
无这些属性

问题：

对于实数集合 $ $ 上的以下关系：

$ R_1 = {(a, b) ^2 | a > b} $ ，“大于”关系
$ R_2 = {(a, b) ^2 | a b} $ ，“大于或等于”关系
$ R_3 = {(a, b) ^2 | a < b} $ ，“小于”关系
$ R_4 = {(a, b) ^2 | a b} $ ，“小于或等于”关系
$ R_5 = {(a, b) ^2 | a = b} $ ，“等于”关系
$ R_6 = {(a, b) ^2 | a b} $ ，“不等于”关系

找到以下集合的结果：

$ R_2 R_4 $
$ R_3 R_6 $
$ R_3 R_6 $
$ R_4 R_6 $
$ R_3 - R_6 $
$ R_6 - R_3 $
$ R_2 R_6 $
$ R_3 R_5 $

解答与解释：

a) $ R_2 R_4 $

$ R_2 = {(a, b) | a b} $ 表示大于或等于，包含了大于和等于的情况。
$ R_4 = {(a, b) | a b} $ 表示小于或等于，包含了小于和等于的情况。
两者的并集 $ R_2 R_4 $ 包括所有 $ a b $ 或 $ a b $ 的情况，也就是包含了所有可能的 $ a $ 和 $ b $ 的比较（包括等于）。

结果：$ R_2 R_4 = R^2 $，因为 $ R^2 $ 已经包括了所有可能的情况。

b) $ R_3 R_6 $

$ R_3 = {(a, b) | a < b} $ 表示小于。
$ R_6 = {(a, b) | a b} $ 表示不等于。
$ R_3 R_6 $ 包含了所有 $ a < b $ 或 $ a b $ 的情况，也就是不包含 $ a = b $ 的情况。

结果：$ R_3 R_6 = R_6 $，因为 $ R_6 $ 包括了所有不等于的情况，也就包括了 $ R_3 $。

c) $ R_3 R_6 $

$ R_3 = {(a, b) | a < b} $
$ R_6 = {(a, b) | a b} $
$ R_3 R_6 $ 表示既是小于又是不等于的情况，这正好是 $ R_3 $，因为 $ a < b $ 就意味着 $ a b $。

结果：$ R_3 R_6 = R_3 $，因为小于关系本身就包含了不等于。

d) $ R_4 R_6 $

$ R_4 = {(a, b) | a b} $
$ R_6 = {(a, b) | a b} $
$ R_4 R_6 $ 表示小于或等于且不等于的情况，也就是 $ a < b $。

结果：$ R_4 R_6 = R_3 $，因为 $ a b $ 且 $ a b $ 时，必然是 $ a < b $。

e) $ R_3 - R_6 $

$ R_3 = {(a, b) | a < b} $
$ R_6 = {(a, b) | a b} $
$ R_3 - R_6 $ 是从 $ R_3 $ 中去掉所有不等于的情况。然而，$ R_3 $ 中的所有元素 $ a < b $ 本身就是不等于的，所以 $ R_3 - R_6 = $。

结果：$ R_3 - R_6 = $，因为 $ R_3 $ 和 $ R_6 $ 没有交集。

f) $ R_6 - R_3 $

$ R_6 = {(a, b) | a b} $
$ R_3 = {(a, b) | a < b} $
$ R_6 - R_3 $ 是从 $ R_6 $ 中去掉所有小于关系的元素，也就是留下 $ a > b $ 和 $ a = b $ 的元素。

结果：$ R_6 - R_3 = R_1 $，因为 $ R_1 = {(a, b) | a > b} $ 表示大于关系，且 $ a b $ 时 $ a > b $ 即为 $ R_1 $。

g) $ R_2 R_6 $

$ R_2 = {(a, b) | a b} $
$ R_6 = {(a, b) | a b} $
$ R_2 R_6 $ 表示 $ R_2 $ 和 $ R_6 $ 的对称差集，即既包含 $ a b $ 的情况，也包含 $ a b $ 的情况，但不包含两者交集的部分，即去掉 $ a = b $ 的情况。

结果：$ R_2 R_6 = R_4 $，因为 $ R_2 R_6 $ 包含的是 $ a b $ 且 $ a b $ 的情况，即 $ R_4 $。

h) $ R_3 R_5 $

$ R_3 = {(a, b) | a < b} $
$ R_5 = {(a, b) | a = b} $
$ R_3 R_5 $ 是 $ R_3 $ 和 $ R_5 $ 的对称差集，表示既包含小于关系也包含等于关系的元素，去掉交集（即去掉 $ a = b $ 且 $ a < b $ 的情况）。

结果：$ R_3 R_5 = R_4 $，因为 $ a b $ 且 $ a b $ 表示小于或等于关系。

总结：

$ R_2 R_4 = R^2 $
$ R_3 R_6 = R_6 $
$ R_3 R_6 = R_3 $
$ R_4 R_6 = R_3 $
$ R_3 - R_6 = $
$ R_6 - R_3 = R_1 $
$ R_2 R_6 = R_4 $
$ R_3 R_5 = R_4 $

问题：

给定关系 $ R $ 的矩阵表示为：

$ M_R = \[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]

我们要求找出以下矩阵：

$ R^{-1} $ 的矩阵表示
$ $（关系 $ R $ 的补集）的矩阵表示
$ R^2 $ 的矩阵表示

解答与解释：

a) $ R^{-1} $ 的矩阵表示

关系 $ R^{-1} $ 表示的是 $ R $ 的逆关系，也就是说，矩阵 $ M_{R^{-1}} $ 是 $ M_R $ 的转置矩阵。

$ M_R $ 是给定的矩阵：

$ M_R =
\[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]
$
转置矩阵 $ M_R^T $ 就是交换矩阵的行和列，即：

$ M_R^{-1} = M_R^T =
\[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]
$

由于 $ M_R $ 是对称矩阵，因此 $ R^{-1} = R $，即 $ M_{R^{-1}} = M_R $。

结果：$ R^{-1} = M_R = \[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]

b) $ $ 的矩阵表示

关系 $ $ 是关系 $ R $ 的补集。对于补集关系，矩阵中的每个元素取反（即 0 变成 1，1 变成 0）。

给定的矩阵 $ M_R $ 是：

$ M_R =
\[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]
$
取反得到补集矩阵 $ M_{} $：

$ M_{} =
\[\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}\]
$

结果：$ = \[\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}\]

c) $ R^2 $ 的矩阵表示

关系 $ R^2 $ 表示 $ R $ 与自身的复合关系，即矩阵 $ M_{R^2} = M_R M_R $。

给定的矩阵 $ M_R $ 是：

$ M_R =
\[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]
$
计算 $ M_R^2 = M_R M_R $：

$ M_R^2 =
\[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\]
$

通过矩阵乘法：
- 第一行：
  - $ (0 + 1 + 1 ) = 2 $
  - $ (0 + 1 + 1 ) = 1 $
  - $ (0 + 1 + 1 ) = 1 $
- 第二行：
  - $ (1 + 1 + 0 ) = 1 $
  - $ (1 + 1 + 0 ) = 2 $
  - $ (1 + 1 + 0 ) = 1 $
- 第三行：
  - $ (1 + 0 + 1 ) = 1 $
  - $ (1 + 0 + 1 ) = 1 $
  - $ (1 + 0 + 1 ) = 2 $
所以：

$ M_R^2 =
\[\begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}\]
$

结果：$ R^2 = \[\begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}\]

总结：

$ R^{-1} = \[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\] $
$ = \[\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}\] $
$ R^2 = \[\begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}\] $

注意这里是布尔积，因此都是1。

问题：

注意和矩阵乘法是有区别的。

给定关系 $ R_1 $ 和 $ R_2 $ 在集合 $ A $ 上的矩阵表示：

$ M_{R_1} = \[\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}\] , M_{R_2} = \[\begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}\]

求：