Discrete Structure 2

Discrete Structure
Relation
ALLPPT.com _ Free PowerPointTemplates, Diagrams and Charts

Relations
• Cartesian Product, Relations, Equivalence

Relations, and Logical Properties of
Relations.
Representation
 Statement (or Descriptive) Form
 Set of apple, orange, pear, and banana  Roster (or List) Form
 N: Set of all natural numbers
 Z: Set of all integers
 Q: Set of all rational numbers
 R: Set of all real numbers
 Z+: Set of all positive integers
 Set-builder notation
Construction
• Cartesian Product
• Purpose of Cartesian Product
– All possible ways to take things from multiple sets
• Example: I have an apple, and orange, and a pear. The TA has a pencil, a pen,
an eraser, and a book. You take one thing from each of us.”
• You are selecting one element from each set. What are the possible selections
you can make? How many possibilities are there?
• Symbolic Notation:
• Definition:
– Example: A standard deck of playing cards is basically the Cartesian Product
Important Property
(commutative property does not hold)
Cardinality
Other representations
Matrices
Graphs
Vertices, Edges
Adjacency Matrix
Relations
Let A and B be sets. A binary relation from A to B is a subset of A × B.
We use the notation aRb to denote that (a, b) ∈ R and a R b to denote that (a,
b) /∈ R. Moreover, when (a, b) belongs to R, a is said to be related to b by R.
Relationships between elements of sets occur in many contexts.
The most direct way to express a relationship be-

tween elements of two sets is to use ordered pairs n-ary relations, which ex-
made up of two related elements. For this reason, press relationships among
sets of ordered pairs are called binary relations. elements of more than two
sets
A binary relation from A to B is a set R of ordered
pairs where the first element of each ordered pair
comes from A and the second element comes from
B.
Relationships between elements of sets are represented using the
structure called a relation, which is just a subset of the Cartesian
product of the sets. Relations can be used to solve problems such as
determining which pairs of cities are linked by airline flights in a net-
work, finding a viable order for the different phases of a complicated
project, or producing a useful way to store information in computer
Relations
 A binary relation from set to is a subset of
 and then
 All possible relations =
 We would say that has this relation, of that is related to by .

 Or, “” indicates that two elements and are related, or “” indicates that two elements and are not
related.
 Relational operators:
 “divides” is a relation on the integers such as
 Mathematical and Programming Functions as a particular kind of relation.
Relations on a Set
A relation on a set A is a relation from A to A.
et A be the set {1, 2, 3, 4}. Which ordered pairs are in the rela-
tion R = {(a, b) | a divides b}? Solution: Because (a, b) is in R if
and only if a and b are positive integers not exceeding 4 such
that a divides b, we see that R = {(1, 1), (1, 2), (1, 3), (1, 4), (2,
2), (2, 4), (3, 3), (4, 4)}.
Properties of relation
There are several properties that are used to classify relations on a set. We will introduce the most impor-
tant of these here. In some relations an element is always related to itself. For instance, let R be the rela-
tion on the set of all people consisting of pairs (x, y) where x and y have the same mother and the same
father. Then xRx for every person x.
Consider the following relations on {1, 2, 3, 4}:
A relation R on a set A is called reflexive if

(a, a) ∈ R for every element a ∈ A.
(1, 1), (2, 2), (3, 3), and (4, 4) must contain
all of the pairs
A relation R on a set A is called symmetric if(b, a) ∈ R
whenever(a, b) ∈ R, for all a, b ∈ A. A relation R on a set A
such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a
= b is called antisymmetric.
Symmetric contains (2, 1) and (1, 2)
Anit Symmetirc For each of these relations there is no pair of
elements a and b with a = b such that both (a, b) and (b, a)
belong to the relation.
A relation R on a set A is called transitive if whenever (a, b)
∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A.
Transitive (3, 2) and (2, 1), (4, 2) and (2, 1), (4, 3) and (3, 1),
and (4, 3) and (3, 2) are the only such sets of pairs, and (3,
1), (4, 1), and (4, 2) belong to R4.
Relations Properties
Relations Properties
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.
Let A = {1, 2, 3} and B = {1, 2, 3, 4}.

The relations R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}
can be combined to obtain
• R1 ∪ R2 = {(1, 1), (1, 2), (1, 3), (1, 4),
• (2, 2), (3, 3)}
• R1 ∩ R2 = {(1, 1)},
• R1 − R2 = {(2, 2), (3, 3)}, • Symmetric difference
• R2 − R1 = {(1, 2), (1, 3), (1, 4)}. • R1 ⊕ R2 =) (R1 ∪ R2).-(R1 ∩ R2.)
Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is
the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which there exists an element b
∈ B such that (a, b) ∈ R and (b, c) ∈ S. We denote the composite of R and S by S ◦R.
Powers of a relation R
• Let R be a relation on the set A.

• The powers Rn, n = 1, 2, 3,..., are defined recursively by
R1 = R and Rn+1 = Rn ◦ R.
2 3 2
The definition shows that R = R ◦ R, R = R ◦ R = (R ◦ R)◦ R, and so on
Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers Rn, n = 2, 3, 4,
◦R, we find that R2 = {(1, 1), (2, 1), (3, 1), (4, 2)}. Furthermore, because R3 = R2 ◦R,
R3 = {(1, 1), (2, 1), (3, 1), (4, 1)}. Additional computation shows that R4 is the same
as R3, so R4 = {(1, 1), (2, 1), (3, 1), (4, 1)}. It also follows that Rn = R3 for n = 5, 6,
7,.......
The relation R on a set A is transitive if
and only if Rn ⊆ R for n = 1, 2, 3,....
n-ary Relation
Let A1, A2,...,An be sets. An n-ary relation on these sets is a subset of
A1 × A2 ×···× An. The sets A1, A2,...,An are called the domains of the
relation, and n is called its degree.
• Relationships among elements from more than two sets are called n-ary relation
Let R be the relation on N × N × N consisting of triples

(a, b, c), where a, b, and c are integers with a<b
Directed Graphs (diagraphs)
Directed Graphs (diagraphs)
Relations as Matrices
Relation as Matrix
Relation as Matrix
Relation as Matrix n-array
Equivalence Relation
 Definition 1: A relation on set is an equivalence relation if it is
reflexive, symmetric, and transitive.
 Example: Suppose
 Equivalence relations can be:
Equivalence Relation
Application
They are also an important data structure

in computer science.
Sequence can be used to represent solutions

to certain counting problems

Discrete Structure 2

Uploaded by

Copyright:

Available Formats

Discrete Structure 2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Structure 2

Uploaded by

Copyright:

Available Formats

Discrete Structure

ALLPPT.com _ Free PowerPointTemplates, Diagrams and Charts

• Cartesian Product, Relations, Equivalence

The most direct way to express a relationship be-

 We would say that has this relation, of that is related to by .

 “divides” is a relation on the integers such as

 Mathematical and Programming Functions as a particular kind of relation.

A relation R on a set A is called reflexive if

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

• Let R be a relation on the set A.

Let R be the relation on N × N × N consisting of triples

They are also an important data structure

Sequence can be used to represent solutions

You might also like