Complete sets of functions A (finite) set $S$ of boolean functions is called functionally complete if every boolean function can be presented as a finite composition of functions from $S$. For example, $\{ \neg,\wedge \}$ is functionally complete. Functionally complete sets are described, in some sense, by Post's functional completeness theorem.
Question: Suppose we have the set of all functions (with a finite number of variables) over a finite field. Is there any results that are similar to Post's theorem for complete sets of boolean functions? Maybe some sufficient conditions? For simple fields?
Thanks in advance.
 A: Post’s result amounts to determining all maximal clones on a two-element set. (In fact, Post completely described the lattice of all clones on a two-element set.) It is known that already on three-element sets, clones have a much more complicated structure than in Post’s case. Nevertheless, maximal clones on finite sets have been described by Rosenberg, which gives a characterization of functionally complete sets of functions. You can find a presentation of Rosenberg’s result here.
A: Let $\ T\ $ be an arbitrary finite $n$-element set. We may label it so that it becomes $\ T=\{0\ldots n\!-\!1\}\ $ (why not). Now let $\ \cdot\ $ and $\ \vee\ $ be short for multiplication $ \mod n\ $ and $\ \max\ $ respectively,   and $\ \prod\ $ and $\ \bigvee\ $ be their finite iterations. Also let $\ E_a : T\rightarrow T\ $ be defined by
$$ E_a(x)\ :=\ 1\quad\Leftrightarrow\quad a=x$$
$$ E_a(x)\ :=\ 0\quad\Leftrightarrow\quad a\ne x$$
for every $\ x\in T$.   Now let $\ f:T^D\rightarrow T\ $ be an arbitrary $D$-argument operation, where $\ D\ $ is a finite set. Then
$$ f\ =\ \bigvee_{\tau\in T^D}\ (\,f(\tau)\ \cdot\ \prod_{d\in D}(E_{\tau(d)}\circ\pi_d)\,)$$
where $\ \pi_d:T^D\rightarrow T\ $ is the cartesian projection for every $\ d\in D$.
Thus we have our first functionally complete set of operations--it consists of $\ n\ $ constants, $\ n\ $ comparisons, and $\ \cdot\ $, and $\ \vee$.   It's a modest start to searching for other complete systems too (or apply your own favorite method :-).
REMARK   Not much is required from $\ \cdot\ $ and $\ \vee$:


*

*$\ x\cdot 0 = 0$

*$\ x\cdot 1 = x$

*$\ x\vee 0 = 0\vee x = x$


for every $\ x\in T\ $ -- that's all.
A: I'll modify my previous answer, then will apply it to derive the Post algebra as presented in @Emil's comment above.
Let $\ T\ $ be an arbitrary finite $n$-element set   ($n\ge 2$).   We may label it so that it becomes $\ T=\{0\ldots n\!-\!1\}$,   and let $\ \Lambda:=n-1$.   Now let $\ \wedge\ $ and $\ \vee\ $ be short for $ \min \ $ and $\ \max\ $ respectively,   and $\ \bigwedge\ $ and $\ \bigvee\ $ be their finite iterations. Also let $\ \lambda_a : T\rightarrow T\ $ be defined by
$$ \lambda_a(x)\ :=\ \Lambda\quad\Leftrightarrow\quad a=x$$
$$ \lambda_a(x)\ :=\ 0\quad\Leftrightarrow\quad a\ne x$$
for every $\ x\in T$.   Consider arbitrary $D$-argument operation $\ f:T^D\rightarrow T\ $,   where $\ D\ $ is a finite set. Then
$$ f\ =\ \bigvee_{\tau\in T^D}\ (\,f(\tau)\ \wedge\ \bigwedge_{d\in D}(\lambda_{\tau(d)}\circ\pi_d)\,)$$
where $\ \pi_d:T^D\rightarrow T\ $ is the cartesian projection for every $\ d\in D$.
Thus we have a (modified) complete set of operations--it consists of $\ n\ $ constants, $\ n\ $ comparisons, and $\ \wedge\ $, and $\ \vee$.
Now let's show that the Post set $\ \{\vee\ \ \neg\ \}\ $ is complete.
Completeness of $\ \{\vee\ \ \neg\ \}$
(The equalities below are theorems, not definitions).
First of all we get constant $\ \Lambda$;   it is the maximum of the consecutive compositions of the negation:
$$\Lambda\ =\ \bigvee_{k=0}^{n-1} \bigcirc^k\neg$$
Of course we identify the constants and the constant operations. Now we get every other constant $\ c\in T$:
$$ c\ = \left(\bigcirc^{c+1} \neg\right)\circ\Lambda$$
for every $\ c\in T$.
Now it's time to obtain the comparisons. Let's start with:
$$ \lambda_0\ \ =\ \ \neg\ \circ\ \bigvee_{k=0}^{n-2} \bigcirc^k\neg$$
Next:
$$ \forall_{a\in T}\quad \lambda_a\ =\ \lambda_0\,\circ\,\bigcirc^{n-a}\,\neg$$
To complete the Post's completeness only $\ \wedge\ $ is left. But first let's define an order negation $\ \sim\,:T\rightarrow T\ $ to the Post's algebraic negation $\ \neg\,$:
$$ \sim\ \ =\ \ \bigvee_{a=0}^{n-1}\ \left(\left(\bigcirc^{n-a}\ \neg\right)\,\circ\,\lambda_a\right) $$
Now the last touch is provided by the De Morgan law:
$$x\,\wedge\,y\ =\ \sim\left(\,\sim\!(x)\ \vee\,\sim\!(y)\,\right)$$
REMARK   One could use exponent $\,\ -\!a\ \,$ instead of $\,\ n-a$.
