Key Concepts in Discrete Structures

Why This Matters

Discrete structures are the fundamental building blocks that power everything from database queries to encryption algorithms to social network analysis. When you're tested on discrete mathematics, you're being evaluated on your ability to recognize which structure models which problem, understand how operations transform these structures, and apply logical reasoning to prove properties. The concepts here (sets, relations, graphs, logic) appear repeatedly across computer science, and exam questions often ask you to connect them.

These structures form a hierarchy of increasing expressiveness. Sets give you collections, relations add connections between elements, functions constrain those connections, and graphs visualize them. Logic provides the language to reason about all of it, and combinatorics counts the possibilities. Don't just memorize definitions. Know what each structure can represent and when to use one over another.

---

Foundational Collections and Mappings

These structures define how we group objects and establish correspondences between them.

Sets

A set is a collection of distinct objects. It's the most primitive discrete structure. You can define a set by listing its elements $\{1, 2, 3\}$ or by specifying a property $\{x : x > 0\}$.

The fundamental operations you need to know:

• Union ($A \cup B$): everything in $A$, $B$, or both
• Intersection ($A \cap B$): only elements in both $A$ and $B$
• Difference ($A - B$): elements in $A$ that are not in $B$
• Complement ($\overline{A}$): everything in the universal set that's not in $A$

Cardinality $|A|$ measures the size of a set. Understanding finite vs. infinite sets matters for counting arguments, and the power set $\mathcal{P}(A)$ (the set of all subsets of $A$) has cardinality $2^{|A|}$.

Relations

A relation on sets $A$ and $B$ is a set of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. It generalizes the idea of "is related to."

Four key properties to check for any relation on a set:

• Reflexive: every element relates to itself ($\forall a, (a,a) \in R$)
• Symmetric: if $(a,b) \in R$ then $(b,a) \in R$
• Transitive: if $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R$
• Antisymmetric: if $(a,b) \in R$ and $(b,a) \in R$ then $a = b$

An equivalence relation is one that's reflexive, symmetric, and transitive. These partition a set into disjoint equivalence classes. On exams, look for all three properties together.

A partial order is reflexive, antisymmetric, and transitive. This models "less than or equal to" style relationships.

Functions

A function is a special relation where each input maps to exactly one output. That uniqueness constraint is what makes functions predictable and useful.

Classification determines what you can do with a function:

• Injective (one-to-one): different inputs always give different outputs
• Surjective (onto): every element in the codomain is hit by some input
• Bijective (both): a perfect one-to-one correspondence, which guarantees an inverse exists

Composition $f \circ g$ means "apply $g$ first, then $f$." An inverse function $f^{-1}$ reverses $f$, but it only exists when $f$ is bijective.

---

Graph-Based Structures

Graphs model pairwise relationships visually and computationally. They're essential for algorithm design and network analysis.

Graphs

A graph $G = (V, E)$ consists of a set of vertices (nodes) connected by edges. It's the go-to structure for modeling networks, dependencies, and relationships.

Types you should know:

• Undirected: edges have no direction (friendship is mutual)
• Directed (digraph): edges have direction (following someone on social media isn't necessarily mutual)
• Weighted: edges carry numerical values (distances, costs)
• Simple: no self-loops and no multiple edges between the same pair of vertices

Key properties:

• Degree of a vertex: the number of edges connected to it. In a directed graph, you track in-degree and out-degree separately.
• Path: a sequence of vertices connected by edges
• Cycle: a path that starts and ends at the same vertex
• Connectivity: a graph is connected if there's a path between every pair of vertices

The Handshaking Lemma states that the sum of all vertex degrees equals $2|E|$, since each edge contributes to the degree of two vertices.

Trees

A tree is a connected graph with no cycles. Equivalently, a tree with $n$ vertices has exactly $n - 1$ edges.

Trees have a hierarchical structure with a root node and parent-child relationships, making them natural for representing recursive structures.

Special types:

• Binary trees: each node has at most 2 children
• Binary search trees (BSTs): left child < parent < right child, enabling efficient searching
• Balanced trees: height is kept at $O(\log n)$ to guarantee efficient operations
• Spanning trees: a subgraph that's a tree and includes all vertices of the original graph

---

Logical Foundations

Logic provides the formal language for reasoning about truth, validity, and proof.

Propositional Logic

A proposition is a statement that's either true or false. You combine propositions using logical connectives:

• $\neg$ (NOT): flips the truth value
• $\land$ (AND): true only when both operands are true
• $\lor$ (OR): true when at least one operand is true
• $\rightarrow$ (implication): $p \rightarrow q$ is false only when $p$ is true and $q$ is false
• $\leftrightarrow$ (biconditional): true when both sides have the same truth value

Truth tables systematically evaluate compound propositions by listing all possible input combinations. They're your main tool for proving logical equivalences.

Key equivalences to memorize:

• De Morgan's Laws: $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$
• Contrapositive: $p \rightarrow q \equiv \neg q \rightarrow \neg p$
• A tautology is always true; a contradiction is always false

Predicate Logic

Predicate logic extends propositional logic with variables and quantifiers:

• Universal quantifier ($\forall$): "for all" or "for every"
• Existential quantifier ($\exists$): "there exists" or "for some"

A predicate like $P(x)$ expresses a property of an object. This lets you write statements like "for all integers $x$, if $x$ is even, then $x^2$ is even."

Negating quantified statements is a common exam skill:

• $\neg(\forall x \, P(x)) \equiv \exists x \, \neg P(x)$
• $\neg(\exists x \, P(x)) \equiv \forall x \, \neg P(x)$

When negating, you flip the quantifier and negate the predicate. For nested quantifiers, apply this rule from left to right.

Boolean Algebra

Boolean algebra is a two-valued system (true/false, 1/0) with operations AND, OR, and NOT. It provides the mathematical foundation of digital circuits.

Key algebraic laws for simplifying expressions:

• Associativity, commutativity, distributivity (AND distributes over OR and OR distributes over AND)
• Absorption: $a \lor (a \land b) = a$
• Identity: $a \lor 0 = a$, $a \land 1 = a$
• Complement: $a \lor \neg a = 1$, $a \land \neg a = 0$

These laws apply directly in circuit design, programming conditionals, and database queries.

---

Counting and Recurrence

These techniques answer "how many?" questions. They're fundamental for algorithm analysis and probability.

Combinatorics

Two core formulas:

• Permutations (order matters): $P(n,r) = \frac{n!}{(n-r)!}$
• Combinations (order doesn't matter): $C(n,r) = \frac{n!}{r!(n-r)!}$

The inclusion-exclusion principle counts the size of unions by correcting for overcounting:

$|A \cup B| = |A| + |B| - |A \cap B|$

This extends to more sets. For three sets:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

The pigeonhole principle is deceptively powerful: if you place $n$ items into $k$ containers and $n > k$, at least one container holds more than one item. Many proof problems rely on this.

Recurrence Relations

A recurrence relation defines each term of a sequence using previous terms. The Fibonacci sequence is a classic example: $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0, a_1 = 1$.

Solving techniques:

1. Iteration (unrolling): substitute repeatedly until you spot a pattern, then prove it
2. Characteristic equation: for linear recurrences like $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, solve $r^2 = c_1 r + c_2$ to find the closed form
3. Generating functions: a more advanced technique that encodes the sequence as coefficients of a power series

In algorithm analysis, the Master Theorem solves recurrences of the form $T(n) = aT(n/b) + f(n)$, which arise from divide-and-conquer algorithms.

---

Computational Models and Languages

These structures formalize computation itself: what can be computed, how efficiently, and with what representations.

Algorithms

An algorithm is a step-by-step procedure for solving a problem. The two key concerns are correctness (does it produce the right answer?) and efficiency (how fast and with how much memory?).

Complexity analysis uses Big-O notation to describe growth rates:

• Time complexity: how the number of operations grows with input size
• Space complexity: how memory usage grows with input size

Common paradigms:

• Divide and conquer: split the problem, solve subproblems, combine results (e.g., merge sort)
• Dynamic programming: solve overlapping subproblems once and store results (e.g., Fibonacci with memoization)
• Greedy: make the locally optimal choice at each step (e.g., Dijkstra's shortest path)

Recognizing which paradigm fits a problem type is a frequent exam skill.

Finite State Machines

A finite state machine (FSM) is a computational model with a finite number of states, transitions triggered by inputs, and designated accepting states. It models systems with limited memory.

• Deterministic FSMs (DFAs): exactly one transition per state-input pair
• Nondeterministic FSMs (NFAs): multiple possible transitions for a given state-input pair

Every NFA can be converted to an equivalent DFA (though the DFA may have exponentially more states). FSMs are used in lexical analysis, protocol design, and pattern matching.

Formal Languages

A formal language is a set of strings over some alphabet, defined by grammatical rules. It formalizes what "valid syntax" means.

The Chomsky hierarchy classifies languages by complexity:

Each level is strictly more powerful than the one above it. Regular languages are the simplest; recursively enumerable languages are the most general.

---

Algebraic Structures

Matrices and number theory provide computational tools for solving systems and securing communications.

Matrices

A matrix is a rectangular array of values arranged in rows and columns. Matrices represent linear transformations and systems of equations.

Key operations and facts:

• Addition: element-wise, requires same dimensions
• Multiplication: $AB$ is defined when the number of columns in $A$ equals the number of rows in $B$. Matrix multiplication is not commutative ($AB \neq BA$ in general).
• Determinant: a scalar value that tells you whether a matrix is invertible. $A^{-1}$ exists if and only if $\det(A) \neq 0$.
• Identity matrix $I$: the matrix equivalent of multiplying by 1

For discrete math specifically, adjacency matrices represent graphs. Entry $(i,j)$ equals 1 if there's an edge from vertex $i$ to vertex $j$, and 0 otherwise. A powerful result: the entry $(i,j)$ in $A^k$ gives the number of paths of length $k$ from vertex $i$ to vertex $j$.

Number Theory

Number theory studies properties of integers, focusing on divisibility, primes, and modular arithmetic.

• Fundamental Theorem of Arithmetic: every integer greater than 1 has a unique prime factorization. This is the foundation for many proofs about integers.
• GCD and LCM: the greatest common divisor and least common multiple. The Euclidean algorithm efficiently computes the GCD through repeated division.
• Modular arithmetic: $a \equiv b \pmod{n}$ means $n$ divides $(a - b)$. This is essential for cryptography (RSA relies on modular exponentiation), hashing, and computer arithmetic.

---

Quick Reference Table

---

Self-Check Questions

1. Both relations and functions are sets of ordered pairs. What property distinguishes a function from a general relation, and how would you verify this property given a relation?

2. Compare graphs and trees: what structural constraint makes a tree a special case of a graph, and what property does this guarantee about paths between vertices?

3. If you need to count the number of ways to select a committee of 5 from 12 people, would you use permutations or combinations? What if the committee has a chair, vice-chair, and three regular members?

4. Explain how propositional logic and predicate logic differ in expressiveness. Give an example of a statement that requires predicate logic to express formally.

5. A recurrence relation defines $T(n) = 2T(n/2) + n$ with $T(1) = 1$. What type of algorithm typically produces this recurrence, and what is its time complexity in Big-O notation?