I was practising some discrete mathematics, and I came over this question:
Q: Show that Sheffer's functor and Peirce's functor are the only 2-argument logical connectives that can be used to define negation, disjunction, conjunction.
Here is what I have tried: I know the definitions
p⟹q
In terms of those two functors, as well as
~p
And
p∨q,p∧q
For example, note that
~(p∧q)=⟺~p∨~q
And hence
p∧q=~(p|q)
But I don't know how to prove. Any help will be appreciated!!
HINT
First you need to consider all binary connectors: How many are there? And why?
Then you need to rule out any of those that are neither the Sheffer Stroke or the Peirce arrow. To do that: think of some interesting property that some of the operators have when looking at their truth table, and see if you can prove that that property remains no matter how many times you apply that operation. For example, for some operators (like the $\leftrightarrow$) you find that the truth-table gives an even number of True's ... is that something that generalizes? That is, does something like $P \leftrightarrow (Q \leftrightarrow Q)$ still have an even number of T's? Could you prove this by induction for any such construction?
For other operators, you may find some other property. An easy one is the connective that always returns True no matter what the input: do you see why any expression built up from this operator alone cannot define something like Negation?
Finally, having shown that all connectives but the Sheffer Stroke and the Peirce Arrow cannot be used to define all of Conjunction, Disjunction, and Negation, you should probably show that the Stroke and the Arrow can be used to define them.