[Tutorial] Introduction to Boolean Algebra, Part II

[Acid_Snake]

We're gonna go a little more deep into boolean functions by explaining some key properties that will help us simplify functions to make them more readable, and easier to understand.

Different types of Functions

Until now we've seen functions in the likes of these: AB' + B'C
As in boolean algebra, we have only two types of functions that we can directly work with: summation of products or multiplication of sums. In other words, boolean algebra can have either of these types of looks:

Code: Select all

-  AB + BC:  a summation of products
-  (A+B) * (B+C):  a multiplication of sums.

it's very easy to work with this, but boolean functions can become much more complex than that,
like this function over here:

Code: Select all

          (A(B+C) + (A+B)' + (AB + ABC) * (A+B')'

It doesn't look like any of the two types of functions I've mentioned, and we can't directly work with it to have the minterms and maxterms (more on that later), that's where a few boolean algebra properties come in handy to simplify a complex function into an easier one.

Properties

- Associative:
Example:

Code: Select all

                  (A+B)+C = A+(B+C) = A+B+C
                  (AB)C = A(BC) = ABC

There isn't much to understand here, and you should already know this from math.

- Commutative:
Example:

Code: Select all

                 A+B  =  B+A
                 A*B  =  B*A

Again, you should know this from math classes. This property is specially important as you need the variables to be in the
correct order if you want to get the minterms or maxterms out of a function (we'll see that in another chapter).

- Distributive:
Example:

Code: Select all

                   A(B+C) = AB + AC
                   A+(BC) = (A+B) * (A+C)

You should also know this from math class so lets go with the more interesting properties.

- Idempotence:
Example:

Code: Select all

                  A+A = A
                  AA = A
                  A'A' = A'

When you AND or you OR a variable with itself, you get that exact variable, very handy for simplification, here's the explanation behind this:
Let's take into consideration that A = 1, if we have A+A, then we have 1 + 1, or 1 OR 1, which is 1.
Same happens with AND: AA, if A = 1, then: 1*1 = 1 AND 1 = 1
Same goes if A = 0.

- Involution:
Example:

Code: Select all

                     A'' = A
                     (A+B)'' = (A+B)

If you negate a variable twice its just like not negating it at all: NOT A means that if A = 1, then NOT A = 0, but NOT NOT A = NOT (NOT A), we know that A = 1 so: NOT (NOT 1), NOT 1 = 0 so: NOT (0), and NOT 0 = 1, we get A's original value.
You may be wondering if there is something more to this than just simplification, there is, this property is very useful for implementing boolean functions using NAND or NOR, which are universal gates and are cheaper to make because you are using the same gates for the entire function rather than different gates, but we'll get to that on another part of the tutorial as we still don't even know how to implement boolean functions using basic gates.

- Absorption:
Example:

Code: Select all

                  A+AB = A
                  AB+ABC = AB
                  A+A'B = A+B
                  A'B'  + A'B'C = A'B' + C

This one is a bit harder to understand and most of the time to even notice on an actual function (specially since functions get more and more complex), but the basic understanding is that if you have an OR between a variable A and an AND between this variable A and some other variables then the A in the AND gets absorbed and becomes unneeded.
Here's an example of why this works, imagine this function: A + AB
We give A the value 1 and B the Value 0:

Code: Select all

       A + AB =   1 + (1*0)   =  1 + 0 = 1
       ||
       A + B   =   1 + 0 = 1

- Neutrals:
Example:

Code: Select all

                  A+1 = 1
                  A*0 = 0
                  A*A' = 0
                  A+A' = 1

Any number that is OR'ed with 1 will give you 1, and any number that is AND'ed with 0 will give you 0, then any number AND'ed with its negated one will give you 0 since you know that one of them will be 0, similar thing happens if you OR an number by its negated version, you know one of them will be 1 so the result will be 1. There is nothing to explain here, this is how the AND and the OR work and you should know this by now.

- DeMorgam's Theorem:
Example:

Code: Select all

                    (A+B)'    =  A'B'
                    (A*B)'    =  A'+B'

This is one of the most widely used theorems in boolean algebra as it allows us to turn an AND into a NOR and viceversa, it is also used, in conjunction with the Idempotence property to create NAND or NOR gates from boolean functions (more on that later, a lot later). The idea here is that if you have an OR between two or more variables and everything is negated, then you can turn it into an AND with all of it's variables negated, same happens with an AND that is completely negated, you can turn it into an OR with each variable negated. Here's an example of why this works giving the variable A the value 1 and B the value 0:

Code: Select all

(A*B)'  =  (1*0)'  =  (0)'  =  1
(A*B)'  =  A'+B'   =  1' + 0'  =  0 + 1 = 1

or using an OR and turning it into an AND:

Code: Select all

(A+B)'  =  (1+0)'  =  (1)'  =  0
(A+B)'  =  A' * B'  =  1' * 0' =  0 * 1 = 0

Also, take into consideration that if, after applying DeMorgam's theorem, a variable gets double negated, you have to apply idempotence:

Code: Select all

 (A+B')'   =   A'  *  B''  =  A'  *  B

Now that we know all important properties of boolean algebra we're going to my initial plan: use them to simplify a complex function that, at first glance, can't be worked with to make it easier to handle.
Do you remember the function I showed earlier that wasn't in any standard form and we couldn't directly work with?
this one:

Code: Select all

(A(B+C) + (A+B)' + (AB + ABC) * (A+B')'

Now that we know all these properties and theorems we can apply them here to make this ugly function and bit better.
First thing I notice is how the function will be a summation of products, it'll be in the form: A + B + C + .....
This means that the brackets will somehow turn into products, so I will work with them separately.
- Let's start with the first one: (A(B+C), we can use the distributive property: AB+AC
- That was easy, now lets go to the next one: (A+B)'
the first thing I notice is that everything is negated, this means I can apply DeMorgam's theorem and turn that into this:
A'B'
- Now that's done with, let's see the other one: (AB + ABC)
this one has to ways to be done: we can use associative and end up with this: AB + ABC
but then, we also know that the whole bracket is multiplied with (A+B')', so associative won't work here.
Is there anything else that can be done? at this point if you haven't figured it out you can simply leave it like that, but
there is one thing you can do: absorption. The end result would be: (AB + C)
If you don't do this it's ok, in the end the function will still look standard, but it won't be simplified to the max,
but we don't want to simplify it, we want to make it look standard, so that we can then simplify it
using an automated method called Karnaugh, we might or we might not get to see this, depends on the overall reviews
of this tutorials.
- Overall the function is starting to look like this:

Code: Select all

 AB+AC + A'B' + (AB+C) * (A+B')'

- Finally we have the last bracket: (A+B')'
First thing I notice is that we can apply DeMorgam's theorem again to turn that unwanted OR into an AND: A' * B''
Now that I've applied the theorem, I notice that B is double negated, so I use idempotence: A' * B
- The function has resulted in:

Code: Select all

AB+AC + A'B' + (AB+C) * A'B

- One more thing to do, get rid of that bracket with that multiplication, how do we do it? at first glance the function's
mighty look could confuse you and you could end up banging your head on how to solve that, but it's quite simple
if you remember one of the first two properties: distributive, remember? A(B+C) = AB+AC. Using this we get that:

Code: Select all

 (AB+C) * A'B  =  A'BAB + A'BC

We know that A'A = 0 and that BB = B, so A'BAB = 0B = 0, so the entire thing drops down to just the A'BC part.
- In the end, the entire function becomes:

Code: Select all

AB+AC + A'B' + A'BC

Now this is more like what we've worked with, isn't it?

As an exercise, I want you to simplify the following functions into a standard form:

Code: Select all

- (A(B'C + BC')) + CD'B
- (A + B')' + (CD)
- ((A'+B)*(C+D)') + (A + B)'

Previous: viewtopic.php?f=37&t=33276
Next: viewtopic.php?f=37&t=33566

Advertising

[pspfanMOHH]

By any numbers the OP means 1 or 0 since its on or off, so if A = 1 then B is 0, remember that throughout the tutorial, if it helps turn the variables to numbers (only numbers you can use is 1 or 0). Everything else you learned in math, the properties of math, except the OP taught few more extra, memorize them like the pemdas chart. Last thing the extra methods/theorms you learn here won't work with numbers 2 or above since these were made for 0 and 1.

Answer Key:

- (A(B'C + BC')) + CD'B = AB'C + ABC' + BCD'
- (A + B')' + (CD) = A'B + CD
- ((A'+B)*(C+D)') + (A + B)' = A'C'D' + BC'D' + A'B'


OFF TOPIC: Every morning I wake up I read one of boolean tutorial since the past 2 days. Was out the whole day yesterday after I finished part 1, came back went to sleep, woke up right now and did this. (It helps before or after sleep)

Advertising

[Acid_Snake]

- (A(B'C + BC')) + CD'B = (AB'C + ABC') + CD'B

it's correct, but you have to apply associative to completely finish it: AB'C + ABC' + CD'B
and, while it's not needed right now, it will come in handy to get used to applying commutative to place all variables in the correct order: AB'C + ABC' + BCD'

- (A + B')' + (CD) = A'B + CD

that's correct

- ((A'+B)*(C+D)') + (A + B)' = ((A'+B)*C'D') + A'B'

that's not finished yet

[pspfanMOHH]

- (A(B'C + BC')) + CD'B = (AB'C + ABC') + CD'B

it's correct, but you have to apply associative to completely finish it: AB'C + ABC' + CD'B
and, while it's not needed right now, it will come in handy to get used to applying commutative to place all variables in the correct order: AB'C + ABC' + BCD'

I skipped that because it would look like letters all over and unorganized.

- ((A'+B)*(C+D)') + (A + B)' = ((A'+B)*C'D') + A'B'

that's not finished yet

Yes I wasn't finished typing, "(A'C'D' + BC'D') + A'B' "

[Acid_Snake]

Yes I wasn't finished typing, "(A'C'D' + BC'D') + A'B' "

that's better, but remember to remove all brackets

I skipped that because it would look like letters all over and unorganized.

the standard for of a boolean function is AB+AB, or (A+B)*(A+B), that function is of the first type so it's best to remove all brackets.

[pspfanMOHH]

Done, is there another part? (I hope I am not spoiling with the Answer Keys)

[Acid_Snake]

I will be making part III and part IV soon but not today

[pspfanMOHH]

Any number that is OR'ed with 1 will give you 1

Any Number means 0 since its on = 1 and off = 0 so its 0+1 = 1, the any number part gets confusing if you forget on and off while reading this, recommend a reminder for the reader.

In DeMorgam's Theorem your basically distributing ' (NOT) to both variables/numbers in the brackets

Also if you come across something like this ((A'+B)*C'D') you can distribute C'D' to A'+B. In 7-8th grade you should have learned that multiple variable/number can be distributed.

Code: Select all

(AB+C) * A'B  =  A'BAB + A'BC

Whats happening here is your distributing A'B to (AB+C) which makes it A'BAB +A'BC, and since its AND(Multiplication) you can reorganize it differently and still get the same answer.
A'BAB = A'ABB, A'A should give you 0 because either way you will be multiplying by 0, and BB = B so 0B is 0 and doesn't count. All your left with is A'BC in you problem so its.

Code: Select all

AB+AC + A'B' + A'BC

(Reason for explaining this is because OP kind of jumped there and reading it once might be confusing)

[3rdroyd]

(AB+C) * A'B = A'BAB + A'BC

NIce tut but...
I dont understand this!!!

I havn't fugure it out how to apply this property >>> A(B+C) = AB+AC on this one>>> (AB+C) * A'B = A'BAB + A'BC

So its (AB+C) to A'BAB ??? if true: Why A became a NOT A, (A') . Then why 2 B's and 2 A's >>> (A'BAB)???

im going to have a headache and want to understand this soooo badly, i think i will have nightmares tonight

[Acid_Snake]

(AB+C) * A'B = A'BAB + A'BC

NIce tut but...
I dont understand this!!!

I havn't fugure it out how to apply this property >>> A(B+C) = AB+AC on this one>>> (AB+C) * A'B = A'BAB + A'BC

So its (AB+C) to A'BAB ??? if true: Why A became a NOT A, (A') . Then why 2 B's and 2 A's >>> (A'BAB)???

im going to have a headache and want to understand this soooo badly, i think i will have nightmares tonight

lets use variable change so it becomes clear.

We want to demonstrate that (AB+C) * A'B = A'BAB + A'BC

first thing I'm going to do is compare (AB+C) * A'B with (X+Y) * Z
therefore, we have:
X represents AB
Y represents C
Z represents A'B

since (X+Y) * Z is easier to see, we can use the property easier:
(X+Y) * Z = X*Z + Y*Z

Now we just change it back to the original values of X, Y and Z and we get:
X*Z + Y*Z -> AB*A'B + C*A'B
in other words: ABA'B + CA'B
so far so good, but this is not done yet.
If you look closely in the first AND we have ABA'B
if you do X AND X', the result is always 0
so:
ABA'B + CA'B = 0 + CA'B -> CA'B - > (we reorganize the variables) A'BC
the result result:
(AB+C) * A'B = A'BC