Relation
Definition
Let A and B be sets. A binary relation (quan h» hai ngôi) from a
set A to a set B is a set
R ⊆ A × BRelations
Tran Vinh Tan
Relation
Definition
Let A and B be sets. A binary relation (quan h» hai ngôi) from a
set A to a set B is a set
R ⊆ A × B

117 trang |

Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 123 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu **Bài giảng Discrete Mathematics I - Chapter 5: Relations**, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.1
Chapter 5
Relations
Discrete Mathematics I on 22 March 2012
Tran Vinh Tan
Faculty of Computer Science and Engineering
University of Technology - VNUHCM
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.2
Contents
1 Properties of Relations
2 Combining Relations
3 Representing Relations
4 Closures of Relations
5 Types of Relations
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.3
Introduction
Function?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.3
Introduction
Function?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.4
Relation
Definition
Let A and B be sets. A binary relation (quan hệ hai ngôi) from a
set A to a set B is a set
R ⊆ A×B
• Notations:
(a, b) ∈ R←→ aRb
• n-ary relations?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.4
Relation
Definition
Let A and B be sets. A binary relation (quan hệ hai ngôi) from a
set A to a set B is a set
R ⊆ A×B
• Notations:
(a, b) ∈ R←→ aRb
• n-ary relations?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.4
Relation
Definition
Let A and B be sets. A binary relation (quan hệ hai ngôi) from a
set A to a set B is a set
R ⊆ A×B
• Notations:
(a, b) ∈ R←→ aRb
• n-ary relations?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.4
Relation
Definition
Let A and B be sets. A binary relation (quan hệ hai ngôi) from a
set A to a set B is a set
R ⊆ A×B
• Notations:
(a, b) ∈ R←→ aRb
• n-ary relations?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.5
Example
Example
Let A = {a, b, c} be the set of students, B = {l, c, s, d} be the set
of the available optional courses. We can have relation R that
consists of pairs (a, b), where a is a student enrolled in course b.
R = {(a, l), (a, s), (a, g), (b, c),
(b, s), (b, g), (c, l), (c, g)}
R l c s g
a x x x
b x x x
c x x
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.5
Example
Example
Let A = {a, b, c} be the set of students, B = {l, c, s, d} be the set
of the available optional courses. We can have relation R that
consists of pairs (a, b), where a is a student enrolled in course b.
R = {(a, l), (a, s), (a, g), (b, c),
(b, s), (b, g), (c, l), (c, g)}
R l c s g
a x x x
b x x x
c x x
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.5
Example
Example
Let A = {a, b, c} be the set of students, B = {l, c, s, d} be the set
of the available optional courses. We can have relation R that
consists of pairs (a, b), where a is a student enrolled in course b.
R = {(a, l), (a, s), (a, g), (b, c),
(b, s), (b, g), (c, l), (c, g)}
R l c s g
a x x x
b x x x
c x x
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.6
Functions as Relations
• Is a function a relation?
• Yes!
• f : A→ B
R = {(a, b) | b = f(a)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.6
Functions as Relations
• Is a function a relation?
• Yes!
• f : A→ B
R = {(a, b) | b = f(a)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.6
Functions as Relations
• Is a function a relation?
• Yes!
• f : A→ B
R = {(a, b) | b = f(a)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.6
Functions as Relations
• Is a function a relation?
• Yes!
• f : A→ B
R = {(a, b) | b = f(a)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.7
Functions as Relations
• Is a relation a function?
• No
• Relations are a generalization of functions
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.7
Functions as Relations
• Is a relation a function?
• No
• Relations are a generalization of functions
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.7
Functions as Relations
• Is a relation a function?
• No
• Relations are a generalization of functions
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.7
Functions as Relations
• Is a relation a function?
• No
• Relations are a generalization of functions
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.8
Relations on a Set
Definition
A relation on the set A is a relation from A to A.
Example
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the
relation R = {(a, b) | a divides b} (a là ước số của b)?
Solution:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
R 1 2 3 4
1 x x x x
2 x x
3 x
4 x
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.8
Relations on a Set
Definition
A relation on the set A is a relation from A to A.
Example
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the
relation R = {(a, b) | a divides b} (a là ước số của b)?
Solution:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
R 1 2 3 4
1 x x x x
2 x x
3 x
4 x
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.8
Relations on a Set
Definition
A relation on the set A is a relation from A to A.
Example
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the
relation R = {(a, b) | a divides b} (a là ước số của b)?
Solution:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
R 1 2 3 4
1 x x x x
2 x x
3 x
4 x
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.9
Properties of Relations
Reflexive xRx,∀x ∈ A
(phản xạ)
Symmetric xRy → yRx,∀x, y ∈ A
(đối xứng)
Antisymmetric (xRy ∧ yRx)→ x = y,∀x, y ∈ A
(phản đối xứng)
Transitive (xRy ∧ yRz)→ xRz,∀x, y, z ∈ A
(bắc cầu)
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.9
Properties of Relations
Reflexive xRx,∀x ∈ A
(phản xạ)
Symmetric xRy → yRx,∀x, y ∈ A
(đối xứng)
Antisymmetric (xRy ∧ yRx)→ x = y,∀x, y ∈ A
(phản đối xứng)
Transitive (xRy ∧ yRz)→ xRz,∀x, y, z ∈ A
(bắc cầu)
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.9
Properties of Relations
Reflexive xRx,∀x ∈ A
(phản xạ)
Symmetric xRy → yRx,∀x, y ∈ A
(đối xứng)
Antisymmetric (xRy ∧ yRx)→ x = y,∀x, y ∈ A
(phản đối xứng)
Transitive (xRy ∧ yRz)→ xRz,∀x, y, z ∈ A
(bắc cầu)
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.9
Properties of Relations
Reflexive xRx,∀x ∈ A
(phản xạ)
Symmetric xRy → yRx,∀x, y ∈ A
(đối xứng)
Antisymmetric (xRy ∧ yRx)→ x = y,∀x, y ∈ A
(phản đối xứng)
Transitive (xRy ∧ yRz)→ xRz,∀x, y, z ∈ A
(bắc cầu)
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.9
Properties of Relations
Reflexive xRx,∀x ∈ A
(phản xạ)
Symmetric xRy → yRx,∀x, y ∈ A
(đối xứng)
Antisymmetric (xRy ∧ yRx)→ x = y,∀x, y ∈ A
(phản đối xứng)
Transitive (xRy ∧ yRz)→ xRz,∀x, y, z ∈ A
(bắc cầu)
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.10
Example
Example
Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 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)},
R5 = {(3, 4)}
Solution:
• Reflexive: R3
• Symmetric: R2, R3
• Antisymmetric: R4, R5
• Transitive: R4, R5
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.10
Example
Example
Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 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)},
R5 = {(3, 4)}
Solution:
• Reflexive: R3
• Symmetric: R2, R3
• Antisymmetric: R4, R5
• Transitive: R4, R5
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.10
Example
Example
Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 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)},
R5 = {(3, 4)}
Solution:
• Reflexive: R3
• Symmetric: R2, R3
• Antisymmetric: R4, R5
• Transitive: R4, R5
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.10
Example
Example
Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 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)},
R5 = {(3, 4)}
Solution:
• Reflexive: R3
• Symmetric: R2, R3
• Antisymmetric: R4, R5
• Transitive: R4, R5
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.10
Example
Example
Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 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)},
R5 = {(3, 4)}
Solution:
• Reflexive: R3
• Symmetric: R2, R3
• Antisymmetric: R4, R5
• Transitive: R4, R5
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.11
Example
Example
What is the properties of the divides (ước số ) relation on the set
of positive integers?
Solution:
• ∀a ∈ Z+, a | a: reflexive
• 1 | 2, but 2 - 1: not symmetric
• ∃a, b ∈ Z+, (a | b) ∧ (b | a)→ a = b: antisymmetric
• a | b⇒ ∃k ∈ Z+, b = ak; b | c⇒ ∃l ∈ Z+, c = bl. Hence,
c = a(kl)⇒ a | c: transitive
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.11
Example
Example
What is the properties of the divides (ước số ) relation on the set
of positive integers?
Solution:
• ∀a ∈ Z+, a | a: reflexive
• 1 | 2, but 2 - 1: not symmetric
• ∃a, b ∈ Z+, (a | b) ∧ (b | a)→ a = b: antisymmetric
• a | b⇒ ∃k ∈ Z+, b = ak; b | c⇒ ∃l ∈ Z+, c = bl. Hence,
c = a(kl)⇒ a | c: transitive
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.12
Example
Example
What are the properties of these relations on the set of integers:
R1 = {(a, b) | a ≤ b}
R2 = {(a, b) | a > b}
R3 = {(a, b) | a = b or a = −b}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.13
Combining Relations
Because relations from A to B are subsets of A×B, two
relations from A to B can be combined in any way two sets can
be combined.
Example
Let A = {1, 2, 3} and B = {1, 2, 3, 4}. List the combinations of
relations R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}.
Solution: R1 ∪R2, R1 ∩R2, R1 −R2 and R2 −R1.
Example
Let A and B be the set of all students and the set of all courses at
school, respectively. Suppose R1 = {(a, b) | a has taken the course
b} and R2 = {(a, b) | a requires course b to graduate}. What are
the relations R1 ∪R2, R1 ∩R2, R1 ⊕R2, R1 −R2, R2 −R1?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.13
Combining Relations
Because relations from A to B are subsets of A×B, two
relations from A to B can be combined in any way two sets can
be combined.
Example
Let A = {1, 2, 3} and B = {1, 2, 3, 4}. List the combinations of
relations R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}.
Solution: R1 ∪R2, R1 ∩R2, R1 −R2 and R2 −R1.
Example
Let A and B be the set of all students and the set of all courses at
school, respectively. Suppose R1 = {(a, b) | a has taken the course
b} and R2 = {(a, b) | a requires course b to graduate}. What are
the relations R1 ∪R2, R1 ∩R2, R1 ⊕R2, R1 −R2, R2 −R1?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.13
Combining Relations
Because relations from A to B are subsets of A×B, two
relations from A to B can be combined in any way two sets can
be combined.
Example
Let A = {1, 2, 3} and B = {1, 2, 3, 4}. List the combinations of
relations R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}.
Solution: R1 ∪R2, R1 ∩R2, R1 −R2 and R2 −R1.
Example
Let A and B be the set of all students and the set of all courses at
school, respectively. Suppose R1 = {(a, b) | a has taken the course
b} and R2 = {(a, b) | a requires course b to graduate}. What are
the relations R1 ∪R2, R1 ∩R2, R1 ⊕R2, R1 −R2, R2 −R1?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.13
Combining Relations
Because relations from A to B are subsets of A×B, two
relations from A to B can be combined in any way two sets can
be combined.
Example
Let A = {1, 2, 3} and B = {1, 2, 3, 4}. List the combinations of
relations R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}.
Solution: R1 ∪R2, R1 ∩R2, R1 −R2 and R2 −R1.
Example
Let A and B be the set of all students and the set of all courses at
school, respectively. Suppose R1 = {(a, b) | a has taken the course
b} and R2 = {(a, b) | a requires course b to graduate}. What are
the relations R1 ∪R2, R1 ∩R2, R1 ⊕R2, R1 −R2, R2 −R1?
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.14
Composition of Relations
Definition
Let R be relations from A to B and S be from B to C. Then the
composite (hợp thành) of S and R is
S ◦R = {(a, c) ∈ A× C | ∃b ∈ B (aRb ∧ bSc)}
Example
R = {(0, 0), (0, 3), (1, 2), (0, 1)}
S = {(0, 0), (1, 0), (2, 1), (3, 1)}
S ◦R = {(0, 0), (0, 1), (1, 1)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.14
Composition of Relations
Definition
Let R be relations from A to B and S be from B to C. Then the
composite (hợp thành) of S and R is
S ◦R = {(a, c) ∈ A× C | ∃b ∈ B (aRb ∧ bSc)}
Example
R = {(0, 0), (0, 3), (1, 2), (0, 1)}
S = {(0, 0), (1, 0), (2, 1), (3, 1)}
S ◦R = {(0, 0), (0, 1), (1, 1)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.14
Composition of Relations
Definition
Let R be relations from A to B and S be from B to C. Then the
composite (hợp thành) of S and R is
S ◦R = {(a, c) ∈ A× C | ∃b ∈ B (aRb ∧ bSc)}
Example
R = {(0, 0), (0, 3), (1, 2), (0, 1)}
S = {(0, 0), (1, 0), (2, 1), (3, 1)}
S ◦R = {(0, 0), (0, 1), (1, 1)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.14
Composition of Relations
Definition
Let R be relations from A to B and S be from B to C. Then the
composite (hợp thành) of S and R is
S ◦R = {(a, c) ∈ A× C | ∃b ∈ B (aRb ∧ bSc)}
Example
R = {(0, 0), (0, 3), (1, 2), (0, 1)}
S = {(0, 0), (1, 0), (2, 1), (3, 1)}
S ◦R =
{(0, 0), (0, 1), (1, 1)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.14
Composition of Relations
Definition
Let R be relations from A to B and S be from B to C. Then the
composite (hợp thành) of S and R is
S ◦R = {(a, c) ∈ A× C | ∃b ∈ B (aRb ∧ bSc)}
Example
R = {(0, 0), (0, 3), (1, 2), (0, 1)}
S = {(0, 0), (1, 0), (2, 1), (3, 1)}
S ◦R = {(0, 0), (0, 1), (1, 1)}
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.15
Power of Relations
Definition
Let R be a relation on the set A. The powers (lũy thừa)
Rn, n = 1, 2, 3, . . . are defined recursively by
R1 = R and Rn+1 = Rn ◦R.
Example
Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers
Rn, n = 2, 3, 4, . . ..
Solution:
R2 = {(1, 1), (2, 1), (3, 1), (4, 2)}
R3 = {(1, 1), (2, 1), (3, 1), (4, 1)}
R4 = {(1, 1), (2, 1), (3, 1), (4, 1)}
· · ·
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.15
Power of Relations
Definition
Let R be a relation on the set A. The powers (lũy thừa)
Rn, n = 1, 2, 3, . . . are defined recursively by
R1 = R and Rn+1 = Rn ◦R.
Example
Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers
Rn, n = 2, 3, 4, . . ..
Solution:
R2 = {(1, 1), (2, 1), (3, 1), (4, 2)}
R3 = {(1, 1), (2, 1), (3, 1), (4, 1)}
R4 = {(1, 1), (2, 1), (3, 1), (4, 1)}
· · ·
Relations
Tran Vinh Tan
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations
5.15
Power of Relations
Definition
Let R be a relation on the set A. The powers (lũy thừa)
Rn, n = 1, 2, 3, . . . are defined recursively by
R1 = R and Rn+1 = Rn ◦R.