This
is bonus material for Philosophy 9.
Mathematicians and logicians alike have been torn between developing systems that are as economical as possible (the fewest possible symbols and rules) and developing systems that are as efficient as possible. As we've seen earlier, we could dispense with what is the most important relationship for most logicians, that of implication (as in P->Q), since every conditional relationship could alternately be expressed as a disjunction (think of how "unless logic is not easy it is fun" is equivalent to "if logic is easy it is fun" or "logic is easy only if it is fun"). Electronics, for instance, makes use gates for AND and OR, but not for IF...THEN. But the economy of doing so in logic does not make up for the efficiency of keeping the additional operator.
In a quick look at the history of symbolic logic we talked about the contribution of Bertrand Russell and Alfred North Whitehead in their book Principia Mathematica. After the First World War, one of Russell's most brilliant students and one of the most important philosophers of the last century, Ludwig Wittgenstein, published Tractatus Logico-Philosophicus and demonstrated the use of the truth table to express the relationships of symbolic logic. Even earlier, though, Henry Maurice Sheffer had shown that all the symbols used by Russell and Whitehead for propositional logic could be replaced with a single symbol (the Sheffer stroke). What he did was take the NAND relationship (what we have with ~(P&Q)) and make it the basis for everything else. He could just as easily have used the NOR relationship (what we have with ~(PvQ)).
To demonstrate this, let's look at all sixteen basic patterns possible with two variables.
This table lists all
the possible truth table combinations for any two elements that involve
just two variables (using P and Q for the models). All WFFs with
the exact same truth table are equivalent.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
What we are going to do now is use the operator | (read "stroke"), which indicates the negation of P&Q. Column 9 above tells us what we have for P|Q.
Since ~(P&Q) negates P&Q, what we can now do is negate the negation to get back to P&Q. Let's look at the truth table for (P|Q)|(P|Q).
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The concept of doubling to express negation then lets us see that P|P is equivalent to ~P.
What is important here
is that with any other effort to reduce the number of signals we must
keep the negation sign (~). Now we do not. That does not
mean the results are especially efficient.
For the bonus quiz
there will be exercises using the Sheffer stroke as a repacement for
all out other operators. For instance, decide
what is the shortest equivalent in our ordinary notation for this
expression: [P|(P|Q)]|Q
P | Q || [P | (P|Q)] | Q
T T T T
F F T
T F T F
T T
F
F T F T
T F
T
F F F T
T T
F
What we find in this
example is that the entire expression has the same truth value as ~Q.