Discrete Mathematics: Sets, Logic, Relations and Graphs

Discrete Mathematics follows the mathematical language underlying algorithms: sets, logic, relations, combinatorics, and graphs. The topics remain on one backbone so that notation and definitions can be reused consistently across later algorithmic problems.

The subject matters not because it is an easier alternative to continuous mathematics, but because many objects in computer science are inherently discrete. A state machine, reachability relation, truth table, combinatorial count, or graph path shares the same discipline: define the objects precisely and make every inference traceable to explicit rules.

Unit 1: Introduction to Set Theory

1.1. Set Concept

A set is a well-defined collection of distinct objects called elements. Membership is written as

x ∈ A
x ∉ A.

A set can be described by listing its elements or by specifying a property that characterizes membership.

1.2. Venn Diagrams

Venn diagrams represent sets as regions and make operations such as union, intersection, difference, and complement visually explicit. They are useful for reasoning but do not replace formal set definitions.

1.3. Finite and Infinite Sets

A finite set has a finite cardinality. Infinite sets contain no finite list of all elements. Different infinite sets can nevertheless be compared through one-to-one correspondences.

1.4. Empty Set

The empty set ∅ contains no elements. It is a subset of every set and is not the same object as a set that contains the empty set.

1.5. Subset and Proper Subset

A ⊆ B

means every element of A belongs to B. A proper subset is a subset that is not equal to the containing set.

1.6. Equality of Sets

Two sets are equal exactly when they contain the same elements:

A = B  ⇔  A ⊆ B and B ⊆ A.

Order and repeated listing do not change a set.

1.7. Universal Set

The universal set U specifies the reference domain in a particular discussion. Complements are always interpreted relative to this universe.

1.8. Union

A ∪ B = {x | x∈A or x∈B}.

1.9. Intersection

A ∩ B = {x | x∈A and x∈B}.

Disjoint sets have empty intersection.

1.10. Complement and Difference

A^c = U \ A
A \ B = {x | x∈A and x∉B}.

1.11. Symmetric Difference

The symmetric difference contains elements that belong to exactly one of the two sets:

A △ B = (A\B) ∪ (B\A).

1.12. Ordered Pairs and Cartesian Product

An ordered pair (a,b) distinguishes first and second components. The Cartesian product is

A x B = {(a,b) | a∈A, b∈B}.

In general A x B and B x A are not the same set.

1.13. Boolean Algebra of Sets

Set operations obey commutative, associative, distributive, identity, absorption, complement, and De Morgan laws. These laws parallel Boolean logic and digital-circuit algebra.

1.14. Number Sets

The common hierarchy includes natural numbers, integers, rational numbers, real numbers, and complex numbers. Inclusion relations depend on the chosen convention for natural numbers but the structural containment is otherwise standard.

1.15. Intervals

Intervals describe subsets of the real line. Parentheses indicate excluded endpoints and brackets included endpoints, with infinity always written as an open boundary.

1.16. Absolute Value

|x| = x       if x ≥ 0
|x| = -x      if x < 0.

Geometrically, |x-a| is the distance between x and a on the real line.

1.17. Integer Part

The floor function ⌊x⌋ is the greatest integer less than or equal to x. It is a step function and must not be confused with ordinary rounding.

1.18. Countability and Cardinality

For finite sets, cardinality is an ordinary nonnegative integer. For infinite sets, the question “how many elements?” is formalized through bijections. Two sets have the same cardinality when a bijection exists between them.

An infinite set is countably infinite when its elements can be placed in one-to-one correspondence with the natural numbers. The integers may appear larger than the natural numbers, yet they can be enumerated in a suitable order. The rational numbers are also countable when arranged by a systematic traversal.

The real numbers are different. Cantor's diagonal argument shows that the real numbers in [0,1] cannot be listed in bijection with the natural numbers. Infinite sets can therefore have genuinely different cardinalities.

Cardinality also has an algorithmic interpretation. Whether a state space is finite, countable, or continuous affects whether exhaustive traversal is possible, how states can be represented, and which verification strategies are feasible.

1.19. Reading Logic, Combinatorics, and Graph Structures Within One Discrete Model

Discrete mathematics supplies structural language for computer science:

Sets
  ↓
Counting and logic
  ↓
Relations and functions
  ↓
Graphs and algebraic structure
  ↓
Algorithms and representations

Sets define collections and domains. Logic defines valid propositions and transformations. Relations model pairwise structure; functions impose deterministic mapping. Graphs model connectivity and dependency. Algorithms convert these mathematical structures into finite computational procedures.

1.20. Separating Relations, Functions, Graphs, and Algorithms

Element ≠ subset. x∈A is membership; B⊆A compares two sets.

Empty set ≠ set containing the empty set. ∅ has zero elements, while {∅} has one element.

Union ≠ intersection. Union uses logical OR; intersection uses logical AND.

Permutation ≠ combination. Permutations distinguish order; combinations do not.

Implication ≠ converse. p→q is equivalent to its contrapositive ¬q→¬p, not generally to q→p.

Tautology ≠ satisfiable formula. A tautology is true under every assignment; a satisfiable formula only needs at least one true assignment.

Symmetric ≠ antisymmetric. Antisymmetry is not the negation of symmetry; a relation can satisfy both in appropriate cases.

Equivalence relation ≠ order relation. Equivalence uses symmetry; partial order uses antisymmetry.

Relation ≠ function. A function must assign exactly one output to each domain element.

Injective ≠ surjective. Injectivity constrains repeated outputs; surjectivity requires the entire codomain to be reached.

Graph ≠ tree. Every tree is a graph, but a tree must be connected and acyclic.

Walk ≠ path. A path imposes stronger nonrepetition conditions than a general walk.

Algorithm ≠ program. An algorithm is an abstract procedure; a program is an implementation in a computational environment.

In discrete mathematics, a strong solution is often determined by representation rather than by a long calculation. Expressing the same problem as a set, relation, proposition, or graph can change both the proof and the algorithm. The core aim is therefore to develop modelling discipline rather than to accumulate formulas.

Unit 2: Permutations and Combinations

2.1. Factorial

For a positive integer n,

n! = n(n-1)...2·1,

with 0! = 1 by convention and combinatorial consistency.

2.2. Counting Principles

The addition rule handles mutually exclusive alternatives. The multiplication rule handles sequential choices. Many combinatorial formulas are direct consequences of these two principles.

2.3. Permutation

When order matters, the number of arrangements of r distinct objects chosen from n is

P(n,r) = n!/(n-r)!.

For all n objects, the count is n!.

2.4. Permutations with Repetition

If a multiset of n objects contains groups of identical elements with multiplicities n1,...,nk, the number of distinct arrangements is

n!/(n1! n2! ... nk!).

2.5. Permutation Group

All permutations of n objects form the symmetric group S_n under composition. The identity permutation, inverses, closure, and associativity give the group structure.

2.6. Combination

When order does not matter,

C(n,r) = n!/[r!(n-r)!].

2.7. Properties of Combinations

Important identities include

C(n,r) = C(n,n-r)
C(n,r) + C(n,r-1) = C(n+1,r).

These connect combinations with Pascal's triangle and the binomial theorem.

2.8. Combinations with Repetition

The number of ways to select r items from n types when repetition is allowed is

C(n+r-1,r).

2.9. Inclusion-exclusion Principle

When objects may satisfy several properties simultaneously, intersections can be counted more than once. The inclusion-exclusion principle corrects this overcounting by alternating signs.

For two sets,

|A ∪ B| = |A| + |B| − |A ∩ B|.

For three sets, pairwise intersections are subtracted and the triple intersection is added back:

|A ∪ B ∪ C|
= |A| + |B| + |C|
− |A ∩ B| − |A ∩ C| − |B ∩ C|
+ |A ∩ B ∩ C|.

In the general form, single-set terms are added, pairwise intersections are subtracted, triple intersections are added, and the sign continues to alternate.

A major application is counting onto functions. If every target value must be used at least once, assignments that leave one or more target values unused can be removed from the unrestricted count through inclusion-exclusion.

The method is therefore not merely a formula to memorize. Its central question is: “which objects have been counted multiple times, and at which intersection level?”

Unit 3: Propositional Logic

To evaluate a logical formula, identify atomic propositions and disambiguate connective scope with parentheses. Use truth tables or equivalence transformations, preserving logical equivalence at each step. With quantifiers, specify the domain and quantifier order explicitly. One counterexample can refute a universal claim, whereas several confirming examples cannot establish its proof.

3.1. Proposition

A proposition is a declarative statement that has a definite truth value, true or false. Questions, commands, and open expressions containing unspecified variables are not propositions until interpreted appropriately.

3.2. Compound Proposition and Truth Table

Logical connectives combine propositions into compound propositions. A truth table lists all possible truth-value assignments and the resulting value of the compound expression.

3.3. Negation

If p is a proposition, ¬p reverses its truth value.

3.4. Conjunction

p ∧ q

is true only when both propositions are true.

3.5. Disjunction

The inclusive OR

p ∨ q

is true when at least one operand is true. Exclusive OR is a different operation and is true when exactly one is true.

3.6. Conditional Proposition

p → q

is false only when p is true and q is false. It is logically equivalent to

¬p ∨ q.

3.7. Converse, Inverse, and Contrapositive

For p→q:

• converse: q→p,
• inverse: ¬p→¬q,
• contrapositive: ¬q→¬p.

The original conditional is logically equivalent to its contrapositive, not generally to its converse or inverse.

3.8. Biconditional

p ↔ q

is true when p and q have the same truth value. It represents two implications together.

3.9. Equivalent Propositions and Standard Forms

Two formulas are logically equivalent if they have identical truth values under every assignment. Conjunctive and disjunctive normal forms provide systematic representations built from literals.

3.10. Tautology and Contradiction

A tautology is true under every truth assignment; a contradiction is false under every assignment. A contingency is true for some assignments and false for others.

3.11. Laws of Logic

Commutative, associative, distributive, identity, idempotent, absorption, double-negation, and De Morgan laws allow expressions to be transformed without changing their truth functions.

3.12. Quine Method

The Quine-style tabular approach systematically manipulates truth assignments or implicants to simplify Boolean expressions. In digital-logic applications, systematic minimization reduces redundant terms.

3.13. Logical Circuits

Boolean expressions map naturally to logic gates. AND, OR, and NOT correspond to fundamental gates, while more complex circuits implement compound propositions. Logical equivalence can therefore be used to simplify circuit structure.

3.14. Proof Patterns for Discrete Structures

A discrete-mathematics result is stronger when its proof method matches the structure of the statement.

Direct proof starts from the hypotheses and derives the conclusion. Contrapositive proof establishes not Q -> not P instead of P -> Q. Contradiction assumes the negation of the target and derives an impossibility. Mathematical induction proves a base case and an induction step.

For recursive data structures and loops, induction and invariants are closely related. The induction hypothesis describes what remains true after a smaller recursive call; a loop invariant describes what remains true after another iteration.

A counterexample is equally important: one valid counterexample is sufficient to disprove a universal claim.

3.15. Predicates and Quantifiers

In propositional logic, each atomic statement is directly true or false. Predicate logic introduces expressions containing variables. An expression such as P(x) need not be a proposition until x is assigned or bound by a quantifier.

The two fundamental quantifiers are

∀x P(x)    P(x) holds for every x
∃x P(x)    P(x) holds for at least one x.

The set over which a variable ranges is the domain of discourse. The same symbolic expression can have different truth values under different domains.

Negation of quantified expressions must switch the quantifier:

¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x).

The negation of “every user is authorized” is not “no user is authorized”; it is “at least one user is not authorized.” This distinction matters in formal requirements and access-control rules.

3.16. Nested Quantifiers

With multiple quantifiers, order can change meaning:

∀x ∃y R(x,y)
∃y ∀x R(x,y).

The first statement permits a different y for each x. The second asserts that one single y works for every x. They are not equivalent in general.

A reliable reading procedure is to identify the domain, bind quantifiers from left to right, and make the dependency of every variable explicit.

3.17. Rules of Inference and Proof Patterns

A valid argument guarantees that whenever all premises are true, its conclusion is true. Common inference rules include modus ponens, modus tollens, hypothetical syllogism, and disjunctive syllogism.

p
p → q
∴ q

is modus ponens. Such a rule is independent of the application domain; its validity comes from logical form.

Core proof patterns in discrete mathematics include:

• Direct proof: derive the conclusion from the hypothesis.
• Proof by contraposition: prove ¬q → ¬p instead of the equivalent p → q.
• Proof by contradiction: assume the negation and derive an impossibility.
• Proof by cases: partition the possibilities into exhaustive cases.
• Existence proof: construct an object or establish existence indirectly.
• Uniqueness proof: assume two candidates and show they must coincide.
• Counterexample: refute a universal claim with one valid case.

Examples can illustrate a theorem, but examples alone do not prove a universal statement. In contrast, one counterexample is enough to disprove it.

3.18. Mathematical, Strong, and Structural Induction

Mathematical induction proves statements indexed by natural numbers through two obligations:

1. establish the base case;
2. show that P(k) implies P(k+1).

Once both are established, the proposition holds from the base index onward.

In strong induction, the proof of P(k+1) may use all earlier cases P(n0), ..., P(k), not only P(k). This form is natural when an object is decomposed into several smaller instances.

Structural induction follows the constructors of a recursively defined structure instead of the natural-number order. Base structures are verified first; then every constructor is shown to preserve the property. Trees, logical formulas, and syntax trees are typical examples.

Loop invariants use the same proof idea in program verification: a property that is true before the loop and preserved by every iteration remains true throughout execution.

3.19. Constructive Proof: Proving Existence by Building the Object

A direct way to prove an existence claim is to construct an object satisfying the required conditions. Such a proof often does more than establish existence: it also provides an algorithm for producing a witness.

Consider the claim:

For every even n >= 4, there exists a simple 3-regular graph on n vertices.

A necessary condition follows from the handshaking lemma:

sum(deg(v)) = 2|E|

In a 3-regular graph, the left side is 3n, so n must be even. That proves necessity, not existence.

For sufficiency, place vertices 0,1,...,n-1 on a cycle and add the cycle edges:

{i, (i+1) mod n}

Then add a perfect matching connecting opposite vertices:

{i, i+n/2}   for 0 <= i < n/2

The cycle contributes degree two at every vertex and the matching contributes one more edge. For n >= 4, no self-loop or duplicate edge is introduced, so every vertex has degree exactly three. The proof is constructive and can be implemented with O(n) edge generation.

The reasoning separates three layers:

necessary condition -> which values cannot work?
construction        -> how is a witness produced?
verification        -> why does the constructed object satisfy every condition?

Constructive proofs are particularly valuable in computer science because an existence argument can become an executable construction procedure.

3.20. Proof, Counterexample, and Structure

Checking a statement on several examples is not a proof. One counterexample can refute a universal claim; proving the claim requires definitions, inference rules, or an appropriate proof technique. In particular, P → Q is not equivalent to its converse Q → P. Its contrapositive ¬Q → ¬P, however, is logically equivalent to the original implication.

Induction has two separate obligations: a base case and an induction step. In the step, the goal is to derive P(k+1) from the assumption that P(k) holds; merely computing another example does not establish the implication. Strong induction allows all earlier cases to be used as the induction hypothesis.

For relations, reflexivity, symmetry, antisymmetry, and transitivity are independent properties. An equivalence relation is reflexive, symmetric, and transitive; a partial order is reflexive, antisymmetric, and transitive. The two structures serve different purposes: equivalence relations partition a set into equivalence classes, while partial orders describe comparison structure.

Graph terminology also matters. Paths, trails, cycles, connectivity, and degree are distinct notions. Summing the degrees of all vertices counts each edge twice, so the total is 2|E|. The same handshake lemma explains why the number of odd-degree vertices must be even.

In counting problems, ask first whether order matters, whether repetition is allowed, and whether choices are independent. Those questions usually identify the correct model more reliably than memorising isolated permutation and combination formulas.

Unit 4: Relations

4.1. Relation Concept

A binary relation from A to B is any subset of the Cartesian product:

R ⊆ A x B.

A relation on A is a subset of A x A.

4.2. Forms of Representation

Relations can be represented as sets of ordered pairs, tables, directed graphs, or zero-one matrices. Each representation emphasizes different operations.

4.3. Inverse Relation

The inverse relation reverses every ordered pair:

R^-1 = {(b,a) | (a,b)∈R}.

4.4. Reflexive Relation

A relation on A is reflexive if

(a,a) ∈ R

for every a∈A.

4.5. Symmetric Relation

It is symmetric if

(a,b)∈R ⇒ (b,a)∈R.

4.6. Antisymmetric Relation

It is antisymmetric if

(a,b)∈R and (b,a)∈R ⇒ a=b.

Antisymmetry does not mean "not symmetric"; the two properties address different conditions.

4.7. Transitive Relation

It is transitive if

(a,b)∈R and (b,c)∈R ⇒ (a,c)∈R.

4.8. Equivalence Relation

An equivalence relation is reflexive, symmetric, and transitive. It divides a set into disjoint equivalence classes.

4.9. Equivalence Classes and Partitions

For an equivalence relation, the class of a is

[a] = {x∈A | xRa}.

Distinct classes are disjoint, and their union is the entire set. Conversely, every partition defines an equivalence relation.

4.10. Order Relations

A partial order is reflexive, antisymmetric, and transitive. A total order additionally makes every pair comparable. Hasse diagrams provide a compact representation of finite partially ordered sets by omitting implied transitive edges.

4.11. Hasse Diagrams and the Structure of Partial Orders

For a finite partial order, a Hasse diagram removes reflexive loops and edges implied solely by transitivity. Larger elements are conventionally drawn higher, making the essential covering relation easier to read.

A minimal element is not the same as a least element. A minimal element has nothing strictly below it; a least element is below every element of the set. Several minimal elements may exist, whereas a least element, if it exists, is unique. The same distinction applies to maximal versus greatest elements.

Elements above every member of a subset are upper bounds; elements below every member are lower bounds. The smallest upper bound is a least upper bound, and the largest lower bound is a greatest lower bound. Partial orders in which the corresponding bounds exist for appropriate pairs lead naturally to lattice structures.

These ideas are useful in dependency analysis, version ordering, and precedence systems where imposing one global total order would discard meaningful incomparability.

4.12. Relation Matrix

For a finite relation, a zero-one matrix records whether each ordered pair belongs to the relation. Reflexivity, symmetry, and other properties can often be checked from matrix structure.

4.13. Closures

A closure adds the minimum information needed to give a relation a desired property, such as reflexive, symmetric, or transitive closure.

4.14. Warshall Algorithm

Warshall's algorithm computes transitive closure from an adjacency/relation matrix. At stage k, paths are allowed to use the first k vertices as intermediate points. The Boolean recurrence is

r_ij^(k) = r_ij^(k-1) OR
           (r_ik^(k-1) AND r_kj^(k-1)).

Unit 5: Functions and Operations

5.1. Function

A function f:A→B assigns exactly one element of B to every element of A. A function is a special kind of relation with a uniqueness and totality requirement on the domain.

5.2. Types of Functions

• injective: distinct inputs have distinct outputs;
• surjective: every element of the codomain is reached;
• bijective: both injective and surjective.

A bijection establishes a one-to-one correspondence between the sets.

5.3. Inverse Function

A function has an inverse function exactly when it is bijective. The inverse reverses input and output roles:

f^-1(f(x)) = x.

5.4. Composition

For compatible functions,

(g∘f)(x) = g(f(x)).

Composition is associative but generally not commutative.

5.5. Binary Operation

A binary operation on A is a function

*: A x A → A.

Closure is therefore built into the definition.

5.6. Properties of an Operation

Associativity, commutativity, identity elements, and inverses are central properties. Different combinations lead to algebraic structures such as semigroups, monoids, and groups.

Unit 6: Graph Theory

A graph problem starts by defining what vertices and edges represent and whether the graph is directed or weighted. Choose traversal for reachability, inspect weight conditions for shortest paths, and evaluate connectivity and weights for spanning-tree problems. A method requiring nonnegative edge weights must not be applied uncritically to negative-edge instances. Verify the answer on the defined graph model rather than conflating it with a different representation.

6.1. Königsberg Bridge Problem

Euler's analysis of the Königsberg bridge problem abstracted land regions as vertices and bridges as edges. The problem became a foundational example of graph theory because connectivity, not geometric distance, determined the answer.

6.2. Fundamental Terminology

A graph consists of vertices and edges. Edges can be undirected or directed, simple or multiple depending on the graph model. Vertex degree counts incident edges in an undirected graph, while directed graphs distinguish indegree and outdegree.

6.3. Walk, Trail, Path, and Circuit

A walk is a sequence of adjacent vertices/edges. A trail does not repeat edges; a path usually does not repeat vertices. A closed trail/circuit returns to its starting point. Terminology varies slightly among texts, so the structural restriction should be stated explicitly.

6.4. Connectivity and Subgraphs

A graph is connected when a path exists between every pair of vertices. A subgraph uses subsets of the original vertices and edges. Connected components are maximal connected subgraphs.

6.5. Trees

A tree is a connected undirected graph with no cycles. For a finite tree with n vertices,

number of edges = n - 1.

Between any two vertices of a tree there is a unique simple path.

6.6. Equivalent Characterizations of Trees

For a finite undirected graph, the concept of a tree can be recognized through several equivalent conditions. For a graph with n vertices, the following descriptions characterize the same structure from different directions:

• the graph is connected and acyclic,
• it is connected and has exactly n-1 edges,
• it is acyclic and has exactly n-1 edges,
• every pair of vertices is joined by exactly one simple path,
• removing any edge disconnects the graph,
• adding one new edge creates exactly one cycle.

These equivalences are useful beyond theory. They provide alternative invariants for validating whether a data representation really is a tree. In one representation checking edge count may be cheap; in another, connectivity and cycle detection may be more natural.

6.7. Directed Graphs

Directed edges have orientation. Reachability, paths, and strongly/weakly connected components reflect this direction information.

6.8. Structural Network Analysis: Cores, Cuts, and Directed Components

Vertex degree is a local connection count; by itself it does not say whether the vertex lies inside a densely connected interior of the network. k-core decomposition captures this distinction. The k-core is the maximal subgraph in which every remaining vertex has degree at least k within that same subgraph. The largest k for which a vertex remains is its core number.

The basic idea is iterative pruning:

1. remove vertices whose degree is below k
2. update neighbor degrees
3. remove newly under-degree vertices
4. continue until stable

With appropriate degree buckets the full decomposition can be computed in O(V + E). A high core number means that a vertex survives deeper inside a cohesive structural region; it is not, by itself, evidence of leadership, importance, or causal influence. A classical reference is Stephen B. Seidman, Network Structure and Minimum Degree (1983): https://doi.org/10.1016/0378-8733(83)90028-X

Bridges and articulation points also have an algorithmic interpretation. During depth-first search, let disc[v] be the discovery time and low[v] the earliest ancestor reachable from the DFS subtree rooted at v. For a tree edge (u,v),

low[v] > disc[u]

identifies a bridge. For a non-root vertex u, an appropriate child v satisfying

low[v] >= disc[u]

makes u an articulation point. Low-link DFS computes these structures in O(V + E). Robert Tarjan's 1972 paper is a foundational source for linear-time DFS graph algorithms, including strongly and biconnected structures: https://doi.org/10.1137/0201010

For directed graphs, weakly connected components (WCCs) and strongly connected components (SCCs) have different evidence requirements. WCC ignores edge orientation. SCC requires direction-respecting paths between vertices. If an observed relation has unknown direction, silently converting it into two directed edges manufactures structure that was not observed; direction coverage should therefore be treated as part of the interpretation.

Another directed-network measure is PageRank. In a simple form:

PR(v) = (1-d)/N + d * sum(PR(u) / outdeg(u))
                         u -> v

where d is the damping factor and dangling-node mass must be handled explicitly. PageRank depends not only on how many incoming links a vertex has but also on the structural weight of the linking vertices. A high score should still not be translated automatically into social or forensic "importance." The classical large-scale Web treatment is Brin and Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine (1998): https://doi.org/10.1016/S0169-7552(98)00110-X

A classical graph path uses only topology. When edges are events with timestamps, a time-respecting path additionally requires temporal order:

v0 --t1--> v1 --t2--> v2 ... --tk--> vk

t1 <= t2 <= ... <= tk

Applications may also impose a maximum gap between consecutive edges or a maximum total span. A static route can therefore exist while no temporally feasible route exists. This is a useful example of how representation determines which conclusions an algorithm is allowed to make.

6.9. Graph Isomorphism and Structural Invariants

Different vertex labels do not imply different graph structures. Two graphs are isomorphic when a bijection between their vertices preserves adjacency.

Isomorphism concerns structure rather than naming. Degree multiset, number of connected components, cycle lengths, and number of bridges are examples of invariants under isomorphism. If any invariant differs, the graphs cannot be isomorphic. Agreement of several simple invariants, however, is not by itself a proof of isomorphism.

This distinction mirrors a common systems concept: identifiers may change while the relationship pattern remains structurally identical.

6.10. Planar Graphs and Euler's Relation

A graph is planar if it can be drawn in the plane so that edges intersect only at common endpoints. Crossings in one particular drawing do not prove nonplanarity; a different embedding may remove them.

For a connected planar embedding, the numbers of vertices, edges, and faces satisfy

V − E + F = 2.

This identity yields useful necessary conditions. For a simple connected planar graph with V ≥ 3,

E ≤ 3V − 6.

If the planar graph contains no triangles, the stronger bound

E ≤ 2V − 4

holds.

Violation of these bounds proves nonplanarity. Satisfying them does not, by itself, guarantee that a graph is planar.

6.11. Weighted Graphs and Minimum Spanning Trees

A weighted graph associates costs or lengths with edges. A minimum spanning tree connects all vertices with no cycles and minimum total edge weight. Classical greedy methods include Kruskal and Prim algorithms.

6.12. Matrices and Graphs

An adjacency matrix records direct edges. Powers of an adjacency matrix encode information about walks of given length, while Boolean matrix operations support reachability computations.

6.13. From Graph Models to communication-relationship Analysis

When graph theory is applied to event data such as communication records, the first decision is not the algorithm but the representation model. It must be explicit whether a node represents a person, device, or another identifier, and whether an edge represents one observed event or an aggregate relation over a time interval. A multigraph that retains individual events does not carry the same information as a relationship graph that collapses every A-B event into one weighted edge.

The same distinction applies to direction, weight, and time. If direction such as caller/callee is observed, a directed graph can preserve it; if direction is unknown, silently replacing an edge with two directed edges manufactures information. Edge weight may mean event count, total duration, or another quantity, and different definitions change the interpretation of centrality. With timestamped events, the existence of a structural path does not guarantee that the events can occur in chronological order; a time-respecting path also carries a temporal constraint.

Centrality, components, bridges, articulation points, and communities are therefore structural descriptors rather than automatic evidence of legal, social, or causal importance. For an analysis to remain auditable, graph edges should be traceable back to source records, and missing direction/time coverage or records outside the selected scope should be treated as limitations on interpretation.

A public application context for these modeling choices is developed in HTS Analysis, including the distinction between event and aggregated relationship graphs, temporal relations, centrality, and traceability back to source records. The related HTS/CDR Analyzer for Java research software is persistently archived on Zenodo (doi:10.5281/zenodo.22685947). This bridge shows how abstract graph structures become concrete data-modeling decisions without assigning automatic meaning to any particular node or relationship.

6.14. Gantt Charts and Activity Networks

Project activities can be represented by time-oriented Gantt charts or dependency networks. Graph-based scheduling makes precedence relations and critical dependencies explicit; it is conceptually distinct from merely drawing a calendar bar.

6.15. Recurrence Relations and Graph Coloring

Many discrete problems have one of two forms: a next value depends on earlier values, or neighboring objects cannot share the same resource. Recurrence relations and graph coloring provide a common mathematical language for these structures.

6.15.1. Recurrence Relations

When a sequence term is defined from preceding terms, the result is a recurrence relation:

a_n = 2 a_(n-1) + 1

The recurrence does not identify a unique sequence without an initial condition. With a_0 = 0, it produces:

0, 1, 3, 7, 15, ...

First-order linear recurrences can often be solved algebraically. In divide-and-conquer algorithms, recurrences such as:

T(n) = 2T(n/2) + n

model total work as the problem size shrinks.

The objective is not always a closed form. Monotonicity, upper and lower bounds, and asymptotic growth may be sufficient for algorithmic reasoning.

6.15.2. Graph Coloring

In vertex coloring, adjacent vertices are assigned different colors. The minimum number of colors required is the graph's chromatic number.

A --- B
|     |
D --- C

This even cycle can be colored with two colors, whereas an odd cycle cannot.

A graph is bipartite exactly when it is two-colorable; BFS or DFS can test this by assigning alternating colors while traversing edges.

6.15.3. Engineering Interpretations

A "color" need not represent a visible color. It can represent a resource or time slot that conflicting items may not share. Examples include:

• exam or job scheduling,
• frequency assignment,
• register allocation,
• resource assignment for conflicting tasks.

The abstraction and the solution method must remain separate. Modeling a problem as a graph exposes its structure; finding an optimal coloring has its own computational cost.

Recurrences and coloring illustrate the same principle: discrete mathematics exposes structural constraints before they are encoded as program logic.

6.15.4. Solving Simple Recurrence Relations

Recurrences express a value through earlier values. They appear in recursive algorithms, counting problems, and dynamic systems.

For T(n)=T(n-1)+c, repeated substitution gives linear growth. For T(n)=2T(n/2)+n, the recursion tree exposes log n levels with approximately n work per level, giving Θ(n log n).

The important step is to state the recurrence from the algorithm before applying a theorem. A wrong recurrence produces a precise answer to the wrong model.

6.15.5. Graph Coloring as a resource-allocation Model

In graph coloring, adjacent vertices cannot share a color. The abstraction maps naturally to exam scheduling, register allocation, radio-frequency assignment, and other conflict problems.

The chromatic number is a graph property, but finding it exactly is computationally hard in general. Heuristics should therefore be reported as algorithms that produce valid colorings, not as proofs of optimality unless an optimality argument is also available.

6.16. Cliques, Independent Sets, Regularity, and Hypergraphs

Local density and local separation in a graph can be expressed with two complementary notions. A set of vertices is a clique when every distinct pair is adjacent; it is an independent set when no distinct pair is adjacent.

The complement graph gives an exact duality:

S is a clique in G
    <=>
S is an independent set in complement(G)

Maximal and maximum are different. A maximal clique cannot be enlarged by adding another vertex; a maximum clique has the largest cardinality among all cliques. The same distinction applies to independent sets. Local non-extendability is not a proof of global optimality.

A graph is k-regular when every vertex has degree k. The handshaking lemma gives an immediate necessary condition:

k * |V| = 2|E|

Thus k|V| must be even. This parity test can reject some claimed regular-graph instances before any construction is attempted.

A hypergraph relaxes the assumption that an edge relates exactly two vertices. A hyperedge may contain an arbitrary subset of the vertex set:

G = (V, E),       e in E -> |e| = 2
H = (V, E_hyper), e in E_hyper -> e is a subset of V

Events, transactions, or groups involving three or more entities can therefore be represented directly. Projecting a hypergraph to an ordinary graph by connecting every pair inside a hyperedge is possible, but it can lose the information that those vertices participated in the same higher-arity relation. Representation choice must therefore precede algorithm choice.

6.17. From Discrete Structures to Search, Planning, and Graph Learning

Discrete mathematics directly supports the symbolic and combinatorial side of AI. Sets, logic, relations, counting, and graphs are natural tools for search, planning, constraint satisfaction, and knowledge representation.

In propositional logic, conclusions follow from explicit premises and inference rules. This differs from statistical learning, where a decision function is estimated from data. Modern systems may combine both: learned perception can produce observations while logical constraints govern admissible actions.

Graph theory creates an even broader bridge. Nodes can represent states, entities, users, or atoms; edges can represent transitions, relations, communication, or chemical bonds. Search operates over a state graph, while graph learning treats the graph itself as data.

A simplified graph-neural-network update is:

h_v^(k+1) = UPDATE(h_v^k, AGGREGATE({h_u^k : u ∈ N(v)}))

The learning mechanism is modern, but neighborhood, path, degree, and connectivity remain graph-theoretic objects.

Combinatorics explains why exhaustive search becomes impossible. The number of permutations of n objects is n!; many scheduling, planning, and feature-subset problems grow too quickly for enumeration. Heuristic search, branch-and-bound, local search, or evolutionary methods become useful because of this combinatorial explosion.

Relations also matter semantically. Equality, similarity, reachability, and ordering do not share the same mathematical properties. A learned similarity score is not necessarily transitive and should not be treated as an equivalence relation without evidence.

Constraint-satisfaction problems provide another direct connection:

X_i ∈ D_i
C_1(X), C_2(X), ...

The objective is to find assignments satisfying the constraints. Scheduling and resource-allocation problems often fit this form. Learning may improve search order, while the meaning of the constraints remains discrete and explicit.

Discrete mathematics is not the sole mathematical foundation of AI. Continuous optimization requires calculus, representation requires linear algebra, and uncertainty requires probability. Its specific contribution is the structure of symbolic inference, graph representation, combinatorial search, and constrained decision problems.

6.18. From Static Graphs to Temporal Graphs

In temporal networks, when an edge occurs is part of the structure, not merely metadata. Collapsing a temporal graph into one static adjacency structure removes edge order, so it can imply paths that could never be traversed in time while also hiding short-lived contacts whose structural importance is diluted by long-term aggregate weight. Time-respecting paths, temporal reachability, edge persistence, burstiness, and time-dependent centrality therefore complement static degree and one-shot community partitions.

• Construct examples where a path exists topologically but is impossible in event order.
• Show how snapshot size changes community and centrality results.
• Represent directed, weighted, and temporal edge semantics explicitly in the data model.

6.19. Subset Selection and Marginal Information Gain

Selecting a limited number of sentences from a collection is a set-selection problem as well as a graph-centrality problem. Each sentence may cover topics, time intervals, or document regions. For a selected set S, the marginal gain of adding a candidate x is F(S ∪ {x}) - F(S). Representing a topic for the first time can yield high gain, while another sentence repeating it contributes less.

When a coverage function is monotone and submodular, greedy selection offers a strong approximation by adding the item with the largest marginal gain at each step. The familiar guarantee under a cardinality constraint relies on specific assumptions; adding negation constraints, mandatory chronological ordering, or strict per-document quotas does not automatically preserve the same guarantee. The objective and its constraints therefore need explicit specification.

In text selection, two superficially similar sentences may express opposing claims. “He will come” and “he will not come” can have high lexical overlap, yet merging them as one fact creates a semantic error. Set-based modeling helps distinguish the underlying information units from the surface sets of shared words.

Testing a shortest-path precondition with a counterexample. Let a directed graph contain edges A → B with weight 2, A → C with weight 5, and C → B with weight −4. The direct path from A to B costs 2, whereas A → C → B costs 5 − 4 = 1. Dijkstra's finalization step relies on nonnegative edge weights; it may finalize B at distance 2 before discovering the cheaper route. Edge-weight signs must therefore be checked before selecting the algorithm. When negative edges exist but no reachable negative cycle invalidates the result, a relaxation-based algorithm such as Bellman–Ford can be used. A reachable negative cycle may mean that no finite shortest path exists for affected destinations. This correctness check precedes any comparison of time complexity.

6.20. Graph Relations, Reachability, and Temporal Paths

A path between two graph vertices does not imply a direct edge between them. In a directed graph \(G=(V,E)\), \((u,v)\in E\) denotes a direct relation, while reachability from \(u\) to \(v\) means that one or more edges can be traversed in sequence. Transitivity, undirected connectivity, and strong connectivity are different concepts. In relationship analysis, belonging to the same connected component and communicating directly represent different evidentiary claims.

If edges carry timestamps, not every path in the static graph is temporally feasible. Suppose \(A\to B\) occurs at 15:00 and \(B\to C\) at 14:00. The two edges form a static path, but they do not establish a time-respecting transfer sequence beginning at 15:00. A temporal path must specify a nondecreasing-time constraint and, where necessary, allowed transmission delay.

A graph algorithm's output should preserve node and edge identities, hop count, direction assumptions, and the filtered temporal interval. BFS finds a path with a minimum number of edges under its usual unweighted assumptions; weighted or time-constrained paths require a different optimization model. Mathematical reachability alone does not prove causality or real-world coordination.

Unit 7: Algorithms

7.1. Algorithm Concept

An algorithm is a finite, unambiguous sequence of effective steps that transforms input into output. Correctness and termination are separate from efficiency.

7.2. Pseudocode

Pseudocode expresses control flow independently of a particular programming language. It should be precise enough that the intended algorithm is unambiguous.

7.3. Decision Structure

Conditional execution selects different steps according to a Boolean condition:

if condition
    action A
else
    action B

7.4. Loop Structures

Loops repeat computation while a condition holds or over a finite collection. for, while, and repeat-until styles differ in how repetition is controlled.

7.5. Subprogram and Function

A subprogram encapsulates a reusable computation. Functions additionally emphasize returning a value, although programming-language terminology varies.

7.6. Finding the Maximum Value

A linear scan can find the maximum of n elements by keeping the largest value seen so far. The algorithm requires n-1 comparisons in the ordinary sequential model.

7.7. Computer Representation of Sets

Finite sets over a known universe can be represented by bit vectors. Membership becomes a bit test; union and intersection correspond naturally to bitwise OR and AND.

7.8. Computer Representation of Relations and Graphs

Adjacency matrices provide constant-time edge lookup but use quadratic space. Adjacency lists use space proportional to vertices plus edges and are often better for sparse graphs.

7.9. Transitive-closure Algorithm

Warshall's dynamic-programming recurrence computes reachability for all vertex pairs in O(n^3) time for an n x n relation matrix.

7.10. Asymptotic Growth and Complexity Classes

Algorithmic cost should not be identified solely with elapsed seconds on one machine. The central question is how the operation count grows as the input size n increases.

Big O gives an asymptotic upper bound, Big Ω a lower bound, and Big Θ a matching growth class:

f(n) = O(g(n))      f is eventually bounded above by a constant multiple of g
f(n) = Ω(g(n))      f is eventually bounded below by a constant multiple of g
f(n) = Θ(g(n))      both bounds hold.

Constant factors and lower-order terms do not change the asymptotic class:

7n² + 4n + 20 = Θ(n²).

These symbols must not be read as ordinary equality. O(n²) describes a growth bound, not an exact running-time formula.

Best-case, average-case, and worst-case complexity must also be distinguished. They may differ for the same algorithm. Time complexity and space complexity measure different resources.

7.11. Divisibility, Modular Arithmetic, and the Euclidean Algorithm

If a divides b exactly, we write a | b. Integer division can be expressed as

a = bq + r,   0 ≤ r < |b|.

The remainder is the basis of modular arithmetic.

a ≡ b (mod m)

means m | (a − b). Congruence classes are compatible with addition and multiplication:

a ≡ b (mod m), c ≡ d (mod m)
⇒ a+c ≡ b+d (mod m)
⇒ ac ≡ bd (mod m).

The greatest common divisor is computed efficiently by the Euclidean algorithm:

gcd(a,b) = gcd(b, a mod b),

repeated until the remainder becomes zero. The extended form also recovers coefficients satisfying ax + by = gcd(a,b).

Modular arithmetic appears in cyclic indexing, checksums, hash structures, and the number-theoretic foundations of public-key cryptography. The purpose here is not protocol design but the integer algebra on which such systems rely.

7.12. From Modular Arithmetic to Finite Fields: the AES Example

Modular arithmetic and the finite-field arithmetic used in cryptography are not identical concepts. Over Z_m, addition and multiplication are performed modulo m; if m is not prime, not every nonzero element has a multiplicative inverse and the structure is not a field. AES instead interprets a byte not merely as an integer in 0..255 but as a polynomial of degree at most seven with coefficients in GF(2), with arithmetic reduced by an irreducible polynomial of degree eight. FIPS 197 uses

m(x) = x^8 + x^4 + x^3 + x + 1

associated with the binary value 0x11B. AES multiplication is therefore not ordinary integer multiplication modulo 256; it is polynomial multiplication and reduction in GF(2^8).

This algebra appears directly in two core AES transformations. SubBytes uses the multiplicative inverse of a nonzero byte in GF(2^8) followed by an affine transformation. MixColumns multiplies each state column by a fixed matrix over the same field. Equivalence classes, polynomial arithmetic, and multiplicative inverses from discrete mathematics thus extend directly into the transformation layers of a real block cipher (NIST FIPS 197).

Algebraic Representation in AES Cryptanalysis develops the algebraic structure from the cryptanalytic/equation-modeling side, while A Lightweight AES-128 Implementation in C treats implementation. The related open-source Lightweight AES-128 software is persistently archived on Zenodo (doi:10.5281/zenodo.22117428). The personal link is not the source of the general AES mathematics; it shows the path from theory to a verifiable software artifact.

7.13. Solving Recurrence Relations

When a sequence is defined from earlier terms, it satisfies a recurrence relation. For a second-order linear homogeneous recurrence

a_n = c1 a_(n−1) + c2 a_(n−2),

trying a solution of the form a_n = r^n gives the characteristic equation

r² − c1 r − c2 = 0.

With distinct roots r1 and r2, the general solution has the form

a_n = A r1^n + B r2^n,

with constants determined by the initial conditions. For a repeated root, an additional independent term proportional to n r^n appears.

Divide-and-conquer algorithms often lead to recurrences such as

T(n) = a T(n/b) + g(n),

where a is the number of subproblems, n/b their size, and g(n) the divide-and-combine cost. The recurrence exposes the algorithmic structure rather than merely defining a numerical sequence.

7.14. Generating Functions

A sequence can be encoded as coefficients of a formal power series:

G(x) = a0 + a1 x + a2 x² + ...

The series G(x) is the sequence's generating function. In discrete mathematics, it is primarily an algebraic encoding device; analytic convergence is not always the main issue.

A recurrence can be multiplied by powers of x and summed to obtain an algebraic equation for G(x). Solving that equation and extracting coefficients may yield a closed form for the original sequence.

Generating functions are also powerful in counting. Products of generating functions combine independent choices, and the coefficient of a selected power can count configurations satisfying a total constraint. A counting problem is thereby converted into a coefficient-extraction problem.

Generating functions share notation with analytic power series in Calculus II, but their primary role here is combinatorial representation rather than convergence analysis.

7.15. Bézout's Identity, Modular Inverses, and the Euler-Fermat Connection

The extended Euclidean algorithm produces coefficients x and y satisfying

ax + by = gcd(a,b).

If gcd(a,m)=1, then

ax + my = 1,

which implies

a x ≡ 1 (mod m).

Thus x is a modular inverse of a modulo m.

Euler's theorem states that when gcd(a,n)=1,

a^phi(n) ≡ 1 (mod n).

Fermat's little theorem is the familiar prime-modulus specialization. These results form part of the discrete mathematical basis of public-key cryptography; protocol engineering itself belongs to cryptography rather than to this course.

7.16. The Mathematical Bridge from Recurrences to Dynamic Programming

When a problem is defined through smaller subproblems, the first object obtained is a mathematical recurrence relation. Dynamic programming changes the evaluation strategy of that relation: repeated states are stored, or the relation is evaluated bottom-up from its base conditions.

A sound DP model makes four items explicit:

• what a state represents,
• which previous states define its transition,
• the base or boundary conditions,
• how the desired solution is read from the states and, when needed, reconstructed.

Dynamic programming is therefore not merely a coding pattern. It is a computational ordering of a recursive mathematical definition. Detailed memory layout and reconstruction strategies belong naturally to algorithm analysis.

7.17. Invariants and Induction as Tools for Program Correctness

Mathematical induction extends naturally to loop invariants. Correctness can be argued through initialization, preservation, and termination.

In binary search, for example, the invariant that a present target remains inside the current search interval exposes off-by-one errors more clearly than random testing alone.

Graph algorithms also rely on invariants: finalized distances in Dijkstra, representative structure in union-find, and indegree conditions in topological sorting are mathematical explanations of why the algorithms work.

7.18. Verification with Counterexamples and Invariants

In discrete mathematics, plausibility is not proof. One counterexample is enough to refute a universal claim, while proving the claim requires a valid argument. The same distinction applies to algorithm correctness.

Small constructed graph cases help expose assumptions: disconnected graphs, cycles, parallel edges, negative weights, and single-node inputs. An algorithm such as Dijkstra can appear to work on some invalid inputs even when its preconditions are violated.

Loop invariants and induction connect program behavior to formal reasoning. Initialization, preservation, and termination provide evidence beyond example outputs.

7.19. From Discrete Mathematics to Formal Languages and Automata

Discrete mathematics is not limited to sets, relations, and graphs. It also provides the mathematical foundation for formal-language theory, which asks which symbol sequences a computational model can recognize and which problems can be solved by which abstract machine. In computer-engineering curricula in Türkiye, this material may follow discrete mathematics directly or appear as a separate course titled Formal Languages and Automata or Automata Theory.

An alphabet is a finite set of symbols. Finite sequences formed from an alphabet are strings, and a set of strings is a language. For example, all binary strings over {0,1} that end in 01 form a language. A formal language does not have to be a programming language; protocol message formats, structured log patterns, and lexical tokens can also be modeled as languages.

7.20. Regular Languages and Finite Automata

Regular expressions, regular languages, and finite automata are alternative representations of the same class of expressive power. A deterministic finite automaton (DFA) has exactly one next state for each state and input symbol. A nondeterministic finite automaton (NFA) may permit several possible transitions, but it does not recognize a broader class of languages than a DFA; an equivalent DFA can be constructed by representing sets of NFA states.

input symbols
      ↓
 [initial state]
      ↓
  transitions
      ↓
[accept / reject]

The memory of a finite automaton is limited to its current state. It therefore cannot, in general, recognize structures that require an unbounded stack, such as arbitrarily nested balanced delimiters. This limitation introduces a question that is more fundamental than “which algorithm is faster?”: is the computational model expressive enough for the problem?

7.21. Context-free Grammars and Pushdown Automata

Programming-language syntax contains blocks, expressions, and nested structures for which regular languages are often insufficient. A context-free grammar (CFG) uses terminals, nonterminals, productions, and a start symbol to describe richer structures. The natural machine model for this class is the pushdown automaton.

characters
   ↓
lexical analysis            regular language / finite automaton
   ↓
tokens
   ↓
parsing                     CFG / pushdown automaton
   ↓
syntax tree

This distinction connects directly to the compiler pipeline discussed in Programming Languages: lexical analysis and parsing are different computational problems. A string being generated by a grammar also does not imply that a program is semantically valid; type checking, name binding, and runtime behavior belong to later layers.

7.22. Turing Machines, Computability, and Decidability

A Turing machine combines finite control with an abstract, unbounded read/write tape. Its purpose is not to imitate a real processor but to define a machine-independent boundary for what it means to be algorithmically computable.

A decision problem requires a yes/no result for every input. If a correct algorithm terminates for every possible input, the problem is decidable. Some problems cannot be solved by any general algorithm for all inputs. The halting problem is important because it demonstrates that no universal, perfect analyzer can determine every relevant property of arbitrary program behavior in advance.

Computability and complexity must remain separate:

computability: Is there an algorithm that solves the problem?
complexity:    If so, how much time or memory does it require?

Automata theory is therefore not merely a historical prerequisite for compiler construction. It supplies a common mathematical vocabulary of state, language, and acceptance used in areas ranging from regular-expression engines and protocol validation to parsing and model checking.

7.23. Modular Algorithms and Complexity Bounds

The extended Euclidean algorithm computes the GCD together with Bézout coefficients; its loop invariants establish when a modular inverse exists. Binary exponentiation processes exponent bits to evaluate a^e mod n using approximately O(log e) modular multiplications rather than a loop linear in e. The bit complexity of large-integer multiplication remains relevant. The Chinese remainder theorem reconstructs solutions from pairwise coprime moduli.

The contribution here is correctness invariants and complexity analysis, not an RSA production implementation. Key generation and side-channel considerations belong to Cryptology.

References

• Ahmet Yesevi Üniversitesi Bilgisayar Mühendisliği Bölümü. Ayrık Matematik (TBIL108) ders materyalleri.

• Albert-László Barabási. Network Science.

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th Edition. McGraw-Hill, 2019.

• Muhammet Ali Köker. HTS/CDR Analyzer for Java v1.0.1 (research software). Zenodo, 2026. doi:10.5281/zenodo.22685947

• Muhammet Ali Köker. lightweight-aes-128-c (research software). Zenodo, 2026. doi:10.5281/zenodo.22117428

• National Institute of Standards and Technology. Advanced Encryption Standard (AES), FIPS PUB 197. doi:10.6028/NIST.FIPS.197

• Petter Holme; Jari Saramäki (eds.). Temporal Network Theory. 2nd ed. Springer Nature Switzerland, 2023.

• Ralph P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction, 5th Edition. Pearson, 2003.

• Reinhard Diestel. Graph Theory, 5th Edition. Springer, 2017.

• Stuart Russell, P. N. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2021.

• Susanna S. Epp. Discrete Mathematics with Applications, 5th Edition. Cengage, 2019.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022.
• Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, 3rd ed., 2025. https://www.routledge.com/Introduction-to-Modern-Cryptography/Katz-Lindell/p/book/9781040366493