2

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?

Damaon
  • 287

1 Answers1

3

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 ...

Peter Smith
  • 54,743