1/17/2019

Tassos Dimitriou

CpE-203
Discrete Structures

Set 4

Prof. Tassos Dimitriou

Computer Engineering Department

Kuwait University

CpE-203: Discrete Structures 1

Tassos Dimitriou

Outline
Functions
 Definitions and properties
 Types of functions
 One-to-one, onto, bijections
 Inverse functions
 Composite

Cardinality of sets revisited

Matrices

CpE-203: Discrete Structures 2

1
 1/17/2019

Tassos Dimitriou

Functions
In many instances we assign to each element of a set a
particular element of a second set.
 For example, suppose that each student in a discrete mathematics
class is assigned a letter grade from the set {A,B,C,D, F}.
 And suppose that the grades are A for Adams, C for Bob, A for
Chris, E for Dave, and D for Emma.

This assignment is an example of a function. The concept of a

function is extremely important
 Functions are used in the definition of such discrete structures as
sequences and strings.
 Functions are also used to represent how long it takes a computer
to solve problems of a given size.
 Recursive functions are defined in terms of themselves

CpE-203: Discrete Structures 3

Tassos Dimitriou

Functions
A function f from a set A to a set B is an assignment of exactly
one element of B to each element of A.
 We write
f(a) = b
if b is the unique element of B assigned by the function f to the
element a of A.

If f is a function from A to B, we write f: AB

(note: Here, “” has nothing to do with “if… then”)

CpE-203: Discrete Structures 4

2
 1/17/2019

Tassos Dimitriou

More about functions

A pre-image The image
of 1 of “a”
Domain Co-domain
Alice A “a” 1
Bob B “bb” 2
Chris C “cccc” 3
Dave D “dd” 4
Emma F “e” 5

A class grade function A string length function

CpE-203: Discrete Structures 5

Tassos Dimitriou

Definition of a function
A function takes an element from a set and maps it to a
UNIQUE element in another set
f maps R to Z
Domain R Z Co-domain
f

f(4.3)

4.3 4

Pre-image of 4 Image of 4.3

CpE-203: Discrete Structures 6

3
 1/17/2019

Tassos Dimitriou

Even more about functions

Range
a 1 “a” 1
e 2 “bb“ 2
i 3 “cccc” 3
o 4 “dd” 4
u 5 “e” 5

Some function…

Not a valid function!

Also not a valid function!

CpE-203: Discrete Structures 7

Tassos Dimitriou

Definition of a function
If the domain of our function f is large, it is convenient to specify f
with a formula, e.g.:

f: RR

f(x) = 2x

This leads to:

f(1) = 2
f(3) = 6
f(-3) = -6
etc.

CpE-203: Discrete Structures 8

4
 1/17/2019

Tassos Dimitriou

Function arithmetic
Let f1 and f2 be functions from A to R. Then the sum and
the product of f1 and f2 are also functions from A to R
defined by
(f1 + f2)(x) = f1(x) + f2(x)
(f1f2)(x) = f1(x) * f2(x)

Let f1(x) = 2x and f2(x) = x2

 What is (f1 + f2)(x) and (f1f2)(x) ?

CpE-203: Discrete Structures 9

Tassos Dimitriou

One-to-one functions
A function is one-to-one if each element in the co-domain
has a unique pre-image (the function never assigns the
same value to two different domain elements)
Formal definition: A function f is one-to-one if f(x) = f(y)
implies x = y.
a 1 a 1
e 2 e 2
i 3 i 3
o 4 o 4
5 5

A one-to-one function A function that is

not one-to-one

CpE-203: Discrete Structures 10

5
 1/17/2019

Tassos Dimitriou

More on one-to-one
Injective is synonymous with one-to-one
 “A function is injective”
A function is an injection if it is one-to-one

a 1
Note that there can be un-used e 2
elements in the co-domain i 3
o 4
5

A one-to-one function

Is the function f(x) = x2 one-to-one?

CpE-203: Discrete Structures 11

Tassos Dimitriou

Onto functions
A function is onto if each element in the co-domain is an
image of some pre-image
Formal definition: A function f is onto if for all y  C,
there exists x  D such that f(x)=y.

a 1 a 1
e 2 e 2
i 3 i 3
o 4 o 4
u 5

An onto function A function that

is not onto

CpE-203: Discrete Structures 12

6
 1/17/2019

Tassos Dimitriou

More on “onto”
Surjective is synonymous with onto
 “A function is surjective”
A function is an surjection if it is onto
a 1

Note that there can be multiply e 2

used elements in the i 3
co-domain o 4
u

An onto function

Is the function f(x) = x2 from the set of integers to the set

of integers onto?
CpE-203: Discrete Structures 13

Tassos Dimitriou

Onto vs. one-to-one game

Are the following functions onto, one-to-one, both, or
neither?
a 1 a 1
a 1
b 2 b 2
b 2
c 3 c 3
c 3
4 d 4
4
1-to-1, not onto Both 1-to-1 and onto Not a valid function

a 1 a 1
b 2 b 2
c 3 c 3
d d 4
Onto, not 1-to-1 Neither 1-to-1 nor onto

CpE-203: Discrete Structures 14

7
 1/17/2019

Tassos Dimitriou

Summary

CpE-203: Discrete Structures 15

Tassos Dimitriou

Identity functions
A function such that the image and the pre-image are
ALWAYS equal

 f(x) = 1*x
 f(x) = x + 0

The domain and the co-domain must be the same set

CpE-203: Discrete Structures 16

8
 1/17/2019

Tassos Dimitriou

Bijections
Consider a function that is both a 1
one-to-one and onto: b 2
c 3
d 4

Such a function is a one-to-one correspondence, or a

bijection.

An interesting property of bijections is that they have an

inverse function. The inverse function of the bijection
f:AB is the function f-1:BA with
f-1(b) = a whenever f(a) = b.

CpE-203: Discrete Structures 17

Tassos Dimitriou

Inverse functions

Let f(x) = 2*x

R f R

f-1

f(4.3)
4.3 8.6
f-1(8.6)

Then f-1(x) = x/2

CpE-203: Discrete Structures 18

9
 1/17/2019

Tassos Dimitriou

Inverse functions game

Can we define the inverse of the following functions?
a 1 a 1
b 2 b 2
c 3 c 3
4 d

What is f-1(2)? What is f-1(2)?

Not onto! Not 1-to-1!

An inverse function can ONLY be defined on a BIJECTION.

 Let f be the function from R to R with f (x) = x2. Is this
function invertible?

CpE-203: Discrete Structures 19

Tassos Dimitriou

Compositions of functions
Consider two functions, the successor function and the
squaring function, defined over the integers, and imagine that
each is represented by a machine.

Combining functions in this way is called composing them; the

resulting function is called the composition of the two
functions.
CpE-203: Discrete Structures 20

10
 1/17/2019

Tassos Dimitriou

Compositions of functions
The composition of two functions g:AB and f:BC, denoted
by f◦g, is defined by

(f◦g)(a) = f(g(a))

This means that

• First, function g is applied to element aA, mapping it onto an
element of B,
• Then, function f is applied to this element of B, mapping it onto
an element of C.

Therefore, the composite function maps from A to C.

CpE-203: Discrete Structures 21

Tassos Dimitriou

Compositions of functions
(f ○ g)(x) = f(g(x))

f○g
A B C
g f

g(a) f(b)
f(g(a))
a
b = g(a)

(f ○ g)(a)

CpE-203: Discrete Structures 22

11
 1/17/2019

Tassos Dimitriou

Compositions of functions
(f ○ g)(x) = f(g(x))
Let f(x) = 2x+3 Let g(x) = 3x+2
f○g
R R R
g f

g(1) f(5)
f(g(1))=13
1
g(1)=5

(f ○ g)(1)

Thus, f(g(x)) = 2(3x+2)+3 = 6x+7

CpE-203: Discrete Structures 23

Tassos Dimitriou

Compositions of functions
Is f(g(x)) = g(f(x))?

Let f(x) = 2x+3 Let g(x) = 3x+2

f(g(x)) = 2(3x+2)+3 = 6x+7

g(f(x)) = 3(2x+3)+2 = 6x+11
Not equal!

Function composition is not commutative!

CpE-203: Discrete Structures 24

12
 1/17/2019

Tassos Dimitriou

Useful functions
Floor: x means take the greatest integer less than or
equal to the number

Ceiling: x means take the lowest integer

greater than or equal to the number

Round(x) =  x+0.5 

CpE-203: Discrete Structures 25

Tassos Dimitriou

Ceiling and floor properties

n is an integer, x is a real number
(1a) x = n if and only if n ≤ x < n+1
(1b) x = n if and only if n-1 < x ≤ n
(1c) x = n if and only if x-1 < n ≤ x
(1d) x = n if and only if x ≤ n < x+1
(2) x-1 < x ≤ x ≤ x < x+1
(3a) -x = - x
(3b) -x = - x
(4a) x+n = x+n
(4b) x+n = x+n

CpE-203: Discrete Structures 26

13
 1/17/2019

Tassos Dimitriou

Factorial
Factorial is denoted by n!

n! = n * (n-1) * (n-2) * … * 2 * 1

Thus, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720

Note that 0! is defined to equal 1

CpE-203: Discrete Structures 27

Tassos Dimitriou

Proving Function problems

Let f be an invertible function from Y to Z
Let g be an invertible function from X to Y
Show that the inverse of f○g is:
 (f○g)-1 = g-1 ○ f-1

(Proof) Thus, we want to show, for all zZ and xX

((f  g)  (g-1  f-1)) (x) = x and ((f-1  g-1)  (g  f)) (z) = z

((f  g)  (g-1  f-1)) (x) = (f  g) (g-1  f-1)) (x))

= (f  g) g-1 f-1(x)))
= (f g g-1 f-1(x)))))
= (f f-1(x))
=x
The second equality is similar
CpE-203: Discrete Structures 28

14
 1/17/2019

Tassos Dimitriou

Graphs
The graph of a function f:AB is the set of ordered pairs
{(a, b) | aA and f(a) = b}.

The graph is a subset of AB that can be used to visualize f

in a two-dimensional coordinate system.

CpE-203: Discrete Structures 29

Tassos Dimitriou

Cardinality of Sets

CpE-203: Discrete Structures 30

15
 1/17/2019

Tassos Dimitriou

Cardinality of sets
Which is bigger the set of natural numbers N or the set
of integers Z?

Which is bigger the set of positive integers or the set of

rational numbers Q?

Which is bigger the set of integers Z or the set of real

numbers R?

When two infinite sets are considered “equal”?

CpE-203: Discrete Structures 31

Tassos Dimitriou

Cardinality
For finite (only) sets, cardinality is the number of elements in
the set

For finite and infinite sets, two sets A and B have the same
cardinality if there is a one-to-one correspondence from A to B
 When A and B have the same cardinality, we write |A| = |B|.

CpE-203: Discrete Structures 32

16
 1/17/2019

Tassos Dimitriou

Cardinality
Example on finite sets:
 Let S = { 1, 2, 3, 4, 5 }
 Let T = { a, b, c, d, e }
 There is a one-to-one correspondence between the sets

Example on infinite sets:

 Let S = Z+
 Let T = { x | x is even and >0}
 One-to-one correspondence:
1↔2 2↔4 3↔6 4↔8
5 ↔ 10 6 ↔ 12 7 ↔ 14 8 ↔ 16
Etc.
 Note that here the ‘↔’ symbol means that there is a correspondence
between them, not the biconditional

CpE-203: Discrete Structures 33

Tassos Dimitriou

More definitions
Countable set (elements can be listed):
 A set that is either finite or
 Has the same cardinality as the set of positive integers (must find
a one-to-one correspondence with the Z+)
 Example: rational numbers, ordered pairs of integers

Uncountable set: A set that is NOT countable (basically its

elements cannot be listed)
 Example: real numbers

CpE-203: Discrete Structures 34

17
 1/17/2019

Tassos Dimitriou

Showing a set is countably infinite

Can be done by showing there is a one-to-one
correspondence between the set and the integers

Examples
 Even numbers
 Hilbert’s Grand Hotel
 The famous mathematician David Hilbert invented the notion of the Grand
Hotel, which has a countably infinite number of rooms, each occupied by a
guest.
 In a hotel with a finite number of rooms where all rooms are occupied, a new
guest cannot be accommodated without evicting a current guest.
 However, we can always accommodate a new guest at the Grand Hotel.
How?

CpE-203: Discrete Structures 35

Tassos Dimitriou

Hilbert’s Grand Hotel

When there are finitely many rooms in a hotel, the notion that all rooms are
occupied is equivalent to the notion that no new guests can be accommodated.
However, Hilbert’s paradox of the Grand Hotel can be explained by noting that
this equivalence no longer holds when there are infinitely many rooms.

CpE-203: Discrete Structures 36

18
 1/17/2019

Tassos Dimitriou

Cardinality game
Which is bigger the set of natural numbers N or the set of
integers Z?

Answer: The set of all integers is countable

 We can list all integers in a sequence by starting with 0 and
alternating between positive and negative integers: 0, 1,−1,
2,−2,. . . .
 Alternatively, we could find a one-to-one correspondence
between the set of positive integers and the set of all integers.
Consider the function
f (n) = n/2 when n is even and
f (n) = −(n − 1)/2 when n is odd

CpE-203: Discrete Structures 37

Tassos Dimitriou

Z is countable

It is clear from the diagram that no integer is counted twice

(so the function is one-to-one) and every integer is counted
eventually (so the function is onto).
Consequently, this diagram defines a correspondence!

CpE-203: Discrete Structures 38

19
 1/17/2019

Tassos Dimitriou

Are all Infinite sets Countable?

Theorem: The set of real numbers is uncountable
Proof by contradiction:
 Consider the numbers between 0 and 1 and assume they can be listed.
Let the decimal representation of these real numbers be

The digits are one

of 0, 1, 2, …, 9

 Now form a new real number r = 0.d1d2d3… that differs in the diagonal
digit of all the listed numbers. Does r belong to the list?
 No! Hence the assumption that all the real numbers between 0 and 1
could be listed is false. So the set of real numbers between 0 and 1 is
uncountable
CpE-203: Discrete Structures 39

Tassos Dimitriou

Matrices

CpE-203: Discrete Structures 40

20
 1/17/2019

Tassos Dimitriou

Matrices
In mathematics, a matrix (plural matrices) is a rectangular
array of numbers, symbols, or expressions, arranged in rows
and columns. The individual items in a matrix are called its
elements or entries.

CpE-203: Discrete Structures 41

Tassos Dimitriou

Matrix Arithmetic
Definition: Let A= [aij] and B=[bij] be mn matrices. The sum of
A and B, denoted by A+B, is the mn matrix that has aij+bij as
its (i,j)th element.

A B A+B

CpE-203: Discrete Structures 42

21
 1/17/2019

Tassos Dimitriou

Matrix Arithmetic (cont.)

Definition: Let A be mk matrix and B be kn matrix. The
product of A and B, denoted by AB, is the mn matrix with its
(i,j)th element equal to the sum of the products of the
corresponding entries from the ith row of A and the jth column
of B. If AB = [cij], then
 cij =ai1b1j+ai2b2j+…+aikbkj.

For the matrices below, is the product defined?

CpE-203: Discrete Structures 43

Tassos Dimitriou

Matrix product

The product of A＝[aij] and B＝[bij].

For two matrices A, B, is AB = BA?

 No, matrix multiplication is not commutative!

CpE-203: Discrete Structures 44

22
 1/17/2019

Tassos Dimitriou

Transposes and Powers of Matrices

Definition: The identity matrix of order n is the nn matrix
In=[δij], where δij=1 if i=j and δij=0 if i≠j.

If A is an m × n matrix, then AIn = ImA = A

CpE-203: Discrete Structures 45

Tassos Dimitriou

Transposes and Powers of Matrices

Powers of square matrices can also be defined. When A is an
n × n matrix, we have
A0= In, Ar = AAA…A

Let A=[aij]. The transpose of A, denoted by At, is the nm

matrix obtained by interchanging the rows and columns of A.
If At =[bij], then bij= aji for i=1, 2, …, n and j=1, 2, …, m.

 What is the transpose of ?

A square matrix A is symmetric if A=At.

 I.e. aij = aji for all i and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n.

CpE-203: Discrete Structures 46

23
 1/17/2019

Tassos Dimitriou

A symmetric matrix

歐亞書局 CpE-203: Discrete Structures P. 47

252

Tassos Dimitriou

Zero-One Matrices
Zero-one matrix: a matrix with entries that are either 0 or 1

Let A= [aij] and B=[bij] be mn zero-one matrices. The join of

A and B is the zero-one matrix with (i,j)th entry aijbij. The
meet of A and B is the zero-one matrix with (i,j)th entry aijbij.

 Find the join and meet of the zero–one matrices

CpE-203: Discrete Structures 48

24
 1/17/2019

Tassos Dimitriou

Zero-One Matrices (cont.)

Let A= [aij] be mk zero-one matrix and B=[bij] be kn zero-
one matrix. The Boolean product of A and B, denoted by A๏B,
is the mn matrix with (i,j)th entry cij where

cij = ((ai1  b1j)  (ai2  b2j)  …  (aik  bkj).

What is the Boolean product of the following matrices?

CpE-203: Discrete Structures 49

Tassos Dimitriou

CpE-203: Discrete Structures 50

25