welcome to lecture five uh which is a continuation of our discussion of Boolean algebra and the uh first problem I'd like to look at today is problem two this is in your book 2.6a which is um uh we're asked to write AB or C Prime D Prime as a product of sums um right now it's in a sum of products form you can see the uh plus sign indicates that we have a sum and uh this is a sum of simple products of Boolean variables so this is a sum of products form similar to what we discussed in lecture 4 uh and we want to convert that to a product or sums form and I'll show you uh one convenient way to do that uh but before I do I want to make an observation uh the observation is just this very simple observation if x is any Boolean variable and we complement it twice we get back that same Boolean variable uh to to prove that that's true uh we can we can make a truth table if you wish so in this case our function that we want to analiz is X compliment complement so we put the function that we want to analyze over here on the right that that's that's the way the truth tables will go is that the function that we want to evaluate or analyze will go on the extreme right column and all of the independent VAR variables in the problem will go to the extreme left and in this case there's only one independent variable and that's X then intermediate columns are used as uh intermediate points in the calculation so in this case there's only one independent variable in that sex there's no y or Z or a or b or anything like that there's only one independent bran variable X and so that's all we have over here in the leftmost column and since it is a Boolean variable it can have two values 0 and one now um perhaps some people don't even need the intermediate column of X complement perhaps they can see immediately what x complement compliment is but just in case you don't see that I'll I'll use this intermediate column of X compliment and of course if x is zero then X complement is one and if x is 1 then X complement is zero and then if we complement those numbers one more time well the complement of one is zero and the complement of zero is one so sure enough we can see that the column for X compliment complement over here the rightmost column is identical to the leftmost column which is the column for x and this is true for every possible value for x and therefore we can say that these two are the same so in other words we have verified here by the truth table that X compliment compliment is indeed uh equal to X itself now the reason that I made this observation is that one convenient way for converting a sum of products form into a product of sums form is to use the fact that the complement of the compliment is the variable itself so let me show you what I'm talking about okay so we start off with AB or C Prime D Prime well according to what we have just said this is the same thing as AB or C Prime D Prime complement complement that's just using the observation that we just made now in order to simplify that expression we're going to do the following we'll write this is AB or C Prime D Prime complement complement that term as we've written it just shows that we do one compliment and then we do another complement and we're just making that a little bit more explicit now I'm going to leave that one compliment uh on the outside of the brackets just as it is so um we'll still have brackets like this and uh this this compliment here will come down but for what's inside the brackets I'm going to use de Morgan's theorem now remember there are two forms to demorgan's theorem one says that the complement of a sum is the product of the individual complement and the other one says the complement of a product is the sum of the individual products well in this case we're dealing with the complement this this uh dagger Mark right here denotes the compliment so this is the compliment of and what we have in here in the interior is a sum so the complement of a sum is equal to the product of the individual compents so we have AB complement and then C Prime D Prime complement this is how the uh everything that's inside the brackets will simplify once again now notice that we have here this is the complement of a sum is equal to the product you can see that this is a product if you wish you can put the dot in there to emphasize that fact this is a product of the complements of the individual terms so here's the complement of the first term ab and this is the complement of the second term C Prime D Prime okay so this is how de Morgan theorem could be used to make one simplification well uh now it can be used once again but this time we'll use the other form of demorgan theum uh notice that each one of these terms that we have down here has the form of a complement of a product and uh the other form of demorgan serum says the complement of a product is the sum of the individual compliment so if we take um uh this first one it will give us a prime or B Prime once again here we're taking the complement of a product to get the sum of the complements of the individual terms okay and we can do the second of we can do the same thing with a second bracketed term as well so we'll get C compliment compliment or with d compliment compliment and then outside the brackets we still have one more uh compliment sign now um I don't think it will surprise you too much to see that uh we can simplify this a bit we'll bring down the first term a compliment or B compliment but now C complement complement just like X complement complement is equal to X so is C complement complement equal to C so this is C or D and then we have this complement sign on the outside now we will uh multiply out everything we have on the inside of the brackets so we get a Prime C plus a prime probably instead of prime should say complement but you you'll understand I use those terms interchangeably so a compliment D B complement C or for B complement D and then we take the complement of all that now uh notice that what we have on the inside of the brackets is a sum of products and we want to take the complement of that sum of products so uh here again is a a chance for us to use the Morgan stum uh where we say that the complement of a sum is the product of the individual complement so we have a complement C we need to take the complement of that uh take the product of that with the complement of a complement D and then we'll need B complement C that needs to be complemented and B complement D also needs to be complemented and once again now notice that this says that the complement of a sum here we see that this is just a sum because these terms are connected by plus signs so this is the complement of a sum is equal to the product because these we could if you wish put dots in between these this is the product of the complement of the individual term so a Prime C compliment a prime D compliment B Prime C compliment and B Prime D compliment and now as our final step we want to use the Morgan's theorem to simplify each one of those terms and of course here we have uh in each one of them it is the complement of a product just like here we have the complement of the product a complement C so the complement of a product remember is the sum of the individual complement so we have a complement complement or C complement again the complement of a product is the sum of the complement of the individual terms so a compliment compliment and C complement and we do that for each one of these a compliment complement or or D compliment B compliment compliment or C compliment and B compliment compliment or D compliment and then as before we uh will simplify all terms that have double complements because a complement complement is a b compliment complement is B so we have a or C complement a or D compliment B or C compliment and b or d complement and notice that now we do indeed have a product of sums form you can see it's clearly a product and each one of these is a sum a simple sum of Boolean variables and therefore this is a product of psms expression and I claim that this is equivalent to this expression that we started with up here at the beginning AB or with C compliment D compliment and now just as practice I would suggest that you try to go backwards and try to take this this product of sums expression and write it as a sum of products expression and of course that sum of products expression should be this right here and so you should get a b or c comp D component and uh I urge you to turn off the video now for a few moments and try to do that on your own and then we'll all do it together okay so I hope you had luck with that and now we'll all do this together um I'll multip I'll go ahead and end the first two terms together and the second two terms together and then end all of it so uh notice that if we end the first two terms together we get so this is a check so we uh and the first two together we get a A or a d Prime D compliment or a c compliment notice there that I'm changing the order uh C compliment a is equal to a c complement but we know that that is true because ending is commutative or C compliment D compliment and and we get a very similar um kind of thing with the second two terms we get bb or b d compliment or B C complement or C complement de compliment now the way that we finish this all off uh very quickly is just to remember that any Boolean variable Ed with it self is itself so a a is equal to a and similarly BB is equal to B now I hope that um at this point you see what we should do next you should recognize that these three terms add to Simply give a and similarly these three terms add to Simply give B if you don't see why that's the case I'll show you how it can be proven but this is one of our simplification properties and it's one that's particularly uh valuable to know about but just in case you've forgotten how that goes we'll notice that um this could be written like uh as follows we could rewrite this as a ended with one or a d complement or a c complement or C complement d d complement and similarly the second term could be written as B ended with one or B ended with d compliment or B C complement or C complement D complement and now we can rewrite each one of those as a ended with one or D compliment or C complement and then or with C compliment D compliment and likewise this could be Rewritten as B ended with one or Dent or C complement or with C compliment D complement and remember that one or with anything and it really is important if if you if this doesn't already jump out at you it should be beginning to do so one or with anything you just need to know automatically one or with anything is one and so therefore this is equal to one and likewise this is equal to one so these two terms now uh simplify quite a bit we have a ended with one or C Prime D Prime and B ended with one or C Prime D Prime and now another thing that should jump out at you is that anything ended with one is itself so a ended with one is a b ended with one is B so we now have a or C compliment D compliment ended with B or C compliment D compliment and we're almost there now let's go ahead and multiply this out and we will have a b or a c compliment D compliment or B C complement D complement or C complement D complement C complement de compliment and uh probably some of you can do this more quickly but I'll go ahead and spell out every step so we have AB or um a c compliment D compliment or B C complement D compliment or C compliment C compliment D compliment de compliment remember we can do that because aning is commutative so we can change the order and of course uh this thing gives us AB or a c complant d compliment or B C complement D compliment or remember any within variable ended with itself is itself so C compliment ended with C compliment is C compliment and D compliment Andy with de compliment is De compliment and now to finish this off we could write that in this form a c complement D complement or B C complement D complement or 1 C complement D complement and so that could be written as AB or with a or b or one C compliment D compliment and finally here then once again one or with anything is one itself so this is AB or one ended with C compliment D complement and of course one ended with anything is that thing itself so we get a B or C compliment D compliment just as we had up here at the very beginning so uh that's the way to go from a sum of products form to a product of sums form and then back from product of sums to sum of products so that gives you a lot of practice uh with uh some of the simplification theorems and also quite a bit of practice which is important indeed quite a bit of practice with both forms of De Morgan's theorems or de Morgan's laws uh which once again we have two forms the complement of a sum is the product of the individual complement the complement of the product is the sum of the individual compents you really need to have that uh have that memorized and and ready to use next let's look at problem 21 a we're asked to simplify an expression using just one of the theorems that we've learned and in uh 21A the expression that we're asked to simplify is the following we have a complement or B complement or C ended with a complement or B complement or C complement and uh if you look at that uh I wouldn't be terribly surprised if your first idea would be to use de Morgan's theorem to try to simplify the second parenthetical term because after all that is the complement this second term here is the compliment of a sum and so you might try to say that well the compliment of a sum is the product of the individual complt and that is correct but that is not the fastest way to simplify this problem the fastest way is to notice that this expression simply has one term ended with a compliment of that term and anything ended with its compliment is zero one ended with one compliment is the same thing as one ended with zero which is zero and zero ended with zero complement is the same thing as zero ended with one and zero ended with one is also zero so anything ended with its compliment is always zero and therefore we can we can do 211A extremely easily let's look at um perhaps 211 c as another example so in this case we have AB or C complement or D ended with a complement now I will admit to you that I have not memorized every single one of these theorems I try to be familiar with them but after all it is difficult uh perhaps to memorize all the theorems you have in every single class but you let's just say you just want to have some familiarity and certainly uh it catches my eye here that we have AB at first and then we have AB complement over here in the second term so if if I were you and I were faced with a problem like this what I would do is I would let AB I would simplify it and call it X and similarly I would call C prime or d y and of course uh AB again uh is X but this time we have that complement it so we have X complement so this has the same form as X or or with X complement Y and uh okay I admit I have to take a break on that one because this one is a little tricky um if you want to know immediately what form this is or uh perhaps let's just say with simplification theorem you need to Simply look at um two I'll say C 2- 14 D on page 42 of your text and that is the uh theorem that is appropriate in this case but I will show you how we can get to the uh desired result um and would be as follows uh we know from our previous work that X or X Y is the same thing as X now uh um how do we know this well X or XY is the same thing as X ended with one or X ended with Y which is the same thing as X ended with one or Y which is the same thing as X ended with one which is X so it so now it might seem a little counterintuitive to take that first X and to rewrite it as X or Y but it will lead to a simplification so that's why we would do that so instead of um um writing X or X complement y we will write X or X Y or X complement y and I I want to make sure over here that you understand uh that maybe I'll go ahead and just um um I'll put a box around this part because we have not we've not simplified that uh then this with this work below is just a elaboration on a way that we can rewrite X okay so uh coming over here we bring the x or X complement y over here and then we use the work we've done over here on the left to rewrite X as X or XY and then we just bring the X complement y over to the right and now I believe you can see why we want to do that because we can now associate the XY and X complement y together and we get X or X complement Y and of course X or with X complement is one and one or with anything is that thing itself so therefore we simply have X or Y and to finish up this problem then if we recall what X and Y are equal to we have then AB that's X and Y Y is C prime or D so we conclude with AB or C prime or D anded with AB complement is simply the same as AB or C compliment or D now I'll certainly admit that uh it was a little tricky to find that one unless you know the the correct simplification theorem it would be easy to miss that one uh but again don't worry about this because we are about to learn some simplification techniques that will make all of this automatic and uh actually I think that this is a good uh a chance for us to look once again at the truth table so um now that we've we've obtained that result let's just backtrack for just a moment and um let's go ahead and look at this theorem that we just used or that we just quoted we didn't actually use it we we uh went ahead and showed the steps but if we had wanted to use the theorem we could have and so let's let's look at the theorem for a moment so 214d on page one on page uh 42 says the following it says XY or excuse me XY complement or Y is equal to X or Y and so let's see how we might uh use truth tables uh to prove this well remember uh in the truth table Technique we will write the independent variables on the left and the dependent variables or the function actually on the right so in both cases whether we're looking at the left hand side of this equation or the right hand side of this equation in both cases the independent variables are X and Y so I'll make one truth table with x y and then um let's say X Y complement and X Y complement or Y you can see that the term on the extreme right is is the function is one of the functions that I'm interested in it's it's it's the left hand side of the equation the two columns on the left are the independent variables and I've used one intermediate column to help me calculate uh to help me do my calculations so now we have two uh independent Boolean variables we have four possible combinations 0 0 0 1 1 0 and 1 one now for each one of these cases we now need to calculate x anded with Y complement well we can do this pretty quickly in the following way whenever X is in the first two rows X is zero and zero ended with anything is zero so it doesn't matter what y complement is these first two rows will give us zero because X is zero now in the next in the final two rows X is equal to 1 and so X Y complement is the same as one ended with Y complement and one ended with anything is that thing itself so in the last two rows we get y complement well in this row Y is zero and the complement of zero is one and in the last row Y is one and the complement of one is zero so that is the value of XY complement for each row and now we finally are ready to calculate the left hand side of the equation in every possible case and we do that by simply oring uh the second column of this table with the third column so 0 or with 0 is 0o one or with Z is 1 zero or with one is one and one or with zero is one so the left hand side of that equation is always equal to one except when X and Y are both zero and in that case is equal to zero now let's do a truth table for the right hand side of the equation and see what it looks like now this one is a little bit simpler again we write our independent variables on the left and we write the function we're interested in on the right and in this case I didn't use any intermediate columns at all because this one's so simple once again we have two independent variables so we have four possibilities 0 0 0 1 1 0 and 1 one and now if we or those two columns together 0 with 0 is 0 0 or with one is one one or with zero is one one or with one is one and now if you compare this column and this column you see that for every possible combination of X and Y it is indeed true that the left hand side of this equation is equal to the right hand side and therefore XY complement or with Y is indeed the same as X or with Y so this we have proven uh the simplification theorem in this this particular simplification theorem in that way I'd like to do now one final problem uh for this lecture and that is problem 213 um B in this problem we're given a circuit uh that looks like the following so we have an input at a um and an inverter an and gate the output of the end gate goes to an orgate the output of that goes to another orgate and the output of that will be called F1 and we have another input B uh with which um we do do the following okay so that's our circuit and actually I see that um I've made an error here this is the circuit not for problem 2113b but for problem 2113a which will be fine so so here's our circuit for problem 2133a and the instructions in your book tell the following it says for this circuit find the output and then we want to design a simpler circuit that will have the same output so let's see how this will go well uh we'll we'll start up here with the a input uh we know that um the input a will be coming along this line uh for the second input of this end gate and for the top input of the end gate our analysis goes as follows we have a coming into this inverter but then when that gets inverted we have a complement so here we have a and a complement going into this end gate and we know that any variable complemented with its excuse me any variable any bullan variable anded with its compant will give zero so the output of that and gate will always be zero regardless of the value of a now once we see that that makes the rest of this problem very easy because we see that the second input to this or gate will be B and B or with Z will give us b as the first input of the final or gate now if we look at the second line we have a b here and B any buan variable order with itself is itself so we have B here and the same principle arises again any Boolean variable or with itself is itself and so we have B and therefore fub1 is simply equal to B and therefore if we want a simpler circuit it would simply be the following because F1 is equal to B so we don't need any components uh at all except for just a a wire which will make F1 always equal exactly equal to B so that's how we would do a problem of that type let's now discuss the problems for this lecture uh problem 5.1 which of the following Expressions is equal to zero for all possible combinations of X Y and Z except when X is equal to 0 and Y is equal to 1 and Z is equal to 0 simultaneously in other words all three of those statements have to be true X must be equal to 0 and Y must be equal to 1 and zal 0 if those three conditions occur simultaneously if all three of them are true then the expression we're looking for is equal to one but in all other combinations of X Y and Z the expression we're looking for must be zero so I'll I'll just give you a little hint on this one since we have three Boolean variables here we have 2 to the 3 power or eight possible combinations of X Y and Z we can have 0 00 0 00 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 and 111 so we have eight possible combinations in all of those combinations the expression we're looking for is equal to zero except the combination x = 0 y = 1 and zal 0 so which of the four Expressions given here a b c and d which expression satisfies those conditions that's problem 5.1 and then in problem 5.2 we have a simple uh circuit and you supposed to find the output either A or B or C or D represents the output of this circuit you determine which one is correct and that concludes lecture five