[Tutorial] Introduction to Boolean Algebra, Part V

[Acid_Snake]

Implementing boolean functions using basic logic gates (AND, OR, NOT)
In this part of the tutorial, and as part of the plan for these tuts, I will be diving into the world of logic circuitry: the real world implementation of boolean algebra, who would have thought that math would actually have a real usage?


Logic gates
As we've seen that in boolean algebra there are three main operations: AND, OR, NOT.
For each of these there is a piece of basic circuitry that implements them on the hardware level, called Logic gates, that have the same name.
When it comes to boolean algebra, a circuit, a function or minterms are all the same, and given one of them, you can easily get the other two. So we're going to analyze circuits to be able to turn them into functions, and functions to be able to turn them into circuits, we'll do the latter first.


AND Logic Gate

Y = A AND B -> A*B -> AB


OR Logic Gate

Y = A OR B -> A+B


NOT Logic Gate

Y = NOT A -> A'


A Variable
In my circuits, variables will look like this:

logic_variable.png (327 Bytes) Viewed 2404 times

1's and 0's
In some cases (specialy with multiplexors and decoders, we'll see them later) there is a need to have a constant value: 0 or 1.
I'll represent 0 as Ground and 1 as a voltage source, like in this picture:

1_0.png (515 Bytes) Viewed 2404 times

Function -> Circuit
Let's see some examples of a function implemented using Logic Gates.
We're gonna start with a very basic function: AC+BD
This function has 4 distinct variables, so that's what we make first:

circuit-1.png (1.15 KiB) Viewed 2404 times

Next thing I see is that there are two AND's, one between A and C, and the other between B and D, so that's what I write:

circuit-1-1.png (1.3 KiB) Viewed 2404 times

I connect the ANDs to the variables as needed, I need to connect A and C to the same AND, and B and D to the other AND:

circuit-1-2.png (1.44 KiB) Viewed 2404 times

Lastly, we know there is an OR between the two ANDs:
AC+BD -> (A AND C) OR (B AND D)
So we write an OR, and we conect the two ANDs to it:

circuit-1-3.png (1.89 KiB) Viewed 2404 times

Circuit -> Function
Lets try to convert the following circuit into a boolean function:

circuit-2.png (2.21 KiB) Viewed 2404 times

Lets go step by step.
- The first thing I notice is that the circuit has an OR in its top level with three inputs, so it will look like this:
(something) OR (something) OR (something), or rather:

Code: Select all

(something) + (something) + (something)

- Connected to the OR there are three AND's, each of them having two inputs, so we now have a better idea of what the
function will look like:

Code: Select all

(something AND something)  +  (something AND something)  +  (something AND something)

or rather:

Code: Select all

(something * something)  +  (something * something)  +  (something * something)

- Now we analyze each AND separately in whatever order you want (commutative), I'll start from top to bottom:
--- In the first AND I can clearly see A connected to it on the first input, on the second input if I follow the connection line
I can see that B is connected to it, the resulting function is:

Code: Select all

(A*B)+(something*something)+(something*something)

--- In the second AND, if I follow the two inputs I realize the AND is connected to B and D, the function now looks like this:

Code: Select all

 (A*B)+(B*D)+(something*something)

--- The last AND has the first input connected to the line where D comes from, so the first input is D, the second input
clearly comes from C, the resulting function is:

Code: Select all

(A*B)+(B*D)+(D*C)

- Now that we have the function we apply associative in order to make the function cleaner:

Code: Select all

AB+BD+DC

Now that we have the function that best describes this circuit, it's up to you to decide if you want to simplify it using Karnaugh or not.



For practicing, try turning these circuits into functions:

circuit-3.png (1.35 KiB) Viewed 2404 times

circuit-4.png (1.57 KiB) Viewed 2404 times

circuit-5.png (2.26 KiB) Viewed 2400 times

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

Advertising

[Xian Nox]

Quick note: said logic gates are based on the US standards. Others seem to also use the newer IEC standard. Here's a comparison:

iec: (rectangular shapes) according to IEC 60617-12, adopted by various national standards
us: (distinctive shapes) according to ANSI/IEEE Std 91-1984 and ANSI/IEEE Std 91a-1991
de: (superseded) according to german standard DIN 40700

Advertising