Complete Sets of Connectives

 

The four connectives in the set  are used to form the wffs of the propositional calculus. Are there other sets of connectives that will do the same job? The answer is yes. A set of connectives is called complete if every wff of the propositional calculus is equivalent to a wff using connectives from the set. We've already seen that every wff has a disjunctive normal form, which uses only the connectives Ø, Ù, and Ú. Therefore {Ø, Ù, Ú} is a complete set of connectives for the propositional calculus. Recall that we don't need implication because we have the equivalence

.

For a second example, consider the two connectives Ø and Ú. To show that these connectives generate the propositional calculus, we need only show that statements of the form A Ù B can be written in terms of Ø and Ú. This can be seen by the equivalence

.

Therefore {Ø, Ú} is a complete set of connectives for the propositional calculus because we know that { Ø, Ù, Ú } is a complete set. Other complete sets are { Ø, Ù } and { Ø, ® }. We'll leave these as exercises.

Are there any single connectives that are complete? The answer is yes, but we won't find one among the four basic connectives. There is a connective called the NAND operator, which is short for the "Negation of AND." We'll write NAND in functional form NAND(P, Q), since there is no well-established symbol for it. Table 5.4 is the truth table for NAND.

Table 5.4

P

Q

NAND(P, Q)

0

0

1

1

0

1

0

1

1

1

1

0

 

To see that NAND is complete, we have to show that the other connectives can be defined in terms of it. For example, we can write negation in terms of NAND as follows:

Ø P º NAND(P, P).

We'll leave it as an exercise to show that the other connectives can be written in terms of NAND.

Another single connective that is complete for the propositional calculus is the NOR operator. NOR is short for the "Negation of OR." Table 5.5 is its truth table.

 

Table 5.5

P

Q

NOR(P, Q)

0

0

1

1

0

1

0

1

1

0

0

0

 

We'll leave it as an exercise to show that NOR is a complete connective for the propositional calculus. NAND and NOR are important because they represent the behavior of two important building blocks for logic circuits.