Métodos de demostración

Integridad funcional

En lógica, un conjunto funcionalmente completo de conectivas lógicas 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. Un conjunto completo de conectivos bien conocido es {AND, NOT}, que consiste en conjunción binaria y negación. Cada uno de los conjuntos de singleton {NAND} y {NOR} está funcionalmente completo.

En un contexto de lógica proposicional, los conjuntos funcionalmente completos de conectivos también se denominan (expresivamente) adecuados. 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 de los tipos prescritos por el conjunto. En particular, todas las puertas lógicas se pueden ensamblar a partir de solo puertas binarias NAND, o solo de puertas binarias NOR.

Introducción

Los textos modernos sobre lógica típicamente toman como primitivos algunos subconjuntos de los conectivos: conjunción (ᐱ); disyunción (ᐯ); negación (¬); material condicional (→); y posiblemente la bicondicional (↔). Se pueden definir más conectivos, si así se desea, definiéndolos en términos de estos primitivos. Por ejemplo, NOR (a veces denotado ↓, la negación de la disyunción) se puede expresar como una conjunción de dos negaciones:

A ↓ B :=¬A ᐱ¬B

Del mismo modo, la negación de la conjunción, NAND (a veces se denota como ↑),se puede definir en términos de disyunción y negación. Resulta que cada conectivo binario se puede definir en términos de {¬, ᐱ,ᐯ,→,↔},por lo que este conjunto está funcionalmente completo.

Sin embargo, aún contiene algo de 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

A →B:=¬A ᐯ B

A ↔B:=(A →B) ᐱ (B →A) .

De ello se deduce que el conjunto más pequeño también está funcionalmente completo. Pero esto todavía no es mínimo, ya que puede definirse como

A ᐯ B:= ¬ (¬A ᐱ¬B)

Definición Formal

Dado el dominio booleano B = {0,1}, un conjunto F de funciones booleanas ƒi: Bni → B está funcionalmente completo si el clon en B generado por las funciones básicas ƒi contiene todas las funciones ƒ: Bn → B, para todos los estrictamente positivos enteros n ≥ 1. En otras palabras, el conjunto está funcionalmente completo si cada función booleana que toma al menos una variable puede expresarse en términos de las funciones ƒi. Dado que cada función booleana de al menos una variable puede expresarse en términos de funciones booleanas binarias, F está funcionalmente completa 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 consista en todas las funciones ƒ: Bn → B, para todos los enteros n ≥ 0. Sin embargo, los ejemplos dados anteriormente no están funcionalmente completos en este sentido más fuerte 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 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 de constante nula, esté funcionalmente completo o, de manera equivalente, 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.

Caracterización de la integridad funcional

Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

• The monotonic connectives; changing the truth value of any connected variables from F to T without changing any from T to F never makes these connectives change their return value from T to F, por ejemplo ᐱ,ᐯ,T,ꓕ.
• Los conectivos afines, de manera que cada variable conectada siempre o nunca afecta el valor de verdad que devuelven estos conectivos.
• Los conectivos auto-duales, que son iguales a su propio dual de Morgan; Si los valores de verdad de todas las variables se invierten, también lo es el valor de verdad que devuelven estos conectores, por ejemplo. ¬ MAJ (p, q, r).
• Los conectivos que preservan la verdad; devuelven el valor de verdad T bajo cualquier interpretación que asigna T a todas las variables.
• Los conectivos que preservan la falsedad. devuelven el valor de verdad F bajo cualquier interpretación que asigne F a todas las variables.

De hecho, Post proporcionó una descripción completa de la red de todos los clones (conjuntos de operaciones cerradas bajo la composición y que contiene todas las proyecciones) en el conjunto de dos elementos {T, F}, actualmente denominado red de Post, que implica el resultado anterior como un Corolario simple: los cinco conjuntos de conectivos mencionados son exactamente los clones máximos.

Mínimo funcionalmente completo de conjuntos de operadores

Cuando un solo operador lógico conectivo o booleano está funcionalmente completo por sí mismo, se denomina función Sheffer o, en ocasiones, un único operador suficiente. No hay operadores unarios con esta propiedad. NAND y NOR, que son duales entre sí, son las únicas dos funciones binarias Sheffer. Estos fueron descubiertos, pero no publicados, por Charles Sanders Peirce alrededor de 1880, y redescubiertos independientemente y publicados por Henry M. Sheffer en 1913. En la terminología de la electrónica digital, la compuerta NAND binaria y la compuerta NOR binaria son las únicas compuertas lógicas universales binarias. Los siguientes son los conjuntos mínimos funcionales completos de conectivos lógicos con aridad ≤ 2

Ejemplos

Ejemplos de uso de la integridad NAND (↑). Como lo ilustra,

• ¬A = A ↑ A
• A ∧ B = ¬ (A ↑ B) = (A ↑ B) ↑ (A ↑ B)
• A ∨ B = (A ↑ A) ↑ (B ↑ B)
• Ejemplos de uso de la integridad NOR (). Como lo ilustra,
• ¬A = A ↓ A
• 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 optimiza mediante la reutilización, lo que reduce el número de puertas. Por ejemplo, la operación "A ∧ B", cuando se expresa mediante ↑ gates, se implementa con la reutilización de "A ↑ B",

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

En otros dominios

Además de los conectores lógicos (operadores booleanos), la integridad funcional se puede introducir en otros dominios. Por ejemplo, un conjunto de puertas 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í misma: un único operador suficiente. Hay muchas otras puertas lógicas universales de tres entradas, como la puerta 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 la funcionalidad completa.

Teoría de Conjuntos

Existe un isomorfismo entre el álgebra de conjuntos y el álgebra de Boole, es decir, tienen la misma estructura. Luego, si asignamos operadores booleanos a operadores de conjuntos, el texto anterior "traducido" 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 conjunto. Los "conjuntos de operadores completos mínimos mínimos" 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 a completar álgebra booleana funcionalmente.

• Datos: Q65162024