Relations

Chapter 5

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Relations
Discrete Structures for Computing on 22 March 2012
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

Huynh Tuong Nguyen, Tran Huong Lan, Tran Vinh Tan
Faculty of Computer Science and Engineering
University of Technology - VNUHCM
5.1


Contents

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan


Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

5.3


Relations

Introduction

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

Function?
5.3


Relations


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

Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations

• Notations:

Types of Relations

5.4


Relations

Relation

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Definition

Let A and B be sets. A binary relation (quan hệ hai ngôi) from a


Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations

• Notations:
(a, b) ∈ R ←→ aRb

•

Types of Relations

n-ary relations?

5.4


Example

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Example

Let A = {a, b, c} be the set of students, B = {l, c, s, g} be the set

R

=

{(a, l), (a, s), (a, g), (b, c),
(b, s), (b, g), (c, l), (c, g)}

Closures of Relations
Types of Relations

5.5


Relations

Example

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Example

Let A = {a, b, c} be the set of students, B = {l, c, s, g} 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.
Contents
Properties of Relations
Combining Relations
Representing Relations

x
x

5.5


Functions as Relations

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

• Is a function a relation?

Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

5.6


Functions as Relations

Relations


Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

5.6


Functions as Relations

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

• Is a function a relation?
• Yes!
• f : A→B

Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations

R = {(a, b) | b = f (a)}

Types of Relations

Vinh Tan

• Is a relation a function?
• No
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

5.7


Functions as Relations

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

• Is a relation a function?
• No
Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Definition

A relation on the set A is a relation from A to A.

Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

5.8


Relations on a Set

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Definition

A relation on the set A is a relation from A to A.
Example

Contents
Properties of Relations
Combining Relations
Representing Relations

Solution:

Closures of Relations

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

1
x

2
x
x

3
x

Types of Relations

4
x

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Contents
Properties of Relations
Combining Relations
Representing Relations
Closures of Relations
Types of Relations

5.9


Relations can have special properties

Relations

Huynh Tuong Nguyen,
Tran Huong Lan, Tran
Vinh Tan

Reflexive
(phản xạ)

xRx, ∀x ∈ A
Contents
Properties of Relations
Combining Relations
Representing Relations