Introduction to Discrete Structures --- Whats and Whys
What is Discrete Mathematics ?
Discrete mathematics is mathematics that deals with discrete objects.
Discrete objects are those which are separated from (not connected to/distinct
from)
each other.
Integers (aka whole numbers), rational numbers (ones that can be
expressed as the quotient of
two integers), automobiles, houses, people etc. are all discrete objects.
On the other hand real numbers which include irrational as well as rational numbers
are not discrete. As you know between any two different real numbers there
is another real number different from either of them. So they are packed without any
gaps and can not be separated from their immediate neighbors. In that sense
they are not discrete.
In this course we will be concerned with objects such as integers, propositions,
sets, relations and functions, which are all discrete. We are going to learn concepts
associated with them, their properties, and relationships among them among others.
Why Discrete Mathematics ?
Let us first see why we want to be interested in the formal/theoretical approaches
in computer science.
Some of the major reasons that we adopt formal approaches are
1) we can handle infinity or large quantity and indefiniteness with them,
and 2) results from formal approaches are reusable.
As an example, let us consider a simple problem of investment. Suppose that
we invest $1,000 every year with expected return of 10% a year.
How much are we going to have after 3 years, 5 years, or 10 years ?
The most naive way to find that out would be the brute force calculation.
Let us see what happens to $1,000 invested at the beginning of each year for three years.
First let us consider the $1,000 invested at the beginning of the first year.
After one year it
produces a return of
$100. Thus at the beginning of the second year, $1,100, which is
equal to $1,000 * ( 1 + 0.1 ), is
invested. This $1,100 produces $110 at the end of the second year. Thus
at the beginning of the third year we have $1,210, which is equal to $1,000 *
( 1 + 0.1 )( 1 + 0.1 ), or $1,000 * ( 1 + 0.1 )2.
After the third year this gives us $1,000 * ( 1 + 0.1 )3.
Similarly we can see that the $1,000 invested at the beginning of the second year
produces $1,000 * ( 1 + 0.1 )2 at the end of the third year, and
the $1,000 invested at the beginning of the third year becomes $1,000 * ( 1 + 0.1 ).
Thus the total principal and return after three years is
$1,000 * ( 1 + 0.1 ) + $1,000 * ( 1 + 0.1 )2 + $1,000 * ( 1 + 0.1 )3,
which is equal to $3,641.
One can similarly calculate the principal and return for 5 years
and for 10 years. It is, however, a long tedious calculation even with
calculators. Further, what if you want to know the principal and return for
some different returns than 10%, or different periods of time such as
15 years ? You would have to do all these calculations all over again.
We can avoid these tedious calculations considerably by noting the similarities
in these problems and solving them in a more general way.
Since all these problems ask for the result of invesing a certain amount
every year for certain number of years with a certain expected annual return,
we use variables, say A, R and n,
to represent the principal newly invested
every year, the return ratio, and the number of years invested, respectively.
With these symbols, the principal and return after n years, denoted by
S, can be expressed as
S = A(1 + R) + A(1 + R)2 + ... + A(1 +
R)n .
As well known, this S can be put into a more compact form
by first computing S - (1 + R)S as
S = A ( (1 + R)n + 1 - (1 + R) ) / R .
Once we have it in this compact form, it is fairly easy to compute S
for different values of A, R and n, though
one still has to compute (1 + R)n + 1 .
This simple formula represents infinitely many cases involving
all different values of A, R and n.
The derivation of this formula, however, involves another problem.
When computing the compact form for S,
S - (1 + R)S
was computed using
S = A(1 + R) + A(1 + R)2 +
... + A(1 +
R)n .
While this argument seems rigorous enough, in fact practically it is a good enough
argument,
when one wishes to be very rigorous, the ellipsis ... in the sum for
S is not considered precise. You are expected to interpret it
in a certain specific way. But it can be interpreted
in a number of different ways. In fact it can mean anything.
Thus if one wants to be rigorous, and absolutely sure about the correctness
of the formula, one needs some other way of verifying it than using the ellipsis.
Since one needs to verify it for infinitely many cases (infinitely many
values of A, R and n), some kind of
formal approach, abstracted away from actual numbers, is required.
Suppose now that somehow we have formally verified the formula successfully
and we are absolutely sure that it is correct. It is a good idea to write
a computer program to compute that S, especially with
(1 + R)n + 1 to be computed.
Suppose again that we have written a program to compute S.
How can we know that the program is correct ? As we know, there are
infinitely many possible input values (that is, values of A, R
and n).
Obviously we can not test it for infinitely many cases. Thus we must take
some formal approach.
Related to the problem of correctness of computer programs, there is
the well known "Halting Problem". This problem, if put into the context of
program correctness, asks
whether or not a given computer program stops
on a given input
after a finite amount of time.
This problem is known to be unsolvable by computers. That is, no one
can write a computer program to answer that question.
It is known to be unsolvable. But, how can we tell it is unsolvable ?.
How can we tell
that such a program can not be written ? You can not try all possible
solution methods and see they all fail. You can not think of all (candidate)
methods to solve the
Halting Problem. Thus you need some kind of formal approaches here to avoid
dealing with a extremely large number (if not infinite) of possibilities.
Discrete mathematics is the foundation for the formal approaches.
It discusses languages used in mathematical reasoning, basic
concepts, and their properties and relationships among them.
Though there is no time to cover them in this course, discrete mathematics
is also concerned with techniques to solve certain types of problems
such as how to count or enumerate quantities.
The kind of counting problems includes: How many routes exist from point A to point B
in a computer network ? How much execution time is required to sort
a list of integers in increasing order ? What is the probability of
winning a lottery ? What is the shortest path from point A to point B
in a computer network ? etc.
The subjects covered in this course include propositional logic, predicate logic,
sets, relations, and functions, in particular growth of function.
The first subject is logic. It is covered in Chapter 1 of the textbook. It is a language
that captures the essence of
our reasoning, and correct reasoning must follow the rules of this language.
We start with logic of sentences
called propositional logic, and study elements of logic, (logical) relationships
between propositions, and
reasoning. Then we learn a little more powerful logic called predicate logic.
It allows us to reason with
statements involving variables among others.
In Chapter 1 we also study sets, relations between sets, and operations on sets.
Just about everything is
described based on sets, when rigor is required. It is the basis of every theory
in computer science and
mathematics.
In Chapter 3 we learn mathematical reasoning, in particular recursive definitions
and mathematical induction. There are sets, operations and functions
that can be defined precisely by recursive definitions. Properties of those recursively
defined objects can be
established rigorously using proof by induction.
Then in Chapter 6 we study relations. They are an abstraction of relations we
are familiar with in everyday life such as husband-wife relation, parent-child relation and ownership relation. They are also one of the key concepts in the
discussion
of many subjects on
computer and computation. For example, a database is viewed as a set of relations
and database query languages
are constructed based on operations on relations and sets. Graphs are also covered
briefly here. They are an
example of discrete structures and they are one of the most useful models for computer scientists and
engineers in solving problems. More in-depth coverage of graph can be found in Chapter 7.
Finally back in Chapter 1 we study functions and their asymptotic behaviors.
Functions are a special type of
relation and basically the same kind of concept as the ones we see in calculus.
However, function is one of the
most important concepts in the discussion of many subjects on computer and computation such as data
structures, database, formal languages and automata, and analysis of algorithms
which is briefly covered in
Chapter 2.
Before we start the study of discrete structures, we briefly learn general framework
of problem solving.
If you are a good problem solver, you may skip that and go to logic.
Next -- Problem Solving Framework
Alternative -- Introduction to Logic
Back to Schedule
Back to Table of Contents