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.



Complete sets of functions
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](http://dmg.tuwien.ac.at/pinsker/papers/diplomarbeit/diplomarbeit.pdf).


