# Proving that $\{NAND\}$ and $\{NOR\}$ each is the only minimal functionally complete set of logical connectives with 1 element

This question is from Shoenfield's Mathematical Logic, chapter 1:

Show that if $$H$$ is a binary truth function such that every truth function is definable in terms of $$H$$, then $$H$$ is NAND or NOR.

The wording of the question is slightly modified; also, the question on the previous paragraph is slightly different wording from the question of the title but I think the meaning is the same (please correct me if I am wrong, and if this is the case please answer the question on the body rather than the title). Here, I use the definition:

an $$n$$-nary truth function $$H$$ is said to be definable in terms of the truth function $$H_1,...,H_k$$ if $$H$$ has a definition $$H(a_1,...,a_n) = K$$ where $$K$$ is built up from $$H_1,...,H_k, a_1,...,a_n$$ and commas and parenthesis.

Here is my attempt (following the book's suggestion): I first proved that if $$H$$ is singulary then every truth function definable in terms of $$H$$ is singulary. The book says in hint that I should prove that $$H(T,T) =F$$ and $$H(F,F) = T$$ and use the fact I first proved. Assuming that $$H(T,T) =F$$ and $$H(F,F) = T$$, I could show that $$H$$ had to be NAND or NOR. However, I am having hard time proving $$H(T,T) =F$$ and $$H(F,F) = T$$. If $$H_\neg(a) = H(a,a)$$ I would be done, but I do not know how. I tried looking at $$H_\lor$$ and $$H_{\iff}$$ but with no avail.

I realize that we can use Post's theorem on minimal funtionally complete sets, but as the chapter from which this problem arises does not mention it I wish to prove this following the book's hint.

Suppose $$H(T,T)=T$$. Then no function arising from compositions of $$H$$ can return $$F$$ if all inputs are $$T$$, so $$H$$ is not functionally complete. Similarly, $$H(F,F)=F$$ implies functional incompleteness, so $$H(T,T)=F$$ and $$H(F,F)=T$$.
• The question asks to show that only two functions are complete. From your answers it seems 2 other functions are also complete. i.e. $H(T,F) = T$ and $H(F, T) = F$ is also complete Feb 24, 2019 at 15:39
• @dEmigOd OP only wanted to show $H(F,F)=T$ and $H(T,T)=F$, and I did that. Feb 24, 2019 at 15:40
• @dEmigOd Also, $T$ or $F$ cannot be used as a literal value by themselves; only $H$ is allowed. Feb 24, 2019 at 15:42
• @dEmigOd You can't use AND! Only $H$ (which may be AND). Feb 24, 2019 at 15:44