1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Can you give a link to the statement of Post's theorem? $\endgroup$ Oct 8, 2013 at 15:36
  • $\begingroup$ @BenjaminSteinberg: recent re-proofs, p.466 $\endgroup$
    – user35603
    Oct 8, 2013 at 15:41
  • $\begingroup$ If you ask about all functions on a set, it is irrelevant what field structure you chose to endow the set with. Am I missing something? $\endgroup$ Oct 8, 2013 at 15:45
  • 1
    $\begingroup$ It might be worth noting that all functions on a finite field are polynomial functions. $\endgroup$ Oct 8, 2013 at 15:51
  • 2
    $\begingroup$ The concept of a function $X^n\to X$ or of composition of functions does not in any way refer to field addition or multiplication. Thus, your question has nothing to do with fields (besides constraining the size of $X$ to being a prime power, which turns out not to make any difference), it is just about functions on finite sets. Since any characterization of functionally complete sets of functions must be invariant under permutations of $X$, it will not respect any additional algebraic structure (like field operations) which you may put on the set. $\endgroup$ Oct 8, 2013 at 16:29

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I see, thanks for your answer and comments. And for the link. $\endgroup$
    – user35603
    Oct 8, 2013 at 16:42
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ The best known example of a functionally complete set of operations on $\{0,\dots,n-1\}$ is Post algebra, which has the binary $\max$ operation, and the unary operation $\neg$ defined by $\neg a=a+1\bmod n$. $\endgroup$ Oct 9, 2013 at 12:11
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.