SPEAKER: Welcome to lecture 9. As the result of a question
that one student raised during our last test,
I realized that there's been one issue I've overlooked
that I'd like to clear up at the present time. Suppose that we have the
following-- f of x, y, z is equal to, let's say, x
prime yz or x y prime z prime. Now, this is called-- obviously, first of all,
this is a minterm expansion because both of
these are minterms. They are simple products of
all of the available Boolean variables in either complemented
or uncomplemented form, and we have a sum
of these products. So this is a minterm
expansion of f. A minterm expansion of f-- in fact, I'll say the
minterm expansion of f because it is unique-- the minterm expansion of
f in algebraic notation. And by algebraic notation,
we mean where the variables are all spelled out. Now, as we've learned before,
we can also have f of x, y, z in what's called
decimal notation, and the way that we get
that is as follows-- for each one of
these minterms, we look at what the variables need
to be in order for each minterm to be equal to 1. Remember, for minterms, we
look when they're equal to 1. For maxterms, we look at
where they're equal to 0. So for this first
minterm to be equal to 1, we would need x is
0, y is 1 and z is 1. And for the next
term-- actually, I want to make a small
change in that next term. I'm going to make
that xy z prime. Don't worry about
my reason for that, I just prefer to have that. So to make this minterm equal
to 1, we would need 1, 1, 0. Actually, now that
I think about it-- well, OK. Let's just leave it at this. OK. So we have x prime
yz or xy z prime-- this is the minterm expansion
of f in algebraic notation. And now, if we wanted
the minterm expansion of f in decimal notation, the
way that we get that is we identify when each
minterm is equal to 1. And now, we interpret
these as binary numbers. So the binary number, 011, when
written in decimal, would be 3, and the binary number, 110,
when written in decimal, would be 4 and 2 and 0 is 6. And so, in decimal notation,
we would have this. This is the minterm expansion
of f in decimal notation. Now, another point that
I'm wanting to make, besides introducing
this terminology of algebraic notation
and decimal notation, the other point I want to
make is the following-- if we wrote f of x, y, z is
equal to y x prime z or y z prime x, notice that that is
still a minterm expansion for f but the two minterms are written
in an order that does not match the order of
the variables given in the argument of the function. And if you don't notice this,
if you just begin the numbering, well, this would
be 101 and this one would be, actually,
also 101, and who knows, you might even be misled. If you saw that the numbers
were the same there, you might even be misled
into combining those two. Of course, they
don't combine at all. But let's say that maybe
you recognize the error here and you change this
last term to yx z prime, and then you would have 110. Well, even if you
did that, though, and now you interpreted
these as binary numbers, you would have 5
and 6 when, in fact, the correct answer for
the decimal notation of f is 3 and 6. And the reason that we have
been led to the wrong answer here is that in our minterms,
we did not list the variables in the correct order. And what is the correct order? Well, it's the order
in which the variables are listed in the
argument of the function. So whenever you're
listing out minterms-- or maxterms for
that matter-- make sure that the variables
appear in the same order that they do in the
argument of the function, and then you'll be able
to do the decimal notation or algebraic notation. You'll know, easily, what
you should use there. So that was just one note
that arose at the end of our-- well, during our last test,
and so I wanted to make sure you were aware of that. So now, I'd like to do a
problem to give us a little more practice with all of this. If you have the
book, again, that's the sixth edition of
Roth's book, Fundamentals of Logic Design. This problem is 430, but
for those who don't have it, I'll go ahead and
spell out the problem. It tells us to find
both the minterm expansion and the
maxterm expansion for the following functions. Now, it also specifies using
algebraic manipulations, but I'm not going to
stipulate that you can only use algebraic manipulations. I'm going to allow you to use
anything you wish in order to find the answer. So here we have a. It says, lowercase f of A, B, C,
D is equal to AB or A prime CD. And we first will find
the minterm expansion and then we'll find the maxterm
expansion for this function. Now, to find the
minterm expansion, we first want to observe
that neither one of the terms here is a minterm. The first term is not a
minterm because it doesn't have either C or D in
it, and the second term is not a minterm because
it doesn't have B in it. And we know how to correct
these deficiencies. For the first term, we
will and it with 1 twice. We'll write the first
one as C or C prime and the second one
as D or D prime. And for the second term, we
will and it with 1 one time. And 1 will be written
as B or B prime since B is the missing
variable in the second term. Now, we multiply this all out. And do be careful-- I noticed with some
students that when they had two parenthetical
expressions like this to multiply with
each other, sometimes they would only multiply
the outside terms and forget the inside terms. So, in other words,
what I mean is they would see CD and
C prime D prime here, but they would forget C
D prime or C prime D. So be careful when you're
multiplying terms together to get all of the terms. So we will get AB and we'll have
CD or C D prime or C prime D or C prime D prime. And the second term only has
one parenthetical expression so it's a little bit easier. We'll get A prime BCD
or A prime B prime CD. By the way, I forgot when
I started this problem but, to be honest, I think
you can probably do this problem on your own. So if you haven't
already done so, I would encourage you to
stop the video at this point and try to finish this problem
on your own and then come back. OK. So let's now finish
this problem. When we multiply
out this first term, we'll have ABCD or ABC D prime
or AB C prime D or AB C prime D prime. And then we bring
down the terms from before for the second term-- A prime BCD or A
prime B prime CD. Now, everything we've
been using here-- you remember I mentioned that
the book specified that you wanted to find the minterm
and maxterm expansions using algebraic manipulations-- and
everything I've done so far here in trying to find
the minterm expansion is an algebraic manipulation. And in fact, we will only
use algebraic manipulations in finding the
minterm expansion. But then to find the
maxterm expansion, rather than starting back here
at this original expression and using algebra, we'll
use a faster way which we've already talked about. We'll get to that
in just a moment. Anyway, now we're ready. We can agree, I think, that
every term here is a minterm. Notice that in each case,
we have a simple product of all of the variables. The variables are in the right
order, and so we can go ahead. And the book does not
tell us whether we should give the expansions
in algebraic notation or in decimal notation
so I will choose to give them in the decimal
notation-- that's shorter. And also, I personally think
it makes it a little bit easier to check for redundancy,
and so let's go ahead and find out how this
would be listed in-- well, actually I guess I
should say the following. So this is the function f of A,
B, C, D. And if we check this, we can see that, in fact,
there is no redundancy here. In other words, no
term has been repeated. And therefore,
we're done if we're satisfied with having f
in algebraic notation. So I'll go ahead and say-- I'll circle this-- and this
is the minterm expansion for f of A, B, C, D
in algebraic notation. OK. So that's really all that
the problem asks us for. So if you wanted to
now, you could go ahead and you could repeat this
function, f of A, B, C, D equals AB or A prime CD-- write it like that and then
use algebraic techniques to find the maxterm expansion. And the way that I would
go about doing that-- it would in fact,
maybe we should just do that just as a good
practice, but then I'll show you a quicker way to do it. So let's find the
maxterm expansion and I'll say one, use
algebraic manipulations. OK. Now, this is similar to the
kind of thing we've done before. Let's go ahead and repeat
our function, f of A, B, C, D is equal to AB or A prime CD. And now, if I wanted to
use algebraic manipulations to find the maxterm
expansion, my approach would be as follows-- I notice that this is a sum of
products, or SOP, expression. And of course, I know
that the maxterm expansion is a POS expression. And we learned-- we've already
seen a couple of examples in which we saw that one
convenient way to get from an SOP expression to a POS
expression is to complement twice, because remember,
anything complimented twice is itself-- like x prime prime is x
or y prime prime is y. So double priming anything
does not change its value. Now, what we'll do-- I'll go ahead and
just remind you that the way that we will
approach this problem is the following-- we will treat those
two primes separately. And so, for the
inner prime right here, this is the
complement of a sum, and by one of De Morgan's
laws, the complement of a sum is the product of the
individual complements. So we have AB-- that's one term-- and
we want its complement. And the other term
is A prime CD, and we will also
want its complement. So again, we're saying
that the complement here-- the complement of a
sum is the product-- you can see that this is a
product here-- if you want, you can put a little
dot just to emphasize that this is a product. This is a product of the
individual complements. And then we don't want to
forget the prime on the outside. Now, on the inside, since each
of those terms is complemented, we can use De Morgan's
theorems again. And this time, since each
of those is a product, we will be using De Morgan's
law for the complement of a product, and that one
says that the complement of a product is the sum of
the individual complements. So we have A prime or B
prime for the first term. And then for the
second term we'll have A prime prime, which
is A, or C prime or D prime. And once again,
we have just twice used the De Morgan's
law that says the compliment of a
product is the sum of the individual complements. Now, what we do, and we're
almost done with this, but now, we will go ahead
and multiply out what's on the inside of the brackets. A prime A-- I hope you readily see
that that's equal to 0 because, remember, any variable
ANDed with its complement is 0. So A prime A gives nothing. Then we have A prime C
prime or A prime D prime or A B prime or B prime C
prime or B prime D prime. And all of that is primed. And now, we will
finally get the POS form by using De Morgan's
law for this, which says the complement of
a sum is the product of the individual
complements, and so we have A prime C prime prime ANDed
with A prime D prime prime ANDed with A B prime prime ANDed with
B prime C prime prime ANDed with B prime D prime prime. Again, this complement
here on the outside-- the complement of a
sum is the product of the individual complements. And so you can see
what we have there. And now, if we use De Morgan's
laws for each one of those, each one of those is the
complement of a product, and we know the
complement of a product is the sum of the
individual complements. So we have A or C ANDed with
A or D ANDed with A prime or B ANDed with B or C, and
finally ANDed with B or D. And notice in each
case, we've said the complement of a
product is the sum of the individual complements. So that's why A prime became A,
C prime became C, A prime is A, D prime is D, A becomes A
prime, B prime becomes B, B prime becomes B, C prime becomes
C, B prime becomes B, D prime becomes D. And notice that now,
we have, indeed, achieved a product
of sums expression. However, our goal was to get
a maxterm expansion, which is a special kind
of POS expression. And you can clearly see
that this is not a maxterm expression because, in fact,
not a single one of these terms is a maxterm. Remember that to
get a maxterm, we need to have all
of the variables present in either complemented
or uncomplemented form. So the question
becomes, now, what do we do to move from
this POS expression to a maxterm expansion? And I will remind you-- I'll say recall-- that x or
y ANDed with x or y prime-- that is equal to x. And I think you can
see that that's true because x ANDed with x would be
x, x ANDed with y prime would be absorbed into x, x ANDed
with y would be absorbed into x, and y ANDed with y prime is 0. So we will now, for
each one of these terms, we can use that notion
going backwards. So A or C is the
same thing as A or B or C ANDed with A or
B prime or C. Now, let me make sure
you follow that. I'm thinking here of A
or C as being like x, and then I'm thinking
of B as being y. So here, you can
see A or C or B-- that's x or y here-- and A or B prime or
C is the same as-- the A or C part is,
again, that's x, and now B prime is y prime. So I have things in
slightly different order, but we're thinking of A or C-- that's playing the role of x-- and B is playing the role of y. And we're going not from left
to right in this equation, but from right to left. So we have this one term-- A or C, the thing
that is being x-- and we're going to the
left, from right to left, we're rewriting it as x or
y ANDed with x or y prime. So we have one term here that
becomes two terms down here and we'll do the same kind of
thing with each of those terms. So the next one can become A or
B or D ANDed with A or B prime or D. The next one
can become A prime or B or C ANDed with A
prime or B or C prime. And the next one can
become A or B or C and D with A prime or B or C. And
finally, the last one all right is A or B or D ANDed
with A prime or B or D. Now, what I want to
emphasize is that we still don't have maxterms. We have four variables
in this problem-- f is a function
of A, B, C, and D, as we can see right up here-- and our problem right here
with our POS expression is that we have a product
of sums like we want. But each one of those sums is
the sum of only two Boolean variables and we need each one
to be a sum of four Boolean variables. So we're going to need to use
this property repeatedly-- this x or y ANDed with
x or y prime equals x. We're going to need to
use that over and over. But to be real careful, I'm
just doing it one at a time. Like for instance,
what I mean there is that we need both B
and D in this first term. You see we have A or C-- we're missing B and
we're also missing D, but I'm not going
to try to introduce both at the same time. I'll just introduce one
extra variable at a time, and so for the first
one, we have B B prime. For this next one,
we have B B prime. The next one-- notice that
C and D are both missing, but I'll just first
introduce C. So that's why we have A prime or B
or C ANDed with A prime or B or C prime. And then for this one,
I have A and A prime, and for this one
also, A and A prime. And then my goal next,
in the next step, would be to introduce
in each case the one more missing
Boolean variable. But before we do that,
we do, fortunately, have some simplification. Notice that right here,
we have A or B or C, and recall that we
have an and here. So we're continuing
this in the second line, but in the second line,
one of the terms we see is A or B or C. And anything
ANDed with itself is itself, so we don't have to
repeat A or B or C and we can cross out
one instance of that. Likewise, here, the third
term is A or B or D, and so is the next to
last term, A or B or D. So I can cross out
one instance of that. And the term right here-- the next to last term
in the first line is A prime or B or C, and that
matches this term down here, the second term in the second
line, A prime or B or C. So I can get rid of that term. I don't believe that
there's any more repetition, so I'll leave it at that
and now, finish this up. Now, you can see this
is quite tedious, and keep in mind just how
tedious this is because you're going to see that there
is a much easier way to do this, which we'll
discuss in just a moment. But first, let's finish this up. Now, we still have a
POS expression here-- this is a POS expression-- and it is closer to
being a maxterm expansion than was our previous
POS expression, but it's still not
a maxterm expansion. And I hope you readily
see that that's the case because each one is
still missing one variable. And so, again, we would
use this very handy fact that we have here. So A or B or C will become A or
B or C or D ANDed with A or B or C or D prime. And A or B prime or C will
become A or B prime or C or D ANDed with A or B
prime or C or D prime. A or B or D will become
A or B or C or D ANDed with A or B or C prime or D. The A or B prime
or D will become A or B prime or C or D
ANDed with A or B prime or C prime or D. And
then A prime or B or C will become A prime
or B or C or D ANDed with A prime
or B or C or D prime. And finally, the
A prime or B or C prime term will become A prime
or B or C prime or D ANDed with A prime or B or
C prime or D prime. And now we notice
that this is still, of course, a POS, or
product of sums, expression. Each one of these terms
is now, indeed, a maxterm but we need to
remove redundancies, and we can see there
definitely are some. In fact, remember now, I want
to emphasize that all of this is just one big product. It's the product of
12 terms, but there are quite a few redundancies. In fact, we see A or B or
C or D is repeated here, and so we can take out one
instance of that and this C. Here we see A or B prime or C
or D and A or B prime or C or D, so we can take out
one instance of that. It's hard, sometimes,
at least for me, it's hard to see
these redundancies. As I say, I like to go
to the decimal notation. For me it's easier
to see if there are redundancies in that way. Maybe some of you see
some other repetitions, but I think I'll go. Before I'm going to say
that this is the maxterm expansion for f in
algebraic notation, before I'm going to
claim that for sure, I want to look at
the decimal notation. So let's see what that would be. Now, remember, for
maxterms the way that we label them is about
when they are equal to 0. So the first term-- we would need all
of the variables to be equal to 0 for
the first term to be 0. For the second one, we
would have 0, 0, 0, 1. For the third one we
would have 0, 1, 0, 0, and for the next
one, 0, 1, 0, 1. The next one, 0, 0, 1, 0. And the next one
here, 0, 1, 1, 0. And going to the final line, we
have 1, 0, 0, 0; 1, 0, 0, 1; 1, 0, 1, 0; and 1, 0, 1, 1. Now, let's look at
each of those things that we just wrote and think of
those as being binary numbers and translate them to decimal. Remember that for a sum we use
this symbol, but for a product we use this symbol right here. It looks almost like
the Greek letter pi. And remember, again, for
maxterms we will have capital M. And 0000 is 0, 0001 is
1, 0100 is 4, 0101 is 5. Going to the next line,
0010 is 2, 0110 is 6. And now going to the last
line, 1000 is 8, 1001 is 9, 1010 is 10, and
finally, 1011 is 11. And we can see there-- now, we do need to write these
numbers in ascending order, which means we need to write
the 2 over here after 1, but we can readily see that
there is no redundancy, and therefore, we can go ahead
and write f of A, B, C, D and likewise, f of A, B, C,
D here and we can conclude-- sorry about that. OK, we can conclude that these
are maxterm expansions for f. This first one is a maxterm
expansion in algebraic notation and that's this, and this-- well, let's go ahead, actually. We probably ought to make
this a little neater-- get rid of all the numbers and also
get rid of the redundant terms, so maybe I should
just repeat this. So let's maybe cross
that out and we'll just say f of A, B, C, D
is equal to A or B or C or D ANDed with A or B or
C or D prime ANDed with A or B or C or D ANDed with
A or B prime or C or D prime ANDed with A or
B or C prime or D-- notice, I'm taking out the
redundant terms from above-- ANDed with A or B prime or C
prime or D ANDed with A prime or B or C or D ANDed with
A prime or B or C or D prime ANDed with A prime
or B or C prime or D ANDed with A prime or B or
C prime or D prime. That, we've already verified
now, that has no redundancy. Each term there is
a maxterm, so this is the maxterm expansion
for f of A, B, C, D in algebraic notation. And f of A, B, C, D is equal to
the product of the maxterms 0, 1, 2, 4, 5, 6, 8, 9,
10, 11 is the maxterm expansion for f of A, B,
C, D in decimal notation. And if you thought that was
painful, it's because it was. It was a tedious
procedure, and so now, I want to show you a much more
efficient procedure for finding the maxterm expression in cases
like this where you already have the minterm expansion. So this will be, I'll
say, alternative method. Now, let's go up, scroll
back through all this work we've just done, and let's just
take a look at this minterm expansion that we found before. Now, remember, the minterm
expansion was very little work. And that's typical, especially
when you start off like this. Notice, this is already a
sum of products expression and when you start off with
the sum of products expression, it is typically quite quick
to get the minterm expansion, just as we did here. Now, we're charged with
finding the maxterm expansion and we would like to do
this as quickly as possible. Well, let me show you the
quickest possible way. So I'm going to repeat the
minterm expansion down here. That's ABCD. So we'll say, recall
that the minterm expansion is f of A, B, C, D-- actually, I'll just
start a new line here-- f of A, B, C, D equals
ABCD or ABC D prime. The next two terms are ABC D
prime and AB C prime D. ABC D prime or AB C prime D.
Now, to scroll back up and find the next two terms. The next two terms have C
prime, D prime, and A prime. C, D, and A are the prime
terms, so ABCD, ABCD and we said C prime and
D prime and A prime. And then the last one
has both A and B primed. That's the minterm expansion
that we found for f. And again, we are now asked
to find the maxterm expansion. Well, there's a very
easy way to do it. The first step-- OK, let me emphasize, this is
algebraic notation, where we've spelled out all the variables. But it's very handy here
to use decimal notation, and so we'll go as follows. Remember, that
for minterms, when we want to label them
using the decimal notation, we look for when
they are equal to 1. So we have 1, 1, 1, 1; 1, 1, 1,
0; 1, 1, 0, 1; 1, 1, 0, 0; 0, 1, 1, 1; 0, 0, 1, 1. And if we interpret each of
those as a binary number, then this is 15. Let's see, this will
be 8 and 4 and 2. So that will be 14. 1, 8 and 4 and 1 is 13. 8 and 4 is 12. 4 and 2 and 1 is 7. And 2 and 1 is 3. So if we write the
minterm expansion for f in decimal notation-- now, this is a minterm
expansion so it says sum, and that's why we
use this symbol, and minterms get a
lower case m And so we will have 3 7 12 13 and 14. And this is a minterm expansion
for f in decimal notation. Now, how do we find the maxterm
expansion in an easy fashion? Well, we can simply
write it down. f of A, B, C, D will
be equal to M 0-- capital M 0, 1, 2,
4, 5, 6, 8, 9, 10-- oh, I'm sorry. Left out the 15 up here. You see that the
first term was 15 and I simply left
that out, so 15. Now, continuing down here
with the maxterm expansion, we have 0, 1, 2, 4, 5, 6, 8,
9, 10, 11, and that is it. That is the maxterm expansion
in decimal notation. And if you compare with
what we had before, you can see, indeed, 0, 1,
2, 4, 5, 6, 8, 9, 10, 11. Now, do you see how
I got that answer? Well, the answer is the
following-- how did I get it? I simply looked at
the minterm expansion and I thought about
what this means. Remember that if you try to
visualize the truth table for f, this information tells
you that in the 0011 row and the 0111 row and in the
1100 row and the 1101 row and the 1110 row and 1111 row-- in other words, in rows that
correspond to the numbers 3, 7, 12, 13 and 14 and
15, f is equal to 1, and therefore, in all the
other rows, f is equal to 0. But that's exactly how we
name the maxterm expansion is by looking at the rows
where f is equal to 0, and those rows will be
the rows corresponding to the numbers 0, 1, 2-- we don't have 3
because 3 is up here-- then 4, 5, 6-- but we leave out 7
because 7 is up here-- 8, 9, 10, 11-- but then we don't
have 12, 13, 14, or 15 because they're up here
in the minterm expansion. And so that's it
it's just that easy. And therefore, to do a problem
like this very efficiently-- notice that this problem
took us quite a bit of time but actually would have been
quite simple because we started out with this SOP expression,
we got the minterm expansion very easily, and then from
the minterm expansion, we can get the maxterm
expansion very easily as well. So that's how we would
do a problem like that. Now, in the b part
of that problem, you're actually given-- let's see here if I wrote
the right problem number. I wrote that incorrect
problem number here. I said that this
was problem 430, but this problem that
I've just done is 429. And if you look at
429b, you start out with a product of
sums expression rather than a sum of
products expression. And so in that case,
it may be easier-- rather than multiplying
everything out-- it may be easier to go ahead
and find the maxterm expression first-- since it's already a POS
expression-- it might be easier to find the maxterm
expression first, and then using this
same technique, you would write the maxterm
expression in decimal notation, see which terms are not there,
and you could immediately get the minterm expansion. So keep in mind that technique
because it can really save a lot of time. Now, the-- well, let's stop
there for just one moment. Yes, I see, actually,
we've taken up enough time for one period. So I'll go ahead now, rather
than covering any more material on this lecture, I'll actually
make up a couple of questions. So let's look now at the
problems for this lecture. 9.1 says, suppose
f of A, B, C, or D is equal to the sum of the
minterms, 0, 1, 2, 6, 7, 13, and 15. And by the way, as I said, this
is called decimal notation. I believe we mentioned
in our previous lecture it's also called
little m notation. But the question here
is the following-- if that's the expression for
capital F, which of these is the minterm
expansion for f prime? Now, be very careful to
notice this is f prime. It's not f itself, it's
the complement of f. So we want the-- f prime, of course,
is also a function of the variables, A, B,
C, and D, just like f is, but we want the minterm
expansion for f prime. And here are your expressions or
your possible answers, A, B, C, and D. And then for 9.2,
we are given a formula, f of the variables, a, b, c--
lowercase variables a, b, c-- is equal to a ANDed with the
sum of b ORed with c prime. This is our formula
for little f and we are asked to find
the maxterm expansion for f of a, b, c, the same
function, in capital M notation. Each one of these you see
has the capital M notation so you don't have
to worry about that. There's no tricks
here, but you just need to find out which of
these capital M notation expressions-- which of these expressions is
the correct minterm expansion for this function. So that concludes
lecture 9 and good luck.