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.