# How to “logically” solve boolean logic

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

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

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!