Cómo mostrar la integridad funcional de las puertas lógicas

Answer 1

Una forma sería usar el teorema de Post (ver Compleción funcional para más detalles).

Otra forma es mediante el uso de un conjunto funcionalmente completo que ya conoce y mostrando que puede hacer las puertas desde ese conjunto desde las puertas de su conjunto.

Por ejemplo, {AND, NOT} está funcionalmente completo, ya que sus operaciones lógicas pueden representar todas las funciones booleanas (tenga en cuenta que OR es NOT AND de las entradas negadas por la ley de De Morgan. Luego puede tomar {AND, NOT} e intentar hacer esas dos puertas con sus puertas dadas, en este caso, {XOR, NOT}.

Desafortunadamente, este método generalmente funciona cuando su conjunto de puertas (operaciones) ES de hecho completo (spoiler: {XOR, NOT} no lo está).

Entonces, volviendo a la magia negra de Post: como NO son solo dos XOR en cascada, solo observaré el conjunto {XOR}.

Para que se complete, según el teorema de Post, XOR no debe preservar cero, preservar uno, ser lineal, ser monótono ni ser dual.

¡Pero XOR es lineal! (compruébelo usted mismo, cuente los que están en la tabla de verdad.

Answer 2

Le daré un enlace que proporciona una explicación muy detallada de lo que es la integridad funcional y cómo probar cualquier sistema booleano para la integridad funcional:

http://cs.ucsb.edu/~victor/ta/cs …

Answer 3

Para mostrar que {XOR, NOT} es funcional completo, debe demostrar que es posible expresar todas las tablas de verdad posibles utilizando {XOR, NOT}. Puede usar tantas instancias de XOR y NO gate como desee.

La manera simple es expresar un conjunto completo funcional ya probado usando {XOR, NOT}.

{NAND, NOR} es un conjunto completo funcional bien conocido.

Entonces su tarea es: hacer una compuerta NAND usando múltiples XOR, NO compuertas y hacer una compuerta NOR usando múltiples XOR, NO.

Desafortunadamente, {XOR, NOT} no está funcionalmente completo. Por lo tanto, no puede construir {NAND, NOR} usando {XOR, NOT}.