How to implement a function using just NAND or NOR logic gates

Question

I am trying to understand the process of creating combinatorial circuits. I understand that first we document the inputs and outputs, then create minterms and max terms, then push them into a k-map and get a function as an output. This function can then be implemented using logic gates.

The problem I have is, I don't understand the logic behind converting the equation that we got, such that I can implement the same circuit using just NAND or nor logic gates.

The image is from my book for converting a half adder circuit. I understand the steps taken but don't understand the reason why they took them. Thanks for the help.

Answer 1

Start with your equation as normal...
Y = ABC+DEF+GHI+JKL...

Repeatedly apply de'Morgan's Theorem to convert all AND and OR and NOT operations into either NAND or NOR as required.

AND(A,B,C,D...) = NAND(NOT(A),NOT(B),NOT(C),NOT(D)...)

OR(A,B,C,D...) = NOR(NOT(A),NOT(B),NOT(C),NOT(D)...)

NOT(A) = NOR(A,0)

NOT(A) = NOR(A,A)

NOT(A) = NAND(A,1)

NOT(A) = NAND(A,A)

Answer 2

Although the other answers do explain the process to use deMorgan's to convert to NAND/NOR, they don't really answer the question if you look at the graphic of a half adder.

$$S = A \overline B + \overline A B$$ $$C = A B$$

deMorgan's, you get:

$$S = \overline {\overline {A \overline B} \cdot \overline {\overline A B}}$$ $$C = \overline {\overline{A B}}$$

The half adder constitutes 7 NAND gates because each of the AB terms is unique.

$$S = A \overline B + \overline A B$$ $$S = A \overline B + 0 + \overline A B + 0$$ $$S = A \overline B + A \overline A + \overline A B + B \overline B $$ $$S = A (\overline A + \overline B) + B (\overline A + \overline B) $$ $$S = A (\overline {A B}) + B (\overline {A B}) $$ $$S = \overline {\overline {A (\overline {A B})} \cdot \overline {B (\overline {A B})}} $$ $$C = \overline {\overline{A B}}$$ The AB term is reused and now the half adder is 5 gates.

^{simulate this circuit – Schematic created using CircuitLab}

---

So to answer the question.

These examples are NOT good for learning how to convert to NAND/NOR gates.

These circuit are examples of the types of optimizations designers used to go through to optimize designs to minimize gates.

Answer 3

The three fundamental logical operations (at least for Boolean logic) are the AND, the OR and the NOT functions. If you do these you can do anything.

As it happens, if you have a collection of NAND gates you are able to all of these. A 2-input NAND gate with both inputs tied together, or one input tied low, is an inverter and performs NOT. Furthermore, DeMorgan's Theorem tells you that, with inverted inputs, a NAND gate becomes functionally an OR gate. So you can do anything with just NAND gates. Likewise, DeMorgan's Theorem applies equally to NOR gates - invert the inputs and they become an AND gate.

Typically, a logic IC will use either type as a basic building block, and repeat the gates as necessary. The classic 7400 family and its bipolar descendants used a multi-emitter NPN transistor which functioned just fine as a NAND gate. Keeping to a single building block simplified chip design back when it was all done by hand, and allowed for straightforward process tweaking where using multiple gate types would have made life difficult.