I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate.

Up to now I'm just solving these boolean implementations by guessing all required gates which is so much time consuming. I'm not able to find any logic in the implementation.

I'm wondering if you have any method, tipp how to solve this.

Here is an example of the Mux requirements presented in the book

Mux requirement image example Mux requirement image example continue

  • $\begingroup$ Welcome to cs.stackexchange. Your question sounds more like a homework. Anyway, you can start looking at the truth-tables -- this may give you a hint. $\endgroup$
    – hola
    Jan 5, 2019 at 19:14
  • $\begingroup$ Have you tried writing a program to conduct a exhaustive search by brute force? $\endgroup$
    – John L.
    Jan 5, 2019 at 20:36
  • $\begingroup$ I realized that my comment above sounds like against the "logically" in the title. Let me just say that there is not much "logic" or "how" to implement other logic gate based on Nand. Just observe some symmetry and follow some deduction order. $\endgroup$
    – John L.
    Jan 5, 2019 at 22:10

1 Answer 1


The nand gate is defined as follows --when and, not gates are available--

a nand b  ≡  ¬(a ∧ b)

Hence, since conjunction is idempotent, $a ∧ a ≡ a$, we have the not gate:

a nand a  ≡  ¬ a

Since negation is its own inverse, $¬ ¬ x ≡ x$, we have the and gate:

  a ∧ b
≡ ¬ ¬ (a ∧ b)                   -- double negation
≡ (¬ (a ∧ b)) nand (¬ (a ∧ b))  -- not in terms of nand
≡ (a nand b) nand (a nand b)    -- using ‘definition’ of nand

Finally, the or gate:

   a ∨ b
≡  ¬¬ a ∨ ¬¬ b                 -- double negation
≡  ¬ (¬ a ∧ ¬ b)               -- De morgan's law
≡  (¬ a) nand (¬ b)            --  using ‘definition’ of nand
≡  (a nand a) nand (b nand b)  -- not in terms of nand



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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