# Boolean Algebra - Postulates

Movie(s) created by Tim Fiegenbaum at North Seattle Community College.

*Related Links*

## Lecture Transcript

We're completing 15.1, and we're looking at Boolean algebra postulates. Boolean algebra can be used to solve complex expressions in order to simplify a logic circuit. Most modern designs and nearly all complex logic circuits are internal to ICs. Boolean algebra has a number of basic rules called postulates or identities and should be studied closely to understand their functions and applications. Thirty-six of these are listed at the end of section 15-1. They are listed for reference purposes. Your text doesn't go into detail about them, but we will be referring to them as we go through this chapter.

Boolean algebra postulates to reduce a Boolean expression and we're going to be doing this. We will be reducing a Boolean expression and this procedure is helpful. Count the number of vincula above each variable and above each operator. These are the knot symbols. Variables with an odd number of vincula have a single vinculum in the final expression, operators with an even number remain as they are, whereas, operators with an odd number will change. We're going to do some examples of these and we'll try to make a little more sense of this statement. Use parenthesis where necessary to ensure that all variables that were grouped in the initial expression remain grouped after the simplification process. Your textbook has six examples at the end of this chapter. I'm going to go through each of these six and give a little more detail, in fact, I'll give a lot more detail than your book gives on these expressions.

The first one looks like this: A or B or C or D, and then we have two knot signs. If we were going to build a circuit based on that expression it would look like the expression right here. We would have a nor gate, notice the nor because the entire equation is or but that it is completely knotted so that would indicate a nor expression, and then the D here, input D, is also[inaudible 0:02:36], so I'd have an additional invertor right here. The purpose of Boolean reduction is to simplify this expression. What we would do we would come in and we would break all of the knots symbols in order to separate each variable and each operator. What we're going to do is we're going to split it and we'll split it here, and we'll split it here, and we'll split it here, maybe a better word is break it. We'll break the vinculi in these three places. In doing this, some things will happen to the equation. When I break a single line it's going to change the operator. It was or now it will become and. When it's a single, you change it; if it's double, if it's even, it remains the same. We also were breaking this so that our knots now instead of having a knot over the entire equation we would just have a knot like this right here. This is equivalent to that.

Then, we'll come to the next one and we will do the same with it. We'll break it and we'll change the operator, and this will become C know, and then this one also, and this one, notice, there are two knot symbols. Each of these is an invertor, so if you invert something twice it's back to the original sign. What we could do is just cancel this, and then this has no inversion symbol over it. This is the Boolean simplification of this expression. We could do something like this if we had our four inputs, A, B, C, and D, and if we had an invertor here, an invertor here, an invertor here, and then we had our final output here, this would be the simplified version of this particular expression.

We'll go to the next one. Here we have a little bit more complexity here. This is the circuit, we'll note. Let's just look at the basis here. Let's see, here we have A or B and it is knotted, so this expression right here A or B, and then we have the knot symbol over it. Then, here we have C or D, and it is knotted, so that would be this expression right here. Then, they are combined with the and expression right here and then the entire expression is knotted so that would be this right here. This would be the circuit expression for this. Let's go in and simplify this. Again, we will break it here, here, and here. Let's see, here we've got double lines so the final expression we'll have an A and a B, but there will be no inversion because they cancel. We will keep the parenthesis because if they are grouped in the original expression you need to group them in the expression that follows. This will remain an or because there are an even number of vinculi so they would remain the same. Here, we have an and now this would become an or. In this expression, we would have C plus D and let's see, we'd have the operator remains the same and we cancel that. We have something that looks kind of like this. If we looked at those rules, we would see they have this expression actually was simplified to A plus B plus C plus D. We would, one, two, three, four, A, B, C, D, this expression would simplify to this. This one we actually do see. It is quite a bit simpler. Some of these you look at them and you think they didn't simplify very much, but this one, in fact, does simplify significantly.

Third one, here we have A plus BC plus D or A or BC or D. We would break it here, and here, and here. Let's see this one would be A, and this one would be, let's see, we'd have B or C, and we need to keep the bracket. This would be and D. Given this expression, A and D are both inputs here. We could, we could since these are both and we need to do something here before we continue, we need to make sure that we retain the knots here. This would be a B knot and this would be a C knot, and this would be a D knot, and then the A would be only one that's not knotted. Now we'll continue. We could combine these two A, D knot times B knot plus C knot. Some would just leave it like this. We could go a little further. We could multiply this times these two so that would give us A, D knot, B knot, plus A, D knot, C knot. That would simplify to, let's see, we would have two and gates and they would feed into an or gate kind of like this. There'd be three inputs here, three inputs here, and that'd be basically our simplification. I hadn't included all the knots, but you get the idea. Here's an and, here's an and, and this would be an or.

This is number four here, and this is our circuit. We're going to split it here and here. Let's see, this would be A knot plus B knot, and then that would anded with C. Now let's take a look at this, let's make sure we've got this right, A and B, so this would be A knot plus B knot, and then this would be anded and that would be AC. Let's see, what can we do with this? Actually, we would have a grouping here because these are together. If we wanted to simplify this further, we could say we take this anded with this, so we can end up with A knot, C plus B knot, C. That would simplify to two and gates or together. Let's see, if we had an A, let's go ahead and then let's put B here and let's put C here. C is going to be actually to be common to both and the B would be here. The B would be knotted. The A would be knotted. I believe that's it. A, A knot, C, B knot, C, and it's going into an or. This would be our simplified expression o f this expression Boolean expression or this would be our simplified circuit of this Boolean expression.

We're in number five. Let's just go ahead and being breaking this up. We would break it here, and here, and here, and here. Here were have AB, and so we're going to say we will keep the A, B, and let's see, we'll keep the expression and this will retain the knot, and that will be anded with, let's see, we will have C knot plus D knot plus E. The E will not be knotted because we have the double inversion here. What can we do with this? We've got AB knot and we do need to keep the parentheses since this was a grouping. We need to keep that grouping together. We have AB anded with these, and so effectively that's multiplying so we could simplify this to A knot, BC knot for the first one, and then A knot, B, D knot plus A knot, BE. We would have three and gates with three inputs and they would fee into an or gate such as this. That is problem number five. I don't have the detail here, but the simplified circuit would look like this.

Then, the final circuit, number six, we're just going to go in and begin breaking this. We'll break it here, here, here, and here. The first part would be A knot and we would keep the grouping, and we're breaking here so that would become the operator would change, and here, let's see, we would retain the B knot but the C would not be knotted. Since there's a double here, we would retain the same operative so that would be BC, and then this would be or'ed with, and again, we're going to have D, in this case. We're going to retain the operator because of the double, and then the E, and then this would be knotted. This have this knotted and we retain the B knot. All the other knotting are simplified out of the equation. In looking at this we have A anded with B and C, so this could be simplified to A and, or A or, or A knot, B, knot C, and that would be or'ed, in fact, maybe just say like this, remove those parentheses, A knot, B knot, C, plus D or E knot. That would be our simplified equation, and we would have and gate here with three inputs plus D and E. This would go into an or gate and then we would have a separate D and an E that would feed, and then we would have our or's. If we label all this, A, B, C, the A would be knotted, the B would be knotted, and this would be D, and this would be E, and the E would be knotted. That would be our simplified expression.

These take some getting used to. You're going to have to do some of them just to get the feel of them. After you do a few, they will become a lot easier. Throughout the remainder of this chapter we will be playing with these Boolean expressions. Just jump in and start playing with them and they will eventually make sense to you.

Boolean algebra postulates to reduce a Boolean expression and we're going to be doing this. We will be reducing a Boolean expression and this procedure is helpful. Count the number of vincula above each variable and above each operator. These are the knot symbols. Variables with an odd number of vincula have a single vinculum in the final expression, operators with an even number remain as they are, whereas, operators with an odd number will change. We're going to do some examples of these and we'll try to make a little more sense of this statement. Use parenthesis where necessary to ensure that all variables that were grouped in the initial expression remain grouped after the simplification process. Your textbook has six examples at the end of this chapter. I'm going to go through each of these six and give a little more detail, in fact, I'll give a lot more detail than your book gives on these expressions.

The first one looks like this: A or B or C or D, and then we have two knot signs. If we were going to build a circuit based on that expression it would look like the expression right here. We would have a nor gate, notice the nor because the entire equation is or but that it is completely knotted so that would indicate a nor expression, and then the D here, input D, is also[inaudible 0:02:36], so I'd have an additional invertor right here. The purpose of Boolean reduction is to simplify this expression. What we would do we would come in and we would break all of the knots symbols in order to separate each variable and each operator. What we're going to do is we're going to split it and we'll split it here, and we'll split it here, and we'll split it here, maybe a better word is break it. We'll break the vinculi in these three places. In doing this, some things will happen to the equation. When I break a single line it's going to change the operator. It was or now it will become and. When it's a single, you change it; if it's double, if it's even, it remains the same. We also were breaking this so that our knots now instead of having a knot over the entire equation we would just have a knot like this right here. This is equivalent to that.

Then, we'll come to the next one and we will do the same with it. We'll break it and we'll change the operator, and this will become C know, and then this one also, and this one, notice, there are two knot symbols. Each of these is an invertor, so if you invert something twice it's back to the original sign. What we could do is just cancel this, and then this has no inversion symbol over it. This is the Boolean simplification of this expression. We could do something like this if we had our four inputs, A, B, C, and D, and if we had an invertor here, an invertor here, an invertor here, and then we had our final output here, this would be the simplified version of this particular expression.

We'll go to the next one. Here we have a little bit more complexity here. This is the circuit, we'll note. Let's just look at the basis here. Let's see, here we have A or B and it is knotted, so this expression right here A or B, and then we have the knot symbol over it. Then, here we have C or D, and it is knotted, so that would be this expression right here. Then, they are combined with the and expression right here and then the entire expression is knotted so that would be this right here. This would be the circuit expression for this. Let's go in and simplify this. Again, we will break it here, here, and here. Let's see, here we've got double lines so the final expression we'll have an A and a B, but there will be no inversion because they cancel. We will keep the parenthesis because if they are grouped in the original expression you need to group them in the expression that follows. This will remain an or because there are an even number of vinculi so they would remain the same. Here, we have an and now this would become an or. In this expression, we would have C plus D and let's see, we'd have the operator remains the same and we cancel that. We have something that looks kind of like this. If we looked at those rules, we would see they have this expression actually was simplified to A plus B plus C plus D. We would, one, two, three, four, A, B, C, D, this expression would simplify to this. This one we actually do see. It is quite a bit simpler. Some of these you look at them and you think they didn't simplify very much, but this one, in fact, does simplify significantly.

Third one, here we have A plus BC plus D or A or BC or D. We would break it here, and here, and here. Let's see this one would be A, and this one would be, let's see, we'd have B or C, and we need to keep the bracket. This would be and D. Given this expression, A and D are both inputs here. We could, we could since these are both and we need to do something here before we continue, we need to make sure that we retain the knots here. This would be a B knot and this would be a C knot, and this would be a D knot, and then the A would be only one that's not knotted. Now we'll continue. We could combine these two A, D knot times B knot plus C knot. Some would just leave it like this. We could go a little further. We could multiply this times these two so that would give us A, D knot, B knot, plus A, D knot, C knot. That would simplify to, let's see, we would have two and gates and they would feed into an or gate kind of like this. There'd be three inputs here, three inputs here, and that'd be basically our simplification. I hadn't included all the knots, but you get the idea. Here's an and, here's an and, and this would be an or.

This is number four here, and this is our circuit. We're going to split it here and here. Let's see, this would be A knot plus B knot, and then that would anded with C. Now let's take a look at this, let's make sure we've got this right, A and B, so this would be A knot plus B knot, and then this would be anded and that would be AC. Let's see, what can we do with this? Actually, we would have a grouping here because these are together. If we wanted to simplify this further, we could say we take this anded with this, so we can end up with A knot, C plus B knot, C. That would simplify to two and gates or together. Let's see, if we had an A, let's go ahead and then let's put B here and let's put C here. C is going to be actually to be common to both and the B would be here. The B would be knotted. The A would be knotted. I believe that's it. A, A knot, C, B knot, C, and it's going into an or. This would be our simplified expression o f this expression Boolean expression or this would be our simplified circuit of this Boolean expression.

We're in number five. Let's just go ahead and being breaking this up. We would break it here, and here, and here, and here. Here were have AB, and so we're going to say we will keep the A, B, and let's see, we'll keep the expression and this will retain the knot, and that will be anded with, let's see, we will have C knot plus D knot plus E. The E will not be knotted because we have the double inversion here. What can we do with this? We've got AB knot and we do need to keep the parentheses since this was a grouping. We need to keep that grouping together. We have AB anded with these, and so effectively that's multiplying so we could simplify this to A knot, BC knot for the first one, and then A knot, B, D knot plus A knot, BE. We would have three and gates with three inputs and they would fee into an or gate such as this. That is problem number five. I don't have the detail here, but the simplified circuit would look like this.

Then, the final circuit, number six, we're just going to go in and begin breaking this. We'll break it here, here, here, and here. The first part would be A knot and we would keep the grouping, and we're breaking here so that would become the operator would change, and here, let's see, we would retain the B knot but the C would not be knotted. Since there's a double here, we would retain the same operative so that would be BC, and then this would be or'ed with, and again, we're going to have D, in this case. We're going to retain the operator because of the double, and then the E, and then this would be knotted. This have this knotted and we retain the B knot. All the other knotting are simplified out of the equation. In looking at this we have A anded with B and C, so this could be simplified to A and, or A or, or A knot, B, knot C, and that would be or'ed, in fact, maybe just say like this, remove those parentheses, A knot, B knot, C, plus D or E knot. That would be our simplified equation, and we would have and gate here with three inputs plus D and E. This would go into an or gate and then we would have a separate D and an E that would feed, and then we would have our or's. If we label all this, A, B, C, the A would be knotted, the B would be knotted, and this would be D, and this would be E, and the E would be knotted. That would be our simplified expression.

These take some getting used to. You're going to have to do some of them just to get the feel of them. After you do a few, they will become a lot easier. Throughout the remainder of this chapter we will be playing with these Boolean expressions. Just jump in and start playing with them and they will eventually make sense to you.