KT14403 Discrete Structure Topic 4

Topic 4: Functions
Exploring the fundamental concepts of mathematical functions in computer science

f :A → B  f(x) = y

   
Domain & Range Mapping Composition Inverse
Input & Output sets One-to-one relation f∘g function Reverse mapping
Learning Objectives

 Learn about functions

 Explore various properties of functions

 Learn about sequences and strings

 Become familiar with the representation of strings in computer

memory
 Learn about binary operations
Function Definition

Let A = {1, 2, 3, 4} and B = {a, b, c, d} be sets and f be

the set
f = {(1, a), (2, a), (3, c), (4, c)}

Because f ⊆ A × B, f is a relation from A into B. We

have (1, a) ∈ f, which here we write as f(1) = a, and so
on. Thus,

f(1) = a, f(2) = a,
f(3) = c, f(4) = c.
Figure 5.1: Arrow diagram representing
relation f from A to B
Key Function Properties

Let us note the following crucial rules that define a valid function:

 (i) Domain Completeness  (ii) Uniqueness

The domain of f is the set A, i.e., An element of A is related to only one

element of B.
D(f) = {1, 2, 3, 4} = A
For an element x ∈ A, there exists a
In other words, there is an arrow unique y ∈ B such that:
originating from each element of A to
an element of B.
f(x) = y
The Function Machine

A function maps an input to a specific output: Example: f : ℝ → ℝ defined by f(x) = x²

x f(x) x x²
input  function f  output input  f(x) = x²  output

FIGURE 5.2 Function machine FIGURE 5.3 Function machine of f(x) = x²

Inputs and outputs of the function machine f(x) = x²:

2  f(x) = x²  4 5  f(x) = x²  25 -3  f(x) = x²  9

FIGURE 5.4 Function machine showing inputs and outputs

Formal Definition of a Function

DEFINITION 5.1.1  Let A and B be nonempty sets and f be a relation from A into
B.

Then f is called a function from A into B if:

(i) the domain of f is A, i.e., D(f) = A, and

(ii) for all (a, b), (a', b') ∈ f, a = a' implies b = b'. In this case, we say that f is well defined or
single valued.

We write f : A → B to indicate that f is a function from A into B.

If (a, b) ∈ f (i.e., f(a) = b), then b is called the image of a under f, and a is called a preimage of b. We also say that a is
mapped to b.
Verification Conditions

So in order to show that a relation f from A to B is a function, we must verify the

following two conditions:

The domain of f is A, which means that every element of A has some

1.
image in B, and

2. an element of A cannot have more than one image in B.

Worked Example: Verifying Functions

EXAMPLE 5.1.2 (i) Let f be a relation from ℝ into ℝ given by

f = {(x, 7x + 3) | x ∈ } ℝ
Now D(f) = {x | x ∈ ℝ} = ℝ. Thus, f satisfies part (i) of Definition 5.1.1. Next let (x, 7x + 3), (y, 7y + 3) ∈ f.
Suppose x = y. Then 7x = 7y, therefore 7x + 3 = 7y + 3.
This shows that f is well defined and therefore f satisfies part (ii) of Definition 5.1.1.
Hence, f is a function from ℝ into ℝ.

(ii) Let g be a relation from ℝ into ℝ given by

g = {(x, 3x² + 5x + 2) | x ∈ } ℝ
Now D(g) = {x | x ∈ ℝ} = ℝ. Thus, g satisfies part (i) of Definition 5.1.1. Next let (x, 3x² + 5x + 2), (y, 3y² + 5y + 2) ∈ g.
Suppose x = y. Then 3x² + 5x + 2 = 3y² + 5y + 2.
This shows that g is well defined. Therefore, g satisfies part (ii) of Definition 5.1.1.
Consequently, g is a function from ℝ into ℝ.
Domain, Codomain & Range

DEFINITION 5.1.2  Let A and B be sets and f : A → B be a function.

The set A is referred to as the domain of the function and the set B is called the codomain, or
target, of f.

The set f(A) = {f(x) | x ∈ A}

is a subset of the codomain B. The set f(A) is called the range of the function f, or the image of
the set A under the function f, denoted by Im(f) or I(f).
Examples of Finding Range

EXAMPLE 5.1.4 (i) Let f : ℤ → ℤ be a function defined by f(n) = 2n + 1 for all n ∈ ℤ.

Observe for all n ∈ ℤ, 2n + 1 is an odd integer. Thus,

ℤ ℤ
Im(f) = {f(m) | m ∈ } = {2m + 1 | m ∈ } = set of all odd integers.

(ii) Let g : ℝ → ℝ be a function defined by g(x) = x² for all x ∈ ℝ. Then

Im(g) = {y ∈ ℝ | y = g(x) for some x ∈ ℝ}
= {y ∈ ℝ | y = x² for some x ∈ ℝ}
= {y ∈ ℝ | y ≥ 0}.

(iii) Let A = {1, 2, 3, 4, 5} and B = {a, b, c, d}. Let h : A → B be defined by:

h(1) = a, h(2) = a, h(3) = c, h(4) = d, and h(5) = c.

Then Im(h) = {a, c, d}.

Arrow Diagram Representation

A B
f  Every function is a relation.
1  Therefore, functions on finite sets can
a be described by arrow diagrams. In
2 the case of functions, the arrow
diagram may be drawn slightly
3 b differently.
 If f : A → B is a function from a finite set
A into a finite set B, then in the arrow
4 c diagram, the elements of A are
enclosed in ellipses rather than
individual boxes.

FIGURE 5.5 Arrow diagram of f

Arrow Diagram Verification

To determine from its arrow diagram whether a relation f from a set A into a set B
is a function, two things are checked:

Check to see if there is an arrow from each element of A to an element of B.

1)  This would ensure that the domain of f is the set A, i.e., D(f) = A.

Check to see that there is only one arrow from each element of A to an
2) element of B.
 This would ensure that f is well defined.
Valid Function Example

A f B
Let A = {1,2,3,4} and B = {a,b,c,d}. The diagram
represents relation f.
1 a
 There is an arrow originating from each
2 b element of A.
D(f) = A

3 c  There is only one arrow from each

element of A to an element of B.
4 d f is well defined.

Therefore, f is a function from A into B.

FIGURE 5.6 Arrow diagram of f
Im(f) = {a, b, d}
Arrow Diagram Example: Function gg

A B  Every element of A has some image in B.

g
→ D(g) = A
1 a
 There is only one arrow from each
element of A to an element of B.
2 b
→ g is well defined

3 c  Therefore, g is a function from A into B.

4 d
 The image of g includes all elements of
B:
Im(g) = {a, b, c, d} = B
FIGURE 5.7 Arrow diagram of g
Non-Function: Not Well-Defined

A B
h  Every element of A has some image in B;
therefore, D(h) = A.
1 a
 However, element 1 has two images in B;
2 b i.e., there are two arrows originating from
1, one going to a and another going to b.
3 c
So h is not well defined.

4 d  Thus, the first condition of Definition 5.1.1

is satisfied, but the second one is not.

Therefore, h is not a function.

FIGURE 5.8 Arrow diagram of relation h
Non-Function: Incomplete Domain

A B  The arrow diagram represents a

k relation k from A into B.
1 a
 Not every element of A has an image in
B. For example, the element 4 has no
2 b image in B. There is no arrow originating
from 4.
3 c
 Therefore,
4 d 4 ∉ D(k), so D(k) ≠ A
 This implies that k is NOT a function
from A into B.
FIGURE 5.9 Arrow diagram of k
Numeric Functions

 If the domain and the range of a function are numbers, then the
function is typically defined by means of an algebraic formula.

 Such functions are called numeric functions.

 Numeric functions can also be defined in such a way so that different

expressions are used to find the image of an element (piecewise
functions).
Identity & Constant Functions

DEFINITION 5.1.3 
A function f : A → A is said to be the identity function if f(x) = x for all x ∈ A. This
function is usually denoted by iA.

DEFINITION 5.1.4 
A function f : A → B is said to be a constant function if there exists b ∈ B such that
f(x) = b for all x ∈ A. That is, all elements of A are mapped to only one element of B.
Types of Functions: Injective, Surjective,
Bijective
DEFINITION 5.1.5 ▶ Let A and B be sets and f: A → B. Then:
(i) f is called one-one (or injective or injection) if for all a₁, a₂ ∈ A,
a₁ ≠ a₂ ⇒ f(a₁) ≠ f(a₂)
(i.e., images of distinct elements of the domain are distinct)

(ii) f is called onto B (or surjective or surjection) if for every b ∈ B there exists at least one a ∈ A such
that f(a) = b, i.e.,
Im(f) = B

(iii) f is called one-to-one correspondence (or bijective or bijection) if f is both one-one and onto.
Example: Bijective Function

Example 5.1.8
 Let A = {1, 2, 3, 4} and B = {a, b, c, d}. Let f : A → B be a
function as shown.
A B
f
1 a  The arrows from a distinct element of A go to a distinct
element of B. Every element of B has at most one arrow
coming to it.
2 b
If a₁, a₂ ∈ A and a₁ = a₂, then f(a₁) = f(a₂). Hence, f is
one-one.
3 c

4 d  Each element of B has an arrow coming to it. That is,

each element of B has a preimage.
Im(f) = B. Hence, f is onto B. It also follows that f is a
one-to-one correspondence (bijective).

FIGURE 5.10 Arrow diagram of f

Example: Neither One-One Nor Onto

Example 5.1.10
A B  Let A = {1,2,3,4} and B = {a, b, c, d, e}
f
1 a
 f : 1 → a, 2 → a, 3 → a, 4 → a
b
2  For this function, the images of distinct
c elements of the domain are not distinct. For
3 example:
d 1 ≠ 2, but f(1) = a = f(2)
4
e
 Im(f) = {a} ≠ B
Hence, f is neither one-one nor onto
B.
FIGURE 5.11 Arrow diagram of f
Example: One-One But Not Onto

A B
f  Let A = {1,2,3,4} and B = {a,b,c,d,e}.
a The function mappings are:
1 f: 1 → a, 2 → b, 3 → d, 4 → e
b
2  For this function, the images of distinct
c elements of the domain are distinct.
Thus, f is one-one.
3
d  In this function, for the element c of B
4 (the codomain), there is no element x in
e the domain such that f(x) = c; i.e., c has
no preimage.

Hence, f is not onto B.

FIGURE 5.12 Arrow diagram of f
Function Composition Definition

DEFINITION 5.1.6 
Let f : A → B and g : B → C be functions. The composition of f and g, written g ∘ f, is the
function from A to C defined as:
(g ∘ f)(a) = g(f(a)), for all a ∈ A.
A B C
g∘f

f g
a f(a) g(f(a))

FIGURE 5.13 Composition of the functions f and g

Composition Example
Example 5.1.15
A f B g C A h=g∘f C
1 a 1
b
7 7
2 2
c 8 8
3 3
d
9 9
4 e
4

FIGURE 5.14 Arrow diagram of the functions f and g FIGURE 5.15 Arrow diagram of h = g ∘ f

Let A = {1,2,3,4}, B = {a,b,c,d,e}, and C = {7,8,9}. Consider the functions f : A → B, g : B → C defined by the arrow diagrams in Figure
5.14. The arrow diagram in Figure 5.15 describes the resulting composition function h = g ∘ f : A → C.
Composition with Identity

Theorem 5.1.1 :
Let f : A → B be a function from a set A into a set B. Consider the
identity functions iA : A → A and iB : B → B. Then

f ∘ iA = f = iB ∘ f .
Associativity of Composition

THEOREM 5.1.2 

Let f : A → B, g : B → C, and h : C → D. Then

h ∘ (g ∘ f) = (h ∘ g) ∘ f ;
i.e., composition of functions is associative, provided the composition is defined.
Properties of Composition

Theorem 5.1.3
Suppose that f : A → B and g : B → C. The following assertions hold:
(i) If both f and g are one-one, then g ∘ f is also one-one.
(ii) If f is onto B and g is onto C, then g ∘ f is also onto C.
(iii) If both f and g are one-to-one correspondences (bijective), then g ∘ f is also a one-to-
one correspondence.

Theorem 5.1.4
Let A be a finite set and f : A → A be a function.
If f is one-one, then f is onto A and hence a one-to-one correspondence (bijective).
 Special Functions and Cardinality
Let A = {1, 2, 3, 4, 5}, B = {a, b, c, d}, and f : A → B be defined by:
f(1) = a, f(2) = a, f(3) = b, f(4) = c, f(5) = d.

A Function f Inverse Relation fB⁻¹

(Domain) B A (Domain)
1 a
1 a
2 b
2 b
3 3
c c
4 4
5 d
5 d

(a) Function f is onto B but not one-one (b) f⁻¹ is not a function (a maps to 1 and 2)

FIGURE 5.16 Arrow diagrams of f and f⁻¹.

Because 1 and 2 map to a, f is not one-one. However, every element of B has a preimage, so f is onto B.
Inverse Relation Analysis

The inverse relation f⁻¹ ⊆ B × A is given by:

f⁻¹ = {(a, 1), (a, 2), (b, 3), (c, 4), (d, 5)}
Condition 1: Domain Completeness 
Each element of B has an image under f⁻¹. Therefore, the domain of f⁻¹ is D(f⁻¹) = {a, b, c, d} = B. Hence,
f⁻¹ satisfies the first condition of Definition 5.1.1.

Condition 2: Uniqueness (Well-defined) 

The element a of B has two distinct images, 1 and 2, under f⁻¹. This implies that f⁻¹ does not satisfy
the second condition of Definition 5.1.1.

 Conclusion: Because it is not well-defined, f⁻¹ is NOT a function.

Inverse Function Theorem

THEOREM 5.2.1 

Let f : A → B be a function. The inverse relation f⁻¹ ⊆ B × A is a

function from B into A if and only if f is both one-one and onto B.

i.e., f must be bijective

Inverse Function Properties

Corollary 5.2.1
Let f : A → B be a one-one and onto (bijective) function. Then f ⁻¹ : B → A is a one-one and onto
function. Moreover, f ⁻¹ ∘ f = iA and f ∘ f ⁻¹ = iB.

Theorem 5.2.2
Let f : A → B be a function such that f is one-one and onto B (bijective).
(i) If there exists a function g : B → A such that g ∘ f = iA, then g = f ⁻¹.
(ii) If there exists a function h : B → A such that f ∘ h = iB, then h = f ⁻¹.

Theorem 5.2.3
The inverse of a function, if it exists, is unique.
Left and Right Invertible Functions
DEFINITION 5.2.1  Let f : A → B be a function from the set A into the set B.

(i) Left Invertible (ii) Right Invertible

f is called left invertible if there exists g : B → A f is called right invertible if there exists h : B → A
such that g ∘ f = iA. such that f ∘ h = iB.
Here, g is called a left inverse of f. Here, h is called a right inverse of f.

g ∘ f = i_A f ∘ h = i_B
A B A B A B
f g h f
a a b b
f(a) h(b)
Inverse Relation Detailed Analysis

The inverse relation f⁻¹ ⊆ B × A is given by:

f⁻¹ = {(a, 1), (a, 2), (b, 3), (c, 4), (d, 5)}
1. Domain Completeness:
From the set notation, each element of B has an
image under f⁻¹.
D(f⁻¹) = {a, b, c, d} = B. (Condition 1 )

2. Well-defined (Uniqueness):
Notice that the element a of B has two distinct
images, 1 and 2, under f⁻¹.
This violates the second condition.
 Hence, f⁻¹ is not a function.
Inverse Function Theorem & Corollary

 Theorem 5.2.1
Let f : A → B be a function. The inverse relation f⁻¹ ⊆ B × A is a function from B into A if
and only if f is both one-one and onto B.

 Corollary 5.2.1
Let f : A → B be a one-one and onto function. Then f⁻¹ : B → A is a one-one and onto
function. Moreover,
f⁻¹ ∘ f = i A and f ∘ f⁻¹ = i B
Uniqueness of Inverse Functions

 Theorem 5.2.2
Let f : A → B be a function such that f is one-one and onto B.
(i) If there exists a function g : B → A such that g ∘ f = iA, then g = f⁻¹.
(ii) If there exists a function h : B → A such that f ∘ h = iB, then h = f⁻¹.

 Theorem 5.2.3
The inverse of a function, if it exists, is UNIQUE .
Left and Right Invertible Functions

DEFINITION 5.2.1 Let f : A → B be a function from the set A into the set B.

 (i) Left Invertible  (ii) Right Invertible

f is called left invertible if there exists g : B f is called right invertible if there exists h : B
→ A such that: → A such that:

g ∘ f = iA f ∘ h = iB
Moreover, if such a function g exists, then g Moreover, if such a function h exists, then h
is called a left inverse of f. is called a right inverse of f.
Restriction of a Function

 DEFINITION 5.2.2
Let f : A → B and ∅ ≠ A' ⊆ A. The restriction of f to A', written f|A', is defined to be:

f|A' = { (a', f(a')) | a' ∈ A' }

 Theorem 5.2.4
Let f : A → B be a function and C be a nonempty subset of A. Then the
restriction of f to C is UNIQUE.
Extension of a Function

DEFINITION 5.2.3 
Let f : A → B and A ⊆ A'. A function g : A' → B is called an extension of f to A' if g|A = f.

EXAMPLE 5.2.4
Suppose A = { a ∈ ℝ | a > 0 }. Let f : A → ℝ be given by f(a) = 1 for all a ∈ A.

 Then g is an extension of f to ℝ, because g|A = f.

Image of Sets & Theorem 5.2.5

Let f : A → B be a function from a set A into a set B. Let P ⊆ A.

The set f(P) = { f(a) | a ∈ P } ⊆ B is called the image (or direct image) of P under f.

 Let X and Y be two nonempty subsets of A. It is interesting to see that, in general,

f(X Y) f(X) f(Y)
∩ ≠ ∩ .

 Theorem 5.2.5
Let X and Y be nonempty sets and f : X → Y be a function. Then f is one-one if and only if
f(A ∩ B) = f(A) ∩ f(B)
for all nonempty subsets A and B of X.
Floor Function

DEFINITION 5.2.4 
For any real number x, the floor of x, written ⌊ x⌋, is the greatest integer less than or equal to
x.

EXAMPLE 5.2.6

Let x = 4.15. Here 4 is the greatest integer that does Let x = 3/4 = 0.75. Here 0 is the greatest integer that
not exceed 4.15. does not exceed 3/4.
Hence, ⌊4.15⌋ = 4 Hence, ⌊3/4⌋ = 0
Consider x = 48.0. The largest integer that does not Now consider x = -3.8. Observe that the largest
exceed 48.0 is 48. integer that does not exceed x is -4.
Thus, ⌊48.0⌋ = 48 Thus, ⌊-3.8⌋ = -4
Floor Function: Existence Proof

Let x be a real number. If x is an integer, then ⌊x⌋ = x. Suppose x is not an integer.

Then x - 1 is also not an integer. See the number line below:

Thus, there exists an integer n such that x - 1 < n < x.

Floor Function Uniqueness Proof

Suppose there exist two integers n, m such that:

x−1<n<x (5.1)

and
x − 1 < m < x.
Multiply the second inequality by −1, to get −(x − 1) > −m > −x or:

−x < −m < −x + 1 (5.2)

Add the corresponding sides of (5.1) and (5.2) to get:

x−1−x<n−m<x−x+1
This implies −1 < n − m < 1. The only integer between −1 and 1 is 0, so n − m = 0, i.e., n = m.

Thus, there exists only one integer n such that x − 1 < n < x. From this it follows that ⌊ x⌋ is the
unique integer satisfying x−1< x x⌊ ⌋≤ . (5.3)
 Ceiling Function & Set Cardinality

 DEF 5.2.5: Ceiling = DEF 5.2.7: Cardinality

For real number x, the ceiling of x, written ⌈x⌉, is the least Sets A and B have the same cardinality if there exists a one-to-
integer ≥ x. one correspondence from A into B.
x ≤ ⌈x⌉ < x + 1 |A| = |B|

 DEF 5.2.6  DEF 5.2.8: Equivalence

(i) f: ℝ → ℝ, f(x) = ⌊x⌋ is a floor function. Sets A and B are equivalent (equipotent), written A ∼ B, if
(ii) g: ℝ → ℝ, g(x) = ⌈x⌉ is a ceiling function. there exists a one-one and onto function from A to B.
A ∼ B ⇔ |A| = |B|

Theorems 5.2.6 & 5.2.7  DEF 5.2.9: Countable Sets

Floor & ceiling functions are neither one-one nor onto ℝ. Set A is countable if either:
For x ∈ ℝ, n ∈ ℕ: |A| = |In| for some positive integer n, OR
⌊x + n ⌋ = ⌊x⌋ + n |A| = |ℕ|
Note: Empty set is countable, |∅| = 0.
Example: Integers are Countable

EXAMPLE 5.2.9
Because f : ℕ → ℤ given by:

f(n) = { n/2-(n-1)/2
if n is even,
if n is odd

is a one-to-one correspondence, it follows that ℤ is a countable set.

Figure 5.18 gives a graphic representation of f, showing a spiral pattern covering all integers.
Countable Sets Example

EXAMPLE 5.2.10
The set S = {n ∈ ℕ | n ≥ 3} is countable. Define the function f : ℕ → S by f(n) = n + 2 for all n
∈ ℕ. Then f is one-one and onto S (see Figure 5.19). Hence, S is countable.
Countable Sets Theorem & Uncountable Sets

 Theorem 5.2.8

(i) The union of two countable sets is countable.

(ii) The Cartesian product of two countable sets is countable.

 DEFINITION 5.2.10

A set S is uncountable if there is no one-to-one correspondence between ℕ and

S.
Definition 5.3.1: Infinite Sequences

An infinite sequence, or simply a sequence, on a nonempty set X is a function from the set of
positive integers ℕ, i.e., from the set {1, 2, ...} into X.
Let f be a sequence on a set X. Then f is a function from ℕ into X. Typically, we use the subscript
notation an (or xn, cn, sn) to denote the image f(n) of n in X.

Suppose f is a sequence on a set X given by f(n) = an. We generally represent f by listing its images at the
integers 1, 2, 3, ... in the form:

f: a1, a2, ..., an, ... or {a1, a2, ...} or briefly by {an}
Where an is the nth term of the sequence. (a1 is 1st term, a2 is 2nd term, etc.)

A sequence whose terms are integers is called an integer sequence.

Arithmetic Progression (AP)

 DEFINITION 5.3.2
Let a and d be real numbers. The sequence:
a, a + d, a + 2d, ..., a + (n - 1)d, a + nd, ...
is called an arithmetic progression (AP). We call a the first term, d the common difference, and a +
(n - 1)d the nth term.

 EXAMPLE 5.3.7
Let {an}∞n=1 be an AP with first term a = 4 and common difference d = 5. Find the first four terms and the nth
term:
a1 = a = 4
a2 = a + d = 4 + 5 = 9
a3 = a + 2d = 4 + 2(5) = 14
a4 = a + 3d = 4 + 3(5) = 19
an = a + (n - 1)d = 4 + (n - 1)5 = 4 + 5(n - 1)
Geometric Progression (GP)

 DEFINITION 5.3.3
Let a and r be real numbers. The sequence
a, ar, ar2, ..., arn-1, arn, ...
is called a geometric progression (GP). We call a the first term and r the common ratio of the sequence.
Furthermore, arn-1 is the nth term of the sequence.

EXAMPLE 5.3.8
Let {an}n=1∞ be a GP such that the first term is a = 3 and the common ratio is r = 1/2. Let us find the first four
terms and the nth term of this sequence.
a1 = a = 3
a2 = ar = 3 · (1/2) = 3/2
a3 = ar2 = 3 · (1/2)2 = 3/4
a4 = ar3 = 3 · (1/2)3 = 3/8
an = arn-1 = 3 / 2n-1
 Summation & Product Notation

 Summation Notation (Σ)  Product Notation (Π)

The sum of terms am, am+1, ..., an: The product of terms am, am+1, ..., an:
n n
am + am+1 + ... + an = ∑ ai am · am+1 · ... · an = ∏ ai
i=m i=m
m: lower limit m: lower limit
n: upper limit n: upper limit
ai: general term ai: general term

Theorem 5.3.1 Theorem 5.3.3

(i) ∑(ai + bi) = ∑ai + ∑bi ∏(ai · bi) = (∏ai) · (∏bi)
(ii) c · ∑ai = ∑(c · ai)
 Strings Definition & Theorem

 DEFINITION 5.3.4: Strings  Theorem 5.3.4

Let A be a nonempty finite set. A string or word over A is a finite Let A be a finite set and let s, s1, s2, s3 be strings over
sequence of elements from A. The set A is called an alphabet. A. Then:

Length |s|: Number of elements. E.g., |mathematics| = 11

1. λs = s = sλ
Empty String (λ): String with no elements. |λ| = 0
2. s1(s2s3) = (s1s2)s3
Concatenation: s1s2 combines elements of s1 followed by s2
3. |s1s2| = |s1| + |s2|
Sequences and Strings

 Representing Strings into Computer Memory

 A convenient way of storing a string into computer memory is to use an
array .

 Programming languages such as C++ and Java provide a data type to

manipulate strings.

 This data type includes algorithms to implement operations such as:

concatenation
finding the length of a string
determining whether a string is a substring in another string
finding a substring into another string
Binary to Decimal Conversion

 ALGORITHM 5.1  Understanding the Algorithm

Nonrecursive algorithm to convert base 2 to base 10 The algorithm computes a weighted sum by iterating
through a 32-bit binary array.
Input: L—an array of the size 32
 Initialization: It starts with x = 0 to accumulate the total
Output: x—decimal representation
decimal value.
1. function nonRecursiveBinaryToDecimal(L)  Iteration: The loop runs from i = 1 to 32.
2. begin
 Array Access L[32 + 1 - i]: This index formula reads the
3. x := 0;
array from right to left (from least significant bit to most
4. for i := 1 to 32 do
significant bit). For i=1, it reads L[32]; for i=32, it reads L[1].
5. x := x + L[32 + 1 - i] * 2i-1;
6. return x;  Weight Calculation * 2i-1: Each bit is multiplied by its
7. end corresponding power of 2 (starting at 20 for i=1) and added to
the running sum x.
 Algorithm: Decimal to Binary

 ALGORITHM 5.2  Understanding the Algorithm

Input: x — decimal representation This algorithm converts a base-10 number to base-2 non-
Output: L — array containing binary representation recursively. Here is how it works:
Initialization (Lines 3-5): The array L (size 32) is filled with zeros. n
1. procedure nonRecursiveDecimalToBinary(L, x) starts at 32 (rightmost position).
2. begin While Loop (Line 6): The process continues as long as x is not zero.
3. for i := 1 to 32 do
Get Remainder (Line 8): x mod 2 gets the least significant bit (0 or
4. L[i] = 0;
5. n := 32; 1). It is stored at position n.
6. while (x ≠ 0) do Move Left (Line 9): n is decremented to point to the next position to
7. begin the left.
8. L[n] := x mod 2; Integer Division (Line 10): x div 2 halves the number, dropping
9. n := n - 1; the remainder, preparing for the next bit extraction.
10. x := x div 2;
11. end
12. end  Key Concept: We build the binary representation from right to left by
repeatedly dividing the number by 2 and saving the remainders.
Binary Operations

 DEFINITION 5.4.1  Examples of Operations

Let S be a nonempty set. A binary operation on S is a  + is a binary operation on ℤ (Integers).

function from S × S into S.
It assigns 24 to the pair (20, 4).

For any ordered pair (x, y) of elements x, y ∈ S, a binary ℤ is closed under + because if we add two
operation on S assigns a unique member of S. integers, we obtain an integer.

Notation:  − (subtraction) is not a binary operation on

If * is a binary operation on S, we write x * y for *(x, y), ℕ (Natural Numbers).
where x, y ∈ S.
Now 3, 10 ∈ ℕ but 3 − 10 = −7 ∉ ℕ.

Because the image of S under * is a subset of S, we say that S is Thus, we say that ℕ is not closed under the
operation −.
closed under *.
Associative & Commutative Properties

DEFINITION 5.4.2 ▶ Let S be a nonempty set and * a binary operation on S. Then:

 (i) Associative  (ii) Commutative

* is called associative if for all * is called commutative if for all

x, y, z ∈ S, x, y ∈ S,

x * (y * z) = (x * y) * z x*y=y*x
Mathematical System, Groupoid & Identity

 DEFINITION 5.4.3 A nonempty set S together with a finite number of binary operations is called
▶
a mathematical system.

We denote a mathematical system by (S, *₁, *₂, *₃, . . . , *ₙ), where S is a nonempty set and *₁, *₂, *₃, .
. . , *ₙ are binary operations on S.

 DEFINITION 5.4.4 ▶ A mathematical system (S, *) with only one binary operation is called
a groupoid.

 DEFINITION 5.4.5 ▶ Let (S, *) be a mathematical system. An element e ∈ S is called an identity of

(S, *) if for all x ∈ S,

e*x=x=x*e
Identity Element Uniqueness

 Theorem 5.4.1:
An identity element (if it exists) of a mathematical system (S,
*) is unique.

 There can never be more than one identity in (S, *).

Semigroup, Commutative Semigroup & Monoid

 DEFINITION 5.4.6 ▶ A mathematical system (S, *) with associative binary operation * is

called a semigroup.

 DEFINITION 5.4.7 ▶ A semigroup (S, *) is called commutative if * is a commutative

x*y=y*x
binary operation; i.e., for all x, y ∈ S, .

 DEFINITION 5.4.8 ▶ A semigroup (S, *) is called a monoid if S contains an element e,

called an identity of (S, *), such that for all x ∈ S,

e*x=x=x*e
Transformation Semigroup

 DEFINITION 5.4.9 ▶ Transformation Semigroup

Let A be a nonempty set. Let TA be the set of all functions on A, i.e.,

TA = { f | f : A → A }
∘
Because composition of functions is a function, the operation (composition of functions), is a binary operation
on TA. By Theorem 5.1.2, ∘ is associative. Hence, TA is a semigroup with respect to the composition of functions.
This semigroup is called the transformation semigroup on A.

 Theorem 5.4.2:
Let A be a nonempty set with more than two elements. The transformation
semigroup TA on A is a noncommutative monoid.
Idempotent Element & Band

 DEFINITION 5.4.10 ▶ Idempotent Element

Let (S, *) be a semigroup. An element a of S is called an idempotent element if a*a=a
.
If every element of a semigroup is idempotent, then it is called an idempotent semigroup, or a band.

 Example: Power Set with Intersection

Let S be a nonempty set and P(S) denote the set of all subsets of S. Define a binary operation * on S by A *
B = A ∩ B for all A, B ∈ P(S). Then (P(S), *) is a semigroup.
A * A = A ∩ A = A for all A ∈ P(S). Hence, this semigroup is an idempotent semigroup.
In this semigroup,
Also, A * B = A ∩ B = B ∩ A = B * A for all A, B ∈ P(S) implies that this is a commutative semigroup.
 Binary Operations: Free Semigroup

 Let A be an alphabet. Let A⁺ be the set of all nonempty strings on A. If u, v ∈ A⁺, then concatenation uv ∈ A⁺.
Thus, concatenation is a binary operation. By Theorem 5.3.23(ii), it is associative. Hence, A⁺ becomes a
semigroup with respect to concatenation. Called a free semigroup generated by A.

 Comparison: Semigroup vs. Free Semigroup

Feature Semigroup (S, *) Free Semigroup (A⁺, concat)

Base Elements Any non-empty set S Set of all non-empty strings A⁺ from alphabet A

Operation Any binary operation * String concatenation

Associativity Required: x*(y*z) = (x*y)*z Guaranteed: u(vw) = (uv)w for strings

Example (ℤ⁺, +) or (ℝ, ×) A = {a,b}. A⁺ = {a, b, aa, ab, ba, bb, aaa...}
Binary Operations: Free Monoid & Comparison

Let A* denote the set of all words including empty word λ. By Theorem 5.3.4(i), λs = s = sλ. Thus, A* is a
 monoid with identity 1 = λ, called a free monoid generated by A.
 If A has >1 element, A* is a noncommutative monoid.

Comparison: Monoid vs Free Monoid (vs Semigroup)

Structure Definition / Base Identity Element Commutativity Example

Semigroup Set S with an associative binary  Not required Depends on specific (ℤ, +), A⁺ (strings > 0 len)
operation (*) structure

General Monoid Semigroup that contains an identity  Yes (e * x = x) Depends on specific (ℤ, +) with e=0
element e structure (TA, ∘) with e=iA

Free Monoid (A*) Set of all words from alphabet A, built  Yes (Empty word λ) Noncommutative {0,1}* = {λ, 0, 1, 00, 01, 10, 11,
by concatenation (if |A| > 1, ab ≠ ba) ...}
Algebraic Structures: Concept Map

 Semigroup  Monoid
Associative binary operation Associative operation
No identity required + Add Identity Element Contains Identity Element (e)
Example: (ℤ⁺, +) or (2ℤ, ×)  Example: (ℤ, +) with e=0

Apply to Strings Apply to Strings

 
 Free Semigroup A⁺  Free Monoid A*
Nonempty strings All words from alphabet A
Concat operation (assoc.) + Include empty string λ
Concat operation (assoc.)
No identity (λ excluded)  Identity = empty word λ
 TOPIC 4: FUNCTIONS - COMPREHENSIVE SUMMARY

 1. Foundations  6. Floor & Ceiling  11. Binary Operations

Function definition (A→B), domain, codomain, range, ⌊x⌋ (floor) and ⌈x⌉ (ceiling) functions, definitions, Function S×S→S. Closure under operation.
image, pre-image, visual arrow diagrams. algebraic properties, existence/uniqueness proofs. Commutative (x*y=y*x) and associative properties.
Identity element uniqueness.

 7. Countable Sets
 2. Function Types  12. Algebraic Structures
Cardinality, bijections with ℕ, countable sets (e.g., ℤ),
Injective (one-to-one), Surjective (onto), Bijective (one- • Groupoid: Mathematical system (S,*)
uncountable sets (e.g., ℝ), union theorems.
to-one correspondence), constant, identity. • Semigroup: Associative operation
• Monoid: Semigroup + Identity
• Band: Idempotent semigroup (a*a=a)
 8. Sequences • Transformation Semigroup: TA with ∘
 3. Composition Infinite sequences as functions (ℕ→X), Arithmetic
g∘f(x) = g(f(x)). Associative property, composition with Progression (AP), Geometric Progression (GP), Σ and
identity function, non-commutative generally. Π notation.

* 13. Free Structures

 9. Strings • Free Semigroup (A⁺): Non-empty strings under
 4. Inverse Functions Alphabets, strings length, empty string λ, concatenation.
Existence (requires bijection), uniqueness, f⁻¹, concatenation, properties, representation in • Free Monoid (A*): All strings including empty word
left/right invertibility, inverse of composition (g∘f)⁻¹. computer memory. λ (identity). Noncommutative if |A| > 1.

 10. Binary Algorithms

 5. Advanced Concepts Algorithm 5.1 (non-recursive binary to decimal),
Function restriction, function extension, image of sets Algorithm 5.2 (non-recursive decimal to binary using  End of Topic 4: Functions
under functions, pre-image properties. division/mod).