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 over .
| Step | On | |
|---|---|---|
| 1 | Remove the arrows. Use material implication for ; split into two conditionals first.Material implication ↗ | |
| 2 | Push every negation onto a letter. Apply De Morgan's law to each negated bracket, from the outside in.De Morgan's laws ↗ | |
| 3 | Cancel double negations. Replace each by .Double negation law ↗ | |
| 4 | Distribute or over and. Any inside a bracket that is joined by must come out: each part of the gets its own copy of the other side.Distributive laws ↗ | |
| 5 | Tidy 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: |