Completitud funcional

En lógica, un conjunto funcionalmente completo de conectivas lógicas u operadores booleanos es aquel que puede ser usado para expresar todas las tablas de verdad posibles combinando sus elementos en expresiones booleanas. Un conjunto bastante conocido de conectivas es { AND, NOT }, que consisten en la conjunción y la negación lógica. También existen conjuntos funcionalmente completos formados por un único operador booleano, como puede ser el caso de { NAND } y { NOR }.

En el contexto de la lógica proposicional, los conjuntos de conectivas funcionalmente completos también son llamados suficientes.

Definición formal

Dado el dominio booleano B = {0,1}, un conjunto de F funciones booleanas ƒ_i: B^n_i → B es funcionalmente completo si el clon algebraico en B generado por las funciones básicas ƒi contiene todas las funciones  ƒ: Bⁿ → B, para todos los enteros positivos n ≥ 1. En otras palabras, el conjunto es funcionalmente completo si todas las funciones booleanas que toman al menos una variable pueden ser expresadas en términos de las funciones ƒ_i. Teniendo en cuenta que todas las funciones boolenas formadas por al menos una variable pueden ser expresadas en términos de funciones booleanas binarias, F es funcionalmente completo sí y solo sí cada función booleana binaria del conjunto puede ser expresada en términos de las funciones de F.

Una condición más natural se daría cuando el clon generado por F, consistiese en todas las funciones ƒ: Bⁿ → B para todos los enteros n ≥ 0. De todas maneras, los ejemplos dados arriba no son funcionalmente completos en su forma más fuerte, porque no es posible escribir una función árida en términos de F si la misma F no contiene como mínimo una función árida. Con esta definición más fuerte, el conjunto funcionalmente completo más pequeño tendría dos elementos.

Otra condición natural sería que el clon generado por F, junto con las dos funciones constantes áridas, sea funcionalmente completo o, equivalentemente, funcionalmente completo en el sentido del párrafo anterior. El ejemplo de la función booleana dada por S(x, y, z) = z si x = y y S(x, y, z) = x nos muestra que esta condición es estrictamente más débil que la completitud funcional.

Conjunto mínimo de operadores funcionalmente completos

Cuando una conectiva lógica u operador booleano es funcionalmente completo por sí mismo, es llamado una función de Sheffer.​ No existen operadores unarios con esta propiedad. NAND y NOR, que comparten un principio de dualidad entre ellos, son las únicas dos funciones de Sheffer binarias. Éstas fueron descubiertas, pero no publicadas, por Charles Sanders Peirce en torno a 1880, y redescubiertas y publicadas por Henry M. Sheffer en 1913.​ En términos de la electrónica digital, la puerta binaria NAND y la puerta binaria NOR son las únicas puertas lógicas binarias universales.

Los siguientes conjuntos de conectivas lógicas son los mínimos funcionalmente completos con aridad ≤ 2:​

Un elemento

{↑}, {↓}.

Dos elementos

$\{\vee ,\neg \}$, $\{\wedge ,\neg \}$, $\{\to ,\neg \}$, $\{\gets ,\neg \}$, $\{\to ,\bot \}$, $\{\gets ,\bot \}$, $\{\to ,\nleftrightarrow \}$, $\{\gets ,\nleftrightarrow \}$, $\{\to ,\nrightarrow \}$, $\{\to ,\nleftarrow \}$, $\{\gets ,\nrightarrow \}$, $\{\gets ,\nleftarrow \}$, $\{\nrightarrow ,\neg \}$, $\{\nleftarrow ,\neg \}$, $\{\nrightarrow ,\top \}$, $\{\nleftarrow ,\top \}$, $\{\nrightarrow ,\leftrightarrow \}$, $\{\nleftarrow ,\leftrightarrow \}$.

Tres elementos

$\{\lor ,\leftrightarrow ,\bot \}$, $\{\lor ,\leftrightarrow ,\nleftrightarrow \}$, $\{\lor ,\nleftrightarrow ,\top \}$, $\{\land ,\leftrightarrow ,\bot \}$, $\{\land ,\leftrightarrow ,\nleftrightarrow \}$, $\{\land ,\nleftrightarrow ,\top \}$.

No hay conjuntos mínimos funcionalmente completos de más de tres conectivas lógicas binarias.

Ejemplos

• Ejemplos de uso de la completitud de NAND:​
  • ¬A = A ↑ A
  • A ∧ B = ¬(A ↑ B) = (A ↑ B) ↑ (A ↑ B)
  • A ∨ B = (A ↑ A) ↑ (B ↑ B)
• Ejemplos de uso de la completitud de NOR:​
  • ¬A = A ↓ A
  • A ∨ B = ¬(A ↓ B) = (A ↓ B) ↓ (A ↓ B)
  • A ∧ B = (A ↓ A) ↓ (B ↓ B)

Teoría de conjuntos

Hay un isomorfismo entre el álgebra de conjuntos y el álgebra de Boole; es decir, que tienen la misma estructura. Entonces, si mapeamos operadores booleanos como conjuntos de operadores, el texto anterior puede ser válido también para conjuntos: hay muchos "conjuntos mínimos de operadores" que pueden generar cualquier otra relación de conjuntos. Los "conjuntos mínimos de operadores" más conocidos son {¬, ∩} y {¬, ∪}.

Referencias

• Datos: Q2348801