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 – do not vary smoothly in this way, but have distinct, separated values. 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 – Branch of discrete mathematics 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 Digital topology – Properties of 2D or 3D digital images that correspond to classic topological properties Algorithmics – Sequence of operations for a taskPages displaying short descriptions of redirect targets Information theory – Scientific study of digital information Computability – Ability to solve a problem by an effective procedure Computational complexity theory – Inherent difficulty of computational problems Probability theory – Branch of mathematics concerning probability Probability – Number measuring the chance an event occurs 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
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 – Branch of discrete mathematics 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 theoryPages displaying short descriptions of redirect targets Venn diagram – Diagram that shows all possible logical relations between a collection of sets Empty set – Mathematical set containing no elements Subset – Set whose elements all belong to another set 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 – Mathematical set of all subsets of a set Simple theorems in the algebra of sets – Basic set identities like commutative and associative laws Naive set theory – Informal set theories Multiset – Mathematical set with repetitions allowed
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 the values of a function Injective function – Function that preserves distinctness Surjection – Mathematical function such that every output has at least one inputPages displaying short descriptions of redirect targets Bijection – One-to-one correspondence 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 – Nearest integers from a numberPages displaying short descriptions of redirect targets Sign function – Function returning minus 1, zero or plus 1 Inclusion map – Set-theoretic function Pigeonhole principle – Theorem in combinatorics Relation composition – Mathematical operationPages displaying short descriptions of redirect targets Permutations – Mathematical version of an order changePages displaying short descriptions of redirect targets Symmetry – Mathematical invariance under transformations
Arithmetic Decimal – Number in base-10 numeral system Binary numeral system – Number expressed in the base-2 numeral systemPages displaying short descriptions of redirect targets Divisor – Integer that divides another integer 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
Left-hand side and right-hand side of an equation – Mathematical nomenclaturePages displaying short descriptions of redirect targets Linear equation – Equation that does not involve powers or products of variables Quadratic equation – Polynomial equation of degree two Solution point – Mathematical formula expressing equalityPages displaying short descriptions of redirect targets 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 – Pattern defining an infinite sequence of numbersPages displaying short descriptions of redirect targets Groups – Set with associative invertible operation Group isomorphism – Bijective group homomorphism Subgroups – Subset of a group that forms a group itselfPages displaying short descriptions of redirect targets Fermat's little theorem – A prime p divides a^p–a for any integer a Cryptography – Practice and study of secure communication techniques Faulhaber's formula – Expression for sums of powers
Mathematical relations Binary relation – Relationship between elements of two sets Heterogeneous relation – Relationship between elements of two setsPages displaying short descriptions of redirect targets Reflexive relation – Binary relation that relates every element to itself Reflexive property of equality – Basic notion of sameness in mathematicsPages displaying short descriptions of redirect targets Symmetric relation – Type of binary relation Symmetric property of equality – Basic notion of sameness in mathematicsPages displaying short descriptions of redirect targets Antisymmetric relation – Type of binary relation Transitivity (mathematics) – Type of binary relation Transitive closure – Smallest transitive relation containing a given binary relation Transitive property of equality – Basic notion of sameness in mathematicsPages displaying short descriptions of redirect targets Equivalence and identity Equivalence relation – Mathematical concept for comparing objects Equivalence class – Mathematical concept Equality (mathematics) – Basic notion of sameness in mathematics Inequation – Mathematical statement that two values are not equal Inequality (mathematics) – Mathematical relation making a non-equal comparison 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 – Mathematical formula expressing equality 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 Substitution property of equality – Basic notion of sameness in mathematicsPages displaying short descriptions of redirect targets Graphing equivalence Extensionality – Logic principle Uniqueness quantification – Logical quantifier
Mathematical phraseology If and only if – Logical connective Necessary and sufficient – Terms to describe a conditional relationship between two statementsPages displaying short descriptions of redirect targets Distinct – Basic notion of sameness in mathematicsPages displaying short descriptions of redirect targets Difference – One of the four basic arithmetic operations Absolute value – Distance from zero to a number Up to – Mathematical statement of uniqueness, except for an equivalent structure Modular arithmetic – Computation modulo a fixed integer Characterization (mathematics) – Term in mathematics Normal form – Standard representation of a mathematical objectPages displaying short descriptions of redirect targets 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 – Exception to a proposed general rule Sufficiently large Pons asinorum – Geometric theorem about isosceles triangles Table of mathematical symbols Contrapositive – Mathematical logic conceptPages displaying short descriptions of redirect targets Mathematical induction – Form of mathematical proof
Combinatorics Combinatorics – Branch of discrete mathematics
Permutations and combinations – Selection of items from a set Permutation – Mathematical version of an order change Combination – Selection of items from a set Factorial – Product of numbers from 1 to n Empty product – Result from multiplying no factors Pascal's triangle – Triangular array of the binomial coefficients Combinatorial proof – Proofs in enumerative combinatorics Bijective proof – Technique for proving sets have equal size Double counting (proof technique) – Type of proof technique
Probability Probability – Number measuring the chance an event occurs
Average – Number taken as representative of a list of numbers Expected value – Average value of a random variable Discrete random variable – Variable representing a random phenomenonPages displaying short descriptions of redirect targets 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 Conditional Probability – Probability of an event occurring, given that another event has already occurredPages displaying short descriptions of redirect targets Independence – When the occurrence of one event does not affect the likelihood of another Random variables – Variable representing a random phenomenonPages displaying short descriptions of redirect targets
Propositional logic Logical operator – Symbol connecting formulas in logicPages displaying short descriptions of redirect targets Truth table – Mathematical table used in logic De Morgan's laws – Pair of logical equivalences Open sentence – Formula that contains at least one free variablePages displaying short descriptions of redirect targets List of topics in logic – Overview of and topical guide to logicPages displaying short descriptions of redirect targets
Mathematicians associated with discrete mathematics
Paul Erdős – Hungarian mathematician (1913–1996) Leonhard Euler - Swiss mathematician (1707-1783) Claude Shannon - American mathematician (1916-2001) Donald Knuth - American mathematician and computer scientist (b. 1938) Aristotle – Ancient Greek philosopher and polymath (384–322 BC)
See also
References
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.