9.1關(guān)系及其性質(zhì)

1、二元關(guān)系

設(shè)A和B是集合，一個從 A 到 B 的二元關(guān)系是A×B的子集。 （序偶集合的子集）

??換句話說，一個從A到B的二元關(guān)系是集合R，其中每個有序?qū)Φ牡谝粋€元素取自A而第二個元素取自B。

我們使用記號 aRb表示(a, b)∈R，aR b表示(a, b)?R。當(a, b)屬于R時，稱a與b有關(guān)系R。

??例：設(shè) A = { 0, 1, 2 }， B = { a, b }

{ (0, a), (0, b), (1, a), (2, b) }是一個從 A 到 B 的關(guān)系。
我們可以用圖或表格來表示從集合 A 到集合 B 的關(guān)系：

2、集合A上的關(guān)系

集合A上的關(guān)系是從A到A的關(guān)系。

??換句話說，集合A上的關(guān)系是從A到A的關(guān)系

??例：設(shè) A = { a, b, c }
那么R = { (a, a), (a, b), (a, c) }是 A 上的關(guān)系

3、n元素集合 有多少個關(guān)系？

A上的關(guān)系和 A × A 的子集是一回事
?所以可以直接計數(shù) A × A 的子集。

因為當 A 是 n 元素集合時 A × A 有 n² 個元素，所以 A × A 的子集有 2^m (m = n²)

??例：設(shè) B = { b }
那么B上的二元關(guān)系共有2個：R1 = ?，R2 = { (b, b) }

??例：設(shè) C = { a, b, c }
那么C上的二元關(guān)系共有2⁹ = 512個

4、關(guān)系的性質(zhì)

1. 自反（Reflexivity）

若對每個元素a∈A有（a，a)∈R，那么定義在集合A上的關(guān)系R稱為自反的 記作aRa，a是A中任意一個元素

用符號表示：（集合A上的關(guān)系）R 是自反的，當且僅當 ?x（x∈A? (x, x)∈R ）

（這里的論域是A中所有元素的集合。）

??例：
以下關(guān)于整數(shù)的關(guān)系是自反的：
R1 = { (a, b) | a ≤ b }，
R3 = { (a, b) | a = b 或 a = – b }，
R4 = { (a, b) | a = b }。

以下關(guān)系不是自反的：
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 上的關(guān)系 R 為對稱的。

用符號表示：R 是對稱的，當且僅當 ?x?y （ (x, y)∈R ? (y, x)∈R ）

??例：
以下關(guān)于整數(shù)的關(guān)系是對稱的：
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 上的關(guān)系 R 為反對稱的。

用符號表示：R 是反對稱的，當且僅當 ?x?y（ (x, y)∈R ∧ (y, x)∈R ? x = y ）

??例：
以下關(guān)于整數(shù)的關(guān)系是反對稱的：
R1 = { (a, b) | a ≤ b }，
R2 = { (a, b) | a > b }，
R4 = { (a, b) | a = b }，
R5 = { (a, b) | a = b + 1 }。

以下關(guān)系不是反對稱的：
R3 = { (a, b) | a = b 或 a = – b }（反例： (1, – 1) 和 (–1, 1) 都屬于R3），
R6 = { (a, b) | a + b ≤ 3 }（反例： (1, 2) 和 (2, 1) 都屬于R6）。

??對稱與反對稱的概念不是對立的，因為一個關(guān)系可以同時有這兩種性質(zhì)或者兩種性質(zhì)都沒有。
一個關(guān)系如果包含了某些形如(a，b）的有序?qū)?，其中a≠b，則這個關(guān)系就不可能同時是對稱的和反對稱的。

4. 傳遞（Transitivity）

若對于任意 a, b, c∈A，(a, b)∈R 并且 (b, c)∈R 則 (a, c)∈R，那么定義在集合 A 上的關(guān)系 R 稱為傳遞的。

用符號表示：R 是傳遞的，當且僅當?x?y?z（ (x, y)∈R ∧ (y, z)∈R ? (x, z)∈R）

??例：
以下關(guān)于整數(shù)的關(guān)系是可傳遞的：
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、關(guān)系的組合

因為從A到B的關(guān)系是 A×B 的子集，所以可以按照兩個集合組合的任何方式來組合兩個從A到B的關(guān)系。

給定兩個關(guān)系R₁和R₂，我們可以使用基本的集合操作將它們組合起來，形成新的關(guān)系，如 R₁ ∪ R₂、R₁ ∩ R₂、R₁ ? R₂ 和 R₂ ? R₁

除了常見的并∪、交∩、差 - 、異或⊕，還有一種新的組合方式：

關(guān)系的合成

設(shè)R₁ 是集合 A 到集合 B 的關(guān)系，R₂ 是集合 B 到集合 C 的關(guān)系。
R₂ 和 R₁ 的合成是 A 到 C 的關(guān)系，其中如果 (x, y) 是 R₁ 的成員，(y, z) 是 R₂的成員，那么 (x, z) 則是 R₁ ° R₂ 的成員。

（R₁ ° R₂ 表示R₁ 和 R₂ 的合成）

關(guān)系的冪

由兩個關(guān)系合成的定義可以遞歸定義關(guān)系R的冪

設(shè)R為A上的二元關(guān)系，則關(guān)系R的n次冪R_n可歸納定義為：
基礎(chǔ)步驟：R¹ = R
歸納步驟：Rⁿ⁺¹ = Rⁿ ° R

傳遞關(guān)系的冪是該關(guān)系的子集
文章來源地址http://www.zghlxwxcb.cn/news/detail-478564.html

到了這里，關(guān)于離散數(shù)學(xué)_九章：關(guān)系（1）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！