Bagaimana cara membangun gerbang XOR hanya menggunakan 4 gerbang NAND?

xorgate, sekarang saya perlu membuat gate ini hanya menggunakan 4 nandgate

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

yang xor = (a and not b) or (not a and b), yang merupakan

Saya tahu jawabannya tetapi bagaimana cara mendapatkan diagram gerbang dari formula?

EDIT

Maksud saya secara intuitif, bagi saya, saya harus mendapatkan yang ini jika saya melakukannya langkah demi langkah diikuti oleh definisi xor = (a and not b) or (not a and b).

dan xorakan dibangun dengan 5 nandgerbang (gambar # 1 pertama di bawah)

pertanyaan saya lebih seperti: bayangkan orang pertama dalam sejarah mencari tahu rumus ini, bagaimana dia (proses berpikir) dapat memperoleh 4 nandsoluion dari rumus ini, langkah demi langkah.

Dari formula itu? Itu bisa dilakukan. Tetapi lebih mudah untuk memulai dengan yang satu ini: (menggunakan notasi yang berbeda di sini)

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

Ok sekarang apa? Akhirnya kita harus menurunkan ~(~(~(a & b) & a) & ~(~(a & b) & b))(yang terlihat seperti memiliki 5 NAND, tetapi seperti diagram rangkaian, ia memiliki sub-ekspresi yang digunakan dua kali).

Jadi buatlah sesuatu yang terlihat seperti ~(a & b) & a(dan hal yang sama tetapi dengan bdi akhir) dan berharap itu akan bertahan: ( andmendistribusikan lebih or)

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

Cukup dekat sekarang, cukup terapkan DeMorgan untuk mengubah tengah itu ormenjadi and:

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

Dan itu saja.

Saya pikir Anda meminta bukti ini:

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

Meskipun ternyata ada 5 NANDs yang digunakan dalam persamaan yang dihasilkan, tetapi duplikat !(AB)akan digunakan hanya sekali ketika Anda mendesain rangkaiannya.

Karena Anda sudah memiliki jawaban diagram, mudah tersedia dari wikipedia dengan mengetikkan judul pertanyaan Anda di Google, sebagai diagram .png yang identik dengan Anda, seharusnya mudah bagi Anda untuk menemukan rumus dengan mengekstraknya dari diagram itu. Diberi definisi NAND sebagai $\text{NAND}(A,B)=\overline{AB}\;$:

• Gerbang paling kiri menghasilkan ;$C=\overline{AB}$

• Gerbang atas memberikan ;$D_1=\overline{AC}$

• Gerbang atas memberikan , karena NAND komutatve seperti DAN;$D_2=\overline{BC}$

• Gerbang paling kanan menghasilkan .$E=\overline{D_1D_2}$

Menyatukan semuanya pertama-tama kita perhatikan itu

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

Demikian pula: $\overline{D_2}=B\overline A$

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

Yang tepatnya definisi XOR. Anda dapat membalikkan semua ini jika Anda ingin memulai dari data awal Anda, bukan hanya memeriksa jawabannya.

Menemukan jawabannya tanpa pengetahuan sebelumnya

Ini dimaksudkan untuk menjawab permintaan eksplisit, ditambahkan sebagai edit untuk pertanyaan, untuk cara menemukan solusi dari awal. Mengingat bahwa pertanyaannya adalah tentang proses berpikir, saya memberikan semua detail.

Saya akan mencoba untuk bergantung pada kendala masalah (hanya 4 gerbang NAND) dan pada kesimetrisannya antara dan $A$$B$ yang dapat dipertahankan dalam solusi.

Satu hal yang saya tahu (dengan asumsi informasi mengalir dari kiri ke kanan seperti pada diagram pertanyaan) adalah harus ada gerbang NAND paling kanan yang menghasilkan jawaban yang diinginkan $\text{XOR}(A,B)=A\overline B + B\overline A\;$.

Jadi kita bisa mencoba menebak input seperti apa ke gerbang ini yang akan menghasilkan output yang diinginkan.

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

Menyatukan formula terakhir ini dengan hasil yang harus kami dapatkan, kami memperoleh:

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

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

Perhatikan bahwa ini hanya kemungkinan yang paling sederhana. Ada pasangan input lain yang akan memberikan hasil yang diinginkan, karena kami tidak menyatukan dalam aljabar gratis, karena NAND memiliki sifat persamaan. Tapi kami mencoba itu sebagai permulaan.

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

Kita dapat mencoba mengulangi prosedur penyatuan (saya lakukan), tetapi ini secara alami akan mengarahkan kita untuk menggunakan empat gerbang lagi, maka untuk solusi 5 gerbang.

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

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

Mudah untuk memeriksanya

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

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

Maka kita dapat menyusun empat gerbang ini untuk mendapatkan hasil yang diinginkan, yaitu fungsi XOR.

Saya mengambil input $(0,0)$ sebagai contoh.

Untuk $\text{XOR}$, output yang diinginkan adalah 0. Namun, $\text{NAND}(0,0) = 1$.

• Karena satu-satunya cara untuk mendapatkan 0 menggunakan $\text{NAND}$ adalah (pada lapisan terakhir) $\text{NAND}(1,1) = 0$, Anda harus terlebih dahulu menghasilkan dua 1.

  • Berdasarkan $\text{NAND}(0,1) = 1$ atau $\text{NAND}(1,0) = 1$, Anda menghasilkan 1 menggunakan satu $\text{NAND}(0,0)$ di lapisan pertama dan beri makan, bersama dengan satu input 0, ke dalam lapisan kedua $\text{NAND}$.

Hanya empat $\text{NAND}$S terlibat. Tetapi itu hanya benar untuk input$(0,0)$sejauh ini. Jadi, Anda perlu memeriksa input lainnya$(0,1), (1,0),$ dan $(1,1)$menentang solusi dan menemukan bahwa itu hanya berfungsi. Beruntung.

Saya mencoba yang terbaik untuk memberikan jawaban menggunakan rumus seperti yang diminta. Semoga Anda menghargainya.
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) '-> Petunjuk
jadi sekarang (AB)' dapat melewati gerbang NAND ke-1, maka di gerbang NAND ke-2 dan ketiga output dari gerbang NAND ke-1 melewati dengan salah satu dari input sebagai A dan B. Setelah ini kita perlu satu pelengkap lagi jadi gunakan gerbang NAND keempat.
NAND (1) = (AB) '= A' + B '
NAND (2) = (A (AB)') '= (A (A' + B '))' = (AB ')' = A '+ B
NAND (3) = (B (AB) ')' = (B (A '+ B')) '= (A'B)' = A + B '
NAND (4) = [(A' + B) (A + B ')]' = [A'B '+ AB]' = (A + B) (A '+ B') = AB '+ A'B

Senang!

Rumusnya: XOR = (a dan bukan b) atau (bukan a dan b).

Bukan itu yang Anda inginkan, Anda menginginkan formula yang merupakan NAND. Ingat bahwa tidak (a atau b) = bukan a dan bukan b, dan karena itu (a atau b) = tidak (bukan a dan bukan b). Karena itu

(a dan bukan b) atau (bukan a dan b) =

not (not (a dan not b) dan not (not a dan b)) =

not ((bukan a atau b) dan (a atau tidak b)) =

NAND (bukan a atau b, a atau tidak b).

Jadi kami menggunakan satu gerbang NAND, dan harus menghitung (bukan a atau b) dan (a atau tidak b) menggunakan tiga NAND. Kami mengubah setiap ekspresi menjadi NAND:

not a atau b = not (a dan not b) = NAND (a, not b)

a atau tidak b = tidak (bukan a dan b) = NAND (bukan a, b)

Sekarang kita amati bahwa (x dan y) = x dan (bukan x atau y): Jika x salah maka kedua sisi salah. Jika x benar maka (bukan x atau y) = (false atau y) = y. Ini berlaku untuk NAND seperti halnya untuk DAN. Karena itu

NAND (a, bukan b) = NAND (a, bukan a atau tidak b) = NAND (a, NAND (a, b))

NAND (b, bukan a) = NAND (b, bukan b atau tidak a) = NAND (b, NAND (a, b)).

Jadi pertama-tama kita menemukan mid = NAND (a, b), kiri = NAND (a, mid) dan kanan = NAND (b, mid), akhirnya XOR = NAND (kiri, kanan).

* Dari kiri ke kanan - D1, D2, D3, D4 ** D1 = (AB) 'ATAU (A' + B ')

seharusnya

(AB) '= C

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

D3 = (BC) '= B' + C 'lalu

D4 = (D2.D3) '

D4 = ((AC) '. (BC)') '

D4 = (AC) '' + (BC) ''

D4 = (AC) + (BC)

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

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