Completitud funcional

Concepto en lógica matemática

En lógica , un conjunto funcionalmente completo de conectivos lógicos u operadores booleanos es uno que se puede usar para expresar todas las tablas de verdad posibles combinando miembros del conjunto en una expresión booleana . ^{[1] [2]} Un conjunto completo de conectivos bien conocido es { AND , NOT } . Cada uno de los conjuntos singleton { 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) funcionalmente completa también puede denominarse puerta universal (o conjunto universal de puertas).

En un contexto de lógica proposicional , los conjuntos funcionalmente completos de conectivos 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 únicamente o de puertas NOR binarias únicamente .

Introducción

Los textos modernos sobre lógica suelen tomar como primitivo algún subconjunto de los conectivos: conjunción ( ); disyunción ( ); negación ( ); condicional material ( ); y posiblemente el bicondicional ( ). Se pueden definir otros conectivos, 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 como ) se puede expresar como conjunción de dos negaciones: ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$ ${\displaystyle \to }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \downarrow }$

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

De manera similar, la negación de la conjunción, NAND (a veces denotada como ), se puede definir en términos de disyunción y negación. Cada conectivo binario se puede definir en términos de , 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 \uparrow }$ ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

${\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 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, como se puede definir como ${\displaystyle \{\neg ,\land ,\lor \}}$ ${\displaystyle \lor }$

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

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

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

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

Definición formal

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 cada función booleana que toma al menos una variable puede expresarse en términos de las funciones f _i . Dado que cada 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 cada 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 de 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 fuerte porque no es posible escribir una función nularia , es decir, una expresión constante, en términos de F si F en sí no contiene al menos una función nularia. Con esta definición más fuerte, 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 nularias sea funcionalmente completo o, equivalentemente, funcionalmente completo en el sentido fuerte 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]}

Caracterización de la completitud funcional

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

• Los conectivos 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 conectivos cambien su valor de retorno de T a F , por ejemplo . ${\displaystyle \vee ,\wedge ,\top ,\bot }$
• Los conectivos afines , tales que cada variable conectada siempre o nunca afecta el valor de verdad que estos conectivos devuelven, por ejemplo . ${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$
• Los conectivos autoduales , que son iguales a su propio dual de Morgan ; si se invierten los valores de verdad de todas las variables, también lo es el valor de verdad que devuelven estos conectivos, por ejemplo , maj ( p , q , r ) . ${\displaystyle \neg }$
• Los conectivos 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 conectivos 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 de la red de todos los clones (conjuntos de operaciones cerrados bajo composición y que contienen todas las proyecciones) en el conjunto de dos elementos { T , F } , hoy llamado red 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]

Conjuntos de operadores mínimos funcionalmente completos

Cuando un único operador conectivo lógico o booleano es funcionalmente completo por sí mismo, se denomina función de Sheffer ^[9] o, a veces, operador único suficiente . No existen 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 de forma independiente 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 funcionalmente completos mínimos 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 \{\to ,\nleftrightarrow \}}$ ${\displaystyle \{\gets ,\nleftrightarrow \}}$ ${\displaystyle \{\to ,\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 conectivos lógicos binarios. ^[11] Para mantener legibles las listas anteriores, se han omitido los operadores que ignoran una o más entradas. Por ejemplo, un operador que ignora la primera entrada y genera la negación de la segunda puede reemplazarse por una negación unaria.

Ejemplos

• Ejemplos de uso de la NANDcompletitud (↑). Como se ilustra en ^[12]
  • ¬ 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 ^[13]
  • ¬ A ≡ A ↓ A
  • A ∨ B ≡ ¬( A ↓ B ) ≡ ( A ↓ B ) ↓ ( A ↓ B )
  • A ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( A ↓ A ) ↓ ( B ↓ B )

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

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

En otros dominios

Además de los conectivos lógicos (operadores booleanos), la completitud funcional se puede introducir en otros dominios. Por ejemplo, un conjunto de puertas 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 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 y la puerta T son universales, aunque con una definición ligeramente más restrictiva que la de completitud funcional.

Teoría de conjuntos

Existe un isomorfismo entre el álgebra de conjuntos y el álgebra de Boole , es decir, tienen la misma estructura . Entonces, si mapeamos los operadores booleanos en operadores de conjunto, el texto "traducido" anterior es válido también para conjuntos: hay 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 se prohíbe el conjunto universal , los operadores de conjunto se limitan a preservar la falsedad (Ø) y no pueden ser equivalentes al álgebra de Boole funcionalmente completa.

Véase también

• Álgebra de conjuntos  – Identidades y relaciones que involucran conjuntos
• Álgebra de Boole  – 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 y la disyunción lógicas
• Lista de temas de álgebra de Boole
• Lógica NAND  : lógica construida únicamente a partir de puertas NAND
• Lógica NOR  : creación de otras puertas utilizando únicamente puertas NOR
• Computadora con un solo conjunto de instrucciones  : máquina abstracta que utiliza solo una instrucción

Referencias

1. Enderton, Herbert (2001), Una introducción matemática a la lógica (2.ª ed.), Boston, MA: Academic Press , ISBN 978-0-12-238452-3. ("Conjunto completo de conectivos lógicos").
2. Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Esquema de teoría y problemas de lógica de Schaum (2.ª ed.), Nueva York: McGraw–Hill , ISBN 978-0-852-3-3-3 978-0-07-046649-4. ("[L]a completitud funcional de [un] conjunto de operadores lógicos").
3. Smith, Peter (2003), Una introducción a la lógica formal , Cambridge University Press , ISBN 978-0-521-00804-4. (Define "expresivamente adecuado", abreviado como "conjunto adecuado de conectores" en un encabezado de sección).
4. Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. p. 41. ISBN 978-0-415-13342-5.
5. Wesselkamper, TC (1975), "Un único operador suficiente", Notre Dame Journal of Formal Logic , 16 : 86–88, doi : 10.1305/ndjfl/1093891614
6. Massey, GJ (1975), "Sobre una supuesta función de Sheffer", Notre Dame Journal of Formal Logic , 16 (4): 549–550, doi : 10.1305/ndjfl/1093891898
7. Wesselkamper, TC (1975), "Una corrección a mi artículo "Un único operador suficiente", Notre Dame Journal of Formal Logic , 16 (4): 551, doi : 10.1305/ndjfl/1093891899
8. Emil Leon Post (1941). Los sistemas iterativos de dos valores de la lógica matemática. Anales de estudios matemáticos. Vol. 5. Princeton: Princeton University Press. doi :10.1515/9781400882366. ISBN 9781400882366.Véase la página 105 para el teorema, las páginas 53, 59, 69, 70, 131 para una definición de las clases A ₁ , L ₁ , C ₂ , C ₃ , D ₃ y las páginas 35, 43 para la definición de la condición [A:a] y la función α, β, γ.
9. El término se limitaba originalmente a las operaciones binarias , pero desde finales del siglo XX se utiliza de forma más general. Martin, NM (1989), Systems of logic , Cambridge University Press, p. 54, ISBN 978-0-521-36770-7.
10. Scharle, TW (1965), "Axiomatización del cálculo proposicional con funtores de Sheffer", Notre Dame J. Formal Logic , 6 (3): 209–217, doi : 10.1305/ndjfl/1093958259.
11. Wernick, William (1942) "Complete Sets of Logical Functions", Transactions of the American Mathematical Society 51 : 117–32. En su lista en la última página del artículo, Wernick no distingue entre ← y →, o entre y . ${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$
12. "Operaciones de compuerta NAND" en http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
13. "Operaciones de la puerta NOR" en http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html