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.