Boolean Algebra

Boolean algebra is the algebraic structure that handles binary variables and logic operations. It is the mathematical foundation of digital circuit design.

Basic Operations

The primary operations are:

• AND ($\cdot$ or $\land$): $1 \cdot 1 = 1$, else $0$.
• OR ($+$ or $\lor$): $0 + 0 = 0$, else $1$.
• NOT ($\bar{x}$ or $\neg x$): $\bar{1} = 0, \bar{0} = 1$.

def boolean_table(func):
  print("A | B | Result")
  print("---------")
  for a in [0, 1]:
      for b in [0, 1]:
          print(f"{a} | {b} | {func(a, b)}")

# XOR Implementation
xor_func = lambda a, b: (a or b) and not (a and b)
boolean_table(xor_func)

Algebraic Laws

1. Idempotence: $x + x = x, x \cdot x = x$.
2. De Morgan’s Laws: $\overline{x + y} = \bar{x} \cdot \bar{y}$ and $\overline{x \cdot y} = \bar{x} + \bar{y}$.
3. Absorption: $x + (x \cdot y) = x$.

def de_morgan_test(x, y):
  lhs = not (x or y)
  rhs = (not x) and (not y)
  return lhs == rhs

print(f"De Morgan (0, 0): {de_morgan_test(0, 0)}")
print(f"De Morgan (1, 0): {de_morgan_test(1, 0)}")
print(f"De Morgan (1, 1): {de_morgan_test(1, 1)}")

Sum of Products (SOP) and Simplification

Every boolean function can be represented as a Sum of Products (canonical form). Simplification is typically done using Karnaugh Maps or the Quine-McCluskey algorithm.

Combinatorics and Enumerative Analysis

Combinatorics is the study of discrete structures. It determines the existence, count, and optimization of arrangements according to specific rules.

Fundamental Principles

• Addition Principle: If events are mutually exclusive, sum the ways.
• Multiplication Principle: If events occur in sequence, multiply the ways.

Permutations and Combinations

Permutations ($P(n, k)$): Choosing and ordering $k$ elements from $n$. $P(n, k) = \frac{n!}{(n-k)!}$

Combinations ($\binom{n}{k}$): Choosing $k$ elements without regard to order. $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

import math

def nCr(n, r):
  return math.comb(n, r)

def nPr(n, r):
  return math.perm(n, r)

print(f"Combinations (10 choose 3): {nCr(10, 3)}")
print(f"Permutations (10 permute 3): {nPr(10, 3)}")

Pascal’s Triangle and Binomial Expansion

The identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ allows for recursive construction.

def pascal_triangle(rows):
  triangle = [[1]]
  for i in range(1, rows):
      row = [1]
      for j in range(1, i):
          row.append(triangle[i-1][j-1] + triangle[i-1][j])
      row.append(1)
      triangle.append(row)
  return triangle

for row in pascal_triangle(6):
  print(str(row).center(30))

Advanced Principles

• Pigeonhole Principle: If $n > m$ items are put in $m$ boxes, one box has $>1$ item.
• Inclusion-Exclusion: Corrects for overcounting in unions ($|A \cup B| = |A| + |B| - |A \cap B|$).

Stars and Bars: Multisets

Choosing $k$ items from $n$ types with repetition: $\binom{n+k-1}{k}$.

from itertools import combinations_with_replacement

# Choosing 2 items from {A, B, C} with repetition
types = ['A', 'B', 'C']
k = 2
combos = list(combinations_with_replacement(types, k))
print(f"Multisets of size {k} from {types}:")
print(combos)
print(f"Formula count: {nCr(len(types) + k - 1, k)}")

Discrete Structures and Counting

Combinatorics is the branch of mathematics dealing with combinations of objects belonging to finite sets. It is foundational for probability and computer science.

Permutations and Combinations

• A permutation is an arrangement of objects in a specific order. The number of permutations of $n$ objects taken $r$ at a time is: $P(n, r) = \frac{n!}{(n-r)!}$
• A combination is a selection of objects where order does not matter: $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

import math

def permutations(n, r):
  return math.factorial(n) // math.factorial(n - r)

def combinations(n, r):
  return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

print(f"Permutations of 5 pick 3: {permutations(5, 3)}") # 60
print(f"Combinations of 5 pick 3: {combinations(5, 3)}") # 10

The Pigeonhole Principle

The pigeonhole principle states that if $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item. While simple, it is a powerful tool for proving existence.

Generating Functions

A generating function is a way of encoding an infinite sequence of numbers $(a_n)$ by treating them as the coefficients of a formal power series: $G(x) = \sum_{n=0}^{\infty} a_n x^n$

def get_fibonacci_coefficient(n):
  """Sequence: 0, 1, 1, 2, 3, 5, ...
  Generating function: x / (1 - x - x^2)"""
  a, b = 0, 1
  for _ in range(n):
      a, b = b, a + b
  return a

print(f"10th Fibonacci number: {get_fibonacci_coefficient(10)}")

Principle of Inclusion-Exclusion

For two sets $A$ and $B$: $|A \cup B| = |A| + |B| - |A \cap B|$ This generalizes to any number of sets, compensating for over-counting elements in intersections.

Relations, Functions, and Morphisms

Mappings allow us to transition from static sets to dynamic interactions. They allow us to compare sets, group elements by shared properties, and transform data while preserving structure.

Binary Relations

A Binary Relation $R$ between sets $A$ and $B$ is a subset of the Cartesian product $A \times B$. If $(a, b) \in R$, we write $aRb$.

A relation $R$ on set $A$ can be:

• Reflexive: $aRa$.
• Symmetric: $aRb \implies bRa$.
• Transitive: $aRb \land bRc \implies aRc$.

def check_properties(elements, relation):
  reflexive = all((e, e) in relation for e in elements)
  symmetric = all((b, a) in relation for (a, b) in relation)
  transitive = all((a, c) in relation 
                   for (a, b1) in relation 
                   for (b2, c) in relation if b1 == b2)
  return {"Reflexive": reflexive, "Symmetric": symmetric, "Transitive": transitive}

S = {1, 2, 3}
R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
print(f"Set: {S}, Relation: {R}")
print(f"Properties: {check_properties(S, R)}")

Equivalence Relations and Partitions

A relation that is reflexive, symmetric, and transitive is an Equivalence Relation. It partitions a set into disjoint Equivalence Classes.

def get_equivalence_classes(elements, relation):
  classes = []
  seen = set()
  for e in elements:
      if e not in seen:
          # Class [e] = {x | xRe}
          cls = {x for x in elements if (x, e) in relation}
          classes.append(cls)
          seen.update(cls)
  return classes

print(f"Equivalence Classes: {get_equivalence_classes(S, R)}")

Classification of Mappings

A function $f: A \to B$ is a relation where every input has exactly one output.

1. Injection (One-to-One): $f(x) = f(y) \implies x = y$.
2. Surjection (Onto): Range equals Codomain.
3. Bijection: Both injective and surjective (invertible).

def classify_function(domain, codomain, f_map):
  # f_map is a dict {x: y}
  injective = len(set(f_map.values())) == len(f_map)
  surjective = set(f_map.values()) == codomain
  
  if injective and surjective: return "Bijection"
  if injective: return "Injection"
  if surjective: return "Surjection"
  return "General Function"

A = {1, 2, 3}
B = {'a', 'b', 'c'}
f = {1: 'a', 2: 'b', 3: 'c'}
print(f"Function mapping: {f}")
print(f"Classification: {classify_function(A, B, f)}")

Morphisms: Structural Preservation

In abstract algebra, we study functions that preserve operations:

• Homomorphism: Preserves algebraic structure $(f(a \cdot b) = f(a) \cdot f(b))$.
• Isomorphism: A bijective homomorphism.

Pre-images and Images

For a subset $T \subseteq B$, the Pre-image is $f^{-1}(T) = \{x \in A \mid f(x) \in T\}$.

Graph Theory: Structures and Connectivity

Graphs provide a formal framework for modeling relationships between discrete objects. A graph $G = (V, E)$ consists of a set of vertices $V$ and edges $E$.

Fundamental Properties

• Degree: The number of edges connected to a vertex.
• Handshaking Lemma: $\sum_{v \in V} \text{deg}(v) = 2|E|$.

def get_degrees(adj_list):
  return {node: len(neighbors) for node, neighbors in adj_list.items()}

# Adjacency List representation
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
}

degrees = get_degrees(graph)
print(f"Degrees: {degrees}")
print(f"Sum of degrees: {sum(degrees.values())}")
print(f"Edges count (Sum/2): {sum(degrees.values()) // 2}")

Connectivity and Traversal

• Connected: A path exists between every pair of vertices.
• Cycle: A path that starts and ends at the same vertex.

def find_path(graph, start, end, path=[]):
  path = path + [start]
  if start == end: return path
  for node in graph[start]:
      if node not in path:
          newpath = find_path(graph, node, end, path)
          if newpath: return newpath
  return None

print(f"Path from A to F: {find_path(graph, 'A', 'F')}")

Planar Graphs and Euler’s Formula

A graph is planar if it can be drawn without edges crossing. For a connected planar graph: $V - E + F = 2$ where $F$ is the number of faces.

Special Graphs: Trees and Bipartite Graphs

• Tree: A connected graph with no cycles. A tree with $n$ vertices always has $n-1$ edges.
• Bipartite: Vertices can be partitioned into two sets such that no edge exists within a set.

def is_bipartite(graph):
  color = {}
  for node in graph:
      if node not in color:
          stack = [(node, 0)]
          color[node] = 0
          while stack:
              u, c = stack.pop()
              for v in graph[u]:
                  if v in color:
                      if color[v] == c: return False
                  else:
                      color[v] = 1 - c
                      stack.append((v, 1 - c))
  return True

print(f"Is graph bipartite? {is_bipartite(graph)}")

Famous Theorems

• Four Color Theorem: Any planar graph can be colored with 4 colors.
• Kuratowski’s Theorem: A graph is planar iff it doesn’t contain $K_5$ or $K_{3,3}$.

Mathematical Induction and Well-Ordering

Mathematical Induction is a method of proof used to establish the truth of an infinite set of statements indexed by natural numbers. Formal grounding lies in the structure of the natural numbers $\mathbb{N}$ and the Well-Ordering Principle.

The Principle of Mathematical Induction

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

1. Base Case: Demonstrate $P(n_0)$ is true.
2. Inductive Step: Prove $P(k) \implies P(k+1)$ for all $k \ge n_0$.

def sum_iterative(n):
  return sum(range(1, n + 1))

def sum_inductive_formula(n):
  return (n * (n + 1)) // 2

n_test = 100
print(f"Iterative Sum(100): {sum_iterative(n_test)}")
print(f"Inductive Formula Value: {sum_inductive_formula(n_test)}")
print(f"Match: {sum_iterative(n_test) == sum_inductive_formula(n_test)}")

Strong Induction

In Strong Induction, we assume $P(m)$ is true for all $n_0 \le m \le k$ to prove $P(k+1)$. This is essential for structures like the Fibonacci sequence.

# The Inductive Base: stored in a persistent structure
cache = {0: 0, 1: 1}

def fibonacci(n):
  # Strong induction: we use multiple previous values (n-1 and n-2)
  if n not in cache:
      cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
  return cache[n]

print(f"F(10) = {fibonacci(10)}")
print(f"Current Inductive Cache: {[(k, cache[k]) for k in sorted(cache.keys())[:7]]}...")

The Well-Ordering Principle

The Well-Ordering Principle states that every non-empty subset of the natural numbers has a least element. This is logically equivalent to the principle of induction.

Structural Induction

Induction extends to recursively defined structures like Trees.

• Base Case: Property holds for leaves.
• Recursive Step: If holds for children, it holds for parent.

class Node:
  def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def count_nodes(node):
  if not node: return 0
  # Structural induction: parent = 1 + left + right
  return 1 + count_nodes(node.left) + count_nodes(node.right)

tree = Node(1, Node(2), Node(3, Node(4)))
print(f"Total nodes in tree: {count_nodes(tree)}")

Information Theory

Information theory is the mathematical study of the quantification, storage, and communication of information. It was founded by Claude Shannon in 1948.

Entropy

Entropy $H(X)$ measures the uncertainty or surprise associated with a random variable $X$. $H(X) = -\sum_{i} P(x_i) \log_b P(x_i)$ Usually, $b=2$ for bits (Shannon entropy).

import math

def calculate_entropy(probabilities):
  entropy = 0
  for p in probabilities:
      if p > 0:
          entropy -= p * math.log2(p)
  return entropy

# Fair coin
print(f"Fair coin entropy: {calculate_entropy([0.5, 0.5])} bits")

# Biased coin (90% heads)
print(f"Biased coin entropy: {calculate_entropy([0.9, 0.1]):.3f} bits")

# Single certain outcome
print(f"Certain outcome entropy: {calculate_entropy([1.0])} bits")

Mutual Information and Kullback-Leibler Divergence

Kullback-Leibler (KL) Divergence, or relative entropy, measures the “distance” (though not a true metric) between two probability distributions $P$ and $Q$: $D_{KL}(P || Q) = \sum_{x \in \mathcal{X}} P(x) \log_2 \left( \frac{P(x)}{Q(x)} \right)$

It quantifies the information lost when $Q$ is used to approximate $P$.

Mutual Information $I(X; Y)$ measures the reduction in uncertainty of $X$ given the knowledge of $Y$: $I(X; Y) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P(x, y) \log_2 \left( \frac{P(x, y)}{P(x)P(y)} \right)$

It is related to entropy by: $I(X; Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X, Y)$.

import math

def kl_divergence(P, Q):
  # D_KL(P || Q) - Sum P(x) log(P(x)/Q(x))
  res = 0
  for p, q in zip(P, Q):
      if p > 0:
          res += p * math.log2(p / q)
  return res

P = [0.1, 0.9]
Q = [0.5, 0.5]
print(f"KL Divergence D_KL(P || Q): {kl_divergence(P, Q):.3f}")

def mutual_information(joint_prob, p_x, p_y):
  # I(X;Y) = Sum P(x,y) log(P(x,y)/(P(x)P(y)))
  mi = 0
  for x in range(len(p_x)):
      for y in range(len(p_y)):
          pxy = joint_prob[x][y]
          if pxy > 0:
              mi += pxy * math.log2(pxy / (p_x[x] * p_y[y]))
  return mi

# Example: X and Y are highly correlated
px = [0.5, 0.5]
py = [0.5, 0.5]
joint = [[0.45, 0.05], [0.05, 0.45]]
print(f"Mutual Information I(X; Y): {mutual_information(joint, px, py):.3f}")

Source Coding Theorem

Shannon’s Source Coding Theorem establishes that the minimum number of bits needed to represent a source is its entropy. Huffman Coding is a common algorithm to achieve this bound.

Channel Capacity

The Shannon-Hartley Theorem defines the maximum rate $C$ at which information can be transmitted over a noisy channel with bandwidth $B$ and signal-to-noise ratio $S/N$: $C = B \log_2(1 + S/N)$

Recurrence Relations

A recurrence relation defines a sequence where each term is a function of preceding terms. They are the discrete analogues of differential equations.

Classification

1. Linear: Terms appear to the first power.
2. Homogeneous: No constant terms or separate functions of $n$.
3. Order: The number of previous terms required.

Solving Linear Homogeneous Recurrences

For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, we solve the Characteristic Equation: $r^2 - c_1 r - c_2 = 0$

import numpy as np

def solve_recurrence(c1, c2, a0, a1, n):
  # Solves a_n = c1*a_{n-1} + c2*a_{n-2}
  roots = np.roots([1, -c1, -c2])
  r1, r2 = roots
  
  # a_n = A*r1^n + B*r2^n
  # a0 = A + B
  # a1 = A*r1 + B*r2
  A_mat = np.array([[1, 1], [r1, r2]])
  B_vec = np.array([a0, a1])
  A, B = np.linalg.solve(A_mat, B_vec)
  
  return A * (r1**n) + B * (r2**n)

# Fibonacci example: a_n = 1*a_{n-1} + 1*a_{n-2}, a0=0, a1=1
val = solve_recurrence(1, 1, 0, 1, 10)
print(f"F(10) via Characteristic Equation: {round(val.real)}")

Binet’s Formula for Fibonacci

The closed-form solution for Fibonacci is: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}, \quad \phi = \frac{1+\sqrt{5}}{2}$

def binet_fib(n):
  phi = (1 + 5**0.5) / 2
  psi = (1 - 5**0.5) / 2
  return round((phi**n - psi**n) / 5**0.5)

print(f"F(20) via Binet: {binet_fib(20)}")

Divide and Conquer: The Master Theorem

In CS, we often see $T(n) = aT(n/b) + f(n)$.

• Merge Sort: $T(n) = 2T(n/2) + n \implies O(n \log n)$.
• Binary Search: $T(n) = T(n/2) + 1 \implies O(\log n)$.

Computational Methods: Matrix Exponentiation

For terms like $F_{10^9}$, floating point precision fails. We use the transformation matrix $M$ where $M^n$ gives the $n$-th term in $O(\log n)$ time.

def matrix_mult(A, B):
  C = [[0, 0], [0, 0]]
  for i in range(2):
      for j in range(2):
          for k in range(2):
              C[i][j] += A[i][k] * B[k][j]
  return C

def matrix_pow(A, p):
  res = [[1, 0], [0, 1]]
  while p > 0:
      if p % 2 == 1: res = matrix_mult(res, A)
      A = matrix_mult(A, A)
      p //= 2
  return res

T = [[1, 1], [1, 0]]
T_n = matrix_pow(T, 10)
print(f"F(10) via Matrix Exponentiation: {T_n[0][1]}")

Axiomatic Set Theory and the ZFC Framework

Set theory is often called the “language of mathematics.” Virtually every mathematical object—numbers, functions, manifolds, operators—can be formally defined as a set.

Russell’s Paradox and the Necessity of Axioms

In Naive Set Theory, one could define a set through any property $P$: $S = \{x \mid P(x)\}$. Bertrand Russell asked: if we define $R = \{x \mid x \notin x\}$ (the set of all sets that do not contain themselves), does $R$ contain itself?

class RussellSet:
  def __contains__(self, item):
      # A set that contains itself only if it DOES NOT contain itself
      return not (item in item if hasattr(item, "__contains__") else False)

r = RussellSet()
try:
  print(f"Does r contain r? {r in r}")
except RecursionError:
  print("Infinite recursion: Russell's Paradox detected!")

The Axioms of ZFC

To resolve such paradoxes, the Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC) were developed.

1. Extensionality: Sets are equal if they have the same elements.
2. Empty Set: $\emptyset$ exists.
3. Power Set: For any set $x$, there exists a set $\mathcal{P}(x)$ containing all subsets of $x$.

from itertools import chain, combinations

def power_set(iterable):
  s = list(iterable)
  return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

s = {1, 2, 3}
ps = list(power_set(s))
print(f"Set: {s}")
print(f"Power Set size: {len(ps)}")
print(f"Subsets: {ps}")

Constructing the Universe: The Von Neumann Hierarchy

Using these axioms, we can build the natural numbers $\mathbb{N}$:

• $0 = \emptyset$
• $1 = \{0\} = \{\emptyset\}$
• $2 = \{0, 1\} = \{\emptyset, \{\emptyset\}\}$

def von_neumann_ordinal(n):
  if n == 0:
      return set()
  prev = von_neumann_ordinal(n - 1)
  # n = prev U {prev}
  return prev | {frozenset(prev)}

for i in range(4):
  print(f"{i}: {von_neumann_ordinal(i)}")

Ordinals and Cardinals

• Ordinals: Describe the order type (position).
• Cardinals: Describe the size (quantity). Two sets have the same cardinality if there exists a bijection between them.

The Axiom of Choice (AC)

AC states that given a collection of non-empty sets, we can select one element from each. While intuitive, it leads to non-constructive results like the Banach-Tarski Paradox (decomposing a ball into two identical balls).