Outline of discrete mathematics

Short description: Overview of and topical guide to 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 as integers, graphs, and statements in logic[1] – do not vary smoothly in this way, but have distinct, separated values.[2] Discrete mathematics, therefore, excludes topics in "continuous mathematics" such as calculus and analysis.

Included below are many of the standard terms used routinely in university-level courses and in research papers. This is not, however, intended as a complete list of mathematical terms; just a selection of typical terms of art that may be encountered.

* Logic - Study of correct reasoning
* Modal logic - Type of formal logic
* Set theory - Branch of mathematics that studies sets
* Number theory - Branch of pure mathematics
* Combinatorics
* Finite mathematics - Syllabus in college and university mathematics
* Graph theory - Area of discrete mathematics
* Digital geometry - Deals with digitized models or images of objects of the 2D or 3D Euclidean space
* Algorithmics
* Information theory - Scientific study of digital information
* Computability - Ability to solve a problem in an effective manner
* Computational complexity theory - Inherent difficulty of computational problems
* Probability theory - Branch of mathematics concerning probability
* Probability - Branch of mathematics concerning chance and uncertainty
* Markov chains - Random process independent of past history
* Linear algebra - Branch of mathematics
* Functions - Association of one output to each input
* Partially ordered set - Mathematical set with an ordering
* Proofs - Reasoning for mathematical statements
* Relation - Relationship between two sets, defined by a set of ordered pairs

## Contents

* 1 Discrete mathematical disciplines
* 2 Concepts in discrete mathematics
* 2.1 Sets
* 2.2 Functions
* 2.3 Arithmetic
* 2.4 Elementary algebra
* 2.5 Mathematical relations
* 2.6 Mathematical phraseology
* 2.7 Combinatorics
* 2.8 Probability
* 2.9 Propositional logic
* 3 Mathematicians associated with discrete mathematics
* 4 See also
* 5 References
* 6 External links

## Discrete mathematical disciplines

For further reading in discrete mathematics, beyond a basic level, see these pages. Many of these disciplines are closely related to computer science.

* Automata theory - Study of abstract machines and automata
* Coding theory - Study of the properties of codes and their fitness
* Combinatorics
* Computational geometry - Branch of computer science
* Digital geometry - Deals with digitized models or images of objects of the 2D or 3D Euclidean space
* Discrete geometry - Branch of geometry that studies combinatorial properties and constructive methods
* Graph theory - Area of discrete mathematics a study of graphs - Vertices connected in pairs by edges
* Mathematical logic - Subfield of mathematics
* Discrete optimization - Branch of mathematical optimization
* Set theory - Branch of mathematics that studies sets
* Number theory - Branch of pure mathematics
* Information theory - Scientific study of digital information
* Game theory - Mathematical models of strategic interactions

## Concepts in discrete mathematics

### Sets

* Set (mathematics) - Collection of mathematical objects
* Element (mathematics) - Any one of the distinct objects that make up a set in set theory
* Venn diagram - Diagram that shows all possible logical relations between a collection of sets
* Empty set - Mathematical set containing no elements
* Subset
* Union (set theory) - Set of elements in any of some sets
* Disjoint union - In mathematics, operation on sets
* Intersection (set theory) - Set of elements common to all of some sets
* Disjoint sets - Sets with no element in common
* Complement (set theory) - Set of the elements not in a given subset
* Symmetric difference - Elements in exactly one of two sets
* Ordered pair - Pair of mathematical objects
* Cartesian product - Mathematical set formed from two given sets
* Power set
* Simple theorems in the algebra of sets
* Naive set theory - Informal set theories
* Multiset

### Functions

* Function - Association of one output to each input
* Domain of a function - Set of all things that may be the input of a mathematical function
* Codomain - Target set of a mathematical function
* Range of a function - Subset of a function's codomain
* Image (mathematics) - Set of all values of a function
* Injective function - Function that preserves distinctness
* Surjection
* Bijection
* Function composition - Operation on mathematical functions
* Partial function - Function whose actual domain of definition may be smaller than its apparent domain
* Multivalued function - Generalized mathematical function
* Binary function - Function that takes two inputs
* Floor function
* Sign function - Function returning minus 1, zero or plus 1
* Inclusion map - Set-theoretic function
* Pigeonhole principle - If there are more items than boxes holding them, one box must contain at least two items
* Symmetry

### Arithmetic

* Decimal
* Divisor
* Division by zero - Class of mathematical expression
* Indeterminate form - Expression in mathematical analysis
* Empty product - Result from multiplying no factors
* Euclidean algorithm - Algorithm for computing greatest common divisors
* Fundamental theorem of arithmetic - Integers have unique prime factorizations
* Modular arithmetic - Computation modulo a fixed integer
* Successor function - Elementary operation on a natural number

### Elementary algebra

Elementary algebra - Basic concepts of algebra

* Linear equation - Equation that does not involve powers or products of variables
* Quadratic equation - Polynomial equation of degree two
* Arithmetic progression - Sequence of equally spaced numbers
* Recurrence relation - Pattern defining an infinite sequence of numbers
* Finite difference - Discrete analog of a derivative
* Difference operator
* Groups - Set with associative invertible operation
* Group isomorphism - Bijective group homomorphism
* Fermat's little theorem - A prime p divides a^p–a for any integer a
* Cryptography
* Faulhaber's formula - Expression for sums of powers

### Mathematical relations

* Binary relation - Relationship between elements of two sets
* Heterogeneous relation
* Reflexive relation - Binary relation that relates every element to itself
* Symmetric relation - Type of binary relation
* Antisymmetric relation - Binary relation such that if A is related to B and is different from it then B is not related to A
* Transitivity (mathematics) - Type of binary relation
* Transitive closure - Smallest transitive relation containing a given binary relation
* Equivalence and identity
* Equivalence relation - Mathematical concept for comparing objects
* Equivalence class - Mathematical concept
* Equality (mathematics) - Relationship asserting that two quantities are the same
* Inequation
* Inequality (mathematics) - Mathematical relation expressed with < or ≤
* Similarity (geometry) - Property of objects which are scaled or mirrored versions of each other
* Congruence (geometry) - Relationship between two figures of the same shape and size, or mirroring each other
* Equation
* Identity (mathematics) - Equation that is satisfied for all values of the variables
* Identity element - Specific element of an algebraic structure
* Identity function - Function that returns its argument unchanged
* Extensionality
* Uniqueness quantification - Logical quantifier

### Mathematical phraseology

* If and only if - Logical connective
* Distinct
* Difference
* Absolute value - Distance from zero to a number
* Up to - Mathematical statement of uniqueness, except for an equivalent structure (equivalence relation)
* Modular arithmetic - Computation modulo a fixed integer
* Characterization (mathematics) - Term in mathematics
* Canonical form - Standard representation of a mathematical object
* Without loss of generality - Expression in mathematics
* Vacuous truth - Conditional statement which is true because the antecedent cannot be satisfied
* Contradiction - Logical incompatibility between two or more propositions, Reductio ad absurdum - Argument that leads to a logical absurdity
* Counterexample
* Pons asinorum - Statement that the angles opposite the equal sides of an isosceles triangle are themselves equal
* Mathematical induction - Form of mathematical proof

### Combinatorics

Combinatorics

* Permutations and combinations - Selection of items from a set
* Permutation
* Combination - Selection of items from a set
* Factorial
* Empty product - Result from multiplying no factors
* Pascal's triangle - Triangular array of the binomial coefficients in mathematics
* Combinatorial proof
* Bijective proof - Technique for proving sets have equal size
* Double counting (proof technique) - Type of proof technique

### Probability

Probability - Branch of mathematics concerning chance and uncertainty

* Average
* Expected value - Average value of a random variable
* Sample space - Set of all possible outcomes or results of a statistical trial or experiment
* Event - In statistics and probability theory, set of outcomes to which a probability is assigned
* Independence - When the occurrence of one event does not affect the likelihood of another

### Propositional logic

* Truth table - Mathematical table used in logic
* De Morgan's laws - Pair of logical equivalences

## Mathematicians associated with discrete mathematics

* Biography:Paul Erdős[3]
* Leonhard Euler - Swiss mathematician (1707-1783)[3]
* Claude Shannon - American mathematician (1916-2001)[3]
* Donald Knuth - American mathematician and computer scientist (b. 1938)[4][5]
* Biography:Aristotle

## See also

## References

1. ↑ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008; James Franklin, Discrete and continuous: a fundamental dichotomy in mathematics, Journal of Humanistic Mathematics 7 (2017), 355-378.
2. ↑ Weisstein, Eric W.. "Discrete mathematics". http://mathworld.wolfram.com/DiscreteMathematics.html.
3. ↑ 3.0 3.1 3.2 "Discrete Mathematics: Past, Present, and Future - Computer Science and Discrete Mathematics (CSDM) | Institute for Advanced Study" (in en). 2008-09-04. https://www.ias.edu/math/csdm/dm.
4. ↑ "Knuth: Selected Papers on Discrete Mathematics". https://www-cs-faculty.stanford.edu/~knuth/dm.html.
5. ↑ Knuth, Donald E. (in en). Selected Papers on Discrete Mathematics. Lecture Notes. Center for the Study of Language and Information. https://press.uchicago.edu/ucp/books/book/distributed/S/bo3613158.html.

## External links

* Archives
* Jonathan Arbib & John Dwyer, Discrete Mathematics for Cryptography, 1st Edition ISBN 978-1-907934-01-8.
* John Dwyer & Suzy Jagger, Discrete Mathematics for Business & Computing, 1st Edition 2010 ISBN 978-1-907934-00-1.

* v
* t
* e

Wikipedia Outlines

General reference

* Culture and the arts
* Geography and places
* Health and fitness
* History and events
* Mathematics and logic
* Natural and physical sciences
* People and self
* Philosophy and thinking
* Religion and belief systems
* Society and social sciences
* Technology and applied sciences

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Outline of discrete mathematics. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Outline_of_discrete_mathematics&oldid=4350529"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template