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

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

logic boolean-algebra

dlaczego chcesz wyrazić i bramy za pomocą XOR iw czym?

— ABD

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

Powiązane: Kompletność funkcjonalna

— CodesInChaos

Powiązane: stackoverflow.com/questions/6106934/…

— rackandboneman

electronics.stackexchange.com/questions/140684/…

— Jon Hanna

Odpowiedzi:

Nie możesz

Ponieważ jest asocjacyjny, tj. , możesz implementować tylko funkcje o postaci gdzie $XOR$ $(x_1\oplus x_2)\oplus x_3=x_1\oplus(x_2\oplus x_3)$ $x_{i_1}\oplus...\oplus x_{i_k}$ $x_{i_j}\in\{x_1,x_2\}$ . Jest to równoważne (w zależności od parzystości liczby wystąpień oraz ) ma wartość 0, , , a , które nie są równoważne i. $x_1$ $x_2$ $x_1$ $x_2$ $x_1\oplus x_2$

— Ariel
źródło

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

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

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

Jakie są te .|, |>?

— Wojowu

@Wojowu Ground i Vcc, jak sądzę.

— John Dvorak

„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