Learn: Discrete Mathematics Definitions

Statement

A sentence that is either true or false, but not both.

Argument

A sequence of statements, the last of which is the conclusion and the rest of which are premises.

Premise

A statement in an argument that is assumed to be true.

Conclusion

The final statement in an argument.

Valid argument

An argument where the conclusion must be true whenever all the premises are true.

Invalid argument

An argument where the premises can all be true while the conclusion is false.

Sound argument

An argument that is valid and has all true premises.

Proof

A sound argument whose conclusion is the statement being proved.

Negation

The statement that reverses the truth value of a statement.

Conjunction

A statement formed using and.

Disjunction

A statement formed using or.

Exclusive or

A statement meaning exactly one of two statements is true.

Conditional statement

A statement of the form "if P, then Q," written P→Q.

Biconditional statement

A statement of the form "P if and only if Q," written P↔Q.

Contrapositive

The statement ¬Q→¬P corresponding to P→Q.

Converse

The statement Q→P corresponding to P→Q.

Inverse

The statement ¬P→¬Q corresponding to P→Q.

Tautology

A statement that is always true.

Contradiction

A statement that is always false.

Logical equivalence

Two statements that have the same truth value in every possible situation.

Universal quantifier

"For all" or "for every," written ∀.

Existential quantifier

"There exists," written ∃.

Unique existence

"There exists exactly one," often written ∃!.

Logical operator

A symbol or word used to combine or modify statements.

Truth table

A table showing the truth values of a statement for every possible combination of truth values of its parts.

Logical implication

The relationship where one statement guarantees another.

Logically equivalent statements

Statements that have identical truth values for every possible assignment of their variables.

Predicate

A statement containing a variable whose truth value depends on the value assigned to that variable.

Domain

The set of possible values for a variable.

Free variable

A variable that has not been bound by a quantifier.

Bound variable

A variable controlled by a quantifier.

Universal statement

A statement asserting that something is true for every element of a domain.

Existential statement

A statement asserting that something is true for at least one element of a domain.

Direct proof

A proof that begins by assuming the hypotheses are true and logically derives the conclusion.

Proof by contrapositive

A proof of P→Q by proving ¬Q→¬P.

Proof by contradiction

A proof where you assume the statement is false and derive a contradiction.

Counterexample

A specific example showing that a statement is false.

Cases

Separate possibilities considered individually in a proof.

Without loss of generality

A phrase used when symmetry allows you to consider only one of several essentially identical cases.

Set

A collection of elements.

Element

An object belonging to a set.

Subset

A⊆B means every element of A is also an element of B.

Proper subset

A subset that is not equal to the original set.

Union

A∪B is the set containing every element in A, B, or both.

Intersection

A∩B is the set containing elements that are in both A and B.

Difference

A-B is the set of elements in A that are not in B.

Complement

The elements in the universal set that are not in the given set.

Cardinality

The number of elements in a set.

Power set

The set of all subsets of a given set.

Function

A relation that assigns exactly one output to every input.

Domain of a function

The set of possible inputs.

Codomain

The set containing the possible outputs.

Range

The set of actual outputs of a function.

Injective

A function where different inputs always have different outputs.

Surjective

A function where every element of the codomain is the output of some input.

Bijective

A function that is both injective and surjective.

Inverse function

A function that reverses the input-output relationship of a bijective function.

Graph

A collection of vertices, some of which are connected by edges.

Vertex

An object/point in a graph.

Edge

A connection between two vertices.

Adjacent

Two vertices are adjacent if connected by an edge; two edges are adjacent if they share a vertex.

Bipartite graph

A graph whose vertices can be divided into two disjoint sets with no edges within the same set.

Complete bipartite graph

A bipartite graph where every vertex in one set is adjacent to every vertex in the other set.

Complete graph

A graph in which every pair of vertices is adjacent.

Connected graph

A graph where there is a path from any vertex to any other vertex.

Chromatic number

The minimum number of colors needed for a proper vertex coloring.

Cycle

A path that starts and ends at the same vertex without repeating any other vertices.

Degree of a vertex

The number of edges incident to a vertex.

Euler trail

A walk that uses every edge exactly once.

Euler circuit

An Euler trail that starts and ends at the same vertex.

Multigraph

A graph that can have multiple edges between two vertices and loops.

Path

A walk that does not repeat vertices or edges, except possibly the first and last.

Planar

A graph that can be drawn in the plane without edges crossing.

Subgraph

A graph H whose vertices and edges are also vertices and edges of G.

Induced subgraph

A subgraph containing a set of vertices from G with exactly the edges between them that exist in G.

Tree

A connected graph with no cycles.

Forest

A graph with no cycles.

Leaf

A vertex in a tree with degree 1.

Vertex coloring

An assignment of colors to the vertices of a graph.

K_n

Complete graph on n vertices.

K{m,n}

Complete bipartite graph with sets of m and n vertices.

C_n

Cycle on n vertices.

P_n

Path with n edges and n+1 vertices.

Tree (Section 2.2)

A connected graph containing no cycles.

Forest (Section 2.2)

A graph containing no cycles.

Spanning tree

A tree that contains all the vertices of a connected graph.

Rooted tree

A tree with one vertex designated as the root.

Root

The designated vertex of a rooted tree.

Parent

The vertex closer to the root when two adjacent vertices are considered.

Child

The vertex farther from the root when two adjacent vertices are considered.

Grandparent

The parent of a vertex's parent.

Grandchild

The child of a vertex's child.

Ancestor

A vertex that lies on the path from another vertex to the root.

Descendant

A vertex whose path to the root contains another vertex.

Siblings

Vertices that have the same parent.

Equivalent definition of a tree

A graph is a tree if and only if there is exactly one path between every pair of distinct vertices.

Equivalent definition of a forest

A graph is a forest if and only if there is at most one path between any pair of vertices.

Planar graph

A graph that can be drawn in the plane without any edges crossing.

Face

A region created by the edges of a planar graph, including the outside region.

Euler's Formula

For a connected planar graph with v vertices, e edges, and f faces, v - e + f = 2.