Conjuntos funcionalmente completos de funciones booleanas

Question

Un conjunto (finito) de funciones booleanas $S=\{f_1,\ldots,f_n\}$ se llama funcionalmente completo si toda función booleana (de un número finito de variables) puede presentarse como una composición finita de funciones de $S$ . Por ejemplo, $$\{ f_1(x_1)=\neg x_1, f_2(x_1,x_2)=x_1 \wedge x_2 \}\:\hbox{or simply $\{ \neg , \wedge \}$}$$ es funcionalmente completo. Digamos que un conjunto funcionalmente completo $S$ es reducible si existe una función $f \in S$ tal que $S \setminus \{f\}$ también está completo. Por ejemplo, $\{ 1,\wedge, \oplus \}$ es un conjunto funcionalmente completo irreducible, mientras que $\{ 0, 1,\wedge, \oplus \}$ es reducible (podemos excluir, por ejemplo, $0$ ya que $0=1 \oplus 1$ ). Se puede demostrar que cualquier conjunto funcionalmente completo irreducible de funciones booleanas contiene a lo sumo 4 funciones.

Pregunta: ¿Puede alguien sugerir un ejemplo de conjunto funcionalmente completo irreducible con 4 funciones?

Gracias de antemano.

Actualización1: Puedo demostrar lo siguiente: si tomamos funciones de 1 y 2 variables entonces todo conjunto funcionalmente completo irreducible contiene a lo sumo 3 funciones. Por lo tanto, con respecto a mi pregunta uno debe considerar las funciones booleanas de 3 y más variables.

Actualización2: Perdón, había una errata en los ejemplos de conjuntos irreducibles y reducibles (debería ser $\{ 1,\wedge, \oplus \}$ y $\{ 0, 1,\wedge, \oplus \}$ en lugar de $\{ 1,\neg, \oplus \}$ y $\{ 0, 1,\neg, \oplus \}$ respectivamente, ya que $\{ 1,\neg, \oplus \}$ no está completo).

Answer 1

Se trata de una simple aplicación de la regla de Post caracterización de la integridad funcional .

A continuación, un ejemplo en tres variables.

Dejemos que ${\cal F}=\lbrace f_1,f_2,f_3,f_4 \rbrace$ con

\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}

Entonces:

$\lbrace f_1,f_2,f_3 \rbrace$ genera sólo funciones booleanas afines, por lo que este conjunto no es funcionalmente completo.

$\lbrace f_1,f_2,f_4 \rbrace$ genera sólo funciones booleanas monótonas, por lo que este conjunto no es funcionalmente completo.

$\lbrace f_1,f_3,f_4 \rbrace$ genera sólo funciones booleanas que preservan la falsedad, por lo que este conjunto no es funcionalmente completo.

$\lbrace f_2,f_3,f_4 \rbrace$ genera sólo funciones booleanas que preservan la verdad, por lo que este conjunto no es funcionalmente completo.

Por otro lado, $\cal F$ es funcionalmente completa (de hecho, $\neg x_1$ puede ser expresado como $f_3(x_1,f_1,f_2)$ y $x_1 \wedge x_2$ como $f_4(f_2,x_1,x_2)$ ), por lo que es un conjunto funcionalmente completo irreducible con cuatro funciones.