Conjunctive normal form (CNF): meaning and examples
Conjunctive normal form (CNF) is an AND of clauses, each clause an OR of literals. It is the input format of SAT solvers, and every formula has an equivalent CNF.
A formula is in conjunctive normal form when it is a conjunction of disjunctions of literals: (A OR B) AND (NOT A OR NOT B) is one, with two clauses. CNF is the logician's name for product of sums. The conversion mirrors the one for DNF: rewrite derived operators, push negations onto variables with De Morgan, then distribute OR over AND. The canonical CNF, built from maxterms, is unique; shorter CNFs are not.
The artefact on this page converts A XOR B. The converter's CNF is (A OR B) AND (NOT A OR NOT B), 2 clauses and 4 literals, reached with one application of XOR elimination: the first clause says at least one is true, the second says not both. The DNF of the same formula is (A AND NOT B) OR (NOT A AND B), also 2 terms and 4 literals. The 4-row table reads false, true, true, false, and the satisfiable check holds with the witness A = FALSE, B = TRUE.
CNF matters because a SAT solver consumes clauses: once a problem is in CNF, satisfiability can be decided by unit propagation and resolution, and the engine itself turns to a solver beyond its exhaustive limit. CNF is also the natural shape of a list of constraints, where each clause is a rule that must hold. The term is confused with DNF, its dual, and “normal form” is sometimes taken to mean simplified, which it does not.
Example
f := A XOR B · output
Exact checks
Truth table (4 rows)
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | TRUE |
| 2 | TRUE | FALSE | TRUE |
| 3 | TRUE | TRUE | FALSE |
Plain-language reading
Beginnerf is true exactly when exactly one of A and B is true (not both).
In every other case, f is false.
About the operators:
- XOR (exclusive or) is true when exactly one of its two parts is true.
Intermediatef is true exactly when exactly one of A and B is true (not both).
In every other case, f is false.
Advancedf is true exactly when exactly one of A and B is true (not both) [exclusive disjunction ⊕].
In every other case, f is false.
Formal notation: A ⊕ B
Normal forms
Conjunctive normal form (CNF)
(A OR B) AND (NOT A OR NOT B)2 clauses, 4 literals · complete · XOR elimination ×1
Disjunctive normal form (DNF)
(A AND NOT B) OR (NOT A AND B)2 terms, 4 literals · complete · XOR elimination ×1
The common slip
Expecting CNF to be short. Converting a DNF with k terms of two literals each can produce 2 to the power k clauses; the converter stops at 4,096 terms and 20,000 literals and reports the limit rather than an incomplete form. The canonical method or the prime-implicant fallback is the alternative.
Questions
Is a formula in CNF automatically satisfiable?
No. (A) AND (NOT A) is in CNF and is a contradiction. CNF is a shape, not a verdict; deciding satisfiability of a CNF is exactly the SAT problem.
Related
Practice
See also
- Disjunctive normal form (DNF): meaning and examples
- Clause in logic: meaning and examples
- Product of sums (POS): meaning and examples
- SAT solver: meaning and examples
- CNF and DNF converter: conjunctive and disjunctive normal forms, minterms and maxterms
- XOR elimination: A XOR B = (A AND NOT B) OR (NOT A AND B)
Glossary
Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build . Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.