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

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?

• Mar 8, 2014 at 14:16

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!]