View source for Chapter 14: Mathematical Foundations

{{TOC}}
{{IntroSection|title=Introduction|body=

Software professionals live with programs. In a
very simple language, one can program only for
something that follows a well-understood, nonambiguous
logic. The Mathematical Foundations
knowledge area (KA) helps software engineers
comprehend this logic, which in turn is translated
into programming language code. The mathematics
that is the primary focus in this KA is quite
different from typical arithmetic, where numbers
are dealt with and discussed. Logic and reasoning
are the essence of mathematics that a software
engineer must address.

Mathematics, in a sense, is the study of formal
systems. The word “formal” is associated with
preciseness, so there cannot be any ambiguous or
erroneous interpretation of the fact. Mathematics
is therefore the study of any and all certain
truths about any concept. This concept can be
about numbers as well as about symbols, images,
sounds, video—almost anything. In short, not
only numbers and numeric equations are subject
to preciseness. On the contrary, a software
engineer needs to have a precise abstraction on a
diverse application domain.

The ''SWEBOK Guide’s'' Mathematical Foundations
KA covers basic techniques to identify a set
of rules for reasoning in the context of the system
under study. Anything that one can deduce following
these rules is an absolute certainty within
the context of that system. In this KA, techniques
that can represent and take forward the reasoning
and judgment of a software engineer in a precise
(and therefore mathematical) manner are defined
and discussed. The language and methods of logic
that are discussed here allow us to describe mathematical
proofs to infer conclusively the absolute
truth of certain concepts beyond the numbers. In short, you can write a program for a problem only
if it follows some logic. The objective of this KA
is to help you develop the skill to identify and
describe such logic. The emphasis is on helping
you understand the basic concepts rather than on
challenging your arithmetic abilities.}}

[[File:Breakdown of Topics for the Mathematical Foundations.jpg|thumb|400px|frame|Figure 14.1: Breakdown of Topics for the Mathematical Foundations KA]]
{{IntroSection|title=Breakdown of Topics for Mathematical Foundations|body=
The breakdown of topics for the Mathematical Foundations KA is shown in Figure 14.1.}}

==Set, Relations, Functions==
{{RightSection|{{referenceLink|number=1|parts=c2}}}}

''Set''. A set is a collection of objects, called elements
of the set. A set can be represented by listing its
elements between braces, e.g., S = {1, 2, 3}.

The symbol ∈ is used to express that an element
belongs to a set, or—in other words—is a
member of the set. Its negation is represented by
∉, e.g., 1 ∈ S, but 4 ∉ S.

In a more compact representation of set using
set builder notation, {x | P(x)} is the set of all x
such that P(x) for any proposition P(x) over any
universe of discourse. Examples for some important
sets include the following:

* N = {0, 1, 2, 3, …} = the set of nonnegative integers.
* Z = {…, −3, −2, −1, 0, 1, 2, 3, …} = the set of integers.

''Finite and Infinite Set''. A set with a finite number
of elements is called a finite set. Conversely,
any set that does not have a finite number of elements
in it is an ''infinite set''. The set of all natural
numbers, for example, is an infinite set.

''Cardinality''. The cardinality of a finite set S is
the number of elements in S. This is represented
|S|, e.g., if S = {1, 2, 3}, then |S| = 3.

''Universal Set''. In general S = {x ∈ U | p(x)},
where U is the universe of discourse in which
the predicate P(x) must be interpreted. The “universe
of discourse” for a given predicate is often
referred to as the universal set. Alternately, one
may define universal set as the set of all elements.

''Set Equality''. Two sets are equal if and only if
they have the same elements, i.e.:

* X = Y ≡ ∀p (p ∈ X ↔ p ∈ Y).

''Subset''. X is a subset of set Y, or X is contained
in Y, if all elements of X are included in Y. This is
denoted by X ⊆ Y. In other words, X ⊆ Y if and only if ∀p (p ∈ X → p ∈ Y).
For example, if X = {1, 2, 3} and Y = {1, 2, 3,4, 5}, then X ⊆ Y.
If X is not a subset of Y, it is denoted as X ⊈ Y.

''Proper Subset''. X is a proper subset of Y (denoted
by X ⊂ Y) if X is a subset of Y but not equal to Y,
i.e., there is some element in Y that is not in X.
In other words, X ⊂ Y if (X ⊆ Y) ∧ (X ≠ Y).
For example, if X = {1, 2, 3}, Y = {1, 2, 3,
4}, and Z = {1, 2, 3}, then X ⊂ Y, but X is not a
proper subset of Z. Sets X and Z are equal sets.
If X is not a proper subset of Y, it is denoted
as X ⊄ Y.

''Superset''. If X is a subset of Y, then Y is called
a superset of X. This is denoted by Y ⊇ X, i.e., Y
⊇ X if and only if X ⊆ Y.
For example, if X = {1, 2, 3} and Y = {1, 2, 3,4, 5}, then Y ⊇ X.

''Empty Set''. A set with no elements is called an
''empty set''. An empty set, denoted by ∅, is also
referred to as a null or void set.

''Power Set''. The set of all subsets of a set X is
called the ''power set'' of X. It is represented as
℘(X).
For example, if X = {a, b, c}, then ℘(X) = {∅,{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. If
|X| = n, then |℘(X)| = 2<sup>n</sup>.

''Venn Diagrams''. Venn diagrams are graphic representations
of sets as enclosed areas in the plane.
For example, in Figure 14.2, the rectangle represents
the universal set and the shaded region
represents a set X.
[[File:Venn Diagram for Set X.jpg|thumb|200px|frame|Figure 14.2: Venn Diagram for Set X]]

===Set Operations===

''Intersection''. The intersection of two sets X and
Y, denoted by X ∩ Y, is the set of common elements
in both X and Y.
In other words, X ∩ Y = {p | (p ∈ X) ∧ (p ∈ Y)}.
As, for example, {1, 2, 3} ∩ {3, 4, 6} = {3}.
If X ∩ Y = f, then the two sets X and Y are said
to be a disjoint pair of sets.

A Venn diagram for set intersection is shown in
Figure 14.3. The common portion of the two sets
represents the set intersection.
[[File:Intersection of Sets X and Y.jpg|thumb|200px|frame|Figure 14.3: Intersection of Sets X and Y]]

''Union''. The union of two sets X and Y, denoted
by X ∪ Y, is the set of all elements either in X, or
in Y, or in both.
In other words, X ∪ Y = {p | (p ∈ X) ∨ (p ∈ Y)}.
As, for example, {1, 2, 3} ∪ {3, 4, 6} = {1, 2, 3, 4, 6}. 
It may be noted that |X ∪ Y| = |X| + |Y| − |X ∩ Y|.

A Venn diagram illustrating the union of two
sets is represented by the shaded region in Figure
14.4.
[[File:Union of Sets X and Y.jpg|thumb|200px|frame|Figure 14.4: Union of Sets X and Y]]

''Complement''. The set of elements in the universal
set that do not belong to a given set X is called
its complement set X'.
In other words, X' ={p | (p ∈ U) ∧ (p ∉ X)}.
The shaded portion of the Venn diagram in Figure
14.5 represents the complement set of X
[[File:Venn Diagram for Complement Set of X.jpg|thumb|200px|frame|Figure 14.5: Venn Diagram for Complement Set of X]]

''Set Difference or Relative Complement''. The set
of elements that belong to set X but not to set Y
builds the set difference of Y from X. This is represented
by X − Y.
In other words, X − Y = {p | (p ∈ X) ∧ (p ∉ Y)}.
As, for example, {1, 2, 3} − {3, 4, 6} = {1, 2}.
It may be proved that X − Y = X ∩ Y’.
Set difference X – Y is illustrated by the shaded
region in Figure 14.6 using a Venn diagram.
[[File:Venn Diagram for X − Y.jpg|thumb|200px|frame|Figure 14.6: Venn Diagram for X − Y]]

''Cartesian Product''. An ordinary pair {p, q} is
a set with two elements. In a set, the order of the
elements is irrelevant, so {p, q} = {q, p}.
In an ordered pair (p, q), the order of occurrences
of the elements is relevant. Thus, (p, q) ≠
(q, p) unless p = q. In general (p, q) = (s, t) if and
only if p = s and q = t.
Given two sets X and Y, their Cartesian product
X × Y is the set of all ordered pairs (p, q) such that
p ∈ X and q ∈ Y.
In other words, X × Y = {(p, q) | (p ∈ X) ∧ (q ∈ Y)}.
As for example, {a, b} × {1, 2} = {(a, 1), (a, 2), (b, 1), (b, 2)}

===Properties of Set===

Some of the important properties and laws of sets
are mentioned below.

1. Associative Laws:

X ∪ (Y ∪ Z) = (X ∪ Y) ∪ Z

X ∩ (Y ∩ Z) = (X ∩ Y) ∩ Z

2. Commutative Laws:

X ∪ Y = Y ∪ X  

X ∩ Y = Y ∩ X

3. Distributive Laws:

X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z)

X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z)

4. Identity Laws:

X ∪ ∅ = X  

X ∩ U = X

5. Complement Laws:

X ∪ X' = U

X ∩ X' = ∅

6. Idempotent Laws:

X ∪ X = X

X ∩ X = X

7.Bound Laws:

X ∪ U = U

X ∩ ∅ = ∅

8. Absorption Laws:

X ∪ (X ∩ Y) = X

X ∩ (X ∪ Y) = X

9. De Morgan’s Laws:

(X ∪ Y)' = X' ∩ Y'

(X ∩ Y)' = X' ∪ Y'

===Relation and Function===

A relation is an association between two sets of
information. For example, let’s consider a set
of residents of a city and their phone numbers.
The pairing of names with corresponding phone
numbers is a relation. This pairing is ''ordered'' for
the entire relation. In the example being considered,
for each pair, either the name comes first
followed by the phone number or the reverse.
The set from which the first element is drawn is
called the ''domain set'' and the other set is called
the ''range set''. The domain is what you start with
and the range is what you end up with.

A function is a ''well-behaved'' relation. A relation
R(X, Y) is well behaved if the function maps
every element of the domain set X to a single element
of the range set Y. Let’s consider domain set
X as a set of persons and let range set Y store their
phone numbers. Assuming that a person may have
more than one phone number, the relation being
considered is not a function. However, if we draw
a relation between names of residents and their
date of births with the name set as domain, then this becomes a well-behaved relation and hence a
function. This means that, while all functions are
relations, not all relations are functions. In case
of a function given an x, one gets one and exactly
one y for each ordered pair (x, y).

For example, let’s consider the following two
relations.

* A: {(3, –9), (5, 8), (7, –6), (3, 9), (6, 3)}.
* B: {(5, 8), (7, 8), (3, 8), (6, 8)}.

Are these functions as well?
In case of relation A, the domain is all the
x-values, i.e., {3, 5, 6, 7}, and the range is all the
y-values, i.e., {–9, –6, 3, 8, 9}.
Relation A is not a function, as there are two
different range values, –9 and 9, for the same
x-value of 3.
In case of relation B, the domain is same as that
for A, i.e., {3, 5, 6, 7}. However, the range is a
single element {8}. This qualifies as an example
of a function even if all the x-values are mapped
to the same y-value. Here, each x-value is distinct
and hence the function is well behaved. Relation
B may be represented by the equation y = 8.

The characteristic of a function may be verified
using a vertical line test, which is stated below:

''Given the graph of a relation, if one can draw a vertical line that crosses the graph in more than one place, then the relation is not a function''.

In this example, both lines L1 and L2 cut the
graph for the relation thrice. This signifies that
for the same x-value, there are three different
y-values for each of case. Thus, the relation is not
a function
[[File:Vertical Line Test for Function.jpg|thumb|200px|frame|Figure 14.7: Vertical Line Test for Function]]

==Basic Logic==
{{RightSection|{{referenceLink|number=1|parts=c1}}}}

===Propositional Logic===

A proposition is a statement that is either true
or false, but not both. Let’s consider declarative
sentences for which it is meaningful to assign
either of the two status values: ''true or false''. Some
examples of propositions are given below.

* 1. The sun is a star
* 2. Elephants are mammals.
* 3. 2 + 3 = 5.

However, a + 3 = b is not a proposition, as it is
neither true nor false. It depends on the values of
the variables ''a'' and ''b''.

''The Law of Excluded Middle'': For every proposition
p, either p is true or p is false.

''The Law of Contradiction'': For every proposition
p, it is not the case that p is both true and false.

Propositional logic is the area of logic that
deals with propositions. A truth table displays
the relationships between the truth values of
propositions.

A Boolean variable is one whose value is either
true or false. Computer bit operations correspond
to logical operations of Boolean variables.

The basic logical operators including negation
(¬ p), conjunction (p ∧ q), disjunction (p ∨ q),
exclusive or (p ⊕ q), and implication (p → q) are
to be studied. Compound propositions may be
formed using various logical operators.

A compound proposition that is always true is a
tautology. A compound proposition that is always
false is a contradiction. A compound proposition
that is neither a tautology nor a contradiction is a
contingency.

Compound propositions that always have the
same truth value are called logically equivalent
(denoted by ≡). Some of the common equivalences
are:

Identity laws:

p ∧ T ≡ p 

p ∨ F ≡ p

Domination laws:

p ∨ T ≡ T

p ∧ F ≡ F

Idempotent laws:

p ∨ p ≡ p

p ∧ p ≡ p

Double negation law:

¬ (¬ p) ≡ p

Commutative laws:

p ∨ q ≡ q ∨ p

p ∧ q ≡ q ∧ p

Associative laws:

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributive laws:

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

De Morgan’s laws:

¬ (p ∧ q) ≡ ¬ p ∨ ¬ q

¬ (p ∨ q) ≡ ¬ p ∧ ¬ q

===Predicate Logic===

A predicate is a verb phrase template that
describes a property of objects or a relationship
among objects represented by the variables. For
example, in the sentence, ''The flower is red'', the
template ''is red'' is a predicate. It describes the
property of a flower. The same predicate may be
used in other sentences too.

Predicates are often given a name, e.g., “Red”
or simply “R” can be used to represent the predicate
''is red''. Assuming R as the name for the predicate
''is red'', sentences that assert an object is of the
color red can be represented as ''R(x)'', where ''x'' represents
an arbitrary object. ''R(x)'' reads as ''x is red''

Quantifiers allow statements about entire collections
of objects rather than having to enumerate
the objects by name.

The Universal quantifier ∀x asserts that a sentence
is true for all values of variable x. For example, ∀x Tiger(x) → Mammal(x)
means all tigers are mammals.

The Existential quantifier ∃x asserts that a sentence
is true for at least one value of variable x. For example, ∃x Tiger(x) → Man-eater(x) means
there exists at least one tiger that is a man-eater.

Thus, while universal quantification uses
implication, the existential quantification naturally
uses conjunction.

A variable x that is introduced into a logical
expression by a quantifier is bound to the closest
enclosing quantifier.
A variable is said to be a free variable if it is not
bound to a quantifier.

Similarly, in a block-structured programming
language, a variable in a logical expression refers
to the closest quantifier within whose scope it
appears.

For example, in ∃x (Cat(x) ∧ ∀x (Black(x))), x
in Black(x) is universally quantified. The expression
implies that cats exist and everything is
black.

Propositional logic falls short in representing
many assertions that are used in computer science
and mathematics. It also fails to compare
equivalence and some other types of relationship
between propositions.

For example, the assertion a ''is greater than 1'' is not a proposition because one cannot infer
whether it is true or false without knowing the
value of ''a''. Thus, propositional logic cannot deal
with such sentences. However, such assertions
appear quite often in mathematics and we want
to infer on those assertions. Also, the pattern
involved in the following two logical equivalences
cannot be captured by propositional
logic: ''“Not all men are smokers”'' and ''“Some men don’t smoke.”'' Each of these two propositions
is treated independently in propositional logic.
There is no mechanism in propositional logic to
find out whether or not the two are equivalent to
one another. Hence, in propositional logic, each
equivalent proposition is treated individually
rather than dealing with a general formula that
covers all equivalences collectively.

Predicate logic is supposed to be a more powerful
logic that addresses these issues. In a sense,
predicate logic (also known as first-order logic
or predicate calculus) is an extension of propositional
logic to formulas involving terms and
predicates.

==Proof Techniques==
{{RightSection|{{referenceLink|number=1|parts=c1}}}}

A proof is an argument that rigorously establishes
the truth of a statement. Proofs can themselves be
represented formally as discrete structures.

Statements used in a proof include axioms
and postulates that are essentially the underlying
assumptions about mathematical structures, the
hypotheses of the theorem to be proved, and previously
proved theorems.

A theorem is a statement that can be shown to
be true.

A lemma is a simple theorem used in the proof
of other theorems.

A corollary is a proposition that can be established
directly from a theorem that has been
proved.

A conjecture is a statement whose truth value
is unknown.

When a conjecture’s proof is found, the conjecture
becomes a theorem. Many times conjectures
are shown to be false and, hence, are not theorems.

===Methods of Proving Theorems===

''Direct Proof''. Direct proof is a technique to establish
that the implication p → q is true by showing
that q must be true when p is true.

For example, to show that if n is odd then n<sup>2</sup>−1
is even, suppose n is odd, i.e., n = 2k + 1 for some
integer k:
∴ n<sup>2</sup> = (2k + 1)<sup>2</sup> = 4k<sup>2</sup> + 4k + 1

As the first two terms of the Right Hand Side
(RHS) are even numbers irrespective of the value
of k, the Left Hand Side (LHS) (i.e., n<sup>2</sup>) is an odd
number. Therefore, n<sup>2</sup>−1 is even.

''Proof by Contradiction''. A proposition p is true
by contradiction if proved based on the truth of
the implication ¬ p → q where q is a contradiction.

For example, to show that the sum of 2x + 1
and 2y − 1 is even, assume that the sum of 2x + 1
and 2y − 1is odd. In other words, 2(x + y), which
is a multiple of 2, is odd. This is a contradiction.
Hence, the sum of 2x + 1 and 2y − 1 is even.

An inference rule is a pattern establishing that
if a set of premises are all true, then it can be
deduced that a certain conclusion statement is
true. The reference rules of addition, simplification,
and conjunction need to be studied.

''Proof by Induction''. Proof by induction is done
in two phases. First, the proposition is established
to be true for a base case—typically for the positive integer 1. In the second phase, it is established
that if the proposition holds for an arbitrary
positive integer k, then it must also hold for the
next greater integer, k + 1. In other words, proof
by induction is based on the rule of inference that
tells us that the truth of an infinite sequence of
propositions P(n), ∀n ∈ [1 … ∞] is established
if P(1) is true, and secondly, ∀k ∈ [2 ... n] if P(k)
→ P(k + 1).

It may be noted here that, for a proof by mathematical
induction, it is not assumed that P(k) is
true for all positive integers k. Proving a theorem
or proposition only requires us to establish
that if it is assumed P(k) is true for any arbitrary
positive integer k, then P(k + 1) is also true. The
correctness of mathematical induction as a valid
proof technique is beyond discussion of the current
text. Let us prove the following proposition
using induction.

Proposition: The sum of the first n positive odd
integers P(n) is n<sup>2</sup>.

Basis Step: The proposition is true for n = 1 as
P(1) = 1<sup>2</sup> = 1. The basis step is complete.

Inductive Step: The induction hypothesis (IH)
is that the proposition is true for n = k, k being an
arbitrary positive integer k.

∴ 1 + 3 + 5+ … + (2k − 1) = k<sup>2</sup>

Now, it’s to be shown that P(k) → P(k + 1).

P(k + 1) = 1 + 3 + 5+ … +(2k − 1) + (2k + 1) = P(k) + (2k + 1) = k<sup>2</sup> + (2k + 1) [using IH] = k<sup>2</sup> + 2k + 1 = (k + 1)<sup>2</sup>

Thus, it is shown that if the proposition is true
for n = k, then it is also true for n = k + 1.

The basis step together with the inductive step of
the proof show that P(1) is true and the conditional
statement P(k) → P(k + 1) is true for all positive
integers k. Hence, the proposition is proved.

==Basics of Counting==
{{RightSection|{{referenceLink|number=1|parts=c6}}}}

The sum rule states that if a task t<sub>1</sub> can be done
in n<sub>1</sub> ways and a second task t<sub>2</sub> can be done in n<sub>2</sub> ways, and if these tasks cannot be done at the same time, then there are n<sub>1</sub>+ n<sub>2</sub> ways to do either
task.

* If A and B are disjoint sets, then |A ∪ B|=|A| + |B|.
* In general if A1, A2, …. , An are disjoint sets, then |A1 ∪ A2 ∪ … ∪ An| = |A1| + |A2| + … + |An|.

For example, if there are 200 athletes doing
sprint events and 30 athletes who participate in
the long jump event, then how many ways are
there to pick one athlete who is either a sprinter
or a long jumper? Using the sum rule, the answer would be 200
+ 30 = 230.

The product rule states that if a task t<sub>1</sub> can be
done in n<sub>1</sub> ways and a second task t<sub>2</sub> can be done
in n<sub>2</sub> ways after the first task has been done, then
there are n<sub>1</sub> * n<sub>2</sub> ways to do the procedure.

* If A and B are disjoint sets, then |A × B| = |A| * |B|.
* In general if A1, A2, …, An are disjoint sets, then |A1 × A2 × … × An| = |A1| * |A2| * …. * |An|.

For example, if there are 200 athletes doing
sprint events and 30 athletes who participate in
the long jump event, then how many ways are
there to pick two athletes so that one is a sprinter
and the other is a long jumper?
Using the product rule, the answer would be
200 * 30 = 6000.

The ''principle of inclusion-exclusion'' states that
if a task t<sub>1</sub> can be done in n<sub>1</sub> ways and a second
task t<sub>2</sub> can be done in n<sub>2</sub> ways at the same time
with t<sub>1</sub>, then to find the total number of ways the
two tasks can be done, subtract the number of
ways to do both tasks from n<sub>1</sub> + n<sub>2</sub>.

* If A and B are not disjoint, |A ∪ B| = |A| + |B| − |A ∩ B|.

In other words, the principle of inclusionexclusion
aims to ensure that the objects in the
intersection of two sets are not counted more than
once.

''Recursion'' is the general term for the practice
of defining an object in terms of itself. There are
recursive algorithms, recursively defined functions,
relations, sets, etc.

A recursive function is a function that calls
itself. For example, we define f(n) = 3 * f(n − 1)
for all n ∈ N and n ≠ 0 and f(0) = 5.

An algorithm is recursive if it solves a problem
by reducing it to an instance of the same problem
with a smaller input.

A phenomenon is said to be random if individual
outcomes are uncertain but the long-term pattern
of many individual outcomes is predictable.

The probability of any outcome for a random
phenomenon is the proportion of times the
outcome would occur in a very long series of
repetitions.

The probability P(A) of any event A satisfies 0
≤ P(A) ≤ 1. Any probability is a number between
0 and 1. If S is the sample space in a probability
model, the P(S) = 1. All possible outcomes
together must have probability of 1.

Two events A and B are disjoint if they have
no outcomes in common and so can never occur
together. If A and B are two disjoint events, P(A
or B) = P(A) + P(B). This is known as the addition
rule for disjoint events.

If two events have no outcomes in common,
the probability that one or the other occurs is the
sum of their individual probabilities.

Permutation is an arrangement of objects in
which the order matters without repetition. One
can choose r objects in a particular order from a
total of n objects by using <sup>n</sup>P<sub>r</sub> ways, where, <sup>n</sup>p<sub>r</sub> = n! / (n − r)!. Various notations like <sup>n</sup>P<sub>r</sub> and P(n, r)
are used to represent the number of permutations
of a set of n objects taken r at a time.

Combination is a selection of objects in which
the order does not matter without repetition. This
is different from a permutation because the order
does not matter. If the order is only changed (and
not the members) then no new combination is
formed. One can choose r objects in any order
from a total of n objects by using <sup>n</sup>C<sub>r</sub> ways, where,
<sup>n</sup>C<sub>r</sub> = n! / [r! * (n − r)!].

==Graphs and Trees==
{{RightSection|{{referenceLink|number=1|parts=c10, c11}}}}

===Graphs===

A graph G = (V, E) where V is the set of vertices
(nodes) and E is the set of edges. Edges are also
referred to as arcs or links.

F is a function that maps the set of edges E to a set of ordered or unordered pairs of elements V.
For example, in Figure 14.8, G = (V, E) where
V = {A, B, C}, E = {e1, e2, e3}, and F = {(e1, (A,C)), (e2, (C, B)), (e3, (B, A))}.
[[File:Example of a Graph.jpg|thumb|200px|frame|Figure 14.8: Example of a Graph]]
The graph in Figure 14.8 is a simple graph that
consists of a set of vertices or nodes and a set of
edges connecting unordered pairs.
The edges in simple graphs are undirected.
Such graphs are also referred to as undirected
graphs.
For example, in Figure 14.8, (e1, (A, C)) may
be replaced by (e1, (C, A)) as the pair between
vertices A and C is unordered. This holds good
for the other two edges too.
In a multigraph, more than one edge may connect
the same two vertices. Two or more connecting
edges between the same pair of vertices may
reflect multiple associations between the same
two vertices. Such edges are called parallel or
multiple edges.

For example, in Figure 14.9, the edges e3 and
e4 are both between A and B. Figure 14.9 is a
multigraph where edges e3 and e4 are multiple
edges.
[[File:Example of a Multigraph.jpg|thumb|200px|frame|Figure 14.9: Example of a Multigraph]]
In a ''pseudograph'', edges connecting a node to
itself are allowed. Such edges are called loops.

For example, in Figure 14.10, the edge e4 both
starts and ends at B. Figure 14.10 is a pseudograph
in which e4 is a loop.

A directed graph G = (V, E) consists of a set of
vertices V and a set of edges E that are ordered
pairs of elements of V. A directed graph may contain
loops.
[[File:Example of a Pseudograph.jpg|thumb|200px|frame|Figure 14.10: Example of a Pseudograph]]

For example, in Figure 14.11, G = (V, E) where
V = {A, B, C}, E = {e1, e2, e3}, and F = {(e1, (A,C)), (e2, (B, C)), (e3, (B, A))}.

In a weighted graph G = (V, E), each edge has a
weight associated with it. The weight of an edge
typically represents the numeric value associated
with the relationship between the corresponding
two vertices.
[[File:Example of a Directed Graph.jpg|thumb|200px|frame|Figure 14.11: Example of a Directed Graph]]

For example, in Figure 14.12, the weights for
the edges e1, e2, and e3 are taken to be 76, 93,
and 15 respectively. If the vertices A, B, and C
represent three cities in a state, the weights, for
example, could be the distances in miles between
these cities.
[[File:Example of a Weighted Graph.jpg|thumb|200px|frame|Figure 14.12: Example of a Weighted Graph]]

Let G = (V, E) be an undirected graph with
edge set E. Then, for an edge e ∈ E where e = {u,v}, the following terminologies are often used:

* u, v are said to be ''adjacent'' or ''neighbors'' or ''connected''.
* edge e is ''incident'' with vertices u and v.
* edge e ''connects'' u and v.
* vertices u and v are ''endpoints'' for edge e.

If vertex v ∈ V, the set of vertices in the undirected
graph G(V, E), then:

* the ''degree'' of v, deg(v), is its number of incident edges, except that any self-loops are counted twice.
* a vertex with degree 0 is called an ''isolated vertex''.
* a vertex of degree 1 is called a ''pendant vertex''.

Let G(V, E) be a directed graph. If e(u, v) is an
edge of G, then the following terminologies are
often used:

* u is ''adjacent to'' v, and v is ''adjacent from'' u.
* e ''comes from'' u and ''goes'' to v.
* e ''connects'' u to v, or e ''goes from'' u to v.
* the ''initial vertex'' of e is u
* the ''terminal vertex'' of e is v.

If vertex v is in the set of vertices for the
directed graph G(V, E), then

* ''in-degree'' of v, deg−(v), is the number of edges going to v, i.e., for which v is the terminal vertex.
* ''out-degree'' of v, deg+(v), is the number of edges coming from v, i.e., for which v is the initial vertex.
* ''degree'' of v, deg(v) = deg<sup>−</sup>(v) + deg<sup>+</sup>(v), is the sum of vs in-degree and out-degree.
* a loop at a vertex contributes 1 to both in-degree and out-degree of this vertex.

It may be noted that, following the definitions
above, the degree of a node is unchanged whether
we consider its edges to be directed or undirected.

In an undirected graph, a path of length n from
u to v is a sequence of n adjacent edges from vertex
u to vertex v.

* A path is a ''circuit'' if u=v.
* A path ''traverses'' the vertices along it.
* A path is ''simple'' if it contains no edge more than once.

A cycle on n vertices C<sub>n</sub> for any n ≥ 3 is a simple
graph where V = {v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub>} and E = {{v<sub>1</sub>, v<sub>2</sub>}, {v<sub>2</sub>, v<sub>3</sub>}, … , {v<sub>n−1</sub>, v<sub>n</sub>}, {v<sub>n</sub>, v<sub>1</sub>}}.

For example, Figure 14.13 illustrates two
cycles of length 3 and 4.
[[File:Example of Cycles C3 and C4.jpg|thumb|200px|frame|Figure 14.13: Example of Cycles C<sub>3</sub> and C<sub>4</sub>]]

An adjacency list is a table with one row per
vertex, listing its adjacent vertices. The adjacency
listing for a directed graph maintains a listing of
the terminal nodes for each of the vertex in the
graph.
[[File:Adjacency Lists for Graphs in Figures 14.10 and 14.11.jpg|thumb|200px|frame|Figure 14.9: Adjacency Lists for Graphs in Figures 14.10 and 14.11]]

For example, Figure 14.14 illustrates the adjacency
lists for the pseudograph in Figure 14.10
and the directed graph in Figure 14.11. As the
out-degree of vertex C in Figure 14.11 is zero,
there is no entry against C in the adjacency list.

Different representations for a graph—like
adjacency matrix, incidence matrix, and adjacency
lists—need to be studied.

===Trees===

A tree T(N, E) is a hierarchical data structure of n = |N| nodes with a specially designated root node
R while the remaining n − 1 nodes form subtrees
under the root node R. The number of edges |E| in
a tree would always be equal to |N| − 1.

The subtree at node X is the subgraph of the
tree consisting of node X and its descendants and
all edges incident to those descendants. As an
alternate to this recursive definition, a tree may
be defined as a connected undirected graph with
no simple circuits.

However, one should remember that a tree is
strictly hierarchical in nature as compared to a
graph, which is flat. In case of a tree, an ordered
pair is built between two nodes as parent and
child. Each child node in a tree is associated
with only one parent node, whereas this restriction
becomes meaningless for a graph where no
parent-child association exists.

An undirected graph is a tree if and only if
there is a unique simple path between any two of
its vertices.

Figure 14.15 presents a tree T(N, E) where the
set of nodes N = {A, B, C, D, E, F, G, H, I, J, K}.
The edge set 
E is {(A, B), (A, C), (A, D), (B, E), (B, F), (B, G), (C, H), (C, I), (D, J), (D, K)}.
[[File:Example of a Tree.jpg|thumb|200px|frame|Figure 14.15: Example of a Tree]]

The parent of a nonroot node v is the unique
node u with a directed edge from u to v. Each
node in the tree has a unique parent node except
the root of the tree.

For example, in Figure 14.15, root node A is
the parent node for nodes B, C, and D. Similarly,
B is the parent of E, F, G, and so on. The root
node A does not have any parent.

A node that has children is called an internal
node.
For example, in Figure 14.15, node A or node B
are examples of internal nodes.
The degree of a node in a tree is the same as its
number of children.
For example, in Figure 14.15, root node A and
its child B are both of degree 3. Nodes C and D
have degree 2.

The distance of a node from the root node in
terms of number of hops is called its ''level''. Nodes
in a tree are at different levels. The root node is at level 0. Alternately, the level of a node X is the
length of the unique path from the root of the tree
to node X.

For example, root node A is at level 0 in Figure
14.15. Nodes B, C, and D are at level 1. The
remaining nodes in Figure 14.15 are all at level 2.
The height of a tree is the maximum of the levels
of nodes in the tree.
For example, in Figure 14.15, the height of the
tree is 2.

A node is called a ''leaf'' if it has no children. The
degree of a leaf node is 0.
For example, in Figure 14.15, nodes E through
K are all leaf nodes with degree 0.
The ancestors or predecessors of a nonroot
node X are all the nodes in the path from root to
node X.
For example, in Figure 14.15, nodes A and D
form the set of ancestors for J.

The successors or descendents of a node X are
all the nodes that have X as its ancestor. For a tree
with n nodes, all the remaining n − 1 nodes are
successors of the root node.
For example, in Figure 14.15, node B has successors
in E, F, and G.
''If node X is an ancestor of node Y, then node Y is a successor of X''.

Two or more nodes sharing the same parent
node are called ''sibling'' nodes.
For example, in Figure 14.15, nodes E and G
are siblings. However, nodes E and J, though
from the same level, are not sibling nodes.
''Two sibling nodes are of the same level, but two nodes in the same level are not necessarily siblings''.

A tree is called an ''ordered tree'' if the relative
position of occurrences of children nodes is
significant.
For example, a family tree is an ordered tree
if, as a rule, the name of an elder sibling appears
always before (i.e., on the left of) the younger
sibling.

In an unordered tree, the relative position of
occurrences between the siblings does not bear
any significance and may be altered arbitrarily.

A binary tree is formed with zero or more nodes
where there is a root node R and all the remaining
nodes form a pair of ordered subtrees under the
root node.

In a binary tree, no internal node can have more
than two children. However, one must consider
that besides this criterion in terms of the degree
of internal nodes, a binary tree is always ordered.
If the positions of the left and right subtrees for
any node in the tree are swapped, then a new tree
is derived. For example, in Figure 14.16, the two binary
trees are different as the positions of occurrences
of the children of A are different in the two trees.
[[File:Examples of Binary Trees.jpg|thumb|200px|frame|Figure 14.16: Examples of Binary Trees]]

According to [1*], a binary tree is called a full
binary tree if every internal node has exactly two
children.
For example, the binary tree in Figure 14.17
is a full binary tree, as both of the two internal
nodes A and B are of degree 2.
A full binary tree following the definition
above is also referred to as a ''strictly binary tree''.
[[File:Example of a Full Binary Tree.jpg|thumb|200px|frame|Figure 14.17: Example of a Full Binary Tree]]

For example, both binary trees in Figure 14.18
are complete binary trees. The tree in Figure
14.18(a) is a complete as well as a full binary
tree. A complete binary tree has all its levels,
except possibly the last one, filled up to capacity.
In case the last level of a complete binary tree is
not full, nodes occur from the leftmost positions
available. 
[[File:Example of Complete Binary Trees.jpg|thumb|200px|frame|Figure 14.18: Example of Complete Binary Trees]]
Interestingly, following the definitions above,
the tree in Figure 14.18(b) is a complete but not
full binary tree as node B has only one child in D.
On the contrary, the tree in Figure 14.17 is a full
—but not complete—binary tree, as the children
of B occur in the tree while the children of C do
not appear in the last level.
A binary tree of height H is balanced if all its
leaf nodes occur at levels H or H − 1.
For example, all three binary trees in Figures
14.17 and 14.18 are balanced binary trees.

There are at most 2<sup>H</sup> leaves in a binary tree of
height H. In other words, if a binary tree with L
leaves is full and balanced, then its height is H =
&lceil;log<sub>2</sub>L&rceil;.

For example, this statement is true for the
two trees in Figures 14.17 and 14.18(a) as both
trees are full and balanced. However, the expression
above does not match for the tree in Figure
14.18(b) as it is not a full binary tree.

A binary search tree (BST) is a special kind of
binary tree in which each node contains a distinct
key value, and the key value of each node in the
tree is less than every key value in its right subtree
and greater than every key value in its left subtree.

A traversal algorithm is a procedure for systematically
visiting every node of a binary tree.
Tree traversals may be defined recursively.

If T is binary tree with root R and the remaining
nodes form an ordered pair of nonnull left
subtree T<sub>L</sub> and nonnull right subtree T<sub>R</sub> below R,
then the preorder traversal function PreOrder(T)
is defined as:

PreOrder(T) = R, PreOrder(T<sub>L</sub>), PreOrder(T<sub>R</sub>) … eqn. 1

The recursive process of finding the preorder
traversal of the subtrees continues till the subtrees
are found to be Null. Here, commas have
been used as delimiters for the sake of improved
readability.

The postorder and in-order may be similarly
defined using eqn. 2 and eqn. 3 respectively.

PostOrder(T) = PostOrder(T<sub>L</sub>), PostOrder(T<sub>R</sub>), R … eqn 2

InOrder(T) = InOrder(T<sub>L</sub>), R, InOrder(T<sub>R</sub>) …eqn 3

For example, the tree in Figure 14.19 is a binary
search tree (BST). The preorder, postorder, and
in-order traversal outputs for the BST are given
below in their respective order.
[[File:A Binary Search Tree.jpg|thumb|200px|frame|Figure 14.19: A Binary Search Tree]]

Preorder output: 9, 5, 2, 1, 4, 7, 6, 8, 13, 11, 10, 15

Postorder output: 1, 4, 2, 6, 8, 7, 5, 10, 11, 15, 13, 9

In-order output: 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15

Further discussion on trees and their usage has
been included in section 6, Data Structure and Representation,
of the Computing Foundations KA.

==Discrete Probability==
{{RightSection|{{referenceLink|number=1|parts=c7}}}}

Probability is the mathematical description of
randomness. Basic definition of probability and randomness has been defined in section 4 of this
KA. Here, let us start with the concepts behind
probability distribution and discrete probability.

A probability model is a mathematical description
of a random phenomenon consisting of two
parts: a sample space S and a way of assigning
probabilities to events. The sample space defines
the set of all possible outcomes, whereas an event
is a subset of a sample space representing a possible
outcome or a set of outcomes.

A random variable is a function or rule that
assigns a number to each outcome. Basically, it
is just a symbol that represents the outcome of an
experiment.

For example, let X be the number of heads
when the experiment is flipping a coin n times.
Similarly, let S be the speed of a car as registered
on a radar detector.

The values for a random variable could be discrete
or continuous depending on the experiment.
A discrete random variable can hold all possible
outcomes without missing any, although it
might take an infinite amount of time.
A continuous random variable is used to measure
an uncountable number of values even if an
infinite amount of time is given.

For example, if a random variable X represents
an outcome that is a real number between 1 and
100, then X may have an infinite number of values.
One can never list all possible outcomes for
X even if an infinite amount of time is allowed.
Here, X is a continuous random variable. On
the contrary, for the same interval of 1 to 100,
another random variable Y can be used to list all
the integer values in the range. Here, Y is a discrete
random variable.

An upper-case letter, say X, will represent
the ''name'' of the random variable. Its lower-case
counterpart, x, will represent the ''value'' of the random
variable.

The probability that the random variable X will
equal x is:

P(X = x) or, more simply, P(x).

A probability distribution (density) function is
a table, formula, or graph that describes the values
of a random variable and the probability associated
with these values.

Probabilities associated with discrete random
variables have the following properties:

i. 0 ≤ P(x) ≤ 1 for all x

ii. ΣP(x) = 1

A discrete probability distribution can be represented
as a discrete random variable.
[[File:A Discrete Probability Function for a Rolling Die.jpg|thumb|300px|frame|Figure 14.20: A Discrete Probability Function for a Rolling Die]]

The mean μ of a probability distribution model
is the sum of the product terms for individual
events and its outcome probability. In other
words, for the possible outcomes x<sub>1</sub>, x<sub>2</sub>, … , x<sub>n</sub>
in a sample space S if p<sub>k</sub> is the probability of outcome
x<sub>k</sub>, the mean of this probability would be μ = x<sub>1</sub>p<sub>1</sub> + x<sub>2</sub>p<sub>2</sub> + … + x<sub>n</sub>p<sub>n</sub>.

For example, the mean of the probability density
for the distribution in Figure 14.20 would be

1 * (1/6) + 2 * (1/6) + 3 * (1/6) + 4 * (1/6) + 5 * (1/6) + 6 * (1/6) = 21 * (1/6) = 3.5

Here, the sample space refers to the set of all
possible outcomes.

The variance s<sup>2</sup> of a discrete probability model is:
s<sup>2</sup> = (x<sub>1</sub> – μ)<sup>2</sup>p<sub>1</sub> + (x<sub>2</sub> – μ)<sup>2</sup>p<sub>2</sub> + … + (x<sub>k</sub> – μ)<sup>2</sup>p<sub>k</sub>.

The ''standard deviations'' is the square root of the
variance.

For example, for the probability distribution in
Figure 14.20, the variation σ<sup>2</sup> would be

s<sup>2</sup> = [(1 – 3.5)<sup>2</sup> * (1/6) + (2 – 3.5)<sup>2</sup> * (1/6) +
(3 – 3.5)<sup>2</sup> * (1/6) + (4 – 3.5)<sup>2</sup> * (1/6) + (5 – 3.5)<sup>2</sup> * (1/6) + (6 – 3.5)<sup>2</sup> * (1/6)] = (6.25 + 2.25 + 0.25 + 0.5 + 2.25 + 6.25) * (1/6) = 17.5 * (1/6) = 2.90

∴ standard deviation s =

These numbers indeed aim to derive the average
value from repeated experiments. This is
based on the single most important phenomenon
of probability, i.e., the average value from
repeated experiments is likely to be close to the
expected value of one experiment. Moreover,
the average value is more likely to be closer to
the expected value of any one experiment as the
number of experiments increases.

==Finite State Machines==
{{RightSection|{{referenceLink|number=1|parts=c13}}}}

A computer system may be abstracted as a mapping
from state to state driven by inputs. In other
words, a system may be considered as a transition
function T: S × I → S × O, where S is the set of
states and I, O are the input and output functions.
If the state set S is finite (not infinite), the system
is called a ''finite state machine'' (FSM).

Alternately, a finite state machine (FSM) is a
mathematical abstraction composed of a finite
number of states and transitions between those
states. If the domain S × I is reasonably small,
then one can specify T explicitly using diagrams
similar to a flow graph to illustrate the way logic
flows for different inputs. However, this is practical
only for machines that have a very small
information capacity.

An FSM has a finite internal memory, an input
feature that reads symbols in a sequence and one
at a time, and an output feature.

The operation of an FSM begins from a start
state, goes through transitions depending on input
to different states, and can end in any valid state.
However, only a few of all the states mark a successful
flow of operation. These are called ''accept states''.

The information capacity of an FSM is
C = log |S|. Thus, if we represent a machine having
an information capacity of C bits as an FSM, then
its state transition graph will have |S| = 2<sup>C</sup> nodes.

A finite state machine is formally defined as M = (S, I, O, f, g, s<sub>0</sub>).

* S is the state set;
* I is the set of input symbols;
* O is the set of output symbols;
* f is the state transition function;
* g is the output function;
* and s<sub>0</sub> is the initial state.

Given an input x ∈ I on state S<sub>k</sub>, the FSM
makes a transition to state S<sub>h</sub> following state transition
function f and produces an output y ∈ O
using the output function g.

For example, Figure 14.21 illustrates an FSM
with S<sub>0</sub> as the start state and S<sub>1</sub> as the final state.
Here, S = {S<sub>0</sub>, S<sub>1</sub>, S<sub>2</sub>}; I = {0, 1}; O = {2, 3}; f(S<sub>0</sub>,
0) = S<sub>2</sub>, f(S<sub>0</sub>, 1) = S<sub>1</sub>, f(S<sub>1</sub>, 0) = S<sub>2</sub>, f(S<sub>1</sub>, 1) = S<sub>2</sub>, f(S<sub>2</sub>,
0) = S<sub>2</sub>, f(S<sub>2</sub>, 1) = S<sub>0</sub>; g(S<sub>0</sub>, 0) = 3, g(S<sub>0</sub>, 1) = 2, g(S<sub>1</sub>,
0) = 3, g(S<sub>1</sub>, 1) = 2, g(S<sub>2</sub>, 0) = 2, g(S<sub>2</sub>, 1) = 3.
[[File:Example of an FSM.jpg|thumb|200px|frame|Figure 14.21: Example of an FSM]]

The state transition and output values for different
inputs on different states may be represented
using a state table. The state table for the FSM in
Figure 14.21 is shown in Figure 14.22. Each pair
against an input symbol represents the new state
and the output symbol.

For example, Figures 14.22(a) and 14.22(b) are
two alternate representations of the FSM in Figure
14.21.
[[File:Tabular Representation of an FSM.jpg|thumb|200px|frame|Figure 14.22: Tabular Representation of an FSM]]

==Grammars==
{{RightSection|{{referenceLink|number=1|parts=c13}}}}

The grammar of a natural language tells us
whether a combination of words makes a valid
sentence. Unlike natural languages, a formal language
is specified by a well-defined set of rules for
syntaxes. The valid sentences of a formal language
can be described by a grammar with the help of
these rules, referred to as ''production rules''.

A formal language is a set of finite-length
words or strings over some finite alphabet, and
a grammar specifies the rules for formation of
these words or strings. The entire set of words
that are valid for a grammar constitutes the language
for the grammar. Thus, the grammar G is
any compact, precise mathematical definition of a
language L as opposed to just a raw listing of all
of the language’s legal sentences or examples of
those sentences.

A grammar implies an algorithm that would
generate all legal sentences of the language.
There are different types of grammars.

A phrase-structure or Type-0 grammar G = (V,T, S, P) is a 4-tuple in which:

* V is the vocabulary, i.e., set of words.
* T ⊆ V is a set of words called terminals.
* S ∈ N is a special word called the start symbol.
* P is the set of productions rules for substituting one sentence fragment for another.

There exists another set N = V − T of words
called nonterminals. The nonterminals represent
concepts like ''noun''. Production rules are applied
on strings containing nonterminals until no more
nonterminal symbols are present in the string.
The start symbol S is a nonterminal.

The language generated by a formal grammar
G, denoted by L(G), is the set of all strings over
the set of alphabets V that can be generated, starting
with the start symbol, by applying production
rules until all the nonterminal symbols are
replaced in the string.

For example, let G = ({S, A, a, b}, {a, b}, S, {S
→ aA, S → b, A → aa}). Here, the set of terminals
are N = {S, A}, where S is the start symbol.
The three production rules for the grammar are
given as P1: S → aA; P2: S → b; P3: A → aa.

Applying the production rules in all possible
ways, the following words may be generated
from the start symbol.

S → aA (using P1 on start symbol)

→ aaa (using P3)

S → b (using P2 on start symbol)

Nothing else can be derived for G. Thus, the
language of the grammar G consists of only two
words: L(G) = {aaa, b}.

===Language Recognition===

Formal grammars can be classified according to the
types of productions that are allowed. The Chomsky
hierarchy (introduced by Noam Chomsky in
1956) describes such a classification scheme.

As illustrated in Figure 14.23, we infer the following
on different types of grammars:

* 1. Every regular grammar is a context-free grammar (CFG).
* 2. Every CFG is a context-sensitive grammar (CSG).
* 3. Every CSG is a phrase-structure grammar (PSG).
[[File:Chomsky Hierarchy of Grammars.jpg|thumb|200px|frame|Figure 14.23: Chomsky Hierarchy of Grammars]]

''Context-Sensitive Grammar'': All fragments in
the RHS are either longer than the corresponding
fragments in the LHS or empty, i.e., if b → a, then |b| < |a| or a = ∅.

A formal language is context-sensitive if a context-
sensitive grammar generates it.
Context-Free Grammar: All fragments in the
LHS are of length 1, i.e., if A → a, then |A| = 1
for all A ∈ N.

The term context-free derives from the fact that
A can always be replaced by a, regardless of the
context in which it occurs.

A formal language is context-free if a contextfree
grammar generates it. Context-free languages
are the theoretical basis for the syntax of
most programming languages.

''Regular Grammar''. All fragments in the RHS
are either single terminals or a pair built by a
terminal and a nonterminal; i.e., if A → a, then
either a ∈ T, or a = cD, or a = Dc for c ∈ T, D ∈ N.

If a = cD, then the grammar is called a right
linear grammar. On the other hand, if a = Dc, then
the grammar is called a left linear grammar. Both
the right linear and left linear grammars are regular
or Type-3 grammar.

The language L(G) generated by a regular
grammar G is called a regular language.

A regular expression A is a string (or pattern)
formed from the following six pieces of information:
a ∈ S, the set of alphabets, e, 0 and the
operations, OR (+), PRODUCT (.), CONCATENATION
(*). The language of G, L(G) is equal to
all those strings that match G, L(G) = {x ∈ S*|x matches G}.

For any a ∈ S, L(a) = a; L(e) = {ε}; L(0) = 0.
+ functions as an or, L(A + B) = L(A) ∪ L(B).
. creates a product structure, L(AB) = L(A) .
L(B).
denotes concatenation, L(A*) = {x1x2…xn |
xi ∈ L(A) and n ³ 0}

For example, the regular expression (ab)*
matches the set of strings: {e, ab, abab, ababab,
abababab, …}.

For example, the regular expression (aa)*
matches the set of strings on one letter a that have
even length.

For example, the regular expression (aaa)* +
(aaaaa)* matches the set of strings of length equal
to a multiple of 3 or 5.

==Numerical Precision, Accuracy, and Errors==
{{RightSection|{{referenceLink|number=2|parts=c2}}}}

The main goal of numerical analysis is to
develop efficient algorithms for computing precise
numerical values of functions, solutions of
algebraic and differential equations, optimization
problems, etc.

A matter of fact is that all digital computers can
only store finite numbers. In other words, there
is no way that a computer can represent an infinitely
large number—be it an integer, rational
number, or any real or all complex numbers (see
section 10, Number Theory). So the mathematics
of approximation becomes very critical to handle
all the numbers in the finite range that a computer
can handle.

Each number in a computer is assigned a location
or word, consisting of a specified number of
binary digits or bits. A k bit word can store a total
of N = 2<sup>k</sup> different numbers.

For example, a computer that uses 32 bit arithmetic
can store a total of N = 2<sup>32</sup> ≈ 4.3 × 10<sup>9</sup> different
numbers, while another one that uses 64
bits can handle N’ = 2<sup>64</sup> ≈ 1.84 × 10<sup>19</sup> different
numbers. The question is how to distribute these
N numbers over the real line for maximum efficiency
and accuracy in practical computations.

One evident choice is to distribute them evenly,
leading to fixed-point arithmetic. In this system,
the first bit in a word is used to represent a sign
and the remaining bits are treated for integer values.
This allows representation of the integers
from 1 − ½N, i.e., = 1 − 2<sup>k−1</sup> to 1. As an approximating
method, this is not good for noninteger
numbers.

Another option is to space the numbers closely
together—say with a uniform gap of 2<sup>−n</sup>—and so
distribute the total N numbers uniformly over the
interval −2<sup>−n−1</sup>N < x ≤ 2<sup>−n−1</sup>N. Real numbers lying
between the gaps are represented by either ''rounding''
(meaning the closest exact representative) or ''chopping'' (meaning the exact representative
immediately below —or above, if negative—the
number).

Numbers lying beyond the range must be represented
by the largest (or largest negative) number
that can be represented. This becomes a symbol
for overflow. Overflow occurs when a computation
produces a value larger than the maximum
value in the range.

When processing speed is a significant bottleneck,
the use of the fixed-point representations
is an attractive and faster alternative to the more
cumbersome floating-point arithmetic most commonly
used in practice.

Let’s define a couple of very important terms:
''accuracy'' and ''precision'' as associated with numerical
analysis.

Accuracy is the closeness with which a measured
or computed value agrees with the true value.
Precision, on the other hand, is the closeness
with which two or more measured or computed
values for the same physical substance agree with
each other. In other words, precision is the closeness
with which a number represents an exact
value.

Let x be a real number and let x* be an approximation.
The absolute error in the approximation
x* ≈ x is defined as | x* − x |. The relative error
is defined as the ratio of the absolute error to the
size of x, i.e., |x* − x| / | x |, which assumes x ¹ 0;
otherwise, relative error is not defined.

For example, 1000000 is an approximation to
1000001 with an absolute error of 1 and a relative
error of 10<sup>−6</sup>, while 10 is an approximation of 11
with an absolute error of 1 and a relative error of
0.1. Typically, relative error is more intuitive and
the preferred determiner of the size of the error.
The present convention is that errors are always
≥ 0, and are = 0 if and only if the approximation
is exact.

An approximation x* has k significant decimal
digits if its relative error is < 5 × 10<sup>−k−1</sup>. This
means that the first k digits of x* following its
first nonzero digit are the same as those of x.

Significant digits are the digits of a number that
are known to be correct. In a measurement, one
uncertain digit is included.

For example, measurement of length with
a ruler of 15.5 mm with ±0.5 mm maximum allowable error has 2 significant digits, whereas
a measurement of the same length using a caliper
and recorded as 15.47 mm with ±0.01 mm maximum
allowable error has 3 significant digits.

==Number Theory==
{{RightSection|{{referenceLink|number=1|parts=c4}}}}

Number theory is one of the oldest branches
of pure mathematics and one of the largest. Of
course, it concerns questions about numbers,
usually meaning whole numbers and fractional or
rational numbers. The different types of numbers
include integer, real number, natural number,
complex number, rational number, etc.

===Divisibility===

Let’s start this section with a brief description of
each of the above types of numbers, starting with
the natural numbers.

''Natural Numbers''. This group of numbers starts
at 1 and continues: 1, 2, 3, 4, 5, and so on. Zero
is not in this group. There are no negative or fractional
numbers in the group of natural numbers.
The common mathematical symbol for the set of
all natural numbers is N.

''Whole Numbers''. This group has all of the natural
numbers in it plus the number 0.

Unfortunately, not everyone accepts the above
definitions of natural and whole numbers. There
seems to be no general agreement about whether
to include 0 in the set of natural numbers.

Many mathematicians consider that, in Europe,
the sequence of natural numbers traditionally
started with 1 (0 was not even considered to be
a number by the Greeks). In the 19th century, set
theoreticians and other mathematicians started
the convention of including 0 in the set of natural
numbers.

''Integers''. This group has all the whole numbers
in it and their negatives. The common mathematical
symbol for the set of all integers is Z, i.e., Z = {…, −3, −2, −1, 0, 1, 2, 3, …}.

''Rational Numbers''. These are any numbers that
can be expressed as a ratio of two integers. The
common symbol for the set of all rational numbers
is Q. Rational numbers may be classified into
three types, based on how the decimals act. The decimals either do not exist, e.g., 15, or, when
decimals do exist, they may terminate, as in 15.6,
or they may repeat with a pattern, as in 1.666...,
(which is 5/3).

''Irrational Numbers''. These are numbers that
cannot be expressed as an integer divided by an
integer. These numbers have decimals that never
terminate and never repeat with a pattern, e.g., PI
or √2.

''Real Numbers''. This group is made up of all the
rational and irrational numbers. The numbers that
are encountered when studying algebra are real
numbers. The common mathematical symbol for
the set of all real numbers is R.

''Imaginary Numbers''. These are all based on the
imaginary number ''i''. This imaginary number is
equal to the square root of −1. Any real number
multiple of ''i'' is an imaginary number, e.g., ''i'', ''5i'',
''3.2i'', ''−2.6i'', etc.

''Complex Numbers''. A complex number is a
combination of a real number and an imaginary
number in the form a + b''i''. The real part is a, and
b is called the imaginary part. The common mathematical
symbol for the set of all complex numbers
is C.

For example, 2 + 3''i'', 3−5''i'', 7.3 + 0''i'', and 0 + 5''i''.
Consider the last two examples:

7.3 + 0''i'' is the same as the real number 7.3.
Thus, all real numbers are complex numbers with
zero for the imaginary part.
Similarly, 0 + 5''i'' is just the imaginary number
5''i''. Thus, all imaginary numbers are complex
numbers with zero for the real part.

Elementary number theory involves divisibility
among integers. Let a, b ∈ Z with a ≠ 0.The expression
a|b, i.e., ''a divides b'' if ∃c ∈ Z: b = ac, i.e., there
is an integer c such that c times a equals b.

For example, 3|−12 is true, but 3|7 is false.

If ''a'' divides ''b'', then we say that a is ''a'' factor of
''b'' or ''a'' is a divisor of ''b'', and ''b'' is a multiple of ''a''.
''b'' is even if and only if 2|''b''.

Let ''a'', ''d'' ∈ Z with d > 1. Then ''a mod d'' denotes
that the remainder ''r'' from the division algorithm
with dividend ''a'' and divisor ''d'', i.e., the remainder
when a is divided by d. We can compute (''a mod d'') by: ''a'' − ''d'' *  &lfloor;a/d&rfloor;, where &lfloor;a/d&rfloor; represents the floor of the real number.

Let Z<sup>+</sup> = {n ∈ Z | n > 0} and ''a'', ''b'' ∈ Z, m ∈ Z+,
then a is congruent to ''b modulo m'', written as ''a'' ≡ ''b'' (''mod m''), if and only if ''m'' | ''a−b''.

===Prime Number, GCD===

An integer p > 1 is prime if and only if it is not
the product of any two integers greater than 1,
i.e., p is prime if p > 1 ∧ ∃ ¬ a, b ∈ N: a > 1, b >
1, a * b = p.

The only positive factors of a prime p are 1
and p itself. For example, the numbers 2, 13, 29,
61, etc. are prime numbers. Nonprime integers
greater than 1 are called composite numbers. A
composite number may be composed by multiplying
two integers greater than 1.

There are many interesting applications of
prime numbers; among them are the publickey
cryptography scheme, which involves the
exchange of public keys containing the product
''p''*''q'' of two random large primes ''p'' and ''q'' (a private
key) that must be kept secret by a given party.
The greatest common divisor gcd(a, b) of integers
a, b is the greatest integer d that is a divisor
both of a and of b, i.e.,

d = gcd(a, b) for max(d: d|a ∧ d|b)

For example, gcd(24, 36) = 12.

Integers ''a'' and ''b'' are called relatively prime or
coprime if and only if their GCD is 1.

For example, neither 35 nor 6 are prime, but
they are coprime as these two numbers have no
common factors greater than 1, so their GCD is 1.

A set of integers X = {i<sub>1</sub>, i<sub>2</sub>, …} is relatively
prime if all possible pairs i<sub>h</sub>, i<sub>k</sub>, h ≠ k drawn from
the set X are relatively prime.

==Algebraic Structures==

This section introduces a few representations
used in higher algebra. An algebraic structure
consists of one or two sets closed under some
operations and satisfying a number of axioms,
including none.

For example, group, monoid, ring, and lattice
are examples of algebraic structures. Each of
these is defined in this section.

===Group===

A set S closed under a binary operation • forms a
group if the binary operation satisfies the following
four criteria:

* Associative: ∀a, b, c ∈ S, the equation (a • b) • c = a • (b • c) holds.
* Identity: There exists an identity element I ∈ S such that for all a ∈ S, I • a = a • I = a. 
* Inverse: Every element a ∈ S, has an inverse a' ∈ S with respect to the binary operation, i.e., a • a' = I; for example, the set of integers Z with respect to the addition operation is a group. The identity element of the set is 0 for
the addition operation. ∀x ∈ Z, the inverse of x would be –x, which is also included in Z.
* Closure property: ∀a, b ∈ S, the result of the operation a • b ∈ S. 
* A group that is commutative, i.e., a • b = b • a, is known as a commutative or Abelian group.

The set of natural numbers N (with the operation
of addition) is not a group, since there is no
inverse for any x > 0 in the set of natural numbers.
Thus, the third rule (of inverse) for our operation
is violated. However, the set of natural number
has some structure.

Sets with an associative operation (the first
condition above) are called semigroups; if they
also have an identity element (the second condition),
then they are called monoids.

Our set of natural numbers under addition is
then an example of a monoid, a structure that
is not quite a group because it is missing the
requirement that every element have an inverse
under the operation.

A monoid is a set S that is closed under a single
associative binary operation • and has an identity
element I ∈ S such that for all a ∈ S, I • a = a • I = a. A monoid must contain at least one element.

For example, the set of natural numbers N
forms a commutative monoid under addition with
identity element 0. The same set of natural numbers
N also forms a monoid under multiplication
with identity element 1. The set of positive integers
P forms a commutative monoid under multiplication
with identity element 1.

It may be noted that, unlike those in a group,
elements of a monoid need not have inverses. A monoid can also be thought of as a semigroup
with an identity element.

A ''subgroup'' is a group ''H'' contained within a
bigger one, ''G'', such that the identity element of
''G'' is contained in ''H'', and whenever h<sub>1</sub> and h<sub>2</sub> are
in ''H'', then so are h<sub>1</sub> • h<sub>2</sub> and h<sub>1</sub><sup>−1</sup>. Thus, the elements
of ''H'', equipped with the group operation on
''G'' restricted to ''H'', indeed form a group.

Given any subset ''S'' of a group ''G'', the subgroup
generate ''S'' and their inverses. It is the smallest subgroup
of ''G'' containing ''S''.

For example, let ''G'' be the Abelian group whose
elements are ''G' = {0, 2, 4, 6, 1, 3, 5, 7} and whose
group operation is addition modulo 8. This group
has a pair of nontrivial subgroups: ''J'' = {0, 4} and
''H'' = {0, 2, 4, 6}, where ''J'' is also a subgroup of ''H''.

In group theory, a cyclic group is a group that
can be generated by a single element, in the
sense that the group has an element ''a'' (called the
''generator'' of the group) such that, when written
multiplicatively, every element of the group is a
power of ''a''.
A group G is cyclic if G = {a<sup>n</sup> for any integer n}.

Since any group generated by an element in a
group is a subgroup of that group, showing that
the only subgroup of a group G that contains a is
G itself suffices to show that G is cyclic.

For example, the group ''G'' = {0, 2, 4, 6, 1, 3, 5,
7}, with respect to addition modulo 8 operation,
is cyclic. The subgroups ''J'' = {0, 4} and ''H'' = {0, 2,
4, 6} are also cyclic.

===Rings===

If we take an Abelian group and define a second
operation on it, a new structure is found that is
different from just a group. If this second operation
is associative and is distributive over the
first, then we have a ring.

A ring is a triple of the form (S, +, •), where (S,
+) is an Abelian group, (S, •) is a semigroup, and
• is distributive over +; i.e., “ a, b, c ∈ S, the equation
a • (b + c) = (a • b) + (a • c) holds. Further, if
• is commutative, then the ring is said to be commutative.
If there is an identity element for the • operation, then the ring is said to have an identity.

For example, (Z, +, *), i.e., the set of integers Z,
with the usual addition and multiplication operations,
is a ring. As (Z, *) is commutative, this ring
is a commutative or Abelian ring. The ring has 1
as its identity element.

Let’s note that the second operation may not
have an identity element, nor do we need to find
an inverse for every element with respect to this
second operation. As for what distributive means,
intuitively it is what we do in elementary mathematics
when performing the following change: 
a * (b + c) = (a * b) + (a * c).

A field is a ring for which the elements of the
set, excluding 0, form an Abelian group with the
second operation.

A simple example of a field is the field of rational
numbers (R, +, *) with the usual addition
and multiplication operations. The numbers of
the format ''a''/''b'' ∈ R, where ''a'', ''b'' are integers and
''b'' ≠ 0. The additive inverse of such a fraction is
simply −''a''/''b'', and the multiplicative inverse is ''b''/''a''
provided that ''a'' ≠ 0.

{{EndSection|title=References|body=
{{reference
|number=1
|author=K. Rosen
|article=
|publication=Discrete Mathematics and Its Applications
|edition=7th ed.
|publisher=McGraw-Hill
|issue=
|date=2011
|part=
|link=
}}{{reference
|number=2
|author=E.W. Cheney and D.R. Kincaid
|article=
|publication=Numerical Mathematics and Computing
|edition=6th ed.
|publisher=Brooks/Cole
|issue=
|date=2007
|part=
|link=
}}{{ReferenceList}}
}}
{{EndSection|title=Acknowledgments|body=

The author thankfully acknowledges the contribution
of Prof. Arun Kumar Chatterjee, Ex-Head,
Department of Mathematics, Manipur University,
India, and Prof. Devadatta Sinha, Ex-Head,
Department of Computer Science and Engineering,
University of Calcutta, India, in preparing
this chapter on Mathematical Foundations.}}