Outline of discrete mathematics

The following outline is presented as an overview of and topical guide to discrete mathematics:

Discrete mathematics – 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.

Subjects in discrete mathematics

• Logic – a study of reasoning
• Set theory – a study of collections of elements
• Number theory –
• Combinatorics – a study of counting
• Graph theory –
• Digital geometry and digital topology
• Algorithmics – a study of methods of calculation
• Information theory –
• Computability and complexity theories – dealing with theoretical and practical limitations of algorithms
• Elementary probability theory and Markov chains
• Linear algebra – a study of related linear equations
• Functions –
• Partially ordered set –
• Probability –
• Proofs –
• Counting –
• Relation –

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 –
• Combinatorics –
• Combinatorial geometry –
• Computational geometry –
• Digital geometry –
• Discrete geometry –
• Graph theory –
• Mathematical logic –
• Combinatorial optimization –
• Set theory –
• Combinatorial topology –
• Number theory –
• Information theory –
• Game theory –

Concepts in discrete mathematics

Sets

• Set (mathematics) –
  • Element (mathematics) –
  • Venn diagram –
  • Empty set –
  • Subset –
  • Union (set theory) –
    • Disjoint union –
  • Intersection (set theory) –
    • Disjoint sets –
  • Complement (set theory) –
  • Symmetric difference –
• Ordered pair –
• Cartesian product –
• Power set –
• Simple theorems in the algebra of sets –
• Naive set theory –
• Multiset –

Functions

• Function –
• Domain of a function –
• Codomain –
• Range of a function –
• Image (mathematics) –
• Injective function –
• Surjection –
• Bijection –
• Function composition –
• Partial function –
• Multivalued function –
• Binary function –
• Floor function –
• Sign function –
• Inclusion map –
• Pigeonhole principle –
• Relation composition –
• Permutations –
• Symmetry –

Operations

Binary operator –

• Associativity –
• Commutativity –
• Distributivity

Arithmetic

Decimal –

• Binary numeral system –
• Divisor –
• Division by zero –
• Indeterminate form –
• Empty product –
• Euclidean algorithm –
• Fundamental theorem of arithmetic –
• Modular arithmetic –
• Successor function

Elementary algebra

Main article: Elementary algebra

Left-hand side and right-hand side of an equation –

• Linear equation –
• Quadratic equation –
• Solution point –
• Arithmetic progression –
• Recurrence relation –
• Finite difference –
• Difference operator –
• Groups –
• Group isomorphism –
• Subgroups –
• Fermat's little theorem –
• Cryptography –
• Faulhaber's formula –

Mathematical relations

• Binary relation –
• Mathematical relation –
• Reflexive relation –
• Reflexive property of equality –
• Symmetric relation –
• Symmetric property of equality –
• Antisymmetric relation –
• Transitivity (mathematics) –
  • Transitive closure –
  • Transitive property of equality –
• Equivalence and identity
  • Equivalence relation –
  • Equivalence class –
  • Equality (mathematics) –
    • Inequation –
    • Inequality (mathematics) –
  • Similarity (geometry) –
  • Congruence (geometry) –
  • Equation –
  • Identity (mathematics) –
    • Identity element –
    • Identity function –
  • Substitution property of equality –
  • Graphing equivalence –
  • Extensionality –
  • Uniqueness quantification –

Mathematical phraseology

If and only if –

• Necessary and sufficient (Sufficient condition) –
• Distinct –
• Difference –
• Absolute value –
• Up to –
• Modular arithmetic –
• Characterization (mathematics) –
• Normal form –
• Canonical form –
• Without loss of generality –
• Vacuous truth –
• Contradiction, Reductio ad absurdum –
• Counterexample –
• Sufficiently large –
• Pons asinorum –
• Table of mathematical symbols –
• Contrapositive –
• Mathematical induction –

Combinatorics

Main article: Combinatorics

• Permutations and combinations –
• Permutation –
• Combination –
• Factorial –
  • Empty product –
• Pascal's triangle –
• Combinatorial proof –
  • Bijective proof –
  • Double counting (proof technique) –

Probability

Main article: Probability

• Average –
• Expected value –
• Discrete random variable –
• Sample space –
• Event –
• Conditional Probability –
• Independence –
• Random variables –

Propositional logic

Logical operator –

• Truth table –
• De Morgan's laws –
• Open sentence –
• List of topics in logic –

Discrete mathematicians

Paul Erdős –

• Ronald Graham –

See also

Discrete mathematics portal

References

1. ^ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
2. ^ Weisstein, Eric W., "Discrete mathematics" from MathWorld.

External links

• Archives
• Jonathan Arbib & John Dwyer, Discrete Mathematics for Cryptography, 1st Edition ISBN 978-1907934018.
• John Dwyer & Suzy Jagger, Discrete Mathematics for Business & Computing, 1st Edition 2010 ISBN 978-1907934001.