Jak zbudować bramę XOR przy użyciu tylko 4 bramek NAND?

17

xorbrama, teraz muszę zbudować tę bramę, używając tylko 4 nandbram

the xor = (a and not b) or (not a and b), czyli

\begin{aligned} \bar{A} B + A \bar{B} \end{aligned}

$\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}$

Znam odpowiedź, ale jak uzyskać schemat bramy ze wzoru?

brama Xor

EDYTOWAĆ

Mam na myśli intuicyjnie, że powinienem dostać ten, jeśli zrobię to krok po kroku, a następnie definicję xor = (a and not b) or (not a and b).

\begin{aligned} \bar{\bar{\bar{A} B} \cdot \bar{A \bar{B}}} \end{aligned}

$\begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split}$

i xorzostanie zbudowany z 5 nandbramami (pierwsze zdjęcie nr 1 poniżej)

xor gate 2

moje pytanie jest bardziej podobne: wyobraź sobie, że pierwsza osoba w historii nandwymyśliła tę formułę, w jaki sposób ona (proces myślenia) może uzyskać krok po kroku 4 rozwiązania z tej formuły.

\begin{aligned} \bar{A} B + A \bar{B} \end{aligned}

$\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}$

logic boolean-algebra

— Ponadczasowy
źródło

Jestem pewien, że wiesz, jak wziąć XOR (lub dowolną inną funkcję) i przekonwertować go na równoważny obwód, który używa tylko NAND (co jest zawsze możliwe, ponieważ NAND jest kompletny ). Jeśli jednak zapytasz, jak zredukować tę formułę do używania tylko 4 NAND, lub ogólnie mniej niż

NAND, i czy możliwe jest nawet uzyskanie równoważnego obwodu z

NAND - nie jestem pewien, czy istnieje łatwy odpowiedz na to.

k

$k$

\leq k

$\le k$

— Ran G.

Poniżej znajdują się dwie odpowiedzi na problem. Mój jest dość szczery, że możesz zaprojektować (a posteriori) sposób na znalezienie pożądanej konstrukcji, znając z góry ostateczny wynik, który został podany w pytaniu i jest dostępny w Internecie. Jest to oczywiście najprostszy sposób robienia rzeczy, choć może się to wydawać absurdalne, bez podania ogólnej procedury, na którą nie ma odpowiedzi. Dlatego interesuje mnie, dlaczego wyborcy wolą jedną odpowiedź od drugiej, kiedy to robią ... jeśli poświęcisz czas na krótki komentarz. Z góry dziękuję.

— babou

To pytanie jest zamknięte jako niejasne. Myślę, że może być całkiem jasne, o co prosi OP, a co bardziej interesujące, jeśli OP zadał sobie trud zareagowania na różnych użytkowników, którzy próbowali mu odpowiedzieć,

— babou

electronics.stackexchange.com/questions/84714/… - to pytanie jest bardziej ogólne, odpowiedzi zawierają więcej informacji na temat ogólnego podejścia do rozwiązania tego problemu, a ta odpowiedź electronics.stackexchange.com/a/84803 pokazuje, jak uzyskać NAND reprezentacja dla operatora XOR

— Anton Trunov

Bawiłem się z podobnymi problemami i właśnie napisałem program, który wypróbował wszystko systematycznie ... Świetnie dla maksymalnie czterech wejść, gdzie jest tylko 65 536 możliwych funkcji. W przypadku nieco bardziej skomplikowanych obwodów pozwoliło mi to również zoptymalizować opóźnienia i znaleźć optymalne obwody, jeśli jedno lub dwa wejścia byłyby dostępne później niż inne. Obwody z 5 wejściami = 2 ^ 32 możliwe funkcje byłyby prawdopodobnie wykonalne przy użyciu siły brutalnej.

— gnasher729,

13

Z tej formuły? To może być zrobione. Ale łatwiej jest zacząć od tego: (używając innej notacji tutaj)

a ^ b = ~(a & b) & (a | b)

Ok, a teraz co? W końcu powinniśmy czerpać~(~(~(a & b) & a) & ~(~(a & b) & b)) (który wygląda na to, że ma 5 NAND, ale podobnie jak schemat obwodu ma podwyrażenie, które jest używane dwukrotnie).

Stwórz więc coś, co wygląda ~(a & b) & a(i to samo, ale z bkońcem) i miej nadzieję, że zostanie: ( androzprowadza się or)

(~(a & b) & a) | (~(a & b) & b)

Teraz już dość blisko, po prostu zastosuj DeMorgan, aby zmienić ten środek orw and:

~(~(~(a & b) & a) & ~(~(a & b) & b))

I to wszystko.

— Harold
źródło

9

Myślę, że prosisz o ten dowód:

A^B = (!A)B + A(!B)
    = !!((!A)B) + !!(A(!B))
    = !(!!A + !B) + !(!A + !!B)
    = !(A + !B) + !(!A + B)
    = !((A + !B)(!A + B))
    = !(A(!A) + AB + (!A)(!B) + B(!B))
    = !(AB + (!A)(!B))
    = !(AB)(!(!A)(!B))
    = !(AB)(!!A + !!B)
    = !(AB)(A+B)
    = !(AB)A + !(AB)B
    = !!(!(AB)A + !(AB)B)
    = !((!(!(AB)A))(!(!(AB)B)))

Chociaż najwyraźniej NANDw równaniu wynikowym zastosowano 5 s, ale duplikat !(AB)zostanie użyty tylko raz podczas projektowania jego obwodu.

— Muntasir
źródło

Przykro mi, ale czy A ^ B nie oznacza A i B? Wygląda na to, że Twoim zamiarem było sprawdzenie XOR, który symbol powinien być ⊕ lub ⊻. Jednak tego dowodu naprawdę szukałem, dziękuję!

— osiixy

5

$\text{NAND}(A,B)=\overline{AB}\;$ :

$C=\overline{AB}$
$D_1=\overline{AC}$
$D_2=\overline{BC}$
$E=\overline{D_1D_2}$

Podsumowując, najpierw to zauważamy

$C=\overline{AB}=\overline A+\overline B$

$\begin{align} \overline{D_1}&=AC\\ &=A(\overline A+\overline B)\\ &=A\overline A+A\overline B\\ &=0+A\overline B\\ &=A\overline B\\ \end{align}$

$\overline{D_2}=B\overline A$

$\begin{align} E&=\overline{D_1D_2}\\ &=\overline{D_1}+\overline{D_2}\\ &=A\overline B + B\overline A \end{align}$

To właśnie jest definicja XOR. Możesz po prostu odwrócić to wszystko, jeśli chcesz zacząć od początkowych danych, zamiast po prostu sprawdzić odpowiedź.

Znalezienie odpowiedzi bez wcześniejszej wiedzy

Ma to na celu odpowiedzieć na wyraźne żądanie dodane jako edycję pytania w celu znalezienia rozwiązania od zera. Biorąc pod uwagę, że pytanie dotyczy procesu myślowego, podaję wszystkie szczegóły.

$A$ $B$

$\text{XOR}(A,B)=A\overline B + B\overline A\;$ .

Możemy więc spróbować zgadnąć, jaki rodzaj danych wejściowych do tej bramki dałby pożądany wynik.

$\text{NAND}(X,Y)=\overline{XY}= \overline X+\overline Y\;$

Ujednolicając tę ostatnią formułę z rezultatem, który musimy uzyskać, otrzymujemy:

$\overline X=A\overline B\;$ $X=\overline{A\overline B}=\overline A+B\;$ .
$Y=\overline{\overline A B}=A+\overline B\;$ .

Pamiętaj, że jest to tylko najprostsza możliwość. Istnieją inne pary danych wejściowych, które dałyby pożądany rezultat, ponieważ nie jednoczymy się w wolnej algebrze, ponieważ NAND ma właściwości równania. Ale próbujemy tego na początek.

$X$ $Y$ $A$ $B$

Moglibyśmy spróbować powtórzyć procedurę unifikacji (ja to zrobiłem), ale to naturalnie doprowadzi nas do użycia czterech kolejnych bramek, a więc rozwiązania 5 bramek.

$X$ $Y$ $Z$ $A$ $B$ zapewni dane wejściowe dla tych dwóch bram pośrednich.

$X$ $Y$ $Z$ $A$ $B$ $A$ $B$

$A$ $B$

$Z=\text{NAND}(A,B)=\overline{AB}= \overline A+\overline B\;$

$Z$ $A$ $B$ $X$ $Y$

$A$ $B$

Łatwo to sprawdzić

$\begin{align} \text{NAND}(Z,A)&=\overline{ZA}\\ &=\overline{\overline{AB}\;A}\\ &=\overline{(\overline A+\overline B)\;A}\\ &=\overline{\overline AA+\overline BA}\\ &=\overline{0+\overline BA}\\ &=\overline{\overline BA}\\ &=\overline{A\overline B}\\ &=X \end{align}$

Similarly $\text{NAND}(Z,B)=Y$

Hence we can compose these four gates to get the desired result, i.e., the XOR function.

— babou
źródło

Not in a reverse way to prove that they are equal. But image that you don't know the diagram but to construct the gate using minimum nand gate.

— Timeless

1

What do you expect as an answer? A systematic technique for doing that. I do not know that there is any that is tractable enough to be worth using in complex cases. Given that I know the answer I can just lie to you and pretend to have found by reasonning what I discovered by checking the answer. This said, looking at what I get with NAND(A,B) is all that seems useful for a start. Then NANDing the result with one argument A or B, is also one thing to look at, to get a view of where I am. From there, one is pretty close to the final answer.

— babou

1

@Timeless Another way to go about it is backward from the answer, knowing that the answer is fron a NAND gate. If you assume that the solution is symmetrical in A and B, it gives you a likely form of the inputs to the last NAND gate. There are many way to go about it, either to find the answer, or to justify finding it a posteriory. But a proof is a proof, whether found by your ingenuity, or given by some oracle or a good friend. And at some point no one can tell the difference. Actually, the backward proof I give could be the best proof, even if the solution was found some other way.

— babou

Actually, it is quite common in math to have an analysis part to find a solution, then a synthesis part where you prove it is the solution. One usually gives both, but only the second part is really necessary.

— babou

@Timeless Both answers were based on the knowledge of a formula to obtain, deduced from the diagram to be obtained. Your edit asked for a plausible intuitive scenario to find the answer without any prior knowledge of the result. I did add that to my answer, but it would be nice to know whether it fits what you expected.

— babou

0

I take the input $(0,0)$ as an example.

For $\text{XOR}$ , the desired output is 0. However, $\text{NAND}(0,0) = 1$ .

Because the only way to get a 0 using $\text{NAND}$ is (at the last layer) $\text{NAND}(1,1) = 0$ , you should first produce two 1's.
- According to $\text{NAND}(0,1) = 1$ or $\text{NAND}(1,0) = 1$ , you produce a 1 using one $\text{NAND}(0,0)$ at the first layer and feed it, along with one input 0, into a second layer $\text{NAND}$ .

Only four $\text{NAND}$ s are involved. But it is only correct for the input $(0,0)$ so far. So you need to check other inputs $(0,1), (1,0),$ and $(1,1)$ against the solution and find that it just works. Lucky.

— hengxin
źródło

0

I tried my best to give the answer using formula as asked.Hope you appreciate it.
Z=AB'+A'B
Z=AA'+AB'+BB'+A'B --->BB'=AA'=0
Z=A(A'+B')+B(B'+A')
Z=A(AB)'+B(AB)' --> Hint
so now (AB)' can get through 1st NAND gate,then in 2nd and third NAND gate the output of 1st NAND gate pass through with one of the input as A and B.After this we need one more complement so use fourth NAND gate.
NAND(1st)=(AB)'=A'+B'
NAND(2nd)=(A(AB)')'=(A(A'+B'))'=(AB')'=A'+B
NAND(3rd)=(B(AB)')'=(B(A'+B'))'=(A'B)'=A+B'
NAND(4th)=[(A'+B)(A+B')]' =[A'B'+AB]'=(A+B)(A'+B')=AB'+A'B

Happy!

— MANVENDRA SINGH MANOHAR
źródło

0

The formula: XOR = (a and not b) or (not a and b).

Thats' not what you want, you want a formula that is a NAND. Remember that not (a or b) = not a and not b, and therefore (a or b) = not (not a and not b). Therefore

(a and not b) or (not a and b) =

not (not (a and not b) and not (not a and b)) =

not ((not a or b) and (a or not b)) =

NAND (not a or b, a or not b).

So we used one NAND gate, and have to calculate (not a or b) and (a or not b) using three NANDs. We turn each expression into a NAND:

not a or b = not (a and not b) = NAND (a, not b)

a or not b = not (not a and b) = NAND (not a, b)

Now we observe that (x and y) = x and (not x or y): If x is false then both sides are false. If x is true then (not x or y) = (false or y) = y. This is true for NAND just as it's true for AND. Therefore

NAND (a, not b) = NAND (a, not a or not b) = NAND (a, NAND (a, b))

NAND (b, not a) = NAND (b, not b or not a) = NAND (b, NAND (a, b)).

So we first find mid = NAND (a, b), left = NAND (a, mid) and right = NAND (b, mid), finally XOR = NAND (left, right).

— gnasher729
źródło

-2

*From left to right--D1,D2,D3,D4 ** D1=(A.B)' OR(A'+B')

suppose

(A.B)'=C

D2=(A.C)'=A'+C'

D3=(B.C)'=B'+C' then

D4=(D2.D3)'

D4=((A.C)'.(B.C)')'

D4=(A.C)''+(B.C)''

D4=(A.C)+(B.C)

D4=A.(A'+B')+B.(A'+B')

D4=AB'+BA' {A.A'=B.B'=0}**

— Bivash
źródło

2

I find it hard to follow this answer or understand what process you are using. Can you add some text sentences to explain the approach, so this isn't just a sequence of equations?

— D.W.