Czy możliwe jest napisanie bramki AND przy użyciu bram XOR?

21

Jak mogę wyrazić bramkę AND używając tylko bramek XOR?

użytkownik2991856
źródło
1
dlaczego chcesz wyrazić i bramy za pomocą XOR iw czym?
ABD
1
Czytam coś o szyfrowaniu homomorficznym, a mianowicie ten eprint.iacr.org/2013/094.pdf, znany również jako schemat LTV. Jest tam powiedziane, że mnożenie oznacza ORAZ dodanie dwóch bitów oznacza XOR. Pytam więc, czy możliwe jest przepisanie schematu przy użyciu tylko XOR? Może powinienem przenieść pytanie do kryptografii beta?
user2991856
4
Powiązane: Kompletność funkcjonalna
CodesInChaos
2
Powiązane: stackoverflow.com/questions/6106934/…
rackandboneman

Odpowiedzi:

36

Nie możesz

Ponieważ jest asocjacyjny, tj. ( X 1x 2 ) x 3 = x 1( x 2x 3 ) , możesz implementować tylko funkcje o postaci x i 1. . . x i k gdzie x i j{ x 1 , x 2 }XOR(x1x2)x3=x1(x2x3)xi1...xikxij{x1,x2}. Jest to równoważne (w zależności od parzystości liczby wystąpień oraz x 2 ) ma wartość 0, x 1 , x 2 , a x 1x 2 , które nie są równoważne i.x1x2x1x2x1x2

Ariel
źródło
5
Możesz także zezwolić na 0 i 1 jako dane wejściowe. Nadal nie dostaniesz AND, chociaż dostaniesz także negację powyższego.
Taemyr
19

Hmmm. Nie da się tego zrobić z algebrą boolowską, to na pewno, ale mógłbym połączyć jedną fizycznie. Sztuką jest podłączenie jednego z wejść do przewodu zasilającego bramki XOR.

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

Brama XOR jest podłączona jako bufor nieodwracający. Sztuczka polega na tym, że jeśli podłączysz VCC do GND (lub przez rozszerzenie uziemienia logicznego), wyjście będzie słabym GND.

Oświadczenie: działa na krzemie, który mam, ale może nie działać na wszystkich krzemach.

Jozuego
źródło
8
Wyjaśnienie, jak to działa, uczyniłoby to znacznie lepszą odpowiedź.
David Richerby
Czy pierwsza bramka nie jest w tym przypadku zbędna?
Nit
1
Jakie są te .|, |>?
Wojowu
1
@Wojowu Ground i Vcc, jak sądzę.
John Dvorak
4
„może nie działać na wszystkich krzemach”. ... tak, a nawet może uszkodzić niektóre - zastosowanie wejścia do fizycznej bramki przy wyłączonym zasilaniu lub nawet gorzej po włączeniu zasilania jest niezgodne ze specyfikacją wielu części (re: efekt zatrzaskiwania CMOS !). Również „prawdziwe” napięcie wyjściowe pierwszej bramki jest niższe niż napięcie zasilające i, w zależności od tego, jak bardzo jest niższe, znacząco zmieni interpretację poziomów wejściowych na drugiej bramce. I nie jest mało prawdopodobne (diody ochronne, komplementarne wyjście ...), że I2 będzie skutecznym zwarciem do masy, gdy dolna bramka nie będzie zasilana.
rackandboneman