Completitud funcional

En lógica , un conjunto funcionalmente completo de conectores lógicos u operadores booleanos es aquel que puede usarse para expresar todas las tablas de verdad posibles combinando los miembros del conjunto en una expresión booleana . ^{[ 1 ] [ 2 ]} Un conjunto completo de conectores bien conocido es { AND , NOT } . Cada uno de los conjuntos unitarios { NAND } y { NOR } es funcionalmente completo. Sin embargo, el conjunto { AND, OR } es incompleto, debido a su incapacidad para expresar NOT.

Una puerta (o conjunto de puertas) que es funcionalmente completa también puede denominarse puerta universal (o conjunto universal de puertas).

En un contexto de lógica proposicional , los conjuntos de conectores funcionalmente completos también se denominan ( expresivamente ) adecuados . ^{[ 3 ]}

Desde el punto de vista de la electrónica digital , la completitud funcional significa que cada puerta lógica posible puede realizarse como una red de puertas de los tipos prescritos por el conjunto. En particular, todas las puertas lógicas pueden ensamblarse a partir de puertas NAND binarias o a partir de puertas NOR binarias .

Los textos modernos sobre lógica suelen tomar como primitivo algún subconjunto de los conectores: la conjunción (${\displaystyle \land }$); disyunción (${\displaystyle \lor }$); negación (${\displaystyle \neg }$); material condicional (${\displaystyle \to }$); y posiblemente la bicondicional (${\displaystyle \leftrightarrow }$). Se pueden definir otros conectores, si así se desea, definiéndolos en términos de estos primitivos. Por ejemplo, NOR (la negación de la disyunción, a veces denotada${\displaystyle \downarrow }$) puede expresarse como una conjunción de dos negaciones:

${\displaystyle A\downarrow B:=\neg A\land \neg B}$

De manera similar, la negación de la conjunción, NAND (a veces denotada como${\displaystyle \uparrow }$), se puede definir en términos de disyunción y negación. Todo conector binario se puede definir en términos de${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$, lo que significa que el conjunto es funcionalmente completo. Sin embargo, contiene redundancia: este conjunto no es un conjunto funcionalmente completo mínimo , porque el condicional y el bicondicional se pueden definir en términos de los otros conectivos como

${\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

De ello se deduce que el conjunto más pequeño${\displaystyle \{\neg ,\land ,\lor \}}$También es funcionalmente completo. (Su completitud funcional también se demuestra mediante el Teorema de la Forma Normal Disyuntiva ). ^{[ 4 ]} Pero esto todavía no es mínimo, ya que${\displaystyle \lor }$puede definirse como

${\displaystyle A\lor B:=\neg (\neg A\land \neg B).}$

Alternativamente,${\displaystyle \land }$puede definirse en términos de${\displaystyle \lor }$de manera similar, o${\displaystyle \lor }$puede definirse en términos de${\displaystyle \rightarrow }$:

${\displaystyle \ A\vee B:=\neg A\rightarrow B.}$

No es posible realizar más simplificaciones. Por lo tanto, todo conjunto de dos elementos de conectivos que contiene${\displaystyle \neg }$y uno de${\displaystyle \{\land ,\lor ,\rightarrow \}}$es un subconjunto funcionalmente completo mínimo de${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$.

Dado el dominio booleano B = {0, 1} , un conjunto F de funciones booleanas f _i  : B ^{n _i} → B es funcionalmente completo si el clon en B generado por las funciones básicas f _i contiene todas las funciones f  : B ⁿ → B , para todos los enteros estrictamente positivos n ≥ 1. En otras palabras, el conjunto es funcionalmente completo si toda función booleana que toma al menos una variable puede expresarse en términos de las funciones f _i . Dado que toda función booleana de al menos una variable puede expresarse en términos de funciones booleanas binarias, F es funcionalmente completo si y solo si toda función booleana binaria puede expresarse en términos de las funciones en F.

Una condición más natural sería que el clon generado por F consistiera en todas las funciones f  : B ⁿ → B , para todos los enteros n ≥ 0 . Sin embargo, los ejemplos dados anteriormente no son funcionalmente completos en este sentido más estricto porque no es posible escribir una función nula , es decir, una expresión constante, en términos de F si F mismo no contiene al menos una función nula. Con esta definición más estricta, los conjuntos funcionalmente completos más pequeños tendrían 2 elementos.

Otra condición natural sería que el clon generado por F junto con las dos funciones constantes nulas sea funcionalmente completo o, equivalentemente, funcionalmente completo en el sentido estricto 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 en caso contrario muestra que esta condición es estrictamente más débil que la completitud funcional. ^{[ 5 ] [ 6 ] [ 7 ]}

Emil Post demostró que un conjunto de conectores lógicos es funcionalmente completo si y solo si no es un subconjunto de ninguno de los siguientes conjuntos de conectores:

• Los conectores monótonos ; cambiar el valor de verdad de cualquier variable conectada de F a T sin cambiar ninguna de T a F nunca hace que estos conectores cambien su valor de retorno de T a F , por ejemplo${\displaystyle \vee ,\wedge ,\top ,\bot }$.
• Los conectores afines , de modo que cada variable conectada afecta siempre o nunca al valor de verdad que devuelven estos conectores, por ejemplo${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$.
• Los conectores autoduales , que son iguales a su propio dual de De Morgan ; si se invierten los valores de verdad de todas las variables, también se invierte el valor de verdad que devuelven estos conectores, por ejemplo${\displaystyle \neg }$, maj ( p , q , r ) .
• Los conectores que preservan la verdad ; devuelven el valor de verdad T bajo cualquier interpretación que asigne T a todas las variables, por ejemplo${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }$.
• Los conectores que preservan la falsedad ; devuelven el valor de verdad F bajo cualquier interpretación que asigne F a todas las variables, por ejemplo${\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }$.

Post dio una descripción completa del retículo de todos los clones (conjuntos de operaciones cerradas bajo composición y que contienen todas las proyecciones) en el conjunto de dos elementos { T , F } , actualmente llamado retículo de Post , lo que implica el resultado anterior como un corolario simple: los cinco conjuntos de conectivos mencionados son exactamente los clones no triviales máximos. ^{[ 8 ]}

Cuando un único operador lógico conectivo o booleano es funcionalmente completo por sí mismo, se le llama función de Sheffer ^{[ 9 ]} o, a veces, operador suficiente único . No hay operadores unarios con esta propiedad. NAND y NOR , que son duales entre sí , son las únicas dos funciones binarias de Sheffer. Estas fueron descubiertas, pero no publicadas, por Charles Sanders Peirce alrededor de 1880, y redescubiertas independientemente y publicadas por Henry M. Sheffer en 1913. ^{[ 10 ]} En la terminología de la electrónica digital, la puerta NAND binaria (↑) y la puerta NOR binaria (↓) son las únicas puertas lógicas universales binarias .

Los siguientes son los conjuntos mínimos funcionalmente completos de conectivos lógicos con aridad ≤  2: ^{[ 11 ]}

Un elemento

{↑}, {↓}.

Dos elementos

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

Tres elementos

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

No existen conjuntos mínimos funcionalmente completos de más de tres como máximo conectores lógicos binarios. ^{[ 11 ]} Para que las listas anteriores sean legibles, se han omitido los operadores que ignoran una o más entradas. Por ejemplo, un operador que ignora la primera entrada y produce la negación de la segunda puede reemplazarse por una negación unaria.

El artículo de Alfred Tarski "Sobre el término primitivo de la logística" demostró que${\displaystyle \{\leftrightarrow \}}$es funcionalmente completo, ^{[ 12 ]} pero esto solo funciona si se utiliza la cuantificación sobre proposiciones (un dispositivo de la lógica de segundo orden ), por lo que no cuenta para la lista anterior.

• Ejemplos de uso de la NANDcompletitud (↑). Como se ilustra en ^{[ 13 ].}
  • ¬ A ≡ A ↑ A
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( A ↑ A ) ↑ ( B ↑ B )
• Ejemplos de uso de la NORcompletitud (↓). Como se ilustra en ^{[ 14 ].}
  • ¬ A ≡ A ↓ A
  • A ∨ B ≡ ¬( A ↓ B ) ≡ ( A ↓ B ) ↓ ( A ↓ B )
  • A ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( A ↓ A ) ↓ ( B ↓ B )

Tenga en cuenta que un circuito electrónico o una función de software se puede optimizar mediante la reutilización, para reducir el número de compuertas. Por ejemplo, la operación " A ∧ B ", cuando se expresa mediante compuertas ↑, se implementa con la reutilización de " A ↑ B ".

X ≡ ( A ↑ B ); A ∧ B ≡ X ↑ X

Además de los conectores lógicos (operadores booleanos), la completitud funcional puede introducirse en otros dominios. Por ejemplo, un conjunto de compuertas reversibles se denomina funcionalmente completo si puede expresar todos los operadores reversibles.

La compuerta Fredkin de 3 entradas es una compuerta reversible funcionalmente completa por sí misma  : un único operador suficiente. Existen muchas otras compuertas lógicas universales de tres entradas, como la compuerta Toffoli .

En la computación cuántica , la puerta Hadamard , la puerta CNOT y la puerta T son universales, aunque con una definición ligeramente más restrictiva que la de completitud funcional.

Existe un isomorfismo entre el álgebra de conjuntos y el álgebra booleana ; es decir, tienen la misma estructura . Entonces, si mapeamos los operadores booleanos a operadores de conjuntos, el texto anterior, traducido, también es válido para conjuntos: existen muchos "conjuntos mínimos completos de operadores de teoría de conjuntos" que pueden generar cualquier otra relación de conjuntos. Los conjuntos mínimos completos de operadores más populares son {¬, ∩ } y {¬, ∪ } . Si el conjunto universal está prohibido , los operadores de conjuntos se restringen a preservar la falsedad (Ø) y no pueden ser equivalentes a un álgebra booleana funcionalmente completa.

• Álgebra de conjuntos : identidades y relaciones que involucran conjuntos. 
• Álgebra booleana : manipulación algebraica de "verdadero" y "falso". 
• Completitud (lógica) – Característica de algunos sistemas lógicos 
• Dualidad conjunción/disyunción : propiedades que vinculan la conjunción lógica y la disyunción. 
• Lista de temas de álgebra booleana
• Lógica NAND : lógica construida únicamente con puertas NAND. 
• Lógica NOR : Creación de otras compuertas utilizando únicamente compuertas NOR. 
• Computadora con un conjunto de instrucciones : máquina abstracta que utiliza solo una instrucción.