Exercise about truth functions in J.R.Shoenfield's "mathematical logic" The first exercise in Joseph R. Shoenfield's "mathematical logic" is:

An n-ary truth function $H$ is definable in terms of the truth functions $H_1,\dots,H_k$ if $H$ has a definition $$H(a_1,\dots,a_n)=\dots$$ where the right-hand side is built up from $H_1,\dots,H_k$,$a_1,\dots,a_n$, and commas and parentheses.

  a) Let $H_{d,n}$ be the truth function defined by setting $$H_{d,n}(a_1,\dots,a_n)=\mathbf{T} \iff a_i=\mathbf{T}$$ for at least one $i$, and let $H_{c,n}$ be the truth function defined by setting $$H_{c,n}(a_1,\dots,a_n)=\mathbf{T}\iff a_i=\mathbf{T}$$ for all $i$.

  Show that every truth function is definable in terms of $H_\neg$ and certain of the $H_{d,n}$ and $H_{c,n}$

Where $H_\neg$ is the standard unary negation ($H_\neg(\mathbf{T})=\mathbf{F}$ and $H_\neg(\mathbf{F})=\mathbf{T}$)
My thougths on this problem:
We can see that this is true for unary truth functions by testing all the 4 cases and for all the binary truth functions by testing all the 16 cases by hand.
For example consider the truth function defined by $$H(\mathbf{T},\mathbf{T})=\mathbf{F}$$
$$H(\mathbf{T},\mathbf{F})=\mathbf{F}$$
$$H(\mathbf{F},\mathbf{T})=\mathbf{F}$$
$$H(\mathbf{F},\mathbf{F})=\mathbf{T}$$
That is, in terms of the functions allowed by the problem $H_\neg(H_{d,2}(\mathbf{A},\mathbf{B}))$, where $\mathbf{A}$ and $\mathbf{B}$ are expressions with a truth value, possibly other truth functions.
Now that we know that this fact holds for binary truth functions we can split every $n$-ary truth function in 2 parts, an unary one and an $(n-1)$-ary one that are combined in the original $n-ary$ truth function in one of the 16 ways possible (and we know that they are all definable in terms of the function allowed, because I checked them by hand).
Now we can reason in the same way on the $(n-1)$-ary function and keep splitting until we reach our base case of binary functions thus proving the fact we were required to prove.

The problem is that I don't know wether my proof is correct and even if it is I think it's rather ugly, involving a lot of cases to be checked by hand, is there an easier way to approach this problem? (It'd be great if you could just give me an hint instead of the full answer)
Thanks
Alessandro
 A: I've read the whole problem in Shoenfield's book, and I think it is quite clear that the author is guiding the readers to the concept of expressively adequate set of connectives (those that can express all truth-functions of the language), splitting the process in several steps. And I am not sure what the author means by "certain of the $H_{d,n}$ and $H_{c,n}$". Perhaps as many of them as we want, or perhaps the "obvious" choice: $H_{d,2}$ and $H_{c,2}$ (which are $H_{\lor}$ and $H_\&$). In fact, it does not matter since any $H_{d,n}$ is definable in terms of $H_{d,2}$ (and the same for $H_{c,n}$):
$H_{d,n}=H_{d,2}(a_1,H_{d,2}(a_2,H_{d,2}(a_3,H_{d,2}(\dots,H_{d,n}(a_{n-1},a_n)\dots))))$
Your proof seems correct to me, but I think your answer is a much stronger result that the one asked in part (a) of the problem. In fact, if in the second step you show that any binary function is definable in terms of $H_\neg$ and $H_{d,2}$ (which I am sure you can do...), you are answering question b) of the problem:

b) Show that every truth function is definable in terms of $H_\neg$ and $H_{\lor}$. [Use (a).]

For part (a), I'd do the following, which is equivalent to writing a formula in disyunctive normal form (one or more disjuncts each of which is a basic conjuntion).
Let $H$ be any $n$-ary truth function. Then either $H$ is always $\mathbf{F}$ or it's $\mathbf{T}$ for at least one valuation of its arguments:


*

*If $H(a_1,\dots,a_n)=\mathbf{F}$ for any valuation of
$a_1,\dots,a_n$, then:
$H(a_1,\dots,a_n)=H_{d,n}(H_{c,2}(a_1,H_\neg(a_1)),H_{c,2}(a_2,H_\neg(a_2)),\dots, H_{c,2}(a_n,H_\neg(a_n)))$ 
(or any other expression wich fullfills the criteria of the problem and has the constant value $\mathbf{F}$).

*Let's say that $H=\mathbf{T}$ for $m$ different n-tuples (valuations). Then $H=H_{d,m}(H_{c,n}(1),\dots,H_{c,n}(m))$ where each $H_{c,n}(i)$ is built in the following way: it is the same as the function $H_{c,n}$ but with the unary negation applied to any argument whose value in the i-tuple (valuation) is $\mathbf{F}$. 
For example, if $H=\mathbf{T}$ for just the two cases: $a_1=\mathbf{F}$, $a_2=\dots=a_n=\mathbf{T}$; and $a_1=\dots=a_{n-1}=\mathbf{T}, a_n=\mathbf{F}$ then: 
$H(a_1,\dots,a_n)=H_{d,2}(H_{c,n}(H_\neg(a_1),a_2,\dots,a_n),H_{c,n}(a_1,a_2,\dots,H_\neg(a_n)))$
It is easy to check that this evaluates to $\mathbf{T}$ just in those two cases, because in fact it has been built to do so. 
So, this shows that any n-ary function $H$ is definable in terms of $H_\neg$, $H_{c,n}$, $H_{c,2}$ and one function $H_{d,m}$. But (given the above remarks about the binary functions), this implies that is definable in terms $H_\neg$, $H_{\lor}$ and $H_{\&}$.
A: Sounds correct to me.  You're essentially proving this by induction on $n$.  And, yes, it's kind of ugly because you have to go through the 16 cases once, but I think there's no "elegant" way around that.
