Disjunctive Normal Form

 

A fundamental conjunction is either a literal or a conjunction of two or more literals. For example, P and  are fundamental conjunctions. A disjunctive normal form (DNF) is either a fundamental conjunction or a disjunction of two or more fundamental conjunctions. For example, the following wffs are DNFs:

, , .

Sometimes the trivial cases are hardest to see. For example, try to explain why the following four wffs are DNFs: P, Ø P, P ÚØ P, and ØP Ù Q. The propositions that we constructed for truth functions are DNFs.

It is often the case that a DNF is equivalent to a simpler DNF. For example, the DNF is equivalent to the simpler DNF P by using (23.1).

For another example, consider the following DNF:

.

The first fundamental conjunction is equivalent to , which we see contains the third fundamental conjunction   as a subexpression. Thus the first term of the DNF can be absorbed by (5.2) into the third term, which gives the following simpler equivalent DNF:

.

For any wff W we can always construct an equivalent DNF. If W is a contradiction, then it is equivalent to the single term DNF . If W is not a contradiction, then we can write down its truth table and use the technique that we used for truth functions to construct a DNF. So we can make the following statement:

  Every wff is equivalent to a DNF.                                                                           

Another way to construct a DNF for a wff is to transform it into a DNF by using the equivalences of (5.2). In fact we'll outline a short method that will always do the job:

First, remove all occurrences (if there are any) of the connective ® by using the equivalence

.

Next, move all negations inside to create literals by using De Morgan's equivalences

  and  .

Finally, apply the distributive equivalences to obtain a DNF. Let's look at an example.

EXAMPLE. We'll construct a DNF for the wff .

Suppose W is a wff having n distinct propositional letters. A DNF for W  is called a full disjunctive normal form if each fundamental conjunction has exactly n literals, one for each of the n letters appearing in W. For example, the following wff is a full DNF:

.

The wff  is a DNF but not a full DNF because the letter Q does not occur in the first fundamental conjunction.

The truth table technique to construct a DNF for a truth function automatically builds a full DNF because all of the letters in a wff occur in each fundamental conjunction. So we can state the following result:

  Every wff that is not a contradiction is equivalent to a full DNF.