Mathematical Logic

Last updated: December 2024

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

1. Propositional Logic

1.1 Basic Propositions

A proposition is a declarative statement that is either true or false, but not both.

1.2 Logical Connectives

1.3 Truth Tables

$p$ $q$ $\neg p$ $p \land q$ $p \lor q$ $p \rightarrow q$ $p \leftrightarrow q$ $p \oplus q$
T T F T T T T F
T F F F T F F T
F T T F T T F T
F F T F F T T F

1.4 Logical Equivalences

1.5 Tautologies and Contradictions

2. Predicate Logic

2.1 Predicates and Quantifiers

2.2 Quantifier Rules

2.3 Multiple Quantifiers

Order matters: $\forall x \exists y P(x,y)$ is different from $\exists y \forall x P(x,y)$

3. Proof Techniques

3.1 Direct Proof

To prove $p \rightarrow q$, assume $p$ is true and show that $q$ must be true.

3.2 Proof by Contraposition

To prove $p \rightarrow q$, prove $\neg q \rightarrow \neg p$ (the contrapositive).

3.3 Proof by Contradiction

To prove $p$, assume $\neg p$ and derive a contradiction.

3.4 Proof by Cases

To prove $p$, consider all possible cases and show $p$ holds in each case.

3.5 Mathematical Induction

To prove $\forall n \geq n_0, P(n)$:

  1. Base case: Prove $P(n_0)$
  2. Inductive step: Prove $P(k) \rightarrow P(k+1)$ for arbitrary $k \geq n_0$

3.6 Strong Induction

To prove $\forall n \geq n_0, P(n)$:

  1. Base case: Prove $P(n_0)$
  2. Inductive step: Assume $P(n_0) \land P(n_0+1) \land \ldots \land P(k)$ and prove $P(k+1)$

4. Set Theory

4.1 Basic Definitions

4.2 Set Operations

4.3 Set Identities

4.4 Cartesian Product

$A \times B = \{(a,b) : a \in A \land b \in B\}$

If $|A| = m$ and $|B| = n$, then $|A \times B| = mn$

4.5 Power Set

$\mathcal{P}(A) = \{S : S \subseteq A\}$ (set of all subsets of $A$)

If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$

5. Relations and Functions

5.1 Relations

A relation $R$ from set $A$ to set $B$ is a subset of $A \times B$.

We write $aRb$ or $(a,b) \in R$ to mean $a$ is related to $b$.

5.2 Properties of Relations (on set $A$)

5.3 Special Types of Relations

5.4 Functions

A function $f: A \rightarrow B$ is a relation where each element in $A$ is related to exactly one element in $B$.

5.5 Types of Functions

6. Boolean Algebra

6.1 Boolean Variables and Operations

Boolean algebra deals with variables that can take values 0 (false) or 1 (true).

6.2 Boolean Laws

7. Code Examples

# Python implementations for logical operations and proofs
from itertools import product

def truth_table(formula, variables):
    """Generate truth table for a logical formula"""
    print(f"Truth table for: {formula.__name__}")
    
    # Print header
    header = list(variables) + [formula.__name__]
    print(" | ".join(f"{var:^8}" for var in header))
    print("-" * (len(header) * 11 - 1))
    
    # Generate all possible truth value assignments
    for values in product([True, False], repeat=len(variables)):
        assignment = dict(zip(variables, values))
        result = formula(**assignment)
        
        row = list(values) + [result]
        print(" | ".join(f"{str(val):^8}" for val in row))

# Define logical operations
def NOT(p):
    return not p

def AND(p, q):
    return p and q

def OR(p, q):
    return p or q

def IMPLIES(p, q):
    return (not p) or q

def BICONDITIONAL(p, q):
    return p == q

def XOR(p, q):
    return p != q

# Example formulas
def de_morgan_1(p, q):
    """De Morgan's Law: ¬(p ∧ q) ≡ ¬p ∨ ¬q"""
    left = NOT(AND(p, q))
    right = OR(NOT(p), NOT(q))
    return left == right

def de_morgan_2(p, q):
    """De Morgan's Law: ¬(p ∨ q) ≡ ¬p ∧ ¬q"""
    left = NOT(OR(p, q))
    right = AND(NOT(p), NOT(q))
    return left == right

def modus_ponens(p, q):
    """Modus Ponens: ((p → q) ∧ p) → q"""
    premise = AND(IMPLIES(p, q), p)
    return IMPLIES(premise, q)

def hypothetical_syllogism(p, q, r):
    """Hypothetical Syllogism: ((p → q) ∧ (q → r)) → (p → r)"""
    premise = AND(IMPLIES(p, q), IMPLIES(q, r))
    conclusion = IMPLIES(p, r)
    return IMPLIES(premise, conclusion)

# Set operations
class Set:
    def __init__(self, elements=None):
        self.elements = set(elements) if elements else set()
    
    def __str__(self):
        return "{" + ", ".join(str(x) for x in sorted(self.elements)) + "}"
    
    def __contains__(self, element):
        return element in self.elements
    
    def union(self, other):
        return Set(self.elements | other.elements)
    
    def intersection(self, other):
        return Set(self.elements & other.elements)
    
    def difference(self, other):
        return Set(self.elements - other.elements)
    
    def symmetric_difference(self, other):
        return Set(self.elements ^ other.elements)
    
    def is_subset(self, other):
        return self.elements <= other.elements
    
    def is_proper_subset(self, other):
        return self.elements < other.elements
    
    def complement(self, universal_set):
        return Set(universal_set.elements - self.elements)
    
    def power_set(self):
        """Return the power set"""
        from itertools import combinations
        power_set_elements = []
        for r in range(len(self.elements) + 1):
            for combo in combinations(self.elements, r):
                power_set_elements.append(Set(combo))
        return power_set_elements
    
    def cartesian_product(self, other):
        """Return Cartesian product with another set"""
        return Set((a, b) for a in self.elements for b in other.elements)

# Mathematical induction proof checker
def prove_by_induction(predicate, base_case, inductive_step, n_max=10):
    """
    Verify a proof by induction for small values
    predicate: function that takes n and returns True/False
    base_case: starting value of n
    inductive_step: function that proves P(k) -> P(k+1)
    """
    print(f"Proving by induction up to n = {n_max}")
    
    # Check base case
    if not predicate(base_case):
        print(f"Base case fails: P({base_case}) is False")
        return False
    print(f"Base case: P({base_case}) is True ✓")
    
    # Check inductive step for small values
    for k in range(base_case, n_max):
        if predicate(k) and not predicate(k + 1):
            print(f"Inductive step fails: P({k}) is True but P({k+1}) is False")
            return False
        elif predicate(k):
            print(f"Inductive step: P({k}) → P({k+1}) ✓")
    
    print("Induction proof verified for the tested range ✓")
    return True

# Example: Prove sum of first n positive integers is n(n+1)/2
def sum_formula(n):
    """Check if sum of first n positive integers equals n(n+1)/2"""
    actual_sum = sum(range(1, n + 1))
    formula_result = n * (n + 1) // 2
    return actual_sum == formula_result

# Example usage
if __name__ == "__main__":
    print("=== Truth Tables ===")
    truth_table(de_morgan_1, ['p', 'q'])
    print()
    
    truth_table(modus_ponens, ['p', 'q'])
    print()
    
    print("=== Set Operations ===")
    A = Set([1, 2, 3, 4])
    B = Set([3, 4, 5, 6])
    U = Set(range(1, 11))
    
    print(f"A = {A}")
    print(f"B = {B}")
    print(f"A ∪ B = {A.union(B)}")
    print(f"A ∩ B = {A.intersection(B)}")
    print(f"A - B = {A.difference(B)}")
    print(f"A △ B = {A.symmetric_difference(B)}")
    print(f"A ⊆ U: {A.is_subset(U)}")
    
    print(f"\nPower set of {{1, 2}}:")
    small_set = Set([1, 2])
    for subset in small_set.power_set():
        print(f"  {subset}")
    
    print("\n=== Mathematical Induction ===")
    prove_by_induction(sum_formula, 1, None, 10)

8. Applications

8.1 Computer Science

8.2 Mathematics

8.3 Philosophy

9. References