1 of 17

Discrete �Mathematics

Chapter 7

Relations (關係)

大葉大學 資訊工程系 黃鈴玲

2 of 17

7.1 Relations and their properties.

※表示兩集合間元素的關係，最直覺的方式就是使用�序對(ordered pair) (有順序的配對)。

由序對構成的集合稱為二元關係(binary relation)。

Ch8-2

Example 1.

A : the set of students in your school.

B : the set of courses.

R = { (a, b) : a∈A, b∈B, 學生a 選修了課程 b }

Def 1

Let A and B be sets. A binary relation from A to B �is a subset R of A×B = { (a, b) : a∈A, b∈B }.

3 of 17

Ch8-3

0

1

2

a

b

A

B

R

R ⊆ A×B = { (0,a) , (0,b) , (1,a)

(1,b) , (2,a) , (2,b)}

∈R

∈R

Example 3. Let A={0, 1, 2} and B={a, b}, then �R = {(0,a),(0,b),(1,a),(2,b)} is a relation from A to B.

用圖形來表示關係：

4 of 17

Example: A : 男生, B : 女生, R : 夫妻關系� A : 城市, B : 州或省 R : 屬於 (Example 2)

Note. Relations vs. Functions

A relation can be used to express a 1-to-many

relationship between the elements of the sets

A and B.

(Function 不可一對多，只可多對一)

Ch8-4

Def 2. A relation on the set A is a subset of A × A

(i.e., a relation from A to A).

5 of 17

Example 4. � Let A be the set {1, 2, 3, 4}. 則� R = { (a, b)| a divides b }裡面包含哪些序對?

Sol :

Ch8-5

1

2

3

4

1

2

3

4

R = { (1,1), (1,2), (1,3), (1,4),

(2,2), (2,4),

(3,3),

(4,4) }

6 of 17

Example 5. 考慮下列定義在Z上的關係.

R1 = { (a, b) | a ≤ b }

R2 = { (a, b) | a > b }

R3 = { (a, b) | a = b or a = −b }

R4 = { (a, b) | a = b }

R5 = { (a, b) | a = b+1 }

R6 = { (a, b) | a + b ≤ 3 }

Ch8-6

哪些關係包含了序對�(1,1), (1,2), (2,1), (1,−1),

及 (2,2)?

Sol :

∈

(1,1)

(1,2)

(2,1)

(1,−1)

(2,2)

R1

​

​

​

​

​

R2

​

​

​

​

​

R3

​

​

​

​

​

R4

​

​

​

​

​

R5

​

​

​

​

​

R6

​

​

​

​

​

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

7 of 17

Exercise 7.1

2. 列出在集合{1, 2, 3, 4, 5, 6}上� 關係 R={(a,b) | a整除b} 中所有的有序數對。

Ch8-7

1. 列出由A={0,1, 2, 3, 4}到 B={0, 1, 2, 3}關係中所有� 的有序數對，其中關係 R 定義如下：� (a) a = b� (b) a + b = 4� (e) gcd(a, b)=1

8 of 17

Def 3. A relation R on a set A is called reflexive (反身性)� if (a,a)∈R for every a∈A.

Example 7. 考慮下列定義在 {1, 2, 3, 4} 上的關係:

R2 = { (1,1), (1,2), (2,1) }

R3 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R4 = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

哪些關係具備反身性(reflexive)？

Ch8-8

Sol :

(1, 1), (2, 2), (3, 3), (4, 4)都必須屬於R

※ 關係的性質：

⇒ R3

9 of 17

Example 8. 下列定義在Z上的關係，哪些具備反身性(reflexive)？

R1 = { (a, b) | a ≤ b }

R2 = { (a, b) | a > b }

R3 = { (a, b) | a = b or a = −b }

R4 = { (a, b) | a = b }

R5 = { (a, b) | a = b+1 }

R6 = { (a, b) | a + b ≤ 3 }

Sol :

所有Z中的元素a，(a,a)都要屬於R，R才有反身性

(0,0)∉R2,

⇒ R1, R3 and R4

Ch8-9

(0,0)∉R5,

(2,2)∉R6

10 of 17

Def 4.

(1) A relation R on a set A is called symmetric (對稱) if for a, b∈A,� (a, b)∈R ⇒ (b, a)∈R.

(2) A relation R on a set A is called � antisymmetric (反對稱) if for a, b∈A,

(a, b)∈R and (b, a)∈R ⇒ a = b.

Ch8-10

即若 a≠b且(a,b)∈R ⇒ (b, a)∉R

11 of 17

Ch8-11

Example 10. 下列關係，哪些有對稱性(symmetric)或反對稱性(antisymmetric)?

R2 = { (1,1), (1,2), (2,1) }

R3 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R4 = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

​

Sol :

對稱：若有序對(a,b)，就要有序對(b,a)� 反對稱：若有序對(a,b)且a≠b，就不能有(b,a)

R2, R3 are symmetric

R4 are antisymmetric.

12 of 17

Def 5. A relation R on a set A is called � transitive(遞移) if for a, b, c ∈A, � (a, b)∈R and (b, c)∈R ⇒ (a, c)∈R.

Ch8-12

13 of 17

Ch8-13

Example 13. 下列關係有哪些具備遞移性(transitive)?

R2 = { (1,1), (1,2), (2,1) }

R3 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R4 = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

​

Sol : 檢查：若(a, b)∈R 且(b, c)∈R ，則 (a, c)也必須∈R

R2 沒有遞移性，因 � (2,1) ∈ R2 and (1,2) ∈ R2 but (2,2) ∉ R2.

R3 沒有遞移性，因 � (2,1) ∈ R3 and (1,4) ∈ R3 but (2,4) ∉ R3.

R4 is transitive.

​

14 of 17

Exercise 7.1

4.對下列定義於所有人形成集合上的關係，判斷� 是否具有反身性、對稱性、反對稱性和遞移性。� 當 (a,b)∈R 若且唯若� (a) a 比 b 高� (b) a 與 b 生於同一天� (c) a 與 b 的名字相同� (d) a 與 b 有相同的祖父母�

Ch8-14

15 of 17

Exercise 7.1

7. 對下列定義於所有整數集合上的關係，判斷是否� 具有反身性、對稱性、反對稱性和遞移性。� (a) R={(x, y) | x ≠ y, where x, y∈Z }� (b) R={(x, y) | xy ≥ 1, where x, y∈Z }� (c) R={(x, y) | x = y + 1 or x = y − 1, where x, y∈Z }� (d) R={(x, y) | x ≡ y (mod 7) , where x, y∈Z }

Ch8-15

16 of 17

Example 17. Let A = {1, 2, 3} and B = {1, 2, 3, 4}.

The relation R1 = {(1,1), (2,2), (3,3)}

and R2 = {(1,1), (1,2), (1,3), (1,4)} can be

combined to obtain

R1 ∪ R2

R1 ∩ R2 = {(1,1)}

R1 － R2 = {(2,2), (3,3)}

R2 － R1 = {(1,2), (1,3), (1,4)}

R1 ⊕ R2 = {(2,2), (3,3), (1,2), (1,3), (1,4)}

Ch8-16

對稱差(symmetric difference), 即 (A ∪ B) – (A ∩ B)

17 of 17

  • 補充 :

antisymmetric 跟 symmetric可並存

Ch8-17

只要R中沒有(a, b)且a≠b即可

例：令A = {1,2,3}, 給出一個定義在A上的關係R，R需同時具備對稱性、反對稱性，但不具備反身性。

Sol :

R = {(1,1), (2,2)}