Discrete Mathematics Tutorial: Introduction
{tocify} $title= {Table
of Contents}
Introduction of Discrete Mathematics
Discrete mathematics, the study of finite systems, has
become increasingly important as the computer age has advanced. The digital
computer is basically a finite structure, and many of its properties can be
understood and interpreted within the framework of finite mathematical systems.
Discrete mathematics is the part of mathematics devoted discrete means
consisting of distinct or unconnected elements.) The kinds of problems solved
using discrete mathematics include:
- How many ways are there to choose a valid password on a computer system?
- What is the probability of winning a lottery?
- Is there a link between two computers in a network?
- How can I identify spam e-mail messages?
- How can I encrypt a message so that no unintended recipient can read it?
- What is the shortest path between two cities using a transportation system?
- How can a list of integers be sorted so that the integers are in increasing order?
- How many steps are required to do such a sorting?
- How can it be proved that a sorting algorithm correctly sorts a list?
- How can a circuit that adds two integers be designed?
- How many valid Internet addresses are there?
You will learn the discrete structures and techniques needed
to solve problems such as these. More generally, discrete mathematics is used
whenever objects are counted, when relationships between finite (or countable)
sets are studied, and when processes involving a finite number of steps are
analyzed. A key reason for the growth in the importance of discrete mathematics
is that information is stored and manipulated by computing machines in a
discrete fashion.
Definition of Discrete Mathematics
Discrete Mathematics is a branch of mathematics involving
discrete elements that uses algebra and arithmetic. It is increasingly being
applied in the practical fields of mathematics and computer science. It is a
very good tool for improving reasoning and problem-solving capabilities. This
tutorial explains the fundamental concepts of Sets, Relations and Functions,
Mathematical Logic, Group theory, Counting Theory, Probability, Mathematical
Induction and Recurrence Relations, Graph Theory, Trees and Boolean Algebra.
Mathematics can be broadly classified into two categories −
- Continuous Mathematics − It is based upon continuous number line or the real numbers. It is characterized by the fact that between any two numbers, there are almost always an infinite set of numbers. For example, a function in continuous mathematics can be plotted in a smooth curve without breaks.
- Discrete Mathematics − It involves distinct values; i.e. between any two points, there are a countable number of points. For example, if we have a finite set of objects, the function can be defined as a list of ordered pairs having these objects, and can be presented as a complete list of those pairs.
Why Learn Discrete Mathematics?
There are several important reasons for studying discrete
mathematics. First, through this course you can develop your mathematical
maturity: that is, your ability to understand and create mathematical
arguments. You will not get very far in your studies in the mathematical
sciences without these skills. Second, discrete mathematics is the gateway to
more advanced courses in all parts of the mathematical sciences. Discrete
mathematics provides the mathematical foundations for many computer science
courses, including data structures, algorithms, database theory, automata
theory, formal languages, compiler theory, computer security, and operating
systems. Students find these courses much more difficult when they have not had
the appropriate mathematical foundations from discrete mathematics.
Math courses based on the material studied in discrete
mathematics include logic, set theory, number theory, linear algebra, abstract
algebra, combinatorics, graph theory, and probability theory (the discrete part
of the subject).
Also, discrete mathematics contains the necessary
mathematical background for solving problems in operations research (including
discrete optimization), chemistry, engineering, biology, and so on. In the
text, we will study applications to some of these areas. Many students find
their introductory discrete mathematics course to be significantly more
challenging than courses they have previously taken. One reason for this is
that one of the primary goals of this course is to teach mathematical reasoning
and problem solving, rather than a discrete set of skills. The exercises in
this book are designed to reflect this goal. Although there are plenty of
exercises in this text similar to those addressed in the examples, a large
percentage of the exercises require original thought.
Some Facts about Discrete mathematics
Much of discrete mathematics is devoted to the study of
discrete structures, used to rep- resent discrete objects. Many important
discrete structures are built using sets, which are collections of objects.
Among the discrete structures built from sets are combinations, unordered
collections of objects used extensively in counting; relations, sets of ordered
pairs that represent relationships between objects; graphs, sets of vertices
and edges that connect vertices; and finite state machines, used to model
computing machines. These are some of the topics we will study in later
chapters.
The concept of a function is extremely important in discrete
mathematics. A function assigns to each element of a first set exactly one
element of a second set, where the two sets are not necessarily distinct.
Functions play important roles throughout discrete mathematics. They are used
to represent the computational complexity of algorithms, to study the size of
sets, to count objects, and in a myriad of other ways. Useful structures such
as sequences and strings are special types of functions. In this chapter, we
will introduce the notion of sequences, which represent ordered lists of
elements. Furthermore, we will introduce some important types of sequences and
we will show how to define the terms of a sequence using earlier terms. We will
also address the problem of identifying a sequence from its first few terms. In
our study of discrete mathematics, we will often add consecutive terms of a
sequence of numbers. Because adding terms from a sequence, as well as other
indexed sets of numbers, is such a common occurrence, a special notation has
been developed for adding such terms. In this chapter, we will introduce the
notation used to express summations. We will develop formulae for certain types
of summations that appear throughout the study of discrete mathematics. For instance,
we will encounter such summations in the analysis of the number of steps used
by an algorithm to sort a list of numbers so that its terms are in increasing
order. The relative sizes of infinite sets can be studied by introducing the
notion of the size, or cardinality, of a set. We say that a set is countable
when it is finite or has the same size as the set of positive integers. In this
chapter we will establish the surprising result that the set of rational
numbers is countable, while the set of real numbers is not. We will also show
how the concepts we discuss can be used to show that there are functions that
cannot be computed using a computer program in any programming language. Matrices
are used in discrete mathematics to represent a variety of discrete structures.
We will review the basic material about matrices and matrix arithmetic needed
to represent relations and graphs. The matrix arithmetic we study will be used
to solve a variety of problems involving these structures.
Topics in Discrete Mathematics
Though there cannot be a definite number of branches of
Discrete Mathematics, the following topics are almost always covered in any
study regarding this matter −
- Sets, Relations and Functions
- Mathematical Logic
- Group theory
- Counting Theory
- Probability
- Mathematical Induction and Recurrence Relations
- Graph Theory
- Trees
- Boolean Algebra
We will discuss each of these concepts in the subsequent
chapters of this tutorial.