Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 37 · Propositional Logic

Normal Forms: CNF and DNF

Convert any propositional formula to conjunctive or disjunctive normal form, understand minterms and maxterms, and implement the conversion in Python and SymPy.

A formula can be written in endlessly many equivalent ways. A normal form picks one standard shape so that tools can assume it. Two normal forms dominate: disjunctive normal form (DNF), an OR of ANDs, and conjunctive normal form (CNF), an AND of ORs. CNF is the input format of every SAT solver, so it is the most practically important shape in logic.

Vocabulary

  • A literal is a variable or its negation: p, ¬q.
  • A clause is an OR of literals: p ∨ ¬q ∨ r.
  • A term (or cube) is an AND of literals: p ∧ ¬q.

DNF is an OR of terms: (p ∧ ¬q) ∨ (¬p ∧ r). CNF is an AND of clauses: (p ∨ ¬q) ∧ (¬p ∨ r).

Every propositional formula is equivalent to a formula in each normal form.

Two normal forms

DNF OR of ANDs
CNF AND of ORs
Literal A variable or its negation

Every formula has both

1 / 2

Building DNF from a truth table

The most direct recipe: look at each row where the formula is true, write the term that matches that row exactly (a minterm), and OR the terms together. For a row with p=T, q=F the minterm is p ∧ ¬q.

Example: take p ⊕ q (exclusive or). It is true in rows (T,F) and (F,T), so its DNF is (p ∧ ¬q) ∨ (¬p ∧ q).

Building CNF from a truth table

Dually, look at each row where the formula is false, write the clause that rules that row out (a maxterm: negate every literal that is true in that row), and AND the clauses. For p ⊕ q, the false rows are (T,T) and (F,F), giving the clauses ¬p ∨ ¬q and p ∨ q:

p ⊕ q ≡ (¬p ∨ ¬q) ∧ (p ∨ q).

Python Canonical DNF and CNF from a truth table

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

These are canonical forms: every term mentions every variable. They are correct but may be long, with up to 2**n terms.

Converting by rewriting

For large formulas you never enumerate rows. Instead you transform symbolically in three steps:

  1. Eliminate ↔ and → using p → q ≡ ¬p ∨ q and p ↔ q ≡ (p → q) ∧ (q → p).
  2. Push negations inward with De Morgan's laws and double negation until negation only touches variables (negation normal form, NNF).
  3. Distribute ∨ over ∧ (for CNF) or ∧ over ∨ (for DNF).

Example: convert (p ∧ q) → r to CNF. Step 1: ¬(p ∧ q) ∨ r. Step 2: (¬p ∨ ¬q) ∨ r, which is already a single clause: ¬p ∨ ¬q ∨ r.

Step 3 can blow up: converting (a1 ∧ b1) ∨ (a2 ∧ b2) ∨ … ∨ (an ∧ bn) to CNF produces 2**n clauses. For SAT solving this is avoided by the Tseitin transformation, which adds fresh variables to keep the CNF linear in size while preserving satisfiability (not equivalence).

Python Rewriting to CNF with SymPy and checking equivalence

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which form for which job?

  • Is it satisfiable? From a DNF, satisfiability is trivial: any term that does not contain both x and ¬x is a satisfying assignment. From CNF it is NP-complete (the Cook-Levin theorem).
  • Is it a tautology? From CNF it is easy: every clause must contain some variable and its negation. From DNF it is co-NP-complete.
  • Circuit design: DNF corresponds to a two-level AND-OR circuit (programmable logic arrays).
  • Solving at scale: CNF, because resolution and unit propagation work clause by clause.

This duality (what is easy in one form is hard in the other) reflects a deep fact about computation, which the SAT lesson will touch on.

Horn clauses, a useful special case

A Horn clause has at most one positive literal, for example ¬a ∨ ¬b ∨ c, which reads "if a and b then c". Sets of Horn clauses can be tested for satisfiability in linear time by forward chaining, which is why Prolog and Datalog restrict themselves to this fragment. The next demo does forward chaining with "if-then rules".

Python Forward chaining on Horn rules

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Forgetting to remove implications before pushing negations.
  • Applying distribution in the wrong direction (CNF needs ∨ over ∧).
  • Treating canonical DNF as minimal. Minimization (Karnaugh maps, Quine-McCluskey) is a separate problem.
  • Thinking a CNF conversion by Tseitin is equivalent; it only preserves satisfiability.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which describes CNF?

    CNF is a conjunction of clauses, each clause a disjunction of literals.
  2. 2. To build canonical DNF from a truth table you use...

    Each true row gives a minterm; OR them together.
  3. 3. What is the first step when converting to CNF by rewriting?

    Remove implications and biconditionals first, then push negations inward, then distribute.
  4. 4. What is a Horn clause?

    Horn clauses such as ¬a ∨ ¬b ∨ c correspond to if-then rules and allow linear-time satisfiability tests.

Summary

  • DNF is an OR of ANDs; CNF is an AND of ORs; every formula has both.
  • Truth tables give canonical forms: true rows for DNF, false rows for CNF.
  • Symbolic conversion: remove →/↔, push negations in (NNF), distribute.
  • CNF can blow up exponentially; Tseitin encoding keeps it small for satisfiability.
  • Horn clauses give fast forward-chaining inference.

Next: Propositional Proofs with Natural Deduction