[Tutorial] Introduction to Boolean Algebra, Part VI

[Acid_Snake]

Universal logic gates: NAND and NOR


What are NAND and NOR gates?
We've already seen the basic logic gates AND, OR, NOT and their representation both on paper and on circuit.
Today, I will introduce two new logic gates: NAND, NOR.
These two gates are easier to understand as: NOT AND (NAND) and NOT OR (NOR).
As the name implies, a NAND gate is a normal AND gate with the output negated, same for NOR.
On paper, NAND and NOR can be seen as:

Code: Select all

NAND:      (A*B)'
NOR:        (A+B)'

On circuit:

NAND-NOR.png (2.45 KiB) Viewed 754 times

If you remember De Morgam's theorem, we can convert NAND and NOR to basic logic gates:
- NAND: (A*B)' -> using DeMorgam -> A'+B'
- NOR: (A+B)' -> using DeMorgam -> A'*B'
So we can also implement NAND as an OR gate with the input negated and NOR as an AND gate with the input negated.
We're gonna use all these to learn why NAND and NOR are universal logic gates and how to implement a function using only one of them (which is a lot cheaper than using different gates).


Why are they universal?
First of all, the term universal gate means that, with only one gate, you can implement both AND, OR and NOT, depending on how they are connected. Lets start with NAND and how to implement AND, OR, NOT with it.


NAND gates

- Implementing NOT using NAND:
We already know the basic equation of NAND is (A*B)', if we connect both inputs to the same variable we have: (A*A)'
Now, we know from boolean properties that A*A = A, so (A*A)' = (A)' -> A', so now we can make a NOT gate to negate any variable:

NAND as NOT.png (876 Bytes) Viewed 754 times

- Implementing AND using NAND:
Again, we're gonna use some boolean properties to turn a NAND into an AND. We can do this using involution: a variable negated twice is like not being negated at all:
(A*B)'' --> (A*B)
So all we have to do is negate the output of NAND to make an AND, we already know how to make a NOT gate from NAND, so this is easy:

NAND as AND.png (1.42 KiB) Viewed 754 times

- Implementing OR using NAND:
As I showed before, we can use DeMorgam to turn NAND: (A*B)', into OR: A'+B'.
Problem is, A and B come out negated, so we need to negate them again to use involution:

Code: Select all

(A' * B')'   ->  A'' + B''  ->  A+B

So all we have to do is negate the input of NAND, and we already know how to mane NOT out of NAND:

NAND as OR.png (1.62 KiB) Viewed 754 times

NOR gates

- Implementing NOT using NOR:
Just as we did with NAND, we can make NOT gates with NOR by connecting all inputs to the same variable:

Code: Select all

(A+A)'  =  A'

NOR as NOT.png (769 Bytes) Viewed 754 times

- Implementing OR using NOR:
Just as with NAND->AND, NOR->OR simple requires negating the output to use involution:

Code: Select all

(A+B)''   ->   A+B

NOR as OR.png (1.33 KiB) Viewed 754 times

- Implementing AND using NOR:
As I showed before, we can use DeMorgam to turn the NOR into an AND:

Code: Select all

(A+B)'   ->  A' * B'

So all we have to do is negate the input of the NOR to obtain an AND:

Code: Select all

( A' + B' )'   ->   A'' * B''  ->  A * B

NOR as AND.png (1.66 KiB) Viewed 754 times

With all this, you can easily replace ANDs, ORs and NOTs in a circuit to a universal logic gate, but it's very hard and highly ineffective. There is a way to turn a basic logic function into a universal one, way faster than doing one by one replacement of the gates and a lot more simplified. We'll see that in the next lesson.


Previous: viewtopic.php?f=37&t=33736
Next: viewtopic.php?f=37&t=33897

Advertising