Disjunctive Normal Form (DNF) Converter online

What is disjunctive normal form?

Disjunctive normal form (DNF) is a standard way of writing a propositional logic formula. A formula is in DNF when it is a disjunction of terms (also called implicants), and each term is a conjunction of literals. A literal is a variable (P) or its negation (¬P).

In other words, DNF is basically one big "OR" (∨) of several blocks, and inside each block there are only "AND" (∧) and negations attached to the letters. For example, (P ∧ ¬Q) ∨ (R ∧ Q ∧ ¬S) is in disjunctive normal form. It is exactly the "upside-down" structure of CNF.

How to convert a formula to DNF in 5 steps

Every propositional formula has an equivalent in disjunctive normal form. The standard method has four steps, plus an optional fifth one for simplifying. The first three are exactly the same as for CNF; the difference is in step 4. The converter runs all of them, but it simplifies as it goes, inside step 4 (step 5 below explains why).

Step 1 · Remove every connective other than ∧ and ∨

We replace the connectives of the original formula with disjunctions (∨) and conjunctions (∧). For DNF we pick the equivalences that already leave disjunctions on the outside whenever possible:

Step 2 · Push negations down to the atoms (De Morgan's laws)

If after the previous step there is still a negation (¬) in front of a parenthesis, we "push it inside" using De Morgan's laws, until every negation affects only a single loose variable:

Step 3 · Remove double negations

Whenever a double negation appears we simplify it with ¬¬A ≡ A. When steps 2 and 3 are done, the formula only has ∧, ∨ and negations attached to the variables; that intermediate form is called negation normal form (NNF), and it is the starting point of the last step.

Step 4 · Apply the distributive property (∧ over ∨)

Here is the key difference with CNF. Now we distribute conjunction over disjunction as many times as needed, until the disjunctions are on the outside and the conjunctions on the inside:

Step 5 (optional) · Simplify, at the end or as you go

Strictly speaking this step is optional: once step 4 is done the formula is already in DNF, and simplifying only makes it shorter without changing what it means. It is still well worth doing, since the result is much cleaner and most courses expect it. You can simplify once at the end, on the finished DNF, or at every iteration, before distributing and after each distribution. Both give an equivalent DNF, but the second saves a lot of work: as soon as something like q ∧ ¬q appears you replace it with 0, instead of copying it through every distribution that follows. The converter simplifies at every iteration, so its output has no separate step 5: each simplification shows up as another line of step 4, labelled with the law it uses. If anything is still left to remove at the end, a "Final cleanup" block appears.

The laws involved are complement (A ∧ ¬A ≡ 0, A ∨ ¬A ≡ 1), domination (A ∧ 0 ≡ 0, A ∨ 1 ≡ 1), identity (A ∨ 0 ≡ A, A ∧ 1 ≡ A), idempotence (A ∧ A ≡ A) and absorption (A ∨ (A ∧ B) ≡ A). If you only simplify at the end, on the finished DNF, they boil down to these cases:

Notice the contrast with CNF: in CNF a clause with q and ¬q is a tautology (always true) and is removed; in DNF a term with q and ¬q is a contradiction (always false) and is also removed, but for the opposite reason.

For example, the formula:

(¬q ∧ q ∧ ¬r ∧ s) ∨ (q ∧ s ∧ ¬r) ∨ (s ∧ ¬r ∧ q) ∨ (s ∧ q)

simplifies by removing the first term (it is a contradiction because it contains q and ¬q) and one of the two identical terms, leaving simply:

(q ∧ s ∧ ¬r) ∨ (s ∧ q)

Worked example, step by step

Related calculators

Frequently asked questions