CSC 413

Discrete Mathematics II
Course Instructors:
Dr. Victor T. Odumuyiwa
Dr. Ufuoma C. Ogude

Department of Computer Sciences

University of Lagos

•Lectures:
– E 304, Wednesday 10:00 am to 11:00 am
– Lab 203, Thursday 10:00 am to 12:00 am
 Course Outline
We study topics in such areas as:
Sets and logic

proof techniques

relations and functions,

counting and combinatorics,

discrete probability,

graphs and trees and

NP-Completeness.
Course Material
Textbook

Discrete Mathematics
and Its Applications
by Kenneth H. Rosen

Use lecture notes as study guide.

 Presentation Outlines
Relation and Functions:

 Definition, representation, relation on a set

Properties:

 Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric

Combining relations:

 , , \, composite of relations

Representing relations:

 0-1 matrices, directed graphs

n-ary Relations & their Applications

 Properties of relations: Reflexive
We will now look at some useful ways to classify relations.

Definition:
A relation R on a set A is called reflexive if (a, a)R for
every element aA.
Are the following relations on {1, 2, 3, 4} reflexive?
R = {(1, 1), (1, 2), (2, 3), (3, 3), (4, 4)} No.

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

R = {(1, 1), (2, 2), (3, 3)} No.

Definition:
A relation on a set A is called irreflexive if (a, a)R for
every element aA.
Example (A):
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), (3,4), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4),
(4,4)}
R6 = {(3,4)}

Which of these relations are reflexive?

Solution:
R3 and R5: reflexive  both contain all pairs of the form (a,
a): (1,1), (2,2), (3,3) & (4,4).

R1, R2, R4 and R6: not reflexive  not contain all of these
ordered pairs.

(3,3) is not in any of these relations.

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), (3,4), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
 Properties of relations: symmetric,
antisymmetric and asymmetric
Definition:
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 is called antisymmetric if a = b
whenever (a, b)  R and (b, a)  R.

A relation R on a set A is called asymmetric if (a, b)  R

implies that (b, a)R for all a, b  R .

Example:
Which of the relations from Example (A) are symmetric
and which are antisymmetric?
Solution:
R2 & R3: symmetric  each case (b, a) belongs to the
relation whenever (a, b) does.

For R2: only thing to check that both (1,2) & (2,1) belong
to the relation

For R3: it is necessary to check that both (1,2) & (2,1)

belong to the relation.

None of the other relations is symmetric: find a pair (a, b)

so that it is in the relation but (b, a) is not.
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 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
Solution (cont.):
R4, R5 and R6: antisymmetric 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.

None of the other relations is antisymmetric: find a pair

(a, b) with a  b so that (a, b) and (b, a) are both in the
relation.
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), (3,4), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
 Properties of relations: symmetric,
antisymmetric and asymmetric
Are the following relations on {1, 2, 3, 4} symmetric,
antisymmetric, or asymmetric?

R = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)} symmetric
R = {(1, 1)} sym. and antisym.
R = {(1, 3), (3, 2), (2, 1)} antisym. and asym.

R = {(4, 4), (3, 3), (1, 4)} antisym.

 Properties of relations: Transitive
Definition:
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  R.

Example:
Are the following relations on {1, 2, 3, 4} transitive?

Solution:

R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)} Yes.

R = {(1, 3), (3, 2), (2, 1)} No.

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

Example:
Which of the relations in example (a) are transitive?
R4 , R5 & R6 : transitive  verify that if (a, b) and (b, c) belong
to this relation then (a, c) belongs also to the relation
R4 transitive since (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.

Same reasoning for R5 and R6.

R1 : not transitive  (3,4) and (4,1) belong to R1, but (3,1) does not.
R2 : not transitive  (2,1) and (1,2) belong to R2, but (2,2) does not.
R3 : not transitive  (4,1) and (1,2) belong to R3, but (4,2) does not.
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), (3,4), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
 Combining Relations
Relations are sets, and therefore, we can apply the
usual set operations to them.

If we have two relations R1 and R2, and both of them

are from a set A to a set B, then we can combine
them to R1  R2, R1  R2, or R1 – R2.

In each case, the result will be another relation from

A to B.
 Combining relations
Example:
Relations from A to B are subsets of A×B, two relations
can be combined in any way that 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)}
R2 – R1 = {(1,2), (1,3), (1,4)}
 Composite Relations
There is another important way to combine relations.

Definition:
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.

In other words, if relation R contains a pair (a, b) and

relation S contains a pair (b, c), then SR contains a
pair (a, c).
Example:
What is the composite of the relations R and S where R is
the relation from {1,2,3} to {1,2,3,4} with
R = {(1,1), (1,4), (2,3), (3,1), (3,4)} and
S is the relation from {1,2,3,4} to {0,1,2} with
S = {(1,0), (2,0), (3,1), (3,2), (4,1)}?

Solution:
S  R is constructed using all ordered pairs in R and
ordered pairs in S, where the second element of the
ordered in R agrees with the first element of the ordered
pair in S.
For example, the ordered pairs (2,3) in R and (3,1) in S
produce the ordered pair (2,1) in S  R. Computing all the
ordered pairs in the composite, we find
S  R = ((1,0), (1,1), (2,1), (2,2), (3,0), (3,1)}
 Power of Relations
Definition:
Let R be a relation on the set A. The powers Rn, n = 1,
2, 3, …, are defined inductively/recursively by
R1 = R
Rn+1 = RnR

In other words:
Rn = RR … R (n times the letter R)
 Power of Relations
Example:
Let R={(1,1),(2,1),(3,2),(4,3)}.
Find the powers Rn, n=2,3,4,…

R2=R∘R, we find R2={(1,1),(2,1),(3,1),(4,2)}, R3=R2∘R,

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

It also follows Rn=R3 for n=5,6,7,…

 Combining Relations
Theorem:
The relation R on a set A is transitive if and only if Rn
 R for all positive integers n.
Remember the definition of transitivity:
Definition:
A relation R on a set A is called transitive if whenever (a,
b)R and (b, c)R, then (a, c)R for a, b, cA.
The composite of R with itself contains exactly these pairs
(a, c).
Therefore, for a transitive relation R, RR does not contain
any pairs that are not in R, so RR  R.
Since RR does not introduce any pairs that are not already
in R, it must also be true that (RR)R  R, and so on, so that
Rn  R.
 n-ary Relations
In order to study an interesting application of relations,
namely databases, we first need to generalize the
concept of binary relations to n-ary relations.

Relationship among elements of more than 2 sets often

arise: n-ary relations

Airline, flight number, starting point, destination, departure

time, arrival time
 n-ary relations
Definition 1:
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.

Example:
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<c.

Then (1,2,3)  R, but (2,4,3)  R.

The degree of this relation is 3. Its domains are equal to the
set of integers.