Table of Contents

1. Evaluating the AST
2. Generating All Assignments
3. Building the Truth Table
4. Extracting DNF
5. Extracting CNF
6. Putting It All Together
7. Worked Example
8. Wrapping Up

Evaluating the AST

Given an AST node and a mapping of variable names to boolean values, evaluateAST recursively computes the result:

function evaluateAST(ast, vars) {
  switch (ast.type) {
    case 'var':
      return vars[ast.value];
    case 'not':
      return !evaluateAST(ast.operand, vars);
    case 'and':
      return evaluateAST(ast.left, vars) && evaluateAST(ast.right, vars);
    case 'or':
      return evaluateAST(ast.left, vars) || evaluateAST(ast.right, vars);
    case 'implies':
      return !evaluateAST(ast.left, vars) || evaluateAST(ast.right, vars);
    case 'equiv':
      return evaluateAST(ast.left, vars) === evaluateAST(ast.right, vars);
    default:
      throw new Error('Unknown AST node type: ' + ast.type);
  }
}

Most cases are straightforward. The two worth noting:

• Implication (A -> B) is implemented as !A || B. This is the standard logical equivalence: an implication is only false when the antecedent is true and the consequent is false.
• Equivalence (A <-> B) uses JavaScript’s === on booleans - true if both sides agree.

Generating All Assignments

For n variables we need to evaluate all $2^n$ possible assignments. We use a classic bit manipulation trick: count from $2^n - 1$ down to $0$ and extract each bit to determine whether a variable is true or false.

const numRows = Math.pow(2, variables.length);

for (let i = numRows - 1; i >= 0; i--) {
  const assignment = {};

  for (let j = 0; j < variables.length; j++) {
    // The MSB corresponds to the first variable.
    assignment[variables[j]] = Boolean((i >> (variables.length - j - 1)) & 1);
  }

  const result = evaluateAST(ast, assignment);
  // ... use assignment and result
}

We count downward so that the first row of the table has all variables set to TRUE (the highest binary number) and the last row has all variables FALSE. The bit shift (i >> (variables.length - j - 1)) & 1 extracts the bit for variable j, with the most significant bit corresponding to the first variable.

Example:

For variables [A, B, C], the value i = 5 in binary is 101. The bit extraction gives A=1, B=0, C=1, meaning A=true, B=false, C=true.

Building the Truth Table

For each row we display each variable’s value and the expression’s result, rendering T for true and F for false:

let tableHTML = '<table><thead><tr>';
variables.forEach((v) => {
  tableHTML += '<th>' + v + '</th>';
});
tableHTML += '<th>' + formatInput(input) + '</th>';
tableHTML += '</tr></thead><tbody>';

// Inside the loop for each assignment:
tableHTML += '<tr>';
variables.forEach((v) => {
  tableHTML += '<td>' + (assignment[v] ? 'T' : 'F') + '</td>';
});
tableHTML += '<td>' + (result ? 'T' : 'F') + '</td>';
tableHTML += '</tr>';

The header’s last column uses formatInput (from Chapter 1) to show the expression with proper Unicode symbols.

Extracting DNF

Disjunctive Normal Form is a disjunction (OR) of conjunctions (ANDs). We build it from the rows where the expression evaluates to TRUE.

For each TRUE row, we create a conjunction clause: each variable appears as itself if it’s true in that row, or negated if it’s false. We then OR all the clauses together.

let dnfClauses = [];

// Inside the loop, when result is true:
if (result) {
  let clause = variables.map((v) => (assignment[v] ? v : symbols.not + v)).join(symbols.and);

  if (variables.length > 1) {
    clause = '(' + clause + ')';
  }
  dnfClauses.push(clause);
}

// After the loop:
let dnf = dnfClauses.length > 0 ? dnfClauses.join(symbols.or) : 'False';

If there are no TRUE rows (the expression is a contradiction), the DNF is simply False.

Extracting CNF

Conjunctive Normal Form is a conjunction (AND) of disjunctions (ORs). We build it from the rows where the expression evaluates to FALSE.

For each FALSE row, we create a disjunction clause - but with the literals flipped: each variable is negated if it’s true in that row, or appears as itself if it’s false. We then AND all the clauses together.

let cnfClauses = [];

// Inside the loop, when result is false:
if (!result) {
  let clause = variables.map((v) => (assignment[v] ? symbols.not + v : v)).join(symbols.or);

  if (variables.length > 1) {
    clause = '(' + clause + ')';
  }
  cnfClauses.push(clause);
}

// After the loop:
let cnf = cnfClauses.length > 0 ? cnfClauses.join(symbols.and) : 'True';

If there are no FALSE rows (the expression is a tautology), the CNF is simply True.

Key Insight:

DNF comes from the TRUE rows - each clause describes exactly one satisfying assignment. CNF comes from the FALSE rows - each clause rules out exactly one falsifying assignment. The literal negation is opposite: DNF keeps a variable positive when it’s true; CNF negates it when it’s true.

Putting It All Together

The generateTableAndNF function orchestrates the entire pipeline. It reads the user’s input, tokenizes it, parses it, generates every assignment, evaluates the AST, builds the table HTML, and computes both normal forms:

function generateTableAndNF() {
  const input = document.getElementById('expr').value;

  try {
    const tokens = tokenize(input);
    const ast = parseExpression(tokens);
    const variables = getVariables(ast);

    // Build truth table HTML...
    // Collect DNF and CNF clauses...

    let resultHTML = tableHTML;
    resultHTML += '<div class="normal-forms">';
    resultHTML += '<p><strong>DNF:</strong> ' + dnf + '</p>';
    resultHTML += '<p><strong>CNF:</strong> ' + cnf + '</p>';
    resultHTML += '</div>';

    document.getElementById('result').innerHTML = resultHTML;
  } catch (e) {
    document.getElementById('result').innerHTML = '<p class="error">Error: ' + e.message + '</p>';
  }
}

Any error during tokenization, parsing, or evaluation is caught and displayed to the user as a red error message.

Worked Example

Let’s trace through the full pipeline for (A & B) -> C.

Variables: [A, B, C] (3 variables = 8 rows)

DNF (from the 7 TRUE rows):

(A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (¬A ∧ B ∧ C) ∨ (¬A ∧ B ∧ ¬C) ∨ (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ ¬B ∧ ¬C)

CNF (from the 1 FALSE row - A=T, B=T, C=F):

(¬A ∨ ¬B ∨ C)

The CNF is remarkably simpler here - only one clause, because there’s only one falsifying assignment. This makes intuitive sense: (A & B) -> C can only be false when both A and B are true but C is false, so the CNF encodes exactly that constraint.

Wrapping Up

We’ve now built the complete truth table calculator pipeline:

1. Frontend (Chapter 1) - input field, button, result area
2. Tokenizer (Chapter 2) - raw string to token array
3. Parser (Chapter 3) - token array to AST
4. Evaluator + Normal Forms (this chapter) - AST to truth table, DNF, and CNF

The full source code is on GitHub, and you can try the live calculator at the project page.

If you’re curious about why this construction always produces correct CNF and DNF - and want to see formal proofs - continue to Chapter 5: The Math Behind It All.

Previous: Chapter 3: Parsing with Recursive Descent

Series: Back to Truth Table, CNF, and DNF Generator