Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Convert a Formula to Conjunctive Normal Form

A formula is in conjunctive normal form (CNF) when it is an and of clauses, and each clause is an or of letters and negated letters. Get there by removing arrows, pushing negations onto letters, and distributing ∨\lor over ∧\land.

Recognize the task

The question asks for CNF, a product of sums, clause form, or input for a SAT solver: ¬(P→Q)∨R\neg(P \to Q) \lor R, P→(Q∧R)P \to (Q \land R), (P∧Q)∨(¬P∧R)(P \land Q) \lor (\neg P \land R). Test for the answer: no →\to or ↔\leftrightarrow, every ¬\neg on a single letter, and no ∧\land inside a bracket that is joined by ∨\lor.
Normal forms are explained with the normal forms converter, together with minterms and maxterms.

Two ways to do it

Rewrite with the lawsusual
A∨(B∧C)≡(A∨B)∧(A∨C)A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)
Remove arrows, push negations in, then apply the distributive law of or over and; this gives a short CNF.
Read it off the truth tabletable
one clause per F row: a T letter appears negated, an F letter plain\text{one clause per F row: a T letter appears negated, an F letter plain}
For each row where the formula is F, write the clause that is false only in that row. The result is the full canonical CNF.

Steps

StepOn ¬(P→Q)∨R\neg(P \to Q) \lor R
1Remove the arrows. Use material implication for →\to; split ↔\leftrightarrow into two conditionals first.Material implication ↗¬(¬P∨Q)∨R\neg(\neg P \lor Q) \lor R
2Push every negation onto a letter. Apply De Morgan's law to each negated bracket, from the outside in.De Morgan's laws ↗(¬¬P∧¬Q)∨R(\neg\neg P \land \neg Q) \lor R
3Cancel double negations. Replace each ¬¬A\neg\neg A by AA.Double negation law ↗(P∧¬Q)∨R(P \land \neg Q) \lor R
4Distribute or over and. Any ∧\land inside a bracket that is joined by ∨\lor must come out: each part of the ∧\land gets its own copy of the other side.Distributive laws ↗(P∨R)∧(¬Q∨R)(P \lor R) \land (\neg Q \lor R)
5Tidy the clauses. Drop any clause that contains a letter and its negation, since it is always T (excluded middle), and repeated letters inside a clause.nothing to drop: (P∨R)∧(¬Q∨R)(P \lor R) \land (\neg Q \lor R)

Worked examples

Example 1 · an arrow into an and

1 distribution
P→(Q∧R)≡¬P∨(Q∧R)P \to (Q \land R) \equiv \neg P \lor (Q \land R)
material implication
≡(¬P∨Q)∧(¬P∨R)\equiv (\neg P \lor Q) \land (\neg P \lor R)
distribute ¬P∨\neg P \lor

Example 2 · from the truth table

F rows
P↔QP \leftrightarrow Q: T, F, F, T
F rows are (T,F)(T, F) and (F,T)(F, T)
row (T,F)(T, F) gives ¬P∨Q\neg P \lor Q
negate the T letter
row (F,T)(F, T) gives P∨¬QP \lor \neg Q
negate the T letter
(¬P∨Q)∧(P∨¬Q)(\neg P \lor Q) \land (P \lor \neg Q)
and of the clauses

Example 3 · two terms joined by or

4 clauses
(P∧Q)∨(¬P∧R)(P \land Q) \lor (\neg P \land R)
start
≡(P∨¬P)∧(P∨R)∧(Q∨¬P)∧(Q∨R)\equiv (P \lor \neg P) \land (P \lor R) \land (Q \lor \neg P) \land (Q \lor R)
pair each part with each part
≡(P∨R)∧(¬P∨Q)∧(Q∨R)\equiv (P \lor R) \land (\neg P \lor Q) \land (Q \lor R)
drop the always-true clause
Check that the start and your CNF are equivalent in the equivalence validator.

See it happen

A CNF is a list of conditions that must all hold. Each clause rules out the rows where all of its literals are F; a clause that uses every letter rules out exactly one row of the truth table. Joining the clauses with ∧\land rules out every false row and leaves the true rows. That is why the table method works, and why the law method, which keeps the formula short, ends with the same truth table.

Common mistakes

Distributing the wrong connective

✗ (P∧¬Q)∨R≡(P∧R)∨(¬Q∧R)(P \land \neg Q) \lor R \equiv (P \land R) \lor (\neg Q \land R)
✓ distribute ∨\lor over ∧\land: (P∨R)∧(¬Q∨R)(P \lor R) \land (\neg Q \lor R)

Stopping with a negated bracket

✗ ¬(P∧Q)∨R\neg(P \land Q) \lor R is in CNF
✓ push the negation in first: ¬P∨¬Q∨R\neg P \lor \neg Q \lor R, a single clause

Using the DNF sign rule

✗ the F row P=TP = T, Q=FQ = F of P↔QP \leftrightarrow Q gives the clause P∨¬QP \lor \neg Q
✓ negate the letters that are T: ¬P∨Q\neg P \lor Q

Distributing before removing the arrows

✗ P→(Q∧R)≡(P→Q)∧(P→R)P \to (Q \land R) \equiv (P \to Q) \land (P \to R), now in CNF
✓ arrows are not allowed in CNF; rewrite them: (¬P∨Q)∧(¬P∨R)(\neg P \lor Q) \land (\neg P \lor R)