A question that had popped up in my head once - how many NAND gates would it take to build a larger, "meta-NAND" gate?

Your task is to build a black-box circuit that takes two input wires A and B and returns one output wire that satisfies A NAND B, subject to the following restrictions:

  • You must use at least two NAND gates in this construction (and no gates other than NAND).
  • You may not have null configurations of gates - that is, systems of gates that are equivalent to a gateless wire. (For example, two NOT gates in series are a null configuration.)
  • You cannot have any stray wires (discarded values or constants).

Fewest gates wins.

up vote 7 down vote accepted

4 gates

(A NAND B) AND-using-NAND (A NAND B)

A---NAND        _
 \ /    \      / \
  X      NAND-<   NAND-->
 / \    /      \_/
B---NAND

Three gates. Compute (((A nand A) nand B) nand B). Unlike the four-gate solution above in which three of the four gates compute A nand B, two of them simultaneously, and substituting one of the simultaneous outputs for the other would yield two consecutive inverters, the three-gate solution uses the three gates to compute different functions: "not A", "A or not B", and "A nand B". Only the last gate computes the desired function.

3 gates

   /-----------\
A-<             \
   \-----\       \
          \       NAND--
           NAND--/
B-<NAND---/

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.