A (finite) set of boolean functions $S=\{f_1,\ldots,f_n\}$ is called functionally complete if every boolean function (of a finite number of variables) can be presented as a finite composition of functions from $S$. For example, $$\{ f_1(x_1)=\neg x_1, f_2(x_1,x_2)=x_1 \wedge x_2 \}\:\hbox{or simply $\{ \neg,\wedge \}$}$$ is functionally complete. Let's say that a functionally complete set $S$ is reducible if there is a function $f \in S$ such that $S \setminus \{f\}$ is also complete. For example, $\{ 1,\wedge, \oplus \}$ is irreducible functionally complete set, while $\{ 0, 1,\wedge, \oplus \}$ is reducible (we can exclude, for example, $0$, since $0=1 \oplus 1$). One can prove that any irreducible functionally complete set of boolean functions contains at most 4 functions.

Question: Can somebody suggest an example of irreducible functionally complete set with 4 functions?

Thanks in advance.

Update1: I can prove the following: if we take functions of 1 and 2 variables then every irreducible functionally complete set contains at most 3 functions. Thus, regarding to my question one should consider boolean functions of 3 and more variables.

Update2: Sorry, there was a typo in examples of irreducible and reducible sets (should be $\{ 1,\wedge, \oplus \}$ and $\{ 0, 1,\wedge, \oplus \}$ instead of $\{ 1,\neg, \oplus \}$ and $\{ 0, 1,\neg, \oplus \}$ respectively, since $\{ 1,\neg, \oplus \}$ is not complete).


This is a simple application of Post’s characterization of functional completeness.

Here is an example in three variables below.

Let ${\cal F}=\lbrace f_1,f_2,f_3,f_4 \rbrace$ with

\begin{align} f_1&=0,\\ f_2&=1,\\ f_3(x_1,x_2,x_3)&=x_1\oplus x_2 \oplus x_3,\\ f_4(x_1,x_2,x_3)&=x_1 \wedge x_2 \wedge x_3 \end{align}

Then :

$\lbrace f_1,f_2,f_3 \rbrace$ generates only affine boolean functions, so this set is not functionally complete.

$\lbrace f_1,f_2,f_4 \rbrace$ generates only monotone boolean functions, so this set is not functionally complete.

$\lbrace f_1,f_3,f_4 \rbrace$ generates only falsity-preserving boolean functions, so this set is not functionally complete.

$\lbrace f_2,f_3,f_4 \rbrace$ generates only truth-preserving boolean functions, so this set is not functionally complete.

On the other hand, $\cal F$ is functionally complete (indeed, $\neg x_1$ can be expressed as $f_3(x_1,f_1,f_2)$ and $x_1 \wedge x_2$ as $f_4(f_2,x_1,x_2)$), so it is an irreducible functionally complete set with four functions.

| cite | improve this answer | |
  • 1
    $\begingroup$ Very nice. Thanks. $\endgroup$ – user35603 Oct 31 '13 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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