Functional Completeness on 3-valued logic I'm asked to prove by induction that a certain set of 4 function is complete on a 3-valued logic (Kleene). However, I'm having difficulty figuring out the induction step. More specifically, I'm not sure how to express multi-variate functions in terms of the bivariate and univariate functions I have.
I'd be grateful for any hints or examples of technique.
(following suggestions from the comments, I provide some more detail)
In detail: The logic is Kleene's $K_3$ with the operations $\neg, \wedge, \vee$ and a fourth univariate operation $*$ defined as $*T = F, *N = T, *F = N$. The question asks to prove expressional completeness: any function $f:\{T, F, N\}^n \to \{T, F, N\}$ can be expressed as a composition of the above four functions.
 A: I'll assume that you don't mean "a composition" literally and that any function that composes any number of those operations is allowed.
To solve this by induction, note that if you treat, say, the first argument separately, then for each possible value of the first argument you can treat the result as a function of the remaining arguments. In two-valued logic, this is already enough to solve the problem, since you can use it to write
$$f(a_1,\dotsc,a_n)=(a_1\land f_T(a_2,\dotsc,a_n))\lor((\neg a_1)\land f_F(a_2,\dotsc,a_n))\;.$$
In three-valued logic, it's not quite as simple, since you need to prevent the three terms you get from changing each other's results. Since $\land$ and $\lor$ still have the property that $\land$ passes $F$ through regardless of the other argument whereas $T$ lets the other argument pass through, and vice versa for $\lor$, you can analogously write
$$f(a_1,\dotsc,a_n)=(\overline{a_1}\land f_T(a_2,\dotsc,a_n))\lor(\overline{*a_1}\land f_N(a_2,\dotsc,a_n))\lor(\overline{*{*}a_1}\land f_F(a_2,\dotsc,a_n))$$
if you can find a unary operation $\overline x$ that's $T$ for $x=T$ and $F$ otherwise. To make that easier, note that $*$ and $\neg$ together generate the group of all permutations of $\{T,N,F\}$, so all you need to find is some unary operation that maps two values to the same value and the third to another, and then you can get the required operation $\overline x$ by applying permutations to the arguments and/or the output.
I'll leave it at that since you asked for hints; feel free to ask again if you have trouble constructing such a unary operation.
