Project 13: Boolean Function Analyzer

Analyze boolean functions, truth tables, and decision diagrams.

Quick Reference

Attribute Value
Difficulty Expert
Time Estimate 2-3 weeks
Language C
Prerequisites Bitwise ops, combinatorics
Key Topics truth tables, BDDs, simplification

1. Learning Objectives

  1. Represent boolean functions as truth tables.
  2. Build a reduced ordered BDD.
  3. Compute properties like tautology, equivalence, sensitivity.
  4. Visualize or serialize BDDs.

2. Theoretical Foundation

2.1 Core Concepts

  • Truth table: 2^n rows for n variables.
  • BDD: DAG representation with reduction rules.
  • Boolean properties: monotonicity, symmetry, equivalence.

2.2 Why This Matters

TAOCP Vol 4A explores boolean function analysis and efficient representations.

2.3 Historical Context / Background

BDDs are widely used in verification and circuit design.

2.4 Common Misconceptions

  • “Truth tables scale”: They explode exponentially.
  • “BDD size is fixed”: It depends on variable ordering.

3. Project Specification

3.1 What You Will Build

A tool that ingests boolean expressions, builds truth tables and BDDs, and computes properties.

3.2 Functional Requirements

  1. Parse boolean expressions (AND/OR/NOT/XOR).
  2. Generate truth table outputs.
  3. Build reduced ordered BDDs.
  4. Check equivalence of two functions.

3.3 Non-Functional Requirements

  • Correctness: BDD reduction rules enforced.
  • Performance: Memoization for node reuse.
  • Usability: Clear CLI output.

3.4 Example Usage / Output

$ ./booltool "a & b | !c"
vars=3, minterms=3
bdd_nodes=5

3.5 Real World Outcome

You can compare boolean expressions and verify equivalence via BDDs.

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│ parser       │────▶│ truth table  │────▶│ BDD builder  │
└──────────────┘     └──────────────┘     └──────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Parser expression to AST recursive descent
Table evaluate assignments bitset storage
BDD reduced DAG unique table

4.3 Data Structures

typedef struct {
    int var;
    int low;
    int high;
} BddNode;

4.4 Algorithm Overview

Key Algorithm: BDD reduce

  1. Apply reduction rules: merge identical subgraphs.
  2. Eliminate nodes with low==high.

Complexity Analysis:

  • Depends on variable ordering; worst-case exponential.

5. Implementation Guide

5.1 Development Environment Setup

gcc --version

5.2 Project Structure

project-root/
├── src/parser.c
├── src/bdd.c
├── src/table.c
└── Makefile

5.3 The Core Question You’re Answering

“How can boolean functions be represented compactly and compared efficiently?”

5.4 Concepts You Must Understand First

  • Boolean algebra identities
  • DAG reduction and memoization
  • Variable ordering impact

5.5 Questions to Guide Your Design

  1. How will you ensure node uniqueness?
  2. What variable order will you use?
  3. How will you verify equivalence?

5.6 Thinking Exercise

Show how changing variable order affects BDD size for the same function.

5.7 The Interview Questions They’ll Ask

  1. What is a BDD and why is it useful?
  2. How do you check boolean equivalence efficiently?
  3. Why does variable ordering matter?

5.8 Hints in Layers

Hint 1: Build truth table evaluator. Hint 2: Build BDD with memoization. Hint 3: Add equivalence checking.

5.9 Books That Will Help

Topic Book Chapter
Boolean functions TAOCP Vol 4A Ch. 7.1.4

5.10 Implementation Phases

Phase 1: Foundation (1 week)

  • Parser + truth table.

Phase 2: Core Functionality (1 week)

  • BDD builder and reduction.

Phase 3: Polish & Edge Cases (3-4 days)

  • Equivalence checks and reporting.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Representation table vs BDD both comparison

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Truth table correctness known functions
BDD node counts simple functions
Equivalence compare (a&b) vs (b&a)

6.2 Critical Test Cases

  1. Tautology and contradiction detection.
  2. Equivalence of reordered expressions.
  3. BDD size sanity checks.

6.3 Test Data

Simple boolean formulas with known outcomes

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
No memoization huge BDD unique table
Wrong precedence incorrect table parser tests
Bad ordering blowup fixed order experiments

7.2 Debugging Strategies

  • Compare truth table results with brute force.
  • Log BDD node counts.

7.3 Performance Traps

Truth tables explode with n; BDD is critical for larger n.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add CNF/DNF conversion.

8.2 Intermediate Extensions

  • Implement variable reordering heuristic.

8.3 Advanced Extensions

  • Add SAT solving via BDD.

9. Real-World Connections

  • Formal verification, circuit optimization, model checking.

10. Resources

  • TAOCP Vol 4A Chapter 7.1.4.

11. Self-Assessment Checklist

  • I can explain BDD reduction rules.
  • My tool correctly detects equivalence.

12. Submission / Completion Criteria

Minimum: Truth table generator. Full: Reduced BDD and equivalence checks. Excellence: Variable reordering and CNF/DNF.

This guide was generated from LEARN_TAOCP_DEEP_DIVE.md. For the complete learning path, see the parent directory README.