Propositional Logic · step 4 of 13

CNF & DNF normal forms

A literal is a variable or its negation. Disjunctive normal form is an OR of ANDs of literals; conjunctive normal form is an AND of ORs. Every formula is equivalent to one of each, which is what makes normal forms useful: CNF is the input format for resolution and SAT solvers, and DNF can be read straight off the true rows of a truth table.

Practise cnf & dnf normal forms free → All Propositional Logic subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Remove → and ↔Rewrite p → q as ¬p ∨ q and expand ↔ into a conjunction of two implications, then remove those too.
Drive negations down to the literalsApply De Morgan until every ¬ sits directly on a variable, cancelling double negations. The formula is now in negation normal form.
Distribute the right way roundFor CNF distribute ∨ over ∧: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C). For DNF distribute ∧ over ∨. Choosing the wrong direction gives the other normal form.
Tidy the clausesDelete repeated literals, drop any clause containing both x and ¬x (for CNF that clause is a tautology and can be removed), and sort the literals so the answer is readable.

Worked example

Convert (p ∧ q) ∨ ¬r to CNF.

No implications to remove, and negation already sits on a variable.
Distribute ∨ over ∧: ((p ∧ q) ∨ ¬r) ≡ (p ∨ ¬r) ∧ (q ∨ ¬r).
Both clauses are disjunctions of literals, so this is CNF.

Answer. (p ∨ ¬r) ∧ (q ∨ ¬r).

Where marks get dropped

These are the specific errors that cost credit on cnf & dnf normal forms questions — QED's rubric penalises each of them separately.

Distributing in the wrong direction and producing a DNF when CNF was asked for. Check the top-level connective of your answer: CNF is an ∧ of ∨s.
Leaving a bracketed subformula that is not a literal, such as ¬(p ∧ q). Negation normal form must come first.
Assuming the normal form is unique. It is not — (p ∨ q) ∧ (p ∨ ¬q) and p are both CNFs of the same function, so an answer that differs from the model solution may still be correct.

Practise this until it is automatic

Unlimited fresh questions

QED generates new cnf & dnf normal forms problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Propositional Logic mastery is tracked so you know when this is exam-ready.

CNF & DNF normal forms — frequently asked questions

Can I read DNF off a truth table?

Yes, and it is often faster. Take each row where the formula is true, write the conjunction of literals describing that row, and OR them together. This gives the full disjunctive normal form.

Why does CNF matter in computer science?

Because resolution and every practical SAT solver take CNF as input. Converting a specification to CNF is the standard first step in automated verification.

Does conversion blow up in size?

It can. Distributing an n-clause formula may produce exponentially many clauses, which is why real tools use the Tseitin transformation to get an equisatisfiable CNF in linear size instead.

The rest of Propositional Logic

Connectives, truth tables, equivalences and normal forms. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make cnf & dnf normal forms exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →