TMC #0002: Boolean Circuit Simulator

"""
The Thinking Machine Chronicles #0002
Boolean Circuit Simulator
=========================
A Python implementation of the algebraic model described in Claude Shannon's 1937/1938
master's thesis "A Symbolic Analysis of Relay and Switching Circuits".

Shannon's key insight: every switching circuit can be represented by a Boolean expression,
and Boolean algebra provides a rigorous calculus for simplifying and transforming circuits.

This module provides:
  - Gate primitives (AND, OR, NOT, NAND, NOR, XOR, XNOR)
  - A composable Circuit class
  - Truth table generation
  - Canonical forms (Sum of Products, Product of Sums)
  - Shannon expansion (basis of BDDs and modern formal verification)
  - A simple expression parser and evaluator

Usage:
    python boolean_circuits.py
"""

from __future__ import annotations

import itertools
from typing import Callable, Dict, FrozenSet, List, Tuple

# ---------------------------------------------------------------------------
# Boolean algebra primitives
# ---------------------------------------------------------------------------


def AND(*args: bool) -> bool:
    return all(args)


def OR(*args: bool) -> bool:
    return any(args)


def NOT(a: bool) -> bool:
    return not a


def NAND(*args: bool) -> bool:
    return not all(args)


def NOR(*args: bool) -> bool:
    return not any(args)


def XOR(a: bool, b: bool) -> bool:
    return a != b


def XNOR(a: bool, b: bool) -> bool:
    return a == b


# ---------------------------------------------------------------------------
# Gate class — a named, composable logic gate
# ---------------------------------------------------------------------------


class Gate:
    """
    A single logic gate with named inputs.

    A Gate is a function  f: {0,1}^n → {0,1}.
    Gates can be composed: the output of one Gate can be the input of another,
    forming a directed acyclic graph — a combinational circuit.
    """

    def __init__(self, name: str, fn: Callable[..., bool], *inputs):
        """
        name   — identifier used in truth tables and descriptions
        fn     — the gate function (AND, OR, NOT, …)
        inputs — either bool literals, variable names (str), or other Gates
        """
        self.name = name
        self.fn = fn
        self.inputs = inputs

    def evaluate(self, assignment: Dict[str, bool]) -> bool:
        """Recursively evaluate the gate given a variable assignment."""
        resolved = []
        for inp in self.inputs:
            if isinstance(inp, Gate):
                resolved.append(inp.evaluate(assignment))
            elif isinstance(inp, str):
                if inp not in assignment:
                    raise KeyError(f"Variable '{inp}' not in assignment.")
                resolved.append(assignment[inp])
            elif isinstance(inp, bool):
                resolved.append(inp)
            else:
                resolved.append(bool(inp))
        return self.fn(*resolved)

    def variables(self) -> FrozenSet[str]:
        """Return the set of all input variable names this gate depends on."""
        result: set[str] = set()
        for inp in self.inputs:
            if isinstance(inp, Gate):
                result |= inp.variables()
            elif isinstance(inp, str):
                result.add(inp)
        return frozenset(result)

    def truth_table(self) -> List[Tuple[Dict[str, bool], bool]]:
        """Generate the complete truth table for this gate."""
        vars_sorted = sorted(self.variables())
        table = []
        for values in itertools.product([False, True], repeat=len(vars_sorted)):
            assignment = dict(zip(vars_sorted, values))
            output = self.evaluate(assignment)
            table.append((assignment, output))
        return table

    def print_truth_table(self) -> None:
        """Pretty-print the truth table."""
        table = self.truth_table()
        vars_sorted = sorted(self.variables())
        header = "  ".join(f"{v:^5}" for v in vars_sorted) + "  │  " + f"{self.name:^7}"
        print(f"\n  {header}")
        print("  " + "─" * (len(header) + 2))
        for assignment, output in table:
            row = "  ".join(f"{'1' if assignment[v] else '0':^5}" for v in vars_sorted)
            out = "1" if output else "0"
            print(f"  {row}  │  {out:^7}")
        print()

    def to_sop(self) -> str:
        """
        Convert to Sum of Products (SOP) canonical form.
        Each minterm is a conjunction of literals; the SOP is their disjunction.
        This corresponds to Shannon's sum of minterms representation.
        """
        vars_sorted = sorted(self.variables())
        minterms = []
        for assignment, output in self.truth_table():
            if output:
                term = " ∧ ".join(v if assignment[v] else f"¬{v}" for v in vars_sorted)
                minterms.append(f"({term})")
        if not minterms:
            return "0"  # always false
        return " ∨ ".join(minterms)

    def to_pos(self) -> str:
        """
        Convert to Product of Sums (POS) canonical form.
        Each maxterm is a disjunction of literals; the POS is their conjunction.
        """
        vars_sorted = sorted(self.variables())
        maxterms = []
        for assignment, output in self.truth_table():
            if not output:
                term = " ∨ ".join(f"¬{v}" if assignment[v] else v for v in vars_sorted)
                maxterms.append(f"({term})")
        if not maxterms:
            return "1"  # always true
        return " ∧ ".join(maxterms)

    def __repr__(self) -> str:
        return f"Gate({self.name!r})"


# ---------------------------------------------------------------------------
# Shannon expansion (cofactor)
# ---------------------------------------------------------------------------


def shannon_expansion(gate: Gate, variable: str) -> Tuple[Gate, Gate]:
    """
    Shannon's expansion theorem (1938):

        f(x₁, …, xₙ) = x·f(x₁,…,xᵢ=1,…,xₙ)  ∨  ¬x·f(x₁,…,xᵢ=0,…,xₙ)

    Returns (positive_cofactor, negative_cofactor):
        positive_cofactor — f with variable fixed to True
        negative_cofactor — f with variable fixed to False

    This is the foundational operation behind Binary Decision Diagrams (BDDs),
    used in hardware verification tools like Cadence and Synopsys.
    """

    class CofactorGate(Gate):
        def __init__(self, original: Gate, var: str, value: bool):
            self.original = original
            self.var = var
            self.value = value
            self.name = f"{original.name}[{var}={'1' if value else '0'}]"
            self.fn = lambda: None  # unused
            self.inputs = ()

        def evaluate(self, assignment: Dict[str, bool]) -> bool:
            return self.original.evaluate({**assignment, self.var: self.value})

        def variables(self) -> FrozenSet[str]:
            return self.original.variables() - {self.var}

    return CofactorGate(gate, variable, True), CofactorGate(gate, variable, False)


# ---------------------------------------------------------------------------
# Classic circuit examples
# ---------------------------------------------------------------------------


def half_adder() -> Tuple[Gate, Gate]:
    """
    Half adder: adds two single bits.
    Outputs: sum = A XOR B,  carry = A AND B
    """
    a, b = "A", "B"
    s = Gate("sum", XOR, a, b)
    c = Gate("carry", AND, a, b)
    return s, c


def full_adder() -> Tuple[Gate, Gate]:
    """
    Full adder: adds two bits plus a carry-in.
    Inputs: A, B, Cin
    Outputs: sum, carry-out

    The circuit that, cascaded, forms a ripple-carry adder —
    the fundamental arithmetic unit in every ALU.

    sum  = A XOR B XOR Cin
    cout = (A AND B) OR (Cin AND (A XOR B))
    """
    a, b, cin = "A", "B", "Cin"
    xor_ab = Gate("xor_ab", XOR, a, b)
    sum_gate = Gate("sum", XOR, xor_ab, cin)
    and_ab = Gate("and_ab", AND, a, b)
    and_xcin = Gate("and_xcin", AND, xor_ab, cin)
    cout = Gate("cout", OR, and_ab, and_xcin)
    return sum_gate, cout


def two_bit_ripple_carry_adder() -> List[Gate]:
    """
    Ripple-carry adder for two 2-bit numbers A₁A₀ + B₁B₀.

    Variables: A0, A1, B0, B1
    Outputs: S0, S1, S2 (S2 is the overflow carry)

    This is how CPUs computed addition before carry-lookahead was invented.
    Shannon's symbolic framework is what makes analysing this circuit tractable.
    """
    # Bit 0: half adder
    xor_0 = Gate("S0", XOR, "A0", "B0")
    and_0 = Gate("C0", AND, "A0", "B0")

    # Bit 1: full adder with carry-in from bit 0
    xor_ab1 = Gate("xab1", XOR, "A1", "B1")
    s1 = Gate("S1", XOR, xor_ab1, and_0)
    and_ab1 = Gate("aab1", AND, "A1", "B1")
    and_xcin1 = Gate("axcin1", AND, xor_ab1, and_0)
    c1 = Gate("S2", OR, and_ab1, and_xcin1)  # final carry = overflow bit

    return [xor_0, s1, c1]


def majority_circuit() -> Gate:
    """
    Majority gate: outputs 1 iff at least 2 of 3 inputs are 1.
    maj(A,B,C) = (A∧B) ∨ (A∧C) ∨ (B∧C)

    Used in fault-tolerant systems and as a primitive in some logic families.
    """
    ab = Gate("AB", AND, "A", "B")
    ac = Gate("AC", AND, "A", "C")
    bc = Gate("BC", AND, "B", "C")
    return Gate("maj", OR, ab, ac, bc)


def demorgans_demo() -> None:
    """
    Demonstrate De Morgan's laws:
        ¬(A ∧ B) = ¬A ∨ ¬B
        ¬(A ∨ B) = ¬A ∧ ¬B

    De Morgan's laws are the algebraic basis for converting between
    AND-centric and OR-centric logic families, and for NAND-only implementations
    (every Boolean function can be expressed using only NAND gates).
    """
    print("  De Morgan's Law 1:  ¬(A ∧ B)  =  ¬A ∨ ¬B")
    lhs = Gate("¬(A∧B)", NAND, "A", "B")
    rhs = Gate("¬A∨¬B", OR, Gate("¬A", NOT, "A"), Gate("¬B", NOT, "B"))

    vars_sorted = ["A", "B"]
    print(f"\n  {'A':^5}  {'B':^5}  │  {'¬(A∧B)':^9}  {'¬A∨¬B':^9}  {'Equal?':^8}")
    print("  " + "─" * 50)
    for a_val, b_val in itertools.product([False, True], repeat=2):
        assignment = {"A": a_val, "B": b_val}
        l = lhs.evaluate(assignment)
        r = rhs.evaluate(assignment)
        eq = "✓" if l == r else "✗"
        print(
            f"  {'1' if a_val else '0':^5}  {'1' if b_val else '0':^5}  │"
            f"  {'1' if l else '0':^9}  {'1' if r else '0':^9}  {eq:^8}"
        )
    print()


# ---------------------------------------------------------------------------
# Simple expression parser (for interactive use)
# ---------------------------------------------------------------------------


def eval_expression(expr: str, assignment: Dict[str, bool]) -> bool:
    """
    Evaluate a simple Boolean expression string.

    Operators:  &  (AND),  |  (OR),  ~  (NOT),  ^  (XOR)
    Variables:  single uppercase letters (A–Z)
    Parentheses are supported.

    Example:
        eval_expression("(A & B) | (~A & C)", {"A": True, "B": False, "C": True})
        → True
    """
    # Replace variable names with Python bool literals
    expr_py = expr
    for var, val in sorted(assignment.items(), key=lambda x: -len(x[0])):
        expr_py = expr_py.replace(var, str(int(val)))

    # Map operators to Python equivalents
    expr_py = (
        expr_py.replace("&", " and ")
        .replace("|", " or ")
        .replace("~", " not ")
        .replace("^", " ^ ")
    )

    try:
        result = eval(expr_py, {"__builtins__": {}})  # noqa: S307  (controlled input)
        return bool(result)
    except Exception as exc:
        raise ValueError(f"Invalid expression: {expr!r}") from exc


def truth_table_from_expression(expr: str, variables: List[str]) -> None:
    """Print a truth table for an arbitrary Boolean expression string."""
    print(f"\n  Expression: {expr}")
    header = "  ".join(f"{v:^5}" for v in variables) + "  │  " + "output"
    print(f"\n  {header}")
    print("  " + "─" * (len(header) + 2))
    for values in itertools.product([False, True], repeat=len(variables)):
        assignment = dict(zip(variables, values))
        output = eval_expression(expr, assignment)
        row = "  ".join(f"{'1' if v else '0':^5}" for v in values)
        print(f"  {row}  │  {'1' if output else '0':^6}")
    print()


# ---------------------------------------------------------------------------
# Main demo
# ---------------------------------------------------------------------------


def main() -> None:
    print("=" * 68)
    print("  THE THINKING MACHINE CHRONICLES #0002")
    print("  Boolean Circuit Simulator")
    print("=" * 68)

    # ── 1. Half adder ──────────────────────────────────────────────────────
    print("\n── Circuit 1: Half Adder ─────────────────────────────────────────")
    s, c = half_adder()
    print("\n  sum (A XOR B):")
    s.print_truth_table()
    print("  carry (A AND B):")
    c.print_truth_table()

    # ── 2. Full adder ──────────────────────────────────────────────────────
    print("── Circuit 2: Full Adder ─────────────────────────────────────────")
    s, c = full_adder()
    table = s.truth_table()
    cout_table = c.truth_table()
    print(f"\n  {'A':^5}  {'B':^5}  {'Cin':^5}  │  {'Sum':^5}  {'Cout':^5}")
    print("  " + "─" * 40)
    for (assign, sv), (_, cv) in zip(table, cout_table):
        a = "1" if assign["A"] else "0"
        b = "1" if assign["B"] else "0"
        ci = "1" if assign["Cin"] else "0"
        print(
            f"  {a:^5}  {b:^5}  {ci:^5}  │  {'1' if sv else '0':^5}  {'1' if cv else '0':^5}"
        )
    print()

    # ── 3. Majority circuit ────────────────────────────────────────────────
    print("── Circuit 3: Majority Gate ──────────────────────────────────────")
    maj = majority_circuit()
    print(f"\n  SOP: {maj.to_sop()}")
    print(f"  POS: {maj.to_pos()}")
    maj.print_truth_table()

    # ── 4. De Morgan's laws ────────────────────────────────────────────────
    print("── Verification: De Morgan's Laws ───────────────────────────────")
    demorgans_demo()

    # ── 5. Shannon expansion ───────────────────────────────────────────────
    print("── Shannon Expansion Theorem ─────────────────────────────────────")
    print("\n  Expanding majority gate on variable A:")
    pos_cf, neg_cf = shannon_expansion(maj, "A")
    print("\n  f(A=1, B, C) — positive cofactor:")
    pos_cf.print_truth_table()
    print("  f(A=0, B, C) — negative cofactor:")
    neg_cf.print_truth_table()
    print("  Theorem: f(A,B,C) = (A ∧ f[A=1]) ∨ (¬A ∧ f[A=0])")
    print("  This is the recursive step in Binary Decision Diagrams (BDDs).\n")

    # ── 6. Expression evaluator ────────────────────────────────────────────
    print("── Expression Evaluator ──────────────────────────────────────────")
    truth_table_from_expression("(A & B) | (~A & C)", ["A", "B", "C"])
    truth_table_from_expression("A ^ B ^ C", ["A", "B", "C"])

    # ── 7. 2-bit ripple-carry adder ────────────────────────────────────────
    print("── 2-bit Ripple-Carry Adder (A₁A₀ + B₁B₀) ──────────────────────")
    s0, s1, s2 = two_bit_ripple_carry_adder()
    print(
        f"\n  {'A1':^4} {'A0':^4} {'B1':^4} {'B0':^4}  │  "
        f"{'S2':^4} {'S1':^4} {'S0':^4}  decimal"
    )
    print("  " + "─" * 55)
    for vals in itertools.product([False, True], repeat=4):
        a1, a0, b1, b0 = vals
        assign = {"A0": a0, "A1": a1, "B0": b0, "B1": b1}
        sv0 = s0.evaluate(assign)
        sv1 = s1.evaluate(assign)
        sv2 = s2.evaluate(assign)
        a_num = int(a1) * 2 + int(a0)
        b_num = int(b1) * 2 + int(b0)
        result = int(sv2) * 4 + int(sv1) * 2 + int(sv0)
        check = "✓" if result == a_num + b_num else "✗"
        print(
            f"  {int(a1):^4} {int(a0):^4} {int(b1):^4} {int(b0):^4}  │  "
            f"{int(sv2):^4} {int(sv1):^4} {int(sv0):^4}  "
            f"{a_num}+{b_num}={result} {check}"
        )
    print()


if __name__ == "__main__":
    main()