Show that | and $\downarrow$ are the only binary connectives \$ such that {$} is functionally complete.

Question

I've been reading and coping with van Dalen's Logic and Structure for a a few days. However, I've getting problems to solve his Exercise 6 from Ch 1 Sec 1.3 (p.28). In this exercise, van Daken asks you to show that NAND and NOR are the only binary connectives \$ such that {$} is functionally complete.

My proof strategy goes naturally as: 1. Suppose that \$ is functionally complete; 2. Show that either \$=| or \$=$\downarrow$.

By the assumption, since \$ is binary, it's truth function must be any one of 16 different combinations (including the AND-function, OR-function and so on...). But now I am stuck. It seems I have to show that each of the singletons {$} of the 14 left possible connectives defined be their truth functions (except from NAND and NOR) are functionally incomplete. I can see how to prove some set S of connectives is functionally complete, but not that it isn't. What would be the best approach for that? Am I in the right track?

Answer 1

Any functionally complete set of connectives must have at least one connective $\$$ such that $\top\$\top$ is equal to $\bot$ and one connective such that $\bot\$\bot$ is equal to $\top$. That means you only need to check the $4$ connectives that satisfy this condition, depending on what they return for $\top\$\bot$ and $\bot\$\top$.