Discrete mathematics

Part of a series on
Mathematics
History Outline Index
Areas Number theory Geometry Algebra Calculus and Analysis Discrete mathematics Logic and Set theory Probability Statistics and Decision theory Relationship with sciences Physics Chemistry Geosciences Computation Biology Linguistics Economics Philosophy Education
Mathematics Portal
v t e

Discrete mathematics is the study of

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

. 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 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.^[6][7] Some high-school-level discrete mathematics textbooks have appeared as well.^[8] At this level, discrete mathematics is sometimes seen as a preparatory course, like precalculus in this respect.^[9]

The Fulkerson Prize is awarded for outstanding papers in discrete mathematics.

Topics in discrete mathematics

Theoretical computer science

Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily on

applies them to representations of images. Theoretical computer science also includes the study of various continuous computational topics.

Information theory

binary, provide a way of representing the word in information theory, as well as for information-processing algorithms

.

Information theory involves the quantification of

analog encryption

.

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) Peirce's law (((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^[10] or, more generally, directed acyclic graph structures^[11][12] (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,^[13] e.g. infinitary logic.

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects, such as {blue, white, red} or the (infinite) set of all prime numbers. Partially ordered sets and sets with other relations have applications in several areas.

In discrete mathematics, countable sets (including finite sets) 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, 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.

. . Topological combinatorics concerns the use of techniques from topology and algebraic topology/combinatorial topology in combinatorics. Design theory is a study of properties. , partition theory is now considered a part of combinatorics or an independent field.

partially ordered sets

, both finite and infinite.

Graph theory

Graph theory, the study of

; 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

.

Algebraic structures

.

Discrete analogues of continuous mathematics

There are many concepts and theories in continuous mathematics which have discrete versions, such as

.

Calculus of finite differences, discrete analysis, and discrete calculus

In

.

The

.

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.

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 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 ${\displaystyle V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}}$ for ${\displaystyle K}$ a field can be studied either as ${\displaystyle \operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K}$, a point, or as the spectrum ${\displaystyle \operatorname {Spec} K[x]_{(x-c)}}$ of the

, making many features of calculus applicable even in finite settings.

Discrete modelling

In applied mathematics, discrete modelling is the discrete analogue of continuous modelling. In discrete modelling, discrete formulae are fit to data. 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.

Challenges

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).^[15]

In

.

The need to

have been driven by this need.

Computational geometry has been an important part of the computer graphics incorporated into modern video games and computer-aided design tools.

Several fields of discrete mathematics, particularly theoretical computer science, graph theory, and combinatorics, are important in addressing the challenging bioinformatics problems associated with understanding the tree of life.^[17]

Currently, one of the most famous open problems in theoretical computer science is the

See also

• Outline of discrete mathematics
• Cyberchase, a show that teaches discrete mathematics to children

References

Further reading

• ISBN 978-0-19-850717-8
  .
• Dwyer, John (2010). An Introduction to Discrete Mathematics for Business & Computing.
  ISBN 978-1-907934-00-1
  .
• ISBN 978-0-495-39132-6
  .
• ISBN 0-201-55802-5
  .
• ISBN 978-0-201-72634-3
  .
• Knuth, Donald E. (2011).
  ISBN 978-0-321-75104-1
  .
• ISBN 978-0-19-850208-1
  .
• Obrenic, Bojana (2003). Practice Problems in Discrete Mathematics. Prentice Hall.
  ISBN 978-0-13-045803-2
  .
• Rosen, Kenneth H.; Michaels, John G. (2000). Hand Book of Discrete and Combinatorial Mathematics. CRC Press.
  ISBN 978-0-8493-0149-0
  .
• Rosen, Kenneth H. (2007). Discrete Mathematics: And Its Applications. McGraw-Hill.
  ISBN 978-0-07-288008-3
  .
• ISBN 978-0-07-709840-7
  .

External links

Wikibooks has a book on the topic of: Discrete Mathematics

Wikimedia Commons has media related to Discrete mathematics.

• Discrete mathematics Archived 2011-08-29 at the Wayback Machine at the utk.edu Mathematics Archives, providing links to syllabi, tutorials, programs, etc.
• Iowa Central: Electrical Technologies Program Discrete mathematics for Electrical engineering.