Completitud funcional

Concepto en lógica matemática

En lógica , un conjunto funcionalmente completo de conectivos lógicos u operadores booleanos es aquel que se puede utilizar 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 {Y, O } está incompleto debido a su incapacidad para expresar NO.

Una puerta (o un conjunto de puertas) que es funcionalmente completa también puede denominarse puerta universal (o un 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 integridad funcional significa que cada puerta lógica posible puede realizarse como una red de puertas del tipo prescrito por el conjunto. En particular, todas las puertas lógicas se pueden ensamblar solo a partir de puertas binarias NAND o solo de puertas binarias NOR .

Introducción

Los textos modernos sobre lógica suelen tomar como primitivo algún subconjunto de conectivos: conjunción ( ); disyunción ( ); negación ( ); condicional material ( ); y posiblemente el bicondicional ( ). Se pueden definir más 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 denominada ) se puede expresar como una 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 denominada ), se puede definir en términos de disyunción y negación. Cada conectivo binario se puede definir en términos de , por lo que este conjunto es funcionalmente completo. ${\displaystyle \uparrow }$ ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

Sin embargo, contiene redundancia: este conjunto no es un conjunto mínimo funcionalmente completo, porque el condicional y el bicondicional pueden definirse 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 también está funcionalmente completo. 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 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 son posibles más simplificaciones. Por lo tanto, cada conjunto de conectivos de dos elementos que contienen y uno de es un subconjunto mínimo funcionalmente completo de . ${\displaystyle \neg }$ ${\displaystyle \{\land ,\lor ,\rightarrow \}}$ ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

Definicion 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 números enteros estrictamente positivos norte ≥ 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 fi . Dado que cada función booleana de al menos una variable se puede expresar en términos de funciones booleanas binarias, F es funcionalmente completa si y sólo si cada función booleana binaria se puede expresar en términos de las funciones en F.

Una condición más natural sería que el clon generado por F conste de todas las funciones f  : B ⁿ → B , para todos los números 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 en sí 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 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 muestra que esta condición es estrictamente más débil que la integridad funcional. ^{[4] [5] [6]}

Caracterización de la integridad 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 , de modo que cada variable conectada siempre o nunca afecta el valor de verdad que devuelven estos conectivos, por ejemplo . ${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$
• Los conectivos autoduales , que son iguales a su propio dual de Morgan ; Si los valores de verdad de todas las variables se invierten, también lo será 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 cerradas bajo composición y que contienen todas las proyecciones) en el conjunto de dos elementos { T , F } , hoy llamado red de Post , que implica el resultado anterior como un corolario simple: los cinco conjuntos de conectivos mencionados son exactamente los clones máximos.

Conjuntos mínimos de operadores funcionalmente completos

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

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

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. ^[9] 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 lo ilustra, ^[10]
  • ¬ A ≡ A ↑ A
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ ( A ↑ A ) ↑ ( B ↑ B )
• Ejemplos de uso de la NORcompletitud (↓). Como lo ilustra, ^[11]
  • ¬ UN ≡ UN ↓ UN
  • 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 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 compuertas reversibles se llama funcionalmente completo si puede expresar cada operador reversible.

La puerta Fredkin de 3 entradas es una puerta reversible funcionalmente completa por sí sola: un único operador suficiente. Hay muchas otras puertas lógicas universales de tres entradas, como la puerta de Toffoli .

En computación cuántica , la puerta de 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 asignamos operadores booleanos a operadores de conjuntos, el texto "traducido" anterior también es válido para conjuntos: hay muchos "conjuntos completos mínimos de operadores de teoría de conjuntos" que pueden generar cualquier otra relación de conjuntos. Los "conjuntos mínimos de operadores completos" más populares son {¬, ∩} y {¬, ∪} . Si el conjunto universal está prohibido , los operadores de conjuntos están restringidos a preservar la falsedad (Ø) y no pueden ser equivalentes al álgebra booleana funcionalmente completa.

Ver también

• Álgebra de conjuntos  : identidades y relaciones que involucran conjuntos
• Álgebra booleana  : manipulación algebraica de "verdadero" y "falso"
• Integridad (lógica)  : característica de algunos sistemas lógicos.
• Lista de temas de álgebra booleana
• Lógica NAND  : lógica construida únicamente a partir de puertas NAND
• Lógica NOR  : creación de otras puertas utilizando solo puertas NOR
• Computadora con un conjunto de instrucciones  : máquina abstracta que usa 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. No, 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-07-046649-4. ("Completitud [f]uncional de [un] conjunto de operadores lógicos").
3. Smith, Peter (2003), Introducción a la lógica formal , Cambridge University Press , ISBN 978-0-521-00804-4. (Define "expresivamente adecuado", abreviado como "conjunto adecuado de conectivos" en el título de una sección).
4. Wesselkamper, TC (1975), "Un único operador suficiente", Notre Dame Journal of Formal Logic , 16 : 86–88, doi : 10.1305/ndjfl/1093891614
5. 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
6. Wesselkamper, TC (1975), "Una corrección a mi artículo" A. Único operador suficiente", Notre Dame Journal of Formal Logic , 16 (4): 551, doi : 10.1305/ndjfl/1093891899
7. El término se restringió originalmente a operaciones binarias , pero desde finales del siglo XX se utiliza de manera más generalizada.Martin, NM (1989), Sistemas de lógica , Cambridge University Press, p. 54, ISBN 978-0-521-36770-7.
8. Scharle, TW (1965), "Axiomatización del cálculo proposicional con functores de Sheffer", Notre Dame J. Formal Logic , 6 (3): 209–217, doi : 10.1305/ndjfl/1093958259.
9. Wernick, William (1942) "Conjuntos completos de funciones lógicas", Transactions of the American Mathematical Society 51 : 117–32. En su lista de la última página del artículo, Wernick no distingue entre ← y →, ni entre y . ${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$
10. "Operaciones de puerta NAND" en http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
11. "Operaciones de puerta NOR" en http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html