Logical Equivalences

Why This Matters

When you refactor a complex if statement, you need to know that the simplified version behaves identically to the original. Logical equivalence gives you the formal guarantee: two expressions are equivalent when they produce the same truth value for every possible input. This is the foundation of code simplification, compiler optimization, and circuit minimization.

A tautology is an expression that is always true, no matter what values the variables take. Its opposite, a contradiction, is always false. Recognizing these patterns lets you eliminate dead code, simplify conditions, and spot impossible states. If a guard condition is a tautology, the branch always executes. If it is a contradiction, it never does.

De Morgan's Laws, double negation, distribution, and absorption are the key equivalence rules. They are the algebra of logic, and they appear constantly in programming, database queries, and circuit design. Mastering them makes you a better debugger and a clearer thinker.

Define Terms

Visual Model

Code Example

// Check if two expressions are logically equivalent
function areEquivalent(exprA, exprB) {
  const values = [
    [true, true], [true, false],
    [false, true], [false, false]
  ];
  for (const [p, q] of values) {
    if (exprA(p, q) !== exprB(p, q)) {
      console.log(`Not equivalent: p=${p}, q=${q}`);
      return false;
    }
  }
  console.log("Logically equivalent!");
  return true;
}

// De Morgans Law: NOT (P AND Q) === (NOT P) OR (NOT Q)
const exprA = (p, q) => !(p && q);
const exprB = (p, q) => (!p) || (!q);
areEquivalent(exprA, exprB); // Logically equivalent!

// Check for tautology: expression is true for all inputs
function isTautology(expr) {
  const values = [[true, true], [true, false], [false, true], [false, false]];
  return values.every(([p, q]) => expr(p, q));
}

console.log("P OR NOT P is tautology:", isTautology((p, q) => p || !p)); // true

// Check for contradiction: expression is false for all inputs
function isContradiction(expr) {
  const values = [[true, true], [true, false], [false, true], [false, false]];
  return values.every(([p, q]) => !expr(p, q));
}

console.log("P AND NOT P is contradiction:", isContradiction((p, q) => p && !p)); // true

// Double negation: NOT NOT P === P
const dblNeg = (p, q) => !!p;
const identity = (p, q) => p;
areEquivalent(dblNeg, identity); // Logically equivalent!

Interactive Experiment

Try these exercises:

• Verify both De Morgan's Laws: NOT (P AND Q) = (NOT P) OR (NOT Q) and NOT (P OR Q) = (NOT P) AND (NOT Q). Build truth tables for each.
• Test the distribution law: P AND (Q OR R) should equal (P AND Q) OR (P AND R). Check all 8 rows.
• Find the simplest equivalent expression for NOT (NOT P OR Q). Hint: apply De Morgan's and double negation.
• Create an expression with 2 variables that is a tautology but is not simply P OR NOT P.
• Write an expression that looks complex but simplifies to just P. Verify with a truth table.

Quick Quiz

Coding Challenge

Real-World Usage

Logical equivalences drive optimization and correctness:

• Compiler optimization: Compilers apply equivalence rules to simplify boolean expressions in compiled code, reducing branch instructions.
• SQL query optimization: Database engines rewrite WHERE clauses using equivalence rules to use indexes more efficiently.
• Circuit minimization: Digital logic designers use Karnaugh maps and boolean algebra to reduce gate count, saving silicon area and power.
• Code refactoring: Knowing that !(a && b) equals !a || !b lets you rewrite conditions for clarity without changing behavior.
• Formal verification: Model checkers use equivalence rules to prove that software specifications match their implementations.

Connections