4

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

user35603
  • 3,002

1 Answers1

4

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.

Ewan Delanoy
  • 61,600