
Discrete mathematics is the study of
mathematical structures that can be considered "discrete" (in a way analogous to
discrete variables, having a
bijection with the set of
natural numbers) rather than "continuous" (analogously to
continuous functions). Objects studied in discrete mathematics include
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s,
graphs, and
statements in
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...
. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s,
calculus
Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizati ...
or
Euclidean geometry
Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry: the ''Elements''. Euclid's approach consists in assuming a small set of intuitively appealing axioms ...
. Discrete objects can often be
enumerated by
integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with
countable sets (finite sets or sets with the same
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
as the natural numbers). However, there is no exact definition of the term "discrete mathematics".
The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.
Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development of
digital computers which operate in "discrete" steps and store data in "discrete" bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, such as
computer algorithms,
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming l ...
s,
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
,
automated theorem proving, and
software development
Software development is the process of conceiving, specifying, designing, programming, documenting, testing, and bug fixing involved in creating and maintaining applications, frameworks, or other software components. Software development inv ...
. Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems.
Although the main objects of study in discrete mathematics are discrete objects,
analytic methods from "continuous" mathematics are often employed as well.
In university curricula, "Discrete Mathematics" appeared in the 1980s, initially as a computer science support course; its contents were somewhat haphazard at the time. The curriculum has thereafter developed in conjunction with efforts by
ACM
ACM or A.C.M. may refer to:
Aviation
* AGM-129 ACM, 1990–2012 USAF cruise missile
* Air chief marshal
* Air combat manoeuvring or dogfighting
* Air cycle machine
* Arica Airport (Colombia) (IATA: ACM), in Arica, Amazonas, Colombia
Computing
* ...
and
MAA into a course that is basically intended to develop
mathematical maturity in first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well.
Some high-school-level discrete mathematics textbooks have appeared as well.
At this level, discrete mathematics is sometimes seen as a preparatory course, not unlike
precalculus in this respect.
The
Fulkerson Prize is awarded for outstanding papers in discrete mathematics.
Grand challenges, past and present

The history of discrete mathematics has involved a number of challenging problems which have focused attention within areas of the field. In graph theory, much research was motivated by attempts to prove the
four color theorem, first stated in 1852, but not proved until 1976 (by Kenneth Appel and Wolfgang Haken, using substantial computer assistance).
In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...
, the
second problem on
David Hilbert's list of open
problems presented in 1900 was to prove that the
axioms of
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th c ...
are
consistent.
Gödel's second incompleteness theorem, proved in 1931, showed that this was not possible – at least not within arithmetic itself.
Hilbert's tenth problem was to determine whether a given polynomial
Diophantine equation with integer coefficients has an integer solution. In 1970,
Yuri Matiyasevich proved that this
could not be done.
The need to
break German codes in
World War II
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the World War II by country, vast majority of the world's countries—including all of the great power ...
led to advances in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
and
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, with the
first programmable digital electronic computer being developed at England's
Bletchley Park with the guidance of
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical c ...
and his seminal work, On Computable Numbers. The
Cold War meant that cryptography remained important, with fundamental advances such as
public-key cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic a ...
being developed in the following decades. The
telecommunication
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than tha ...
industry has also motivated advances in discrete mathematics, particularly in graph theory and
information theory.
Formal verification of statements in logic has been necessary for
software development
Software development is the process of conceiving, specifying, designing, programming, documenting, testing, and bug fixing involved in creating and maintaining applications, frameworks, or other software components. Software development inv ...
of
safety-critical systems, and advances in
automated theorem proving have been driven by this need.
Computational geometry has been an important part of the
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great deal ...
incorporated into modern
video game
Video games, also known as computer games, are electronic games that involves interaction with a user interface or input device such as a joystick, game controller, controller, computer keyboard, keyboard, or motion sensing device to gener ...
s and
computer-aided design tools.
Several fields of discrete mathematics, particularly theoretical computer science, graph theory, and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, are important in addressing the challenging
bioinformatics problems associated with understanding the
tree of life
The tree of life is a fundamental archetype in many of the world's mythological, religious, and philosophical traditions. It is closely related to the concept of the sacred tree.Giovino, Mariana (2007). ''The Assyrian Sacred Tree: A Histo ...
.
Currently, one of the most famous open problems in theoretical computer science is the
P = NP problem, which involves the relationship between the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms ...
es
P and
NP. The
Clay Mathematics Institute has offered a $1 million
USD prize for the first correct proof, along with prizes for
six other mathematical problems.
Topics in discrete mathematics
Theoretical computer science

Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily on
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
and
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
. Included within theoretical computer science is the study of algorithms and data structures.
Computability studies what can be computed in principle, and has close ties to logic, while complexity studies the time, space, and other resources taken by computations.
Automata theory and
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of s ...
theory are closely related to computability.
Petri nets and
process algebra
In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, an ...
s are used to model computer systems, and methods from discrete mathematics are used in analyzing
VLSI electronic circuits.
Computational geometry applies algorithms to geometrical problems and representations of
geometrical objects, while
computer image analysis applies them to representations of images. Theoretical computer science also includes the study of various continuous computational topics.
Information theory

Information theory involves the quantification of
information
Information is an abstract concept that refers to that which has the power to inform. At the most fundamental level information pertains to the interpretation of that which may be sensed. Any natural process that is not completely random, ...
. Closely related is
coding theory which is used to design efficient and reliable data transmission and storage methods. Information theory also includes continuous topics such as:
analog signal
An analog signal or analogue signal (see spelling differences) is any continuous signal representing some other quantity, i.e., ''analogous'' to another quantity. For example, in an analog audio signal, the instantaneous signal voltage vari ...
s,
analog coding
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studie ...
,
analog encryption
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studie ...
.
Logic
Logic is the study of the principles of valid reasoning and
inference, as well as of
consistency,
soundness, and
completeness. For example, in most systems of logic (but not in
intuitionistic logic
Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, system ...
)
Peirce's law
In logic, Peirce's law is named after the philosopher and logician Charles Sanders Peirce. It was taken as an axiom in his first axiomatisation of propositional logic. It can be thought of as the law of excluded middle written in a form tha ...
(((''P''→''Q'')→''P'')→''P'') is a theorem. For classical logic, it can be easily verified with a
truth table. The study of
mathematical proof is particularly important in logic, and has accumulated to
automated theorem proving and
formal verification of software.
Logical formulas are discrete structures, as are
proofs, which form finite
trees or, more generally,
directed acyclic graph structures (with each
inference step combining one or more
premise branches to give a single conclusion). The
truth values of logical formulas usually form a finite set, generally restricted to two values: ''true'' and ''false'', but logic can also be continuous-valued, e.g.,
fuzzy logic. Concepts such as infinite proof trees or infinite derivation trees have also been studied, e.g.
infinitary logic.
Set theory
Set theory is the branch of mathematics that studies
sets, which are collections of objects, such as or the (infinite) set of all
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
s.
Partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binar ...
s and sets with other
relations
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
have applications in several areas.
In discrete mathematics,
countable sets (including
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. ...
s) are the main focus. The beginning of set theory as a branch of mathematics is usually marked by
Georg Cantor's work distinguishing between different kinds of
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only ...
, motivated by the study of trigonometric series, and further development of the theory of infinite sets is outside the scope of discrete mathematics. Indeed, contemporary work in
descriptive set theory makes extensive use of traditional continuous mathematics.
Combinatorics
Combinatorics studies the way in which discrete structures can be combined or arranged.
Enumerative combinatorics concentrates on counting the number of certain combinatorial objects - e.g. the
twelvefold way provides a unified framework for counting
permutations,
combinations and
partitions.
Analytic combinatorics concerns the enumeration (i.e., determining the number) of combinatorial structures using tools from
complex analysis and
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
. In contrast with enumerative combinatorics which uses explicit combinatorial formulae and
generating functions to describe the results, analytic combinatorics aims at obtaining
asymptotic formulae.
Topological combinatorics concerns the use of techniques from
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
and
algebraic topology/
combinatorial topology in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
.
Design theory is a study of
combinatorial designs, which are collections of subsets with certain
intersection properties.
Partition theory
In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same part ...
studies various enumeration and asymptotic problems related to
integer partitions, and is closely related to
q-series,
special functions
Special functions are particular mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications.
The term is defined ...
and
orthogonal polynomials. Originally a part of
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
and
analysis, partition theory is now considered a part of combinatorics or an independent field.
Order theory is the study of
partially ordered sets, both finite and infinite.
Graph theory

Graph theory, the study of
graphs and
networks, is often considered part of combinatorics, but has grown large enough and distinct enough, with its own kind of problems, to be regarded as a subject in its own right.
Graphs on Surfaces
Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001 Graphs are one of the prime objects of study in discrete mathematics. They are among the most ubiquitous models of both natural and human-made structures. They can model many types of relations and process dynamics in physical, biological and social systems. In computer science, they can represent networks of communication, data organization, computational devices, the flow of computation, etc. In mathematics, they are useful in geometry and certain parts of topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
, e.g. knot theory. Algebraic graph theory has close links with group theory and topological graph theory has close links to topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
. There are also continuous graphs; however, for the most part, research in graph theory falls within the domain of discrete mathematics.
Number theory
Number theory is concerned with the properties of numbers in general, particularly integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s. It has applications to cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
and cryptanalysis, particularly with regard to modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
, diophantine equations
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates t ...
, linear and quadratic congruences, prime numbers and primality testing. Other discrete aspects of number theory include geometry of numbers. In analytic number theory, techniques from continuous mathematics are also used. Topics that go beyond discrete objects include transcendental numbers, diophantine approximation, p-adic analysis and function fields.
Algebraic structures
Algebraic structures occur as both discrete examples and continuous examples. Discrete algebras include: boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...
used in logic gates and programming; relational algebra used in databases; discrete and finite versions of groups, rings and fields are important in algebraic coding theory; discrete semigroup
In mathematics, a semigroup is an algebraic structure consisting of a Set (mathematics), set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplication, multiplicatively ...
s and monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
s appear in the theory of formal languages.
Discrete analogues of continuous mathematics
There are many concepts and theories in continuous mathematics which have discrete versions, such as discrete calculus, discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
s, discrete geometry, discrete logarithms, discrete differential geometry, discrete exterior calculus, discrete Morse theory, discrete optimization, discrete probability theory, discrete probability distribution, difference equations, discrete dynamical systems, and discrete vector measures.
Calculus of finite differences, discrete analysis, and discrete calculus
In discrete calculus and the calculus of finite differences, a function defined on an interval of the integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s is usually called a sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
. A sequence could be a finite sequence from a data source or an infinite sequence from a discrete dynamical system. Such a discrete function could be defined explicitly by a list (if its domain is finite), or by a formula for its general term, or it could be given implicitly by a recurrence relation or difference equation. Difference equations are similar to differential equations, but replace differentiation by taking the difference between adjacent terms; they can be used to approximate differential equations or (more often) studied in their own right. Many questions and methods concerning differential equations have counterparts for difference equations. For instance, where there are integral transforms in harmonic analysis for studying continuous functions or analogue signals, there are discrete transforms for discrete functions or digital signals. As well as discrete metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
s, there are more general discrete topological space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest t ...
s, finite metric spaces, finite topological space
In mathematics, a finite topological space is a topological space for which the underlying set (mathematics), point set is finite set, finite. That is, it is a topological space which has only finitely many elements.
Finite topological spaces are ...
s.
The time scale calculus is a unification of the theory of difference equations with that of differential equations
In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, a ...
, which has applications to fields requiring simultaneous modelling of discrete and continuous data. Another way of modeling such a situation is the notion of hybrid dynamical system A hybrid system is a dynamical system that exhibits both continuous and discrete dynamic behavior – a system that can both ''flow'' (described by a differential equation) and ''jump'' (described by a state machine or automaton). Often, the ...
s.
Discrete geometry
Discrete geometry and combinatorial geometry are about combinatorial properties of ''discrete collections'' of geometrical objects. A long-standing topic in discrete geometry is tiling of the plane
A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of g ...
.
In algebraic geometry, the concept of a curve can be extended to discrete geometries by taking the spectra of polynomial rings over finite fields to be models of the affine spaces over that field, and letting subvarieties
Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Mo ...
or spectra of other rings provide the curves that lie in that space. Although the space in which the curves appear has a finite number of points, the curves are not so much sets of points as analogues of curves in continuous settings. For example, every point of the form for a field can be studied either as , a point, or as the spectrum of the local ring at (x-c), a point together with a neighborhood around it. Algebraic varieties also have a well-defined notion of tangent space called the Zariski tangent space, making many features of calculus applicable even in finite settings.
Discrete modelling
In applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemat ...
, discrete modelling Discrete modelling is the discrete analogue of continuous modelling
Continuous modelling is the mathematical practice of applying a model to continuous data (data which has a potentially infinite number, and divisibility, of attributes). They ofte ...
is the discrete analogue of continuous modelling. In discrete modelling, discrete formulae are fit to data
In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpret ...
. A common method in this form of modelling is to use recurrence relation. Discretization concerns the process of transferring continuous models and equations into discrete counterparts, often for the purposes of making calculations easier by using approximations. Numerical analysis provides an important example.
See also
* Outline of discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such a ...
* Cyberchase, a show that teaches Discrete Mathematics to children
References
Further reading
*
*
*
*
*
*
*
*
*
*
*
External links
Discrete mathematics
at the utk.edu Mathematics Archives, providing links to syllabi, tutorials, programs, etc.
Iowa Central: Electrical Technologies Program
Discrete mathematics for Electrical engineering.
{{DEFAULTSORT:Discrete Mathematics