Proof that any other 2 argument logic function other than NAND or NOR is not functionally complete

Question

Any tips how to prove the title? I know how to show that NAND and NOR are functionally complete, but how do you prove reverse for any other 2 argument logic function?

Answer 1

You could, boringly, examine all sixteen possible truth-functions of two variables in turn, and argue by elimination. But here's how to speed things up considerably, in three steps

1. Argue that the value of $A \circ B$ for $A$ and $B$ both T has to be F if the set of connectives containing just $\circ$ by itself is to be functionally complete (a.k.a. expressively adequate). [Why? Well suppose $A \circ B$ were also T when $A$ and $B$ both are: could you ever express negation using $\circ$ ?]
2. Argue that the value of $A \circ B$ for $A$ and $B$ both F has to be T [Why? A dual argument, flipping F's and T's ...]
3. So that means there are only four possible candidates for the complete truth-table for an expressive adequate $\circ$, namely NAND, NOR and two others. Argue that the other two can't possibly be expressively adequate connectives [Why? Trivial when you note what these other two are!]

And you are done ...