The Sheffer Stroke In our Truth-functional Completeness section, we showed that PL is functionally complete using just {v, ~, &}. In fact, we could also show that it is functionally complete if we just used {~, &} or {~,v}. The reason for this is simple: The wff (A&B) is logically equivalent to ~(~A v ~B), and the wff (A v B) is logically equivalent to ~(~A & ~B). So if we wanted to get by without the "&", we simply would replace all conjunctions with negations of disjunctions of negations. Alternatively, if we wanted to get by without the "v", we would replace disjunctions with negations of conjunctions of negations. There is an operator called the Sheffer Stroke, which is not part of PL, but which easily could be introduced, if we wanted to add it. It is a truth functional operator, like all of our operators, and it is the operator which expresses the English connective "not both A and B". The symbol is the stroke "|". So (A | B) means "Not both A and B", or in PL, ~(A & B). The truth-table for the Sheffer Stroke is:
Sheffer not only introduced his stroke, but he showed that a system of propositional logic which had the Sheffer Stroke as its sole operator, is truth-functionally complete. Based on our discussion of truth-functional completeness, we'll leave it as an extra-credit exercise for you to prove that a system of propositional logic which just contains the Sheffer Stroke is functionally complete.
|
| table of contents | List of Exercises |
|
|