¿Es posible escribir una compuerta AND usando compuertas XOR?

21

¿Cómo podría expresar una puerta AND usando solo puertas XOR?

logic boolean-algebra usuario2991856
fuente
1
¿Por qué quieres expresar y puertas con xor y en qué?
ABD
1
Estoy leyendo algo sobre el cifrado homomórfico, a saber, este documento eprint.iacr.org/2013/094.pdf también conocido como esquema LTV. Allí se afirma que la multiplicación significa AND, la suma entre dos bits significa XOR. ¿Entonces pregunto si es posible reescribir el esquema usando solo XOR? ¿Tal vez debería migrar la pregunta a Cryptography beta?
user2991856
44
Relacionado:
Completitud
2
Relacionado: stackoverflow.com/questions/6106934/…
rackandboneman
1
electronics.stackexchange.com/questions/140684/…
Jon Hanna

Respuestas:

36

No puedes

Como es asociativo, es decir , solo puede implementar funciones de la forma donde . Esto es equivalente a (dependiendo de la paridad del número de instancias de y ) 0, , o , que no son equivalentes a AND.( x 1 ⊕ x 2 ) ⊕ x 3 = x 1 ⊕ ( x 2 ⊕ x 3 ) x i 1 ⊕ . . . ⊕ xXOR(x1⊕x2)⊕x3=x1⊕(x2⊕x3) x i j ∈{x1,x2}x1x2x1x2x1⊕x2xi1⊕...⊕xikxij∈{x1,x2}x1x2x1x2x1⊕x2

Ariel
fuente
55
Es posible que desee permitir 0 y 1 como entradas también. Sin embargo, todavía no obtendrá AND, aunque también obtendrá la negación de lo anterior.
Taemyr
19

Hmmm No se puede hacer con álgebra booleana, eso es seguro, pero podría conectar uno físicamente. El truco es conectar una de las entradas a un cable de alimentación de una puerta XOR.

                     I2
                     |
      0  I1          |
      |   |          |
     \|   |/         |
     |\   / |        |
.|---| \ /  |--------/
     \  V  /  
      \   /  
       \ /  
        V 
        |            
     AND OUTPUT

La puerta XOR está cableada como un búfer no inversor. El truco implicado es que si conecta VCC a GND (o, por extensión, una conexión a tierra lógica), la salida es un GND débil.

Descargo de responsabilidad: esto funciona en el silicio que tengo, pero podría no funcionar en todo el silicio.

Joshua
fuente
8
Alguna explicación de cómo funciona esto haría que esta sea una respuesta mucho mejor.
David Richerby
¿No es redundante la primera puerta en este caso?
Nit
1
¿Qué es esto .|, |>?
Wojowu
1
@Wojowu ground y Vcc, supongo.
John Dvorak
44
"podría no funcionar en todo el silicio". ... sí, e incluso podría dañar algunos: aplicar una entrada a una puerta física con la alimentación apagada, o peor aún, encender la alimentación después, está fuera de especificaciones para muchas partes (re: efecto de retención CMOS !). Además, el voltaje de salida "verdadero" de la primera puerta es menor que el voltaje de suministro y, dependiendo de cuánto más bajo sea, cambiará significativamente la interpretación de los niveles de entrada en la segunda puerta. Y no es improbable (diodos de protección, salida complementaria ...) que I2 sea un cortocircuito efectivo a tierra cuando la puerta inferior esté sin alimentación.
rackandboneman