Discrete Mathematics and Its Applications - Key Terminology

Comprehensive practice vocabulary flashcards covering key definitions, mathematical structures, and concepts from Discrete Mathematics and Its Applications (7th Edition).

Proposition

A declarative sentence (a sentence that declares a fact) that is either true or false, but not both.

Negation

The proposition, denoted by $\neg p$ (or $\overline{p}$), stating "It is not the case that $p$," which has the truth value opposite to that of $p$.

Conjunction

The compound proposition $p \wedge q$ ("$p$ and $q$") that is true when both $p$ and $q$ are true, and is false otherwise.

Disjunction

The compound proposition $p \vee q$ ("$p$ or $q$") that is false when both $p$ and $q$ are false, and is true otherwise.

Exclusive Or (XOR)

The proposition $p \oplus q$ that is true when exactly one of $p$ and $q$ is true, and is false otherwise.

Conditional Statement

The proposition $p \rightarrow q$ ("if $p$, then $q$") that is false when $p$ is true and $q$ is false, and is true otherwise; also called an implication.

Contrapositive

The conditional proposition $\neg q \rightarrow \neg p$ formed from the conditional statement $p \rightarrow q$, which always has the identical truth value as $p \rightarrow q$.

Biconditional Statement

The proposition $p \leftrightarrow q$ ("$p$ if and only if $q$") that is true when $p$ and $q$ have the same truth values, and is false otherwise.

Tautology

A compound proposition that is always true, regardless of the truth values of the propositional variables that occur in it.

Contradiction

A compound proposition that is always false, regardless of the truth values of the propositional variables that occur in it.

Logical Equivalence

The relationship between two compound propositions $p$ and $q$, denoted $p \equiv q$, meaning that $p \leftrightarrow q$ is a tautology.

Propositional Satisfiability

The property of a compound proposition being true for at least one assignment of truth values to its variables.

Predicate

The part of a statement that refers to a property that the subject of the statement can have, forming a propositional function $P(x)$ when combined with a variable.

Universal Quantification

The statement $\forall x P(x)$, asserting that $P(x)$ is true for all values of $x$ in the domain of discourse.

Existential Quantification

The statement $\exists x P(x)$, asserting that there exists an element $x$ in the domain such that $P(x)$ is true.

Uniqueness Quantifier

The quantifier denoted by $\exists! x P(x)$ or $\exists_1 x P(x)$, stating that there exists a unique (exactly one) element $x$ such that $P(x)$ is true.

Modus Ponens

The rule of inference based on the tautology $(p \wedge (p \rightarrow q)) \rightarrow q$, establishing that if $p$ and $p \rightarrow q$ are true, then $q$ is true.

Modus Tollens

The rule of inference based on the tautology $(\neg q \wedge (p \rightarrow q)) \rightarrow \neg p$, establishing that if $\neg q$ and $p \rightarrow q$ are true, then $\neg p$ is true.

Direct Proof

A mathematical proof of a conditional statement $p \rightarrow q$ that begins by assuming $p$ is true and uses definitions, axioms, theorems, and rules of inference to show that $q$ must also be true.

Proof by Contraposition

An indirect proof of a conditional statement $p \rightarrow q$ that proves the logically equivalent contrapositive statement $\neg q \rightarrow \neg p$.

Proof by Contradiction

An indirect proof of a statement $p$ that assumes $\neg p$ is true and shows that this assumption leads to a contradiction of the form $r \wedge \neg r$.

Set

An unordered collection of objects, called elements or members of the set.

Subset

A set $A$ is a subset of $B$, denoted $A \subseteq B$, if and only if every element of $A$ is also an element of $B$.

Power Set

The set of all subsets of the set $S$, denoted by $\mathcal{P}(S)$; for a finite set with $n$ elements, it contains $2^n$ elements.

Cartesian Product

The set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$, denoted by $A \times B = \{(a, b) \mid a \in A \wedge b \in B\}$.

Set Union

The set containing those elements that are in $A$, in $B$, or in both, denoted by $A \cup B = \{x \mid x \in A \vee x \in B\}$.

Set Intersection

The set containing those elements that are in both $A$ and $B$, denoted by $A \cap B = \{x \mid x \in A \wedge x \in B\}$.

Set Difference

The set containing those elements that are in $A$ but not in $B$, denoted by $A - B = \{x \mid x \in A \wedge x \notin B\}$; also called the complement of $B$ with respect to $A$.

Function

An assignment of exactly one element of a set $B$ (the codomain) to each element of a set $A$ (the domain), denoted $f: A \rightarrow B$.

Injection (One-to-One Function)

A function $f$ such that $f(a) = f(b)$ implies $a = b$ for all $a$ and $b$ in its domain.

Surjection (Onto Function)

A function $f: A \rightarrow B$ such that for every element $b \in B$, there exists an element $a \in A$ with $f(a) = b$.

Bijection (One-to-One Correspondence)

A function that is both injective (one-to-one) and surjective (onto).

Floor Function

The function denoted by $\lfloor x \rfloor$ that assigns to the real number $x$ the largest integer that is less than or equal to $x$.

Ceiling Function

The function denoted by $\lceil x \rceil$ that assigns to the real number $x$ the smallest integer that is greater than or equal to $x$.

Countable Set

A set that is either finite or has the same cardinality as the set of positive integers ($\aleph_0$).

Algorithm

A finite sequence of precise instructions for performing a computation or for solving a problem.

Big-O Notation

The asymptotic relationship asserting that $f(x)$ is $O(g(x))$ if there exist constants $C$ and $k$ such that $|f(x)| \le C|g(x)|$ whenever $x > k$.

Big-Omega Notation

The asymptotic relationship asserting that $f(x)$ is $\Omega(g(x))$ if there exist positive constants $C$ and $k$ such that $|f(x)| \ge C|g(x)|$ whenever $x > k$.

Big-Theta Notation

The asymptotic relationship asserting that $f(x)$ is $\Theta(g(x))$ if $f(x)$ is both $O(g(x))$ and $\Omega(g(x))$.

Greedy Algorithm

An algorithm that makes the optimal or best choice at each individual step according to a specified condition, without regard to future steps.

Halting Problem

The unsolvable decision problem asking whether a given computer program with a specific input will eventually stop running or continue forever.

Divisibility

The condition that for nonzero integer $a$ and integer $b$, there exists an integer $c$ such that $b = ac$, denoted by $a \mid b$.

Division Algorithm

The theorem stating that if $a$ is an integer and $d$ is a positive integer, there exist unique integers $q$ and $r$ with $0 \le r < d$ such that $a = dq + r$.

Congruence Modulo m

The relation stating that integers $a$ and $b$ are congruent modulo $m$, denoted $a \equiv b \pmod m$, if $m$ divides $a - b$.

Prime Number

An integer $p$ greater than 1 whose only positive integer divisors are 1 and $p$.

Fundamental Theorem of Arithmetic

The theorem stating that every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes in nondecreasing order.

Greatest Common Divisor (GCD)

The largest integer $d$ such that $d \mid a$ and $d \mid b$, where $a$ and $b$ are integers not both zero.

Bézout's Theorem

The theorem stating that if $a$ and $b$ are positive integers, there exist integers $s$ and $t$ such that $\gcd(a, b) = sa + tb$.

Chinese Remainder Theorem

A theorem stating that a system of linear congruences with pairwise relatively prime moduli has a unique simultaneous solution modulo the product of the moduli.

Fermat's Little Theorem

The theorem stating that if $p$ is a prime and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \pmod p$.

Principle of Mathematical Induction

The proof technique proving that a propositional function $P(n)$ is true for all positive integers $n$ by establishing that $P(1)$ is true (basis step) and that $P(k) \rightarrow P(k+1)$ is true for all positive integers $k$ (inductive step).

Strong Induction

A proof technique establishing that $P(n)$ is true for all positive integers $n$ by showing that $P(1)$ is true and that $[P(1) \wedge P(2) \wedge \dots \wedge P(k)] \rightarrow P(k+1)$ is true for all positive integers $k$.

Well-Ordering Property

The axiom stating that every nonempty subset of nonnegative integers has a least element.

Structural Induction

A proof technique used to prove properties of recursively defined sets by demonstrating the basis step for all initial elements and the recursive step for all elements constructed from existing elements.

Product Rule

A counting principle stating that if a procedure can be broken down into a sequence of two tasks, with $n_1$ ways to do the first task and $n_2$ ways to do the second task, then there are $n_1 n_2$ ways to do the procedure.

Sum Rule

A counting principle stating that if a task can be done either in one of $n_1$ ways or in one of $n_2$ ways, where none of the sets of ways overlap, then there are $n_1 + n_2$ ways to do the task.

Pigeonhole Principle

The principle stating that if $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then at least one box must contain two or more of the objects.

r-Permutation

An ordered arrangement of $r$ distinct elements selected from a set of $n$ elements, with count given by $P(n, r) = \frac{n!}{(n-r)!}$.

r-Combination

An unordered selection of $r$ elements from a set of $n$ elements, with count given by $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$.

Binomial Theorem

The identity stating that for variables $x$ and $y$ and nonnegative integer $n$, $(x+y)^n = \sum_{j=0}^n \binom{n}{j} x^{n-j} y^j$.

Pascal's Identity

The combinatorial identity stating that $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$ for positive integers $n$ and $k$ with $n \ge k$.

Combinatorial Proof

A mathematical proof of an identity based on counting arguments—either double counting (counting the same set in two different ways) or bijective proofs (establishing a one-to-one correspondence).

Derangement

A permutation of objects that leaves no object in its original position.

Random Variable

A function defined from the sample space of an experiment to the set of real numbers.

Expected Value

The weighted average or mean of a random variable $X$ on a sample space $S$, defined as $E(X) = \sum_{s \in S} p(s)X(s)$.

Variance

The measure of dispersion of a random variable $X$, defined as $V(X) = \sum_{s \in S} (X(s) - E(X))^2 p(s) = E(X^2) - E(X)^2$.

Recurrence Relation

An equation that expresses the $n$th term $a_n$ of a sequence in terms of one or more of the previous terms $a_0, a_1, \dots, a_{n-1}$.

Linear Homogeneous Recurrence Relation of Degree k

A recurrence relation of the form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$, where $c_1, c_2, \dots, c_k$ are real numbers and $c_k \neq 0$.

Divide-and-Conquer Algorithm

An algorithm that solves a problem by recursively dividing it into one or more smaller subproblems of the same type until simple base cases can be solved directly.

Generating Function

The formal power series $G(x) = \sum_{k=0}^\infty a_k x^k$ representing the sequence $a_0, a_1, \dots, a_k, \dots$.

Principle of Inclusion–Exclusion

A counting formula for the number of elements in the union of finite sets $A_1, A_2, \dots, A_n$ obtained by alternately adding and subtracting the sizes of all possible intersections of these sets.

Binary Relation

A subset of the Cartesian product $A \times B$ representing a relationship between elements of set $A$ and set $B$.

Reflexive Relation

A relation $R$ on a set $A$ such that $(a, a) \in R$ for every element $a \in A$.

Symmetric Relation

A relation $R$ on a set $A$ such that $(b, a) \in R$ whenever $(a, b) \in R$.

Antisymmetric Relation

A relation $R$ on a set $A$ such that for all $a, b \in A$, if $(a, b) \in R$ and $(b, a) \in R$, then $a = b$.

Transitive Relation

A relation $R$ on a set $A$ such that whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

Transitive Closure

The smallest transitive relation containing a given relation $R$, equal to the connectivity relation $R^* = \bigcup_{n=1}^\infty R^n$.

Equivalence Relation

A relation on a set that is reflexive, symmetric, and transitive.

Equivalence Class

The set of all elements in $A$ that are related to an element $a$ under an equivalence relation $R$, denoted by $[a]_R = \{s \mid (a, s) \in R\}$.

Partition

A collection of disjoint nonempty subsets of a set $S$ whose union equals $S$, which uniquely corresponds to the equivalence classes of an equivalence relation on $S$.

Partial Ordering

A relation on a set $S$ that is reflexive, antisymmetric, and transitive, forming a partially ordered set (poset) $(S, \preccurlyeq)$.

Hasse Diagram

A graphical representation of a finite poset where loops and edges implied by transitivity are omitted, and edges are drawn without arrows pointing upward.

Lattice

A partially ordered set in which every pair of elements has both a least upper bound (join) and a greatest lower bound (meet).

Topological Sorting

The construction of a total ordering compatible with a given partial ordering on a finite poset.

Simple Graph

An undirected graph in which each edge connects two distinct vertices and no two edges connect the same pair of vertices.

Degree of a Vertex

The number of edges incident with a vertex in an undirected graph, with loops counted twice, denoted by $\text{deg}(v)$.

Handshaking Theorem

The theorem stating that in an undirected graph $G = (V, E)$ with $m$ edges, $2m = \sum_{v \in V} \text{deg}(v)$.

Bipartite Graph

A graph whose vertex set $V$ can be partitioned into two disjoint subsets $V_1$ and $V_2$ such that every edge connects a vertex in $V_1$ to a vertex in $V_2$.

Matching

A subset of edges in a graph such that no two edges share a common vertex.

Hall's Marriage Theorem

The theorem stating that a bipartite graph with bipartition $(V_1, V_2)$ has a complete matching from $V_1$ to $V_2$ if and only if $|N(A)| \ge |A|$ for all subsets $A \subseteq V_1$.

Euler Circuit

A simple circuit in a graph containing every edge of that graph exactly once.

Euler Path

A simple path in a graph containing every edge of that graph exactly once.

Hamilton Circuit

A simple circuit in a graph that passes through every vertex of the graph exactly once.

Planar Graph

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

Euler's Formula

The relationship $r = e - v + 2$ connecting the number of regions $r$, edges $e$, and vertices $v$ in a connected planar simple graph.

Chromatic Number

The least number of colors needed to color the vertices of a graph so that no two adjacent vertices have the same color, denoted by $\chi(G)$.

Tree

A connected undirected graph containing no simple circuits.

Rooted Tree

A tree in which one vertex is designated as the root and every edge is directed away from this root.

Binary Search Tree

A binary tree where each vertex is labeled with a key such that the key of each vertex is larger than all keys in its left subtree and smaller than all keys in its right subtree.

Spanning Tree

A subgraph of a graph $G$ that is a tree containing every vertex of $G$.