Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 68 ยท Logic

Normal Forms and SAT

Convert logical formulas to CNF and DNF, understand the SAT problem, write a brute-force solver and learn how DPLL with unit propagation searches smarter.

A logical formula can be written in many equivalent ways. That is convenient for humans, but a program that has to reason about formulas wants one predictable shape. Two such shapes dominate computer science: the disjunctive normal form (an OR of ANDs) and the conjunctive normal form (an AND of ORs). Every formula has an equivalent in each of them.

The conjunctive form is the input language of SAT solvers, programs that decide whether any assignment of true and false makes a formula true. SAT sounds abstract, yet it sits underneath hardware verification, package managers, planning and puzzle solving. In this lesson you will build both normal forms from a truth table, write a brute-force SAT solver, and see the idea that makes real solvers fast.

Literals, clauses and terms

A literal is a variable or its negation: p or ยฌp. Two ways of gluing literals together give the two normal forms.

  • A term is literals joined by AND, for example p โˆง ยฌq โˆง r. A formula that is an OR of terms is in DNF.
  • A clause is literals joined by OR, for example p โˆจ ยฌq โˆจ r. A formula that is an AND of clauses is in CNF.

So DNF reads "this combination, or that combination, or another one", while CNF reads "this restriction, and that restriction, and another one". Rules, constraints and requirements are usually restrictions, which is why CNF is so common in practice.

Two shapes for every formula

DNF An OR of ANDs. Lists the winning cases.
CNF An AND of ORs. Lists the rules to obey.

Both are equivalent to the original formula.

1 / 2

Building both forms from a truth table

The recipe is mechanical, and it proves that normal forms always exist.

For DNF, look at each row where the formula is true. Write a term that is true on exactly that row: use the variable itself where the row has true, and its negation where the row has false. OR all those terms together.

For CNF, look at each row where the formula is false. Write a clause that is false on exactly that row: use the negation of the variable where the row has true, and the variable itself where the row has false. AND all those clauses together. The formula is then false precisely on the rows you excluded.

The next program applies both recipes to the formula (p โˆง q) โˆจ ยฌr and double-checks the results against the original on all eight rows.

Python 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.

The result is correct but long: one term per true row means up to 2โฟ terms for n variables. Real conversions use the laws from Logical Equivalences and Laws to keep the output small.

Converting by algebra

You can also reach a normal form by rewriting, in three steps.

  1. Remove implications and biconditionals: replace p โ†’ q with ยฌp โˆจ q.
  2. Push negations inward with De Morgan's laws until they sit only on variables, and cancel double negations.
  3. Distribute. For CNF, distribute OR over AND: a โˆจ (b โˆง c) becomes (a โˆจ b) โˆง (a โˆจ c). For DNF, distribute AND over OR.

Take (p โˆง q) โˆจ r. It is already an OR of a term and a literal, so it is in DNF. To reach CNF, distribute: (p โˆจ r) โˆง (q โˆจ r).

Distribution can blow the formula up exponentially. Converting (a1 โˆง b1) โˆจ (a2 โˆง b2) โˆจ ... โˆจ (an โˆง bn) to CNF produces 2โฟ clauses. Practical tools avoid this with the Tseitin transformation, which adds fresh helper variables and yields a CNF whose size grows only linearly, at the price of being equisatisfiable (satisfiable exactly when the original is) rather than equivalent.

Principal normal forms: PDNF and PCNF

The forms built from a truth table have a special name. A principal disjunctive normal form (PDNF) is a DNF in which every term contains every variable exactly once (as itself or negated). Such a full term is a minterm: it is true on exactly one row. A principal conjunctive normal form (PCNF) is a CNF in which every clause contains every variable exactly once. Such a full clause is a maxterm: it is false on exactly one row.

Number the rows by reading the variables as a binary number, with true as 1 (for p, q, r, the row T F T is 101 = 5). Then minterm m_i is the term true only on row i, and maxterm M_i is the clause false only on row i. This gives compact notation:

TEXT
f = ฮฃ m(rows where f is true)       (PDNF)
f = ฮ  M(rows where f is false)      (PCNF)

Two facts follow. First, the PDNF and the PCNF are unique (apart from ordering), so two formulas are equivalent exactly when their PDNFs are equal, which is a canonical test for equivalence. Second, the index lists are complements of each other: the minterm indices are the rows missing from the maxterm list, and M_i is the negation of m_i. A tautology has all 2^n minterms; a contradiction has an empty PDNF.

You can also reach the principal forms by algebra. Take any DNF and, for each term missing a variable x, multiply by (x โˆจ ยฌx), which equals true, and distribute. For example, with variables p, q, the term p becomes p โˆง (q โˆจ ยฌq) = (p โˆง q) โˆจ (p โˆง ยฌq). Duplicate terms are then dropped.

Python Minterm and maxterm lists, and algebraic completion

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.

Printing the minterm list is also a handy way to check that your code for a formula has the truth table you intended.

The satisfiability problem

A formula is satisfiable if at least one assignment makes it true, and unsatisfiable otherwise. This is the idea from Truth Tables turned into a question: contradictions are the unsatisfiable formulas, while tautologies are the formulas whose negation is unsatisfiable.

SAT is the problem of deciding satisfiability of a CNF formula. Solvers use a compact input format: each variable is a positive integer, a negated variable is the negative integer, and a clause is a list of such integers. The formula (x1 โˆจ x2) โˆง (ยฌx1 โˆจ x3) โˆง (ยฌx2 โˆจ ยฌx3) becomes [[1, 2], [-1, 3], [-2, -3]].

The simplest solver tries every assignment:

Python A brute-force SAT solver

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.

This checks 2โฟ assignments, so it is fine for 20 variables and hopeless for 200. SAT is the classic NP-complete problem: checking a proposed answer is fast, but nobody knows a method that is guaranteed to find answers quickly in the worst case. Whether one exists is the famous P versus NP question.

The DPLL idea

Real solvers do not try assignments blindly. The DPLL procedure (Davis, Putnam, Logemann, Loveland) searches, but prunes early using two ideas.

  • Unit propagation. If a clause has only one literal left, that literal is forced to be true. Setting it simplifies the other clauses: clauses containing the literal vanish (they are satisfied), and the opposite literal is deleted from the clauses that contain it.
  • Branching. If nothing is forced, pick a variable, try it true, and if that fails try it false.

If simplification ever produces an empty clause (all literals deleted), that branch is a dead end and the solver backtracks. If all clauses disappear, the formula is satisfied.

flowchart TD
    A["Simplify with unit propagation"] --> B{"Empty clause?"}
    B -- yes --> C["Backtrack"]
    B -- no --> D{"No clauses left?"}
    D -- yes --> E["Satisfiable"]
    D -- no --> F["Pick a literal, try it true, then false"]
    F --> A

DPLL alternates forced moves with guesses and backs up when a guess contradicts the clauses.

Python DPLL with unit propagation

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.

The first problem has a solution, the second asks for the impossible (all four combinations of two variables ruled out), and the third encodes the pigeonhole principle: four pigeons cannot each get their own hole among three. That example is unsatisfiable, so DPLL must explore its whole search tree before answering None. Notice that the answer may leave some variables out of the dictionary: they were never needed, so either value works.

SAT in practice

Modern solvers add clause learning (remember why a branch failed), smart variable-ordering heuristics and restarts. They routinely handle formulas with millions of clauses, even though the worst case stays exponential. People use them to:

  • verify that a chip design matches its specification;
  • resolve version constraints in package managers;
  • solve scheduling, timetabling and Sudoku-like puzzles by encoding the rules as clauses;
  • search for test inputs and prove properties of programs.

You will build a complete solver in Project: A Tiny SAT Solver.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which description matches a formula in conjunctive normal form?

    CNF is an AND of clauses, and each clause is an OR of literals. The OR-of-ANDs shape is DNF.
  2. 2. To build a DNF from a truth table, which rows do you use?

    Each true row becomes a term that is true on exactly that row, and the OR of those terms is true exactly on the true rows. The false rows are used for CNF.
  3. 3. In the clause list [[1, -2], [2]], what does the second clause force?

    A clause with a single literal is a unit clause. The only way to make it true is to make that literal true, so x2 is true. Unit propagation then simplifies the first clause to [1].
  4. 4. Why is the brute-force SAT solver impractical for big formulas?

    Each variable doubles the number of assignments to try. Twenty variables give about a million, and two hundred give far more than could ever be enumerated.
  5. 5. What does an empty clause mean during DPLL?

    An empty clause is an OR of nothing, which is false. If every literal of a clause has been falsified, no completion of the current assignment can satisfy the formula.

Summary

  • A literal is a variable or its negation; DNF is an OR of AND-terms and CNF is an AND of OR-clauses, and every formula has an equivalent in both.
  • True rows of a truth table give a DNF; false rows give a CNF. Algebraic conversion removes implications, pushes negations inward and distributes.
  • Distribution can blow up exponentially, which is why tools use the Tseitin transformation to stay linear.
  • SAT asks whether a CNF formula has a satisfying assignment; it is NP-complete, and brute force tries 2โฟ assignments.
  • DPLL combines unit propagation, branching and backtracking; modern solvers add clause learning and handle huge practical instances.

Next: Predicates and Quantifiers, where statements talk about all or some members of a domain.