[Music] [Music] Hello all and welcome back to this course on digital systems. So in the last lecture, we looked at the introduction of uh introduction to Boolean variables. So in this lecture, we are going to carry on with that, and we are going to look at the topic of Boolean algebra. So the idea here is just like in algebra, there are certain rules and certain expressions that we use, right, based on which we build on more complex things. We are going to define those set of rules that we will be using quite often in Boolean algebra in order to simplify the uh Boolean expressions that we get or the Boolean functions that we have, right. So let's start with some very simple properties, actually. Okay, these properties are uh quite obvious to see, uh because we're talking about Boolean variables, and these variables can take only a value of either zero or one. So let us assume X, Y, Zed that we are going to talk about, you know, in this section here, they are all Boolean variables that means they can take value

of either zero or one. Okay, nothing in between. So the first property that is used quite often, right, is that X + 0 or X or the plus, by the way, remember I told you that it basically stands for the OR operation. X OR 0 is X, right? So essentially, this is very easy to see. You take an OR gate, right, and you connect one of the inputs to 0, then what goes through the gate is actually just X. Okay. And it's also trivially seen if you take X equal to 0, then the left-hand side is 0, right-hand side is 0. If X equal to 1, then it is just 1 OR 0, which is 1, and the right-hand side is also 1. Okay. Now, on the other hand, you also have X, the dual of this X, and 1 is also X, okay. So this is, again, it's basically taking an AND gate, tying one of the inputs to 1, then what goes through the AND gate is just X itself. This also is very trivially seen, right. Then you have

x + x' equal to 1. Now, I must mention here that in the textbooks, x' which basically stands for the complement of X, right, which I had also mentioned in the context of the inverter. x' could be represented as X apostrophe. Okay, this is purely a sort of historically has its Origins from the typewriter because you need a separate key to actually type x' A Bar Bar Bar C bar and all that but instead of that if you have X followed by an apostrophe then the apostrophe is a different key and therefore it makes it easier for you to type and therefore you could type X apostrophe y apostrophe and so on but the textbooks might use X the apostrophe symbol. We might be using x' in the question paper you might see a combination of you know X apostrophe or x' but they are all one and the same. Okay, so x + x' is 1, right, and on the other hand X and x' is equal to zero.

right so the uh second property that is X or xar right what are we saying we are basically saying you take an orgate feed one input to X the other input to xar what it basically means is at for any com ination one of the inputs has to be a one to that orgate and therefore the output of that orgate has to be a logical one right uh likewise if you look at X and xar right if you look at this property here we are talking about U taking an and gate x with one input connected to X the other input connected to xar and therefore any one input has to be zero for whatever value of x X either X is zero or xar has to be zero because in that case X has to be one right so in that case obviously the and gate is going to you know kill the output uh uh because one of them is always zero so this is also a very common property that we will be using in our theorems proofs and discussions

right, so then there are also, you know, the usual properties that carry over from algebra. For example, I could have x + y equals y + x. This actually just carries over from algebra. This is not necessarily true only in Boolean algebra. X and Y is equal to Y and X. So essentially, this also is a very straightforward thing. It doesn't, the AND gate and the OR gate, they don't differentiate the order of inputs. You can connect any input to any terminal without the logic being altered. Similarly, you also have the general idea of the distributive law, which is X into y + z equals x and y OR X and Z. And you also have the counterpart, which you can write. So we will come to this a little later, x + y z. Now, on the left-hand side, what I have written here essentially holds in algebra also. If you treat the plus and multiplication as addition and the dot as multiplication.

it holds even in algebra, but this X x + y z is equal to X + Y into x + z. This does not hold in algebra; it holds only in Boolean algebra, right? So we will come to this uh little later, right? And U, you also have another very important property: if I complement, okay, if I complement a Boolean variable twice, I will get back the original variable, okay? This uh is also, this is probably better written in terms of the uh apostrophe: X complement whole complement is equal to X, essentially, right? So these are some of the very simple and obvious properties that we will use in order to go ahead and derive many of the other laws that we are going to talk about, okay? So U, let me also list a few more properties. For example, x + x x or X is going to be X, all right? So what essentially this tells us, right, is that you take an orgate, you connect both inputs to X, right, the same input, then what goes through is just the same variable because what happens is if x is

zero then both inputs are zero, and the output is obviously zero. If x is one, both inputs are one, and therefore it's a one, right? Likewise, x and x is also X. Again, this is very specific to Boolean algebra because of the nature of values that it basically takes, okay? So we will essentially use some of these properties in order to go ahead and prove some of the important theorems, okay? Um, again, the proof, you know, we could do the proof in multiple ways because it's a Boolean algebra problem. If you have two inputs, you could just try for 2 power two, four combinations, and it works, yeah, that is also a valid proof, but when the number of inputs grows, then it becomes difficult, and therefore it's also useful to prove it in the algebraic sense, okay? So let us look at one of these things, okay? Let us look at this x + y z is equal to X + Y into x + z, okay? What is the number I have here for that number four, number four, okay, some sort of

the distributive law is slightly different in the case of Boolean algebra right this is basically called the law okay so I'll take the right hand side and we'll start okay now uh before I start let me just do one truth table operation to show you this right so this is basically three it involves three Boolean variables x y and Zed so I could write Zed okay and I will go through all eight combinations 0 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 right so I have eight combinations I'm going to evaluate the left hand side on this and the right hand side out here okay so obviously the left hand side when all three are zero right is zero because uh it's X or Y Y and Zed right the right hand side x or y or X or Zed both are zero and you're doing an and therefore it has to be a zero right

now the left hand side again for the next value. If any of Y or Zed happen to be zero, then the Y Z is going to be zero. And therefore I have U for the second option X 0 0 1. I will still get zero as my output on the right hand side. Again, it's X or Y that is zero. Then it doesn't matter what the other input to the AND gate is. So this is also zero. Now likewise X 0 1 0 where Y is one and Zed is zero. It's the same thing. You'll see exactly the same thing. Now when X is zero, Y and Zed both of them happen to be one. We are talking about Y Z, the AND gate giving you one and ORing with X. So it doesn't matter what X is after that actually. And therefore the output is going to be one here on the right hand side. The X or Y is one. X or Zed is also one. Both are one. And therefore the

and is going to give you a one here right now. Um, this again will be 0 0 right. Uh, oh no, this is not going to be 0 0 because X is one. It does not matter now. So the moment X is one, the left-hand side has to be one because it's an OR gate with X OR Y Z, right? And therefore, I'm going to simply say this is one. This has to be one on the right-hand side. Again, it's X OR Y, X OR Z, and you will get one out there as well. This has to be one one, right? And yeah, so on the right-hand side also, it's X OR Y and X OR Z, so if X is one, then both those terms evaluate one and you're adding them and has to be one. So therefore, the LHS is equal to the RHS for all values, right? But of course, we also want to ensure that we are able to prove this in an algebraic manner because we want to do algebraic manipulation for large number.

of variables going forward. So let us start with that. I take the RHS and just do X or Y and X or Zed. So what is this? I'm going to simply expand this uh and operation. Okay, I'm going to do it termwise. Okay, X and X um X and Zed X and Y Y and Zed. Right. And therefore, what I have here is we go back and look at the properties that we wrote. X and X we saw is already X. So we use property six here. Okay, I'll just put the property here. Property six here. Okay. And replace this by X or X Z plus X Y plus Y Z. Now what I do is I have three terms like this, right? Boolean terms like this. And what I'm going to do is I'm going to simply um use the um uh the commutative law. It does not matter in which order I do the R, right? I can do it in any order. So I'll do X plus X Z plus X Y Y plus Y Z. Right. Now X plus X Z I can write as

X into and 1 + z. Okay, plus x y + y z. Okay, now what do I do? I go back again, use the idea that x. Uh oh, we have not put that here. Is it, um, is that, uh, true? We haven't put it. No, so I'll write a sth property. X or 1 happens to be one. And, um, X and 0 happens to be zero, right? This is actually quite, again, it's trivial because you in an orgate any input happens to be one, the output has to be a one. Okay, so by property 7, right? Uh, property 7, I will replace this as X into 1 + z. That 1 + z is 1 + x y + y z. Okay, and therefore I will repeat the same operation that I did. I will write this as X into 1 + y + y z, right? And therefore it is X into 1 + Y, which is x + y z, which is the HS. And hence the, um, theorem is proved. Okay, so the distributive law operates.

slightly different in Boolean algebra, and this is a very useful result that we will repeatedly use going forward. Okay, now we also go to something which is, you know, a very, very important application maybe, right? So let us just say, for example, you know, this in the case if Z is equal to X in the previous expression, then I'm talking of X + XY. Okay, and this is going to be X and 1 or Y, and therefore this is X. In fact, this is what we used earlier, so this sort of absorbs Y, okay? And this is a very, very useful result for us to deal with, right? Now, likewise, if I have X into X + Y, okay, X into X + Y, then I can write this as X and X + X and Y, okay? And then this is X and X is X plus X and Y, and then I'm going to use the previous property that we just proved. This is X into 1 + Y, and therefore this is equal to X. Okay, so you know, this simple

distributive law has a very powerful implication in bul algebra, and you will be using quite often for Boolean simplification going forward. Okay, so one other very important law right in um in in the uh in Boolean algebra is to do with the idea of the complement of a function. [Music]

W4_L1_Properties in Boolean Algebra

W4_L1_Properties in Boolean Algebra