Must every clause contain several literals?

No. A unit clause contains one literal and is valid CNF.

Does CNF solve the problem?

No. It is a representation. A solver still has to determine whether the clauses can be satisfied, and difficult instances may require substantial work.

Is it the same as disjunctive normal form?

No. DNF has an OR of AND groups. CNF has an AND of OR groups; exchanging the arrangement without valid transformations changes meaning.

AI Glossary / Data engineering and architecture / Intermediate

Conjunctive normal form

Definition

Conjunctive normal form, or CNF, is a way of writing a logical formula as an AND of clauses, where each clause is an OR of literals. A literal is a proposition or its negation, such as Approved or NOT Approved.

What it means

CNF arranges logical requirements into a regular structure. Every clause must be satisfied, but within a clause at least one literal must be true. For example, (A OR B) AND (NOT A OR C) contains two clauses.

The form is useful in automated reasoning, especially Boolean satisfiability solving, where a system asks whether some assignment of true and false values can satisfy all requirements. It does not make the underlying problem automatically easy or prove that the requirements accurately describe the business.

This entry concerns propositional logic. CNF also appears in treatments of first-order logic with additional conversion steps. It is unrelated to Chomsky normal form for grammars, despite sharing the same abbreviation, and to normal forms used in relational database design.

How it works

First define each proposition precisely. Rewrite implications where needed: A implies B becomes NOT A OR B. Move negations inward using logical equivalences, so negation applies to individual propositions. Distribute OR over AND when constructing an equivalent CNF directly.

For example, A OR (B AND C) becomes (A OR B) AND (A OR C). These formulas agree for every truth assignment to A, B and C. A single literal can form a one-literal clause, so A AND B is already CNF.

Direct expansion can make some formulas exponentially larger. Practical SAT encodings often introduce auxiliary variables, as in a Tseitin transformation, to keep the representation compact while preserving satisfiability. That is a different guarantee from casually claiming an identical formula over exactly the same variables. The encoding must be interpreted with its new variables and constraints.

Three practical examples

1. Product configuration: a configurator requires at least one power option and forbids an incompatible pair of components. Clauses make these requirements available to a solver.

2. Deployment planning: a release checker represents dependencies between enabled features, approved services and required resources. It searches for a configuration satisfying the encoded rules.

3. AI-assisted requirements review: an assistant translates a small policy draft into candidate clauses. A domain reviewer checks each translation before a reasoning tool searches for conflicts or permitted combinations.

Think of it this way

Think of an application form with several required sections. Each section offers alternatives, and at least one acceptable choice must be made in every section. That resembles AND between clauses and OR within a clause. The analogy does not capture negated literals or relationships between repeated variables; those require the actual logical formula.

Worked example

A fictional publishing workflow uses three propositions: P means publish, R means reviewed, and A means archived. Its requirements are: publishing requires review; publishing and archiving cannot both happen; and the item must be published or archived.

The CNF is (NOT P OR R) AND (NOT P OR NOT A) AND (P OR A).

Try P = true, R = true, A = false. The first clause is true because R is true, the second because NOT A is true, and the third because P is true. The assignment satisfies all requirements.

Now try P = true, R = false, A = false. The first clause is false, so the whole formula fails even though the other two clauses pass. Try P = false, R = false, A = true: all three pass. The rules permit archiving without review. If stakeholders intended review before either action, the model needs an additional requirement; a solver cannot supply that missing intent.

Illustrative case study

Illustrative fictional case: Brookside Devices asks an AI assistant to encode accessory compatibility. The wording says a starter kit needs a battery or mains adaptor. The assistant interprets “or” as exclusive and forbids buying both.

During review, a salesperson explains that customers may choose both for backup power. The team replaces the incorrect restriction with an inclusive-OR clause and retains a separate incompatibility rule for a different component pair.

The solver then checks the revised requirements. The fictional lesson is that a correctly executed reasoning procedure can still answer the wrong question when natural-language requirements are translated incorrectly. CNF makes the translation inspectable; it does not remove the need for review.

Common misconceptions and mistakes

Do not assume OR means exactly one. Inclusive OR permits both literals to be true. To require exactly one of A and B, use (A OR B) AND (NOT A OR NOT B).

Do not confuse satisfiable with always true: one satisfying assignment establishes possibility, not universal validity. Do not assume CNF is unique or necessarily minimal. Avoid treating a timeout as proof of inconsistency. Also keep SQL's treatment of null and unknown separate from this entry's ordinary two-valued propositional setting.

Business use

Use CNF when a requirement must be passed to a suitable reasoning tool or when a small set of Boolean constraints needs a clear review format. Keep a mapping from each proposition and clause back to the original requirement.

For business use, review both satisfying and deliberately forbidden scenarios. If the tool reports inconsistency, inspect the implicated requirements rather than automatically deleting clauses. For AI-generated encodings, retain the original wording, the proposed interpretation and the human-approved correction so later changes do not revive an earlier misunderstanding.

Check your understanding

Is (A OR NOT B) AND C in CNF?

Answer: Yes. It contains the two-literal clause A OR NOT B and the unit clause C. Both clauses must be true for the whole formula to be true.

Related terms

Literal
Clause
Satisfiability
Constraint satisfaction
Automated reasoning
Boolean logic
SAT solver
disjunctive normal form
Tseitin transformation

Learn next

Practice evaluating small clauses with truth tables. Then convert one implication and one inclusive-or requirement into CNF. Study satisfiability and auxiliary-variable encodings next, paying attention to the difference between logical equivalence and preserved satisfiability.

Sources

Curtis Bright, University of Waterloo, satisfiability solving and CNF: https://cs.uwaterloo.ca/~cbright/cdm/08-satisfiability-solving.html

Marijn Heule, Carnegie Mellon University, representations for automated reasoning, including Tseitin encoding: https://www.cs.cmu.edu/~mheule/15816-f24/slides/representations.pdf

Stanford University, propositional logic and CNF conversion: https://web.stanford.edu/class/archive/cs/cs221/cs221.1196/lectures/logic2.pdf

Publishing and product scenarios are original teaching examples using ordinary propositional logic.

Previous: Conjunction Next: Connected-component labeling