0
$\begingroup$

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

$\endgroup$
  • $\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$ – pushpen.paul Jan 5 at 19:14
  • $\begingroup$ Have you tried writing a program to conduct a exhaustive search by brute force? $\endgroup$ – Apass.Jack Jan 5 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$ – Apass.Jack Jan 5 at 22:10
1
$\begingroup$

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

Neato!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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