Discrete Mathematics — The Foundation of Computing

ℹ️ Why It Matters

Computer science is built on discrete math. Algorithms, data structures, complexity theory, cryptography, and logic all rely on discrete mathematics.

Logic

Propositional Logic

Basic connectives:

Symbol	Name	Read as	Truth Table
¬P	NOT	"not P"	T→F, F→T
P ∧ Q	AND	"P and Q"	Both T → T, else F
P ∨ Q	OR	"P or Q"	Both F → F, else T
P → Q	IMPLIES	"if P then Q"	P=T, Q=F → F, else T
P ↔ Q	IFF	"P if and only if Q"	Same → T, Different → F

Important equivalences:

ℹ️ Logical Equivalences

De Morgan's Laws:

$\neg(P \wedge Q) = \neg P \vee \neg Q$
$\neg(P \vee Q) = \neg P \wedge \neg Q$

Contrapositive:

(P \rightarrow Q) \equiv (\neg Q \rightarrow \neg P)

Double negation:

\neg\neg P \equiv P

Predicate Logic (First-Order Logic)

ℹ️ Predicate Logic Components

Variables: $x, y, z$
Constants: $0, 1, \text{"Alice"}$
Predicates: $P(x), Q(x,y)$
Quantifiers:
- $\forall x \, P(x)$ — "for all x, P(x) is true"
- $\exists x \, P(x)$ — "there exists x such that P(x) is true"

📝Examples of Quantifiers

$\forall x \, (x + 0 = x)$ — "Adding zero to any number gives itself"
$\exists x \, (x^2 = 4)$ — "There exists a number whose square is 4"
$\forall x \exists y \, (x + y = 0)$ — "For every x, there exists y such that x + y = 0"

Set Theory

Basic Operations

📝Set Operations

Let $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$

Union: $A \cup B = \{1, 2, 3, 4, 5, 6\}$
Intersection: $A \cap B = \{3, 4\}$
Difference: $A - B = \{1, 2\}$
Complement: $A^c = \{\text{all elements not in A}\}$
Symmetric: $A \triangle B = \{1, 2, 5, 6\}$

Set Relationships

ℹ️ Set Relationships

Subset: $A \subseteq B$ (every element of A is in B)
Proper subset: $A \subset B$ ( $A \subseteq B$ and $A \neq B$ )
Empty set: $\emptyset = \{\}$
Power set: $\mathcal{P}(A)$ = set of all subsets of A

Set Laws

ℹ️ Set Laws

Commutative: $A \cup B = B \cup A$
Associative: $(A \cup B) \cup C = A \cup (B \cup C)$
Distributive: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
Identity: $A \cup \emptyset = A$ , $A \cap U = A$
De Morgan: $(A \cup B)^c = A^c \cap B^c$

Counting and Combinatorics

Permutations (Order matters)

Permutations

P(n,r) = \frac{n!}{(n-r)!}

Here,

$n$ =Total items
$r$ =Items to arrange

📝Example: Permutations

How many ways to arrange 3 books from 5?

P(5,3) = \frac{5!}{2!} = 60

Combinations (Order doesn't matter)

Combinations

C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Here,

$n$ =Total items
$r$ =Items to choose

📝Example: Combinations

How many ways to choose 3 books from 5?

C(5,3) = \frac{5!}{3! \times 2!} = 10

Important Counting Principles

Addition Principle: If task A can be done in m ways and task B in n ways, and they can't both be done, total = m + n

Multiplication Principle: If task A can be done in m ways and task B in n ways, total = m × n

Inclusion-Exclusion:

Inclusion-Exclusion

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

Here,

$|A|$ =Cardinality of set A

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|

Binomial Theorem

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}

Here,

$n$ =Exponent

📝Example: Binomial Theorem

(x + 1)^3 = x^3 + 3x^2 + 3x + 1

Graph Theory

Basic Concepts

DfGraph

A graph $G = (V, E)$ consists of:

$V$ = set of vertices (nodes)
$E$ = set of edges (connections)

Types of Graphs

Type	Description
Undirected	Edges have no direction
Directed (Digraph)	Edges have direction (arrows)
Weighted	Edges have values
Bipartite	Vertices can be divided into two groups
Complete	Every pair of vertices is connected
Tree	Connected graph with no cycles

Degree

\text{deg}(v) = \text{number of edges connected to vertex } v

Here,

$v$ =A vertex

Handshaking Lemma: $\sum \text{deg}(v) = 2|E|$ (Sum of all degrees = twice the number of edges)

Paths and Cycles

ℹ️ Path and Cycle Definitions

Path: A sequence of edges connecting two vertices
Cycle: A path that starts and ends at the same vertex
Eulerian circuit: A cycle that visits every edge exactly once
Hamiltonian path: A path that visits every vertex exactly once

Graph Algorithms

BFS (Breadth-First Search):

ℹ️ BFS

Explores level by level
Uses a queue
Finds shortest path in unweighted graphs
Time: $O(V + E)$

DFS (Depth-First Search):

ℹ️ DFS

Explores as far as possible before backtracking
Uses a stack (or recursion)
Time: $O(V + E)$

Dijkstra's Algorithm:

ℹ️ Dijkstra's Algorithm

Finds shortest path in weighted graphs
Uses a priority queue
Time: $O((V + E) \log V)$

Trees

Properties:

Connected and acyclic
$n$ vertices → $n-1$ edges
Unique path between any two vertices

Types:

Binary tree: Each node has at most 2 children
Binary search tree: Left < Root < Right
Balanced tree: $O(\log n)$ height (AVL, Red-Black)
Heap: Parent ≥ (or ≤) children

Number Theory

Modular Arithmetic

DfModular Arithmetic

$a \equiv b \pmod{n}$ means $n$ divides $(a - b)$

📝Example: Modular Arithmetic

17 \equiv 2 \pmod{5} \text{ because } 17 - 2 = 15 = 3 \times 5

Properties:

$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$
$(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$

Applications:

Hash functions
Cryptography (RSA)
Rolling hash (Rabin-Karp algorithm)

Prime Numbers

DfPrime Number

A number > 1 that has no divisors other than 1 and itself.

ThFundamental Theorem of Arithmetic

Every integer > 1 can be uniquely factored into primes.

Sieve of Eratosthenes: Find all primes up to n

ℹ️ Sieve Algorithm

List numbers 2 to n
Mark 2 as prime, cross out all multiples of 2
Find next unmarked number, mark as prime, cross out its multiples
Repeat until done

GCD and LCM

\text{GCD}(a,b) \times \text{LCM}(a,b) = a \times b

Here,

$\text{GCD}(a,b)$ =Greatest Common Divisor
$\text{LCM}(a,b)$ =Least Common Multiple

Euclidean Algorithm for GCD:

\text{GCD}(a,b) = \text{GCD}(b, a \bmod b)

Boolean Algebra

Boolean Operations

ℹ️ Boolean Operations

AND: $0 \wedge 0 = 0$ , $0 \wedge 1 = 0$ , $1 \wedge 0 = 0$ , $1 \wedge 1 = 1$
OR: $0 \vee 0 = 0$ , $0 \vee 1 = 1$ , $1 \vee 0 = 1$ , $1 \vee 1 = 1$
NOT: $\neg 0 = 1$ , $\neg 1 = 0$
XOR: $0 \oplus 0 = 0$ , $0 \oplus 1 = 1$ , $1 \oplus 0 = 1$ , $1 \oplus 1 = 0$

Boolean Laws

ℹ️ Boolean Laws

Commutative: $A \wedge B = B \wedge A$
Associative: $(A \wedge B) \wedge C = A \wedge (B \wedge C)$
Distributive: $A \wedge (B \vee C) = (A \wedge B) \vee (A \wedge C)$
De Morgan: $\neg(A \wedge B) = \neg A \vee \neg B$
Absorption: $A \vee (A \wedge B) = A$
Idempotent: $A \wedge A = A$

Logic Gates

ℹ️ Logic Gates

AND gate: Output = $A \wedge B$
OR gate: Output = $A \vee B$
NOT gate: Output = $\neg A$
XOR gate: Output = $A \oplus B$
NAND gate: Output = $\neg(A \wedge B)$ — universal gate!
NOR gate: Output = $\neg(A \vee B)$ — universal gate!

Applications: Digital circuits, database queries, search engines

📋Key Takeaways

Logic is the language of computation. Propositional connectives ( $\wedge$ , $\vee$ , $\neg$ , $\rightarrow$ ) and De Morgan's Laws $\neg(P \wedge Q) = \neg P \vee \neg Q$ form the basis of Boolean circuits and query optimization.
Combinatorics counts possibilities efficiently. Permutations $P(n,r) = \frac{n!}{(n-r)!}$ count ordered arrangements; combinations $C(n,r) = \frac{n!}{r!(n-r)!}$ count unordered selections — essential for algorithm analysis and complexity theory.
Graphs model relationships. A graph $G = (V, E)$ captures nodes and edges; BFS finds shortest paths in $O(V+E)$ , Dijkstra's handles weighted graphs in $O((V+E)\log V)$ , and trees guarantee unique paths between any two vertices.
Modular arithmetic underpins cryptography. $a \equiv b \pmod{n}$ means $n \mid (a-b)$ — hash functions, RSA encryption, and rolling hashes all rely on modular operations.
The Fundamental Theorem of Arithmetic guarantees unique prime factorization. Every integer $> 1$ factors uniquely into primes — critical for number theory applications and understanding algorithmic complexity.
Set theory provides the foundation for data structures. Union $A \cup B$ , intersection $A \cap B$ , and the Inclusion-Exclusion Principle $|A \cup B| = |A| + |B| - |A \cap B|$ are used everywhere from database queries to probability calculations.