[Tutorial] Introduction to Boolean Algebra, Part VII

[Acid_Snake]

Implementing boolean functions using universal logic gates (NAND, NOR)


We have already demonstrated that NAND and NOR gates are universal, and can be use to implement basic logic gates and boolean functions. In this part of the tutorial, we are going to implement a boolean function using NAND gates and NOR gates.
This will be the function I will use:

Code: Select all

ACD + A'BC + B'C'D

When we implement it with basic logic gates we get:

basic_gates.png (3.26 KiB) Viewed 2428 times

- Implementing the function using NAND gates:
First of all, we need to get rid of the OR gate that's on the top level. The only way to do this is to negate the function so that we can apply DeMorgam's theorem:

Code: Select all

( ACD + A'BC + B'C'D )'     ->   (ACD)'  *  (A'BC)'  *  (B'C'D)'

but we don't want to change the function at all, so we're gonna negate it twice (because something negated twice leaves it as is):

Code: Select all

( ACD + A'BC + B'C'D )''   ->    ( (ACD)'  *  (A'BC)'  *  (B'C'D)' )'

Now, if you pay close attention, the entire function looks like this:

Code: Select all

(XXX *  XXX * XXX)'

This is nothing more than a simple NAND gate with three inputs.
Each of its input has the following structure:

Code: Select all

(XXX)'

which is another NAND gate. So now we have a 3 input NAND gate with other NAND gates as inputs:

Code: Select all

( (ACD)'  *  (A'BC)'  *  (B'C'D)' )'

We only have to take into consideration that NOT gates must also be implemented using NAND and we can already create the circuit:

NAND gates.png (3.42 KiB) Viewed 2428 times

In summary: to convert a function to use NAND gates all you have to do is double negate the function and apply DeMorgam's theorem once.


- Implementing the function using NOR gates:
Just as we did with NAND we're going to take advantage of involution and DeMorgam's theorem to be able to implement it using NOR gates, but the procedure is different.

Code: Select all

ACD + A'BC + B'C'D

First of all, we have an OR gate at the top level, we need it to be a NOR, so we double negate it:

Code: Select all

( ACD + A'BC + B'C'D )''

Now we have a NOR gate at top level, but the ANDs at lower level are stopping us, so we're gonna double negate them too:

Code: Select all

(  (ACD)''  +  (A'BC)''  +  (B'C'D)''  )''

Then we apply DeMorgam on each of the ANDs and we get:

Code: Select all

(  (A'+C'+D')'  +  (A''+B'+C')'  +  (B''+C''+D')'  )''

we do involution where needed and:
( (A'+C'+D')' + (A+B'+C')' + (B+C+D')' )''
Now this is a NOR at top level with three inputs, each being other NORs, so we can already draw the circuit:

NOR gates.png (4.89 KiB) Viewed 2428 times

This concludes the part about universal logic gates, next up we'll learn about special gates: XOR and XNOR.
It'll be a quick lesson as there isn't much to understand about these two.

Previous: viewtopic.php?f=37&t=33895

Advertising