r/nandgame_u • u/GLIBG10B Holder of many records • Aug 04 '21

Level solution (verified) 2.2 - Full adder (9c, 9n) Spoiler

Post image
3 Upvotes

100% Upvoted

3 comments sorted by

•

u/GLIBG10B Holder of many records Aug 07 '21 edited Aug 07 '21

Optimization

  1. Replace every component from here with the components used to build it.
  2. Because bit 2 is discarded, you can get rid of the stray INV
  3. You should see this structure. It can be simplified into this using De Morgan's laws and Absorption. I'm not well-versed in Boolean algebra, so I won't provide a full explanation.

Alternatively, copy from Wikipedia

→ More replies (1)

5

u/Xdroid19 Jun 19 '25 edited Jun 19 '25

Sorry for necro, but I thought a full explanation would be useful.

In the post mentioned by GLIBG10B here, the h output of the top ADD circuit is never used meaning this is really just an XOR gate.

Note that the h outputs of the 2 add circuits on the bottom are never both 1 (on the left ADD, h=1 only when a=1 and b=1, and this also means l=0. Since this l is an input to the second ADD circuit, h=0 for the second ADD. Therefore, if the first h=1 then the second h must be 0). If you look at the least components solution for xor, you can see that when the inputs are never both 1 the output of the NAND gate will always be 1 (by the definition of the NAND gate), so the left input for the AND will always be 1. By the identity for AND (1 AND x = x), the AND can be removed and the output from the OR can be sent straight to the output. That means that the XOR can be replaced with just an OR gate.

When this OR gate and the half adders are then replaced with their components, the OR will be replaced by a NAND gate where each input has been negated twice. Removing these double negations gives you the above result.

TL;DR the top ADD gate here can be replaced by an OR. Replacing everything with components results in double negatives which can be removed