I'm showing again my Boolean network model with the X equals ab node connected

to the f equals Xb plus bY plus XY node. And I've got a little truth table here.

with the x equals ab node pointing at it, and it's got three columns, abX.

and under it all of the Boolean values of ab and X from 000 to 111, so there's

eight rows. And then there's another column that says

can it occur? And what we're really asking here is

inside this logic network, now that we know that X is ab.

Can each of these eight patterns of a and b and X actually occur?

The first thing we can do is just say, well, four of them can certainly occur

because X is equal to a and b. The patterns associated with X equals to

a and b can occur. So 000 can occur, 010 can occur, 100 can

occur, and 111 can occur. We have yes's in all of those rows.

So, it seemed that all the other rows are no's and yeah that's actually correct.

There are four patterns that can not happen to a b and X, 001, 011, 101 and

110. And you know, we can illustrate one of

those clearly, by just pointing at one of the rows.

So, let's point at the 001 row and say, well why is it that cannot occur?

And the answer is, well, a and b are 0's, and X is an end gate output, you can't

put two 0's into an AND gate and have a 1 come out.

So that's just not possible. So here's all of the possible and

impossible patterns for a and b and X. Now, however, I'm not that interested in

the patterns of a and b and X. I'm interested in the patterns of X and B

and Y. Because that's actually what f is a

function of. I need to figure out how I can take the a

b X patterns and I know something about what can't happen, and turn those things

into X b Y patterns. And all I can [COUGH] all I can tell you

at this point is you just have to sort of stare at things.

we're going to figure out computationally how to do this in a bit.

So the first thing is that there are three pairs of rows.

the rows that start 0, 0. The rows that start 0, 1.

And the rows that start 1, 1 in this table of xbY eight rows, patterns.

Because look, Y as far as we know, is a primary input.

It just you know, it's not dependent on anything.

So Y can be anything. But X and b are dependent on each other.

And the Xb00 pattern can happen. The Xb01 pattern can happen.

And the Xb11 pattern can happen. And that would seem to suggest that these

two rows, XbY is 100, and 101, cannot happen and, and that's actually correct.

And why that can't happen is that this is trying to put b equals 0 in to what is

actually an AND gate, and get X equals 1 out.

You don't put a 0 in an and gate and get a 1 out.

A 0 cannot go into the X node and have a 1 come out.

So any of the patterns that have X is 1 and b is 0 are impossible.

And so we found a couple of impossible patterns for our f node.

And so we can use those things. We can check in our Karnaugh map which

I've got drawn here again. For the Xb versus y, four variables

horizontally two variables vertically I've got the same Karnaugh map drawn with

the same three terms, XbbXY. Now, I'm going to say, what happens if we

add the impossible patterns? The answer is we have two impossible

patterns. XbY is 100 and 101.

I get two Don't Cares. The entire right column of the Karnaugh

map 100 and 101 are now Don't Cares. Suddenly, I can circle the Karnaugh map

in a different way. I can circle this in what I think is a

nicer solution. if I'm going to write the function now.

I have that the function is equal to x plus bY.

And that's simpler than Xb plus bY plus XY.

And so it looks like I've saved something.

So I can actually simplify this network. It is no longer Xb plus bY plus XY, it's

now X plus bY. It looks like I saved three literals.

And actually saved a product term. This is actually really good.

So, just because of the context of how X is a function of a and b, there are

patterns of X and b and Y that cannot happen.

So we can continue this and just try another one.

now what happens if Y is also a pattern, what happens if Y is b plus c?

It's again computed internally. We can do this again, we can say, are

there impossible patterns of the inputs and outputs of the Y node of b, and c,

and Y? And so, I've got another truth table here

that has three columns, bcY, with eight rows from 000 to 111.

And the column to the right says, can it occur.

And you start just like before, with the patterns that can occur.

You can send 2 0's into an OR gate and have a 0 come out.

The 0 0 0 is a yes. If you send any 1 in to an OR gate, you

get a 1 out. The 011, 101 and 110 rows for bcY are a

yes. Which leaves the other rows as a no.

001, 010, 100 and 110 cannot happen. We can draw those to be clear, the 001

row says you cannot put two 0's in an OR gate and have a 1 come out.

That's not possible. And the 110 row says, similarly, you

can't put two 1's into an or gate and have a 0 come out.

All four of the rows in this truth table are impossible because they're just not

legitimate patterns of inputs and outputs for the Y node in this network.

Now, we can take all of the information we've got, I'll admit a rather

complicated looking slide here. I've got the logic network, again, X

equals ab node. Y equals b plus c node.

Feeding the f equals Xb plus bY plus XY node.

I've got the impossible patterns for abX, again, drawn above it.

001, 011, 101, 110. And I've got the newly found impossible

patterns of bcY drawn above, above it 001, 010, 100, 110.

And I've got another truth table xbY, eight rows, 000 to 111 and another column

that says, can it occur? And just as before, I don't really want

The abx impossible patterns and the bcy impossible patterns.

I want po-, impossible patterns I can do something with, that I can use to create

maybe some Don't Cares for the f node. And so right now, you have no

computational technique for doing this other than to stare at this and try to

figure out what can and can't happen. So the first thing you do is you say,

alright, look, I stare at it. And I believe that XbY is 000, 001, 011

and 111 can happen. And if you just try all those patterns on

your x equals ab and y equals b plus c nodes.

You'll see that you can find other values for the inputs not specified.

In this case. A and C, that make that work and so that

leaves us with these four patterns. Zero 1, 0.

One, 0, 0. One, 0, 1.

One, 1, 0. For X, B, Y, as impossible and we can

again look at them. Why is 0,1, 0, and impossible pattern for

X, B, Y? Because you are trying to put a 1 in an

orgate and get a 0 out. Y is 1, 1, 0, impossible, because you're

trying to put a 1 in an OR gate and get a 0 out.

Why are the two patterns, 1, 0, 0, and 1, 0, 1 impossible?

Because you're trying to put a 0 and an AND gate and get a 1 out.

Because of the context of this network of what X is as a function of a and b and

what Y is as a function of b and c. Certain patterns of X and b and Y are

impossible jointly. And these things become Don't Cares.

And so, we get some more good stuff, okay?

So if we take these impossible patterns, and so I'm drawing the Boolean network

again, X is ab, Y is b plus c, f is Xb plus bY plus XY.

I'm drawing the impossible pattern above the XbY inputs to f 010, 100, 101, 110

for X b and Y. Those are impossible.

I've now got four don't cares that I can use, and what I actually get is to new

Don't Cares. I get a Don't Care for the XbY 010 and I

get a Don't Care for the XbY 111. So it's in this Karnaugh map four columns

wide by two rows deep. Only the Xb00 column has 0's in it.

Everything else has a Don't Care or a 1 in it.

So if I was to circle this Karnaugh map, I'd just circle this.

I'd circle the two middle columns. And if I write this as a Boolean

equation, this is now f equals b. And that's pretty surprising, because

that means that. I don't really care about the X node, and

I don't really care about the Y node. I only really care about the b primary

input. Just because of the context of X and Y

now being related because they share some variables.

And I don't even have to circle one of those previous ones in this Karnaugh map,

because become a Don't Care because as this context.

So wow, f was Xb plus bY plus XY. That looks like three AND gates in an OR

gate with three inputs and that whole thing gets replaced by a wire.

Wow, thatâs pretty surprising. That's pretty impressive.

And so this is just the first start of our examples for how we find Don't Cares.

This is one kind of a Don't Care. These are actually things called

Satisfiability Don't Cares and Controlability Don't Cares.

But these are the only kinds, there's actually some more kinds.

So in the next lecture, we're going to look at some other implicit Don't Cares

that we can pull out of this network.