DISCRETE

Statement

A declarative sentence that is either true or false.

Truth value

The truth or falsity of a statement.

Atomic statement

A statement that cannot be broken down into simpler statements.

Logical connective

A symbol or word used to combine or modify statements.

Conjunction

The statement P∧Q, meaning “P and Q.”

Disjunction

The statement P∨Q, meaning “P or Q.”

Implication

The statement P→Q, meaning “if P, then Q.”

Biconditional

The statement P↔Q, meaning “P if and only if Q.”

Negation

The statement ¬P, meaning “not P.”

Predicate

A statement involving a variable that becomes a statement with a truth value when the variable is assigned a value.

Quantifier

A symbol that specifies how many elements in a domain satisfy a predicate.

Universal quantifier

The symbol ∀, meaning “for all.”

Existential quantifier

The symbol ∃, meaning “there exists.”

Domain

The collection of values that a variable is allowed to take.

Free variable

A variable that is not bound by a quantifier.

Section 1.2

Implications

Hypothesis (antecedent)

The “if” part of an implication.

Conclusion (consequent)

The “then” part of an implication.

Converse

The implication Q→P, formed by switching the hypothesis and conclusion of P→Q.

Contrapositive

The implication ¬Q→¬P, formed by negating and switching the hypothesis and conclusion.

Inverse

The implication ¬P→¬Q, formed by negating the hypothesis and conclusion without switching them.

Necessary condition

A condition that must be true for another statement to be true.

Sufficient condition

A condition that guarantees another statement is true.

If and only if (iff)

A statement meaning that each of two conditions implies the other.

Logically equivalent statements

Statements that have the same truth value in every possible situation.

Section 1.3

Logical Reasoning

Truth table

A table showing the truth values of a logical statement for all possible truth-value combinations of its components.

Tautology

A statement that is true in every possible case.

Contradiction

A statement that is false in every possible case.

Contingency

A statement that is true in some cases and false in others.

Premise

A statement assumed to be true in an argument.

Conclusion

The statement an argument attempts to establish from its premises.

Deduction rule

A rule that allows a conclusion to be drawn from given premises.

Valid argument

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

De Morgan’s laws

Logical equivalences stating that the negation of a conjunction is equivalent to the disjunction of the negations, and the negation of a disjunction is equivalent to the conjunction of the negations.

Proof

A logical argument establishing that a mathematical statement is true.

Direct proof

A proof that starts with the hypothesis and uses logical steps to reach the conclusion.

Proof by contrapositive

A proof of P→Q by proving the equivalent statement ¬Q→¬P.

Proof by contradiction

A proof that assumes a statement is false and derives a contradiction.

Counterexample

An example demonstrating that a statement is false.

Arbitrary element

An element chosen without any special restrictions, used to prove a statement for all elements of a set.

Existence proof

A proof establishing that at least one object with a specified property exists.

Uniqueness proof

A proof establishing that exactly one object has a specified property.

Biconditional proof

A proof of an “if and only if” statement by proving both directions.

Lemma

A mathematical statement proved to help establish another result.

Proposition

A mathematical statement that has been proved to be true.

Corollary

A result that follows directly from a previously established theorem or result.

Set

A collection of distinct objects.

Element

An object that belongs to a set.

Empty set

A set containing no elements, denoted by ∅.

Subset

A set A is a subset of B if every element of A is also an element of B.

Proper subset

A set A is a proper subset of B if every element of A is in B, but A

Set equality

Two sets are equal if they contain exactly the same elements.

Union

The set A∪B containing elements that belong to A, B, or both.

Intersection

The set A∩B containing elements that belong to both A and B.

Set difference

The set A∖B containing elements that belong to A but not to B.

Complement

The set of elements in the universal set that do not belong to a specified set.

Cartesian product

The set A×B of all ordered pairs (a,b) where a∈A and b∈B.

Ordered pair

A pair of elements in which order matters.

Power set

The set of all subsets of a set A, denoted by P(A).

Cardinality

The number of elements in a set.

Relation

A set of ordered pairs describing a relationship between elements.

Reflexive relation

A relation in which every element is related to itself.

Irreflexive relation

A relation in which no element is related to itself.

Symmetric relation

A relation in which if a is related to b, then b is related to a.

Antisymmetric relation

A relation in which if a is related to b and b is related to a, then a=b.

Transitive relation

A relation in which if a is related to b and b is related to c, then a is related to c.

Equivalence relation

A relation that is reflexive, symmetric, and transitive.

Graph

An ordered pair G=(V,E), where V is a nonempty set of vertices and E is a set of two-element subsets of V called edges.

Vertex

An element of the vertex set of a graph.

Edge

A connection between two vertices of a graph.

Adjacent vertices

Two vertices connected by an edge.

Adjacent edges

Two edges that share a vertex.

Degree of a vertex

The number of edges incident to that vertex, with a loop counting twice when loops are allowed.

Degree sequence

The list of vertex degrees of a graph, usually arranged in nonincreasing order.

Isolated vertex

A vertex with degree zero.

Loop

An edge that connects a vertex to itself.

Multigraph

A graph that allows multiple edges between the same pair of vertices and may allow loops.

Simple graph

A graph with no loops or multiple edges.

Complete graph

A simple graph in which every pair of distinct vertices is connected by an edge, denoted by K

Complete bipartite graph

A bipartite graph in which every vertex in one part is connected to every vertex in the other part, denoted by K

Walk

A sequence of vertices in which consecutive vertices are connected by edges.

Path

A walk in which no vertex is repeated.

Cycle

A closed path that starts and ends at the same vertex, with no other repeated vertices.

Connected graph

A graph in which a path exists between every pair of vertices.

Disconnected graph

A graph that is not connected.

Bipartite graph

A graph whose vertices can be divided into two disjoint sets so that every edge connects a vertex in one set to a vertex in the other.

Vertex coloring

An assignment of colors to the vertices of a graph.

Proper coloring

A vertex coloring in which adjacent vertices have different colors.

Chromatic number

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

Graph isomorphism

A correspondence between the vertices of two graphs that preserves adjacency.

Isomorphic graphs

Two graphs that have the same structure, even if their vertices have different names or drawings.

Bijection

A function that is both injective and surjective. (Included as a function term for review; the textbook introduces it later.)

Subgraph

A graph formed from a subset of the vertices and a subset of the edges of another graph.

Induced subgraph

A subgraph formed by choosing a subset of vertices and including every edge of the original graph connecting two chosen vertices.

Handshake lemma

The sum of the degrees of all vertices in a finite graph equals twice the number of edges.

Even-degree vertex

A vertex whose degree is an even number.

Odd-degree vertex

A vertex whose degree is an odd number.

Path graph

A graph consisting of a single path, denoted by P

​