When we talk about algorithms and computer science, we are standing on a foundation of discrete mathematics. Unlike continuous mathematics (like calculus), discrete mathematics studies objects that are countable, separate, and well-defined. Below, we will walk through its core areas, giving you a high-level but structured overview.

Propositional Logic

Propositional logic deals with statements that are either true or false. We use logical operators such as AND (∧), OR (∨), NOT (¬), IF…THEN (→), IF AND ONLY IF (↔).

Example: If it rains, then the ground is wet.

Fuzzy Logic

While propositional logic is binary, fuzzy logic allows values between 0 and 1. It models uncertainty and partial truth, widely used in artificial intelligence and control systems.

Syllogism

A syllogism is a form of reasoning where a conclusion is drawn from two premises.

Example:
- All humans are mortal.
- Socrates is a human.
- Therefore, Socrates is mortal.

Predicate Logic

In propositional logic, we only handle whole statements:

Example: The sky is blue (this is either true or false).

But propositional logic cannot express details like who or what the statement is about. That’s where predicate logic comes in. A predicate is a statement that becomes true or false once we provide a subject. Predicates let us talk about properties of objects.

Example: Let P(x) mean “x is a prime number”. - If x = 2, then P(2) = true. - If x = 4, then P(4) = false.

But it goes beyond propositions by allowing quantifiers to express generality.

Universal quantifier (∀) → “for all”

Example: ∀x P(x) means “For all x, x is prime”.

This statement is false, since not every number is prime.

Example: ∀x (Human(x) → Mortal(x))

For every x, if x is human, then x is mortal (classic syllogism: all humans are mortal).

Existential quantifier (∃) → “there exists”

Example: ∃x P(x) means “There exists some x such that x is prime”.

This is true, since 2 is prime.

∃x (Student(x) ∧ Smart(x))

There exists at least one student who is smart.

Set Theory

The language of mathematics.

• Union (A ∪ B), Intersection (A ∩ B), Complement (Aᶜ), Difference (A – B).
• Fundamental to probability, databases, and algorithms.

Theory of Computation

The theory of computation asks a fundamental question: what can a machine actually compute? It is the branch of computer science that studies the limits and capabilities of algorithms, and it gives us the vocabulary to reason about efficiency, solvability, and complexity. At the core of computation we find automata theory—abstract machines that process input according to a set of rules. Examples include:

• Finite Automata (FA): machines with limited memory, used to model regular languages.
• Pushdown Automata (PDA): machines with a stack, powerful enough to model context-free languages (like many programming language grammars).
• Turing Machines (TM): the most general model of computation, capable of simulating any algorithm.

Formal languages classify sets of strings that machines can recognize, forming the Chomsky hierarchy (regular, context-free, context-sensitive, recursively enumerable). But not all solvable problems are equally easy to solve. Complexity theory divides problems into classes:

• P: solvable in polynomial time (efficient).
• NP: solutions can be verified quickly, but it is not clear if they can always be found quickly.
• Undecidable problems: problems that no algorithm can ever solve in general.

This helps us understand why some problems are practical and others are intractable.

Alan Turing & Halting Problem

Alan Turing (1912–1954) is considered the father of theoretical computer science. He introduced the Turing Machine, a mathematical abstraction consisting of:

• An infinite tape (memory).
• A read/write head (processor).
• A set of rules (the program).

Though simple, Turing Machines can represent any algorithm. This is known as the Church–Turing Thesis: anything computable can be computed by a Turing Machine. One of Turing’s most famous results is the halting problem. It asks:

Is there an algorithm that can decide, for any given program and input, whether the program will eventually stop running or run forever?

Turing proved the answer is no. There is no universal procedure that can always predict whether a program halts. This discovery set the boundaries of computation: some problems are not just hard—they are fundamentally unsolvable.

Number Theory

Number theory is the branch of mathematics that studies the properties of integers. It may sound simple at first… after all, we are “just” dealing with whole numbers, but it is one of the deepest and most influential fields in mathematics, with applications ranging from cryptography to computer algorithms.

• Divisibility: we say that an integer n is divisible by another integer d if there exists an integer k such that n = d x k. Examples:

12 is divisible by 3 (since 12 = 3 × 4) 15 is not divisible by 4 (since 15 ÷ 4 leaves a remainder)

• Congruence: it is a way of comparing numbers by their remainders. We write: a \equiv b \pmod{m} to mean that a and b leave the same remainder when divided by m. Examples:

17 ≡ 5 (mod 12), because both leave remainder 5 when divided by 12. 21 ≡ 1 (mod 10), because both leave remainder 1 when divided by 10.

• Factorization: it is the process of writing a number as a product of prime numbers. Examples:

60 = 2 × 2 × 3 × 5 91 = 7 × 13

Every integer greater than 1 has a unique factorization into primes (this is the Fundamental Theorem of Arithmetic). Prime factorization is easy for small numbers but becomes very difficult for large integers. This difficulty is what makes modern cryptographic systems like RSA encryption possible.

Proof Techniques

Mathematics stands on proofs:

• Direct Proof
• Contradiction
• Contrapositive

Mathematical Induction

Used to prove statements valid for all natural numbers.

• Base case: prove for n = 1.
• Inductive step: assume true for n, then prove for n+1.

I have discussed more about it here.

Combinatorics

Counting methods:

• Rule of sum, rule of product.
• Permutations and combinations.

Pigeonhole Principle

If n+1 pigeons are placed in n holes, at least one hole contains two pigeons. A surprisingly powerful principle.

Recurrence and Recursion

• Recurrence relations: equations defining sequences based on previous terms.
• Recursion: defining functions in terms of themselves.

Graph Theory

Graphs are sets of vertices (nodes) connected by edges. Applications: networks, shortest path algorithms, social graphs.

Four Color Theorem

Every planar map can be colored with at most 4 colors such that no two adjacent regions share the same color. A classic in graph theory.

Exercise: The Detective Puzzle

A detective interviewed 4 suspects: the Butler, the Cook, the Gardener, and the Janitor. From the testimonies:

1. If the butler is telling the truth, the cook is also telling the truth.
2. The cook and the gardener cannot both be telling the truth.
3. The gardener and the janitor are both telling the truth.
4. If the janitor is telling the truth, then the cook is lying.

Step 1. Translate into logic:

• B → C
• ¬(C ∧ G)
• G ∧ J
• J → ¬C

Step 2. Analyze statement (3):
G = true, J = true.

Step 3. Use statement (4):
If J = true, then C = false.
So C = false.

Step 4. Use statement (1):
If B = true, then C = true. But C is false.
Therefore, B = false.

Final Solution:

• Butler = false
• Cook = false
• Gardener = true
• Janitor = true

This overview shows how discrete mathematics provides the language and tools we use daily in algorithms and computer science. From logic and proofs to graphs and recursion, every modern system relies on these foundations. The detective puzzle illustrates how logic connects abstract theory to practical reasoning.

• Previous
  Base Mathematics in Data Structures and Algorithms