Construir una puerta AND a partir de puertas XOR

No. Debido a la naturaleza tanto complementaria como simétrica de las entradas y salidas de XOR, no hay forma de configurar ninguna de ellas para generar una salida que no muestre la misma simetría.

La operación XOR es bilinear : invertir cualquiera de las entradas invierte siempre la salida.

Esta propiedad se conserva incluso si se conectan en cascada múltiples puertas XOR (y, opcionalmente, entradas constantes y / o NO puertas) juntas: la inversión de cualquier entrada siempre invierte la salida. Por supuesto, puede construir circuitos más complejos donde una sola entrada se puede dividir y alimentar en múltiples puertas, pero todos estos circuitos se pueden expandir en un árbol equivalente de puertas XOR, posiblemente con la misma entrada que aparece varias veces. Para cada entrada, se mantendrá uno de los dos casos siguientes:

• si el valor de entrada aparece un número impar de veces en el árbol XOR, al invertir esa entrada se invierte la salida;

• si el valor de entrada aparece un número par de veces en el árbol XOR, sus efectos en la salida se cancelan, y la salida termina siendo completamente independiente de esa entrada.

En cualquier caso, los únicos tipos de funciones que puede construir combinando puertas XOR son aquellas donde cada entrada que nunca afecta a la salida, o siempre invierte el salida cuando la entrada se invierte.

Ahora considere una puerta AND: si la primera entrada es 1, la salida es igual a la segunda entrada, mientras que si la primera entrada es 0, la salida siempre será 0 independientemente de la segunda entrada. Esto es imposible de implementar con compuertas XOR: en cualquier circuito de solo XOR, alternar la segunda entrada siempre debe cambiar la salida o nunca cambiarla.

Todo esto se puede expresar de manera concisa en términos matemáticos: XOR es un operador multilineal, y la composición de los operadores multilineales es siempre multilineal. AND es no un operador multilineal, por lo que no se puede obtener combinando operadores XOR.

Aquí hay una prueba que podría ser un poco más fácil de visualizar visualmente. . .

Dado que XOR es conmutativo ( p XOR q = q XOR p ) y asociativo ( p XOR (q XOR r) = (p XOR q) XOR r ), no hay una forma interesante de reordenar o reestructurar una fórmula donde XOR es la única puerta; algo como p XOR ((t XOR (s XOR q)) XOR r) es equivalente a p XOR q XOR r XOR s XOR t .

Entonces, si solo tiene dos variables p y q , y la única puerta que tiene es XOR , entonces su fórmula puede simplificarse a la forma (p XOR p XOR ... XOR p) XOR (q XOR q XOR ... XOR q) . Podemos simplificar p XOR p XOR ... XOR p así:

# of p's       full version     simplification
   0               FALSE             FALSE
   1                 p                 p
   2              p XOR p            FALSE
   3           p XOR p XOR p           p
   4        p XOR p XOR p XOR p      FALSE
   5     p XOR p XOR p XOR p XOR p     p
   .                 .                 .
   .                 .                 .
   .                 .                 .

. . . y de manera similar con q XOR q XOR ... XOR q . Así que solo hay cuatro funciones que puedes calcular:

FALSE XOR FALSE          FALSE
FALSE XOR   q              q
  p   XOR FALSE            p
  p   XOR   q           p XOR q

Como dice que logró construir una puerta NO, supongo que también se está permitiendo proporcionar una entrada constante; pero como puede ver, agregar FALSE no cambiará el resultado, agregar un número par de TRUE no cambiará el resultado, y agregar un número impar de TRUE simplemente invertirá el resultado (dando TRUE , NOT p , NOT q , o p XNOR q ). Ninguna de estas posibilidades es equivalente a AND.

Cualquier circuito puramente combinatorio que consiste completamente en compuertas XOR, desde un punto de vista combinatorio, computará la función de paridad par o impar para alguna combinación de sus entradas e ignorará el resto. Esto se puede mostrar por inducción si se observa que cada entrada será la función de paridad impar de sí misma, y el xor de dos funciones de paridad será una función de paridad de sus entradas desunidas (los términos de entrada que se usan en ambas se cancelarán). El xor de dos funciones de paridad par o impar será una función de paridad par; el xor de un par con un impar (o viceversa) será una función de paridad impar.

Incluso si uno no se limita a los circuitos combinatorios y está dispuesto a asumir retrasos de propagación deterministas a través de las puertas, eso no ayudará a menos que los retrasos de propagación a través de una puerta XOR varíen dependiendo del tipo de señal que se transmite. De lo contrario, si una de las entradas de un circuito cambia, cada nodo nunca se verá afectado o siempre experimentará las mismas transiciones de estado en los mismos momentos en relación con el cambio, independientemente del estado de cualquier otro nodo. Dado que una compuerta AND requiere que un cambio en una de las entradas solo cambie la salida si la otra entrada es baja, una compuerta XOR no tendría forma de simular dicho comportamiento condicional.