Scribd
Upload
0 views

Notes Week 5

Uploaded by

bill19012004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0 views

Notes Week 5

Uploaded by

bill19012004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

MATH2081 | MATH2328: Math for Computing

1
Lecturers: Dr Nguyen Hieu Thao & Dr Jeff Nijsse
Email: thao.nguyenhieu@rmit.edu.vn

Lecture Notes: Sequences, Strings and


Relations
(2024C, Week 5)1

A sequence s is a function whose domain D is a subset of integers. The notation sn is


typically used instead of the more general function notation s(n). The term n is the index of
the sequence. If D is a finite set, we call s a finite sequence; otherwise, s is an infinite sequence.

(a) A sequence s is increasing (respectively, decreasing) if for all i and j in the domain of s,
if i < j, then si < sj (respectively, si > sj ).
(b) A sequence s is nondecreasing (respectively, nonincreasing) if for all i and j in the domain
of s, if i < j, then si ≤ sj (respectively, si ≥ sj ).
(c) A subsequence of a sequence s is a sequence obtained from s by choosing certain terms of
s in the same order in which they appear in s.
(d) If {ai }i=m is a sequence, we define
n

n n
(1)
X Y
ai = am + am+1 + · · · + an , ai = am am+1 · · · an .
i=m i=m

The formalism i=m is the sum (or sigma) notation and i=m is the product notation.
Pn Qn
In (1), i is the index, m is the lower limit and n is the upper limit.

A string over X, where X is a finite set, is a finite sequence of (repeatable) elements from
X. Since a string is a sequence, order is taken into account.
(a) Repetitions in a string can be specified by superscripts. For example, the string ‘110001’
over the binary set {0, 1} can be written as ‘12 03 1’.
(b) The string with no element is the null string and is denoted by λ.
(c) X ∗ denotes the set of all strings over X including the null string, and X + denotes the set
of all nonnull strings over X.
(d) The length of a string α, denoted by |α|, is the number of elements in α.
(e) If α and β are two strings, the string consisting of α followed by β, written αβ (or α + β),
is the concatenation of α and β.
(f) A string β is a substring of a string α if there are strings γ and δ such that α = γβδ.

1 Most of the content of this document is taken from the book [1].
2

Let X be a finite set of unambiguous symbols (the alphabet). A language L over X is a


subset of X ∗ .

A grammar G is a quadruple consisting of

(i) a finite set N of nonterminal symbols (or variables),


(ii) a finite set T of terminal symbols (or leaves), where N ∩ T = ∅,
(iii) a finite subset R of [(N ∪ T )∗ \ T ∗ ] × (N ∪ T )∗ , called the set of rules,

(iv) and a starting symbol σ ∈ N .


The language generated by G, written L(G), consists of all strings over T derivable from S
using the set of rules R.

Example. The set of all integers N is the language generated by the following grammar.

(i) N = {integer, digit, signed integer, unsigned integer}.


(ii) T = {+, −, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Johnsonbaugh-50623 book February 3, 2017 14:2
(iii) The set of rules is below:

< integer > −→ < signed integer > | < unsigned integer >,
< signed integer > −→ < + >< unsigned integer > 142
| < unsigned3 integer
− >< Chapter ◆ Functions,
>, Sequences, and
< unsigned integer > −→ < digit > | < digit >< unsigned integer >,
< digit > −→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8| | 9.

(iv) The starting symbol σ = integer.




A (binary) relation R from a set X to a set Y is a subset


Example 3.3.4 Let R be the relation
of the Cartesian product X × Y . If (x, y) ∈ R, we write
R = {(1, 1), (1
xRy and say that x is related to y. If X = Y , R is a
1 2
relation on X. An informativ
graphs are discussed
connection with rela
An informative way to picture a relation on a set is to draw dots or vertices to r
its digraph. To draw the digraph of a relation on a set X, vertices to represent
(x, y) is in the relatio
we first draw dots or vertices to represent the elements of 3 4
ure 3.3.1, we have d
Example 3.3.4. Noti
X. Next, if the element (x, y) is in the relation, we draw directed edge from x
an arrow (a directed edge) from x to y. An element of Figure 3.3.1 The digraph of the Figure 3.3.1.
Figure 1: Digraph
relation of Exampleof the relation
3.3.4.
the form (x, x) in a relation corresponds to a directed edge xRy if x ≤ y on {1, 2, 3, 4}.
from x to x. Such an edge is a loop. Example 3.3.5 The relation R on X
❦ (b, c), (c, b), (d, d)}.
3

Let R be a relation on a set X.

(a) R is reflexive if (x, x) ∈ R for every x ∈ X.

(b) R is symmetric if for all x, y ∈ X, if (x, y) ∈ R, then (y, x) ∈ R.

(c) R is antisymmetric if for all x, y ∈ X, if (x, y) ∈ R and (y, x) ∈ R, then x = y.

(d) R is transitive if for all x, y, z ∈ X, if (x, y) and (y, z) ∈ R, then (x, z) ∈ R.

(e) R is an equivalence relation if R is reflexive, symmetric, and transitive. Let R be an


equivalence relation on a set X. For each a ∈ X, let [a] = {x ∈ X | xRa}. Then S =
{[a] | a ∈ X} is a partition of X. The set [a] is the equivalence class of a in X given by
the relation R.

(f) R is a partial order if R is reflexive, antisymmetric and transitive. If R is a partial order


on a set X, the notation x  y is used to indicate that (x, y) ∈ R. This notation suggests
that we are interpreting the relation as an ordering of the elements in X. Let R be a partial
order on X. If x, y ∈ X and either x  y or y  x, we say that x and y are comparable.
If x, y ∈ X and x  y and y  x, we say that x and y are incomparable. If every pair of
elements in X is comparable, R is a total order.

Let R be a relation from X to Y . The inverse of R, denoted by R−1 , is the relation from Y
to X defined by
R−1 = {(y, x) | (x, y) ∈ R} .

Let R1 be a relation from X to Y and R2 be a relation from Y to Z. The composition of


R1 and R2 , denoted by R2 ◦ R1 , is the relation from X to Z defined by

R2 ◦ R1 = {(x, z) | (x, y) ∈ R1 and (y, z) ∈ R2 for some y ∈ Y } .

A matrix is a convenient way to represent a relation R from X to Y . We label the rows


with the elements of X (in some order) and the columns with the elements of Y (again, in some
order). We then set the entry in row x and column y to 1 if xRy and to 0 otherwise. This matrix
is the matrix of the relation R relative to the chosen orderings of X and Y .

References
1. Johnsonbaugh, R.: Discrete Mathematics - Eighth Edition. Pearson Education, New York
(2018).

You might also like