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

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

a b out
0 0 0
0 1 1
1 0 1
1 1 0

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

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

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).

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

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.

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.

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.

$\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.

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.

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!

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).

*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}**