Constructing Full Normal Forms using Equivalences

 

We can construct full normal forms for wffs without resorting to truth table techniques. Let's start with the full disjunctive normal form. To find a full DNF for a wff, we first convert it to a DNF by the usual actions: eliminate conditionals, move negations inside, and distribute Ù over Ú. For example, the wff  can be converted to a DNF in two steps, as follows:

.

The right side of the equivalence is a DNF. However, it's not a full DNF because the two fundamental conjunctions don't contain all three letters. The trick to add the extra letters can be described as follows:

To add a letter, say R, to a fundamental conjunction С without changing

the value of C, write the following equivalences:

.

Then distribute Ù over Ú to obtain a disjunction of two fundamental conjunctions.

Let's continue with our example. First, we'll add the letter R to the fundamental conjunction . Be sure to justify each step of the following calculation:

Next, we'll add the letter Q to the fundamental conjunction :

.

Lastly, we put the two wffs together to obtain a full DNF for:

.

EXAMPLE. We'll construct a full DNF for the wff P ® Q. Make sure to justify each line of the following calculation:

We can proceed in an entirely analogous manner to find a full CNF for a wff. The trick in this case is to add letters to a fundamental disjunction without changing its truth value. It goes as follows:

 

To add a letter, say R, to a fundamental disjunction D without changing the value of D, write the following equivalences:

.

Then distribute Ú over Ù to obtain a conjunction of two fundamental disjunctions.

For example, let's find a full CNF for the wff . To start off, we put the wff in conjunctive normal form as follows:

.

The right side is not a full CNF because the letter Q does not occur in the fundamental disjunction P. So we'll apply the trick to add the letter Q. Make sure you can justify each step in the following calculation:

The result is a full CNF that is equivalent to the original wff. Let's do another example.

EXAMPLE. We'll construct a full CNF for . After converting the wff to conjunctive normal form, all we need to do is add the letter R to the fundamental disjunction P Ú Q. Here's the transformation: