Starting with a few simple abstractions (wires that can carry on/off values and switches that can control the values carried by wires), we address in this lecture the design of the circuits that implement computer processors. We consider gates that implement simple logical functions and components for higher-level functions, such as addition. The lecture culminates with a full circuit for an arithmetic/logic unit.
that's going to help us understand the behavior of our circuits.
Boolean algebra was developed by George Boole in the 1840s to study logic problems.
a formal system that could help understand statements that are true or false.
So we wanted to have the idea of variables that represent true or false.
And we're going interpret them as one or zero, of course.
OR, and NOT, and those are very familiar with us.
logic, and computer science for many, many, many applications.
In fact, it's so widely used that there's several different notations in common use.
and we have the idea of a Boolean variable in Java.
and we say NOT, we say x prime.
So that's one notation that we're going to use in this lecture.
then you have a traditional algebra where the variables are numbers.
which we can work on and prove in just a minute.
than switches that we can understand what they're doing.
well, he had to express everything in terms of yes and no.
And, well, we've seen plenty of examples of that earlier in this course.
is the idea of a function. So, what's a function.
A function is the thing that takes arguments and it has a value.
systematically describe or define a Boolean function.
the function value for the specified arguments.
each of the variables can take one of two values.
So there's going to have to be two to the N rows.
If X is zero, X prime is one.
If X is one, X prime is zero.
And again, we've seen these functions before in other applications.
which is X AND Y is one.
If they're both one, otherwise it's zero.
If they're both zero, otherwise it's one.
So those tables, there's functions that take two arguments.
either they're both zero or X is zero Y is one or X is one Y zero or they're both one.
the definition of what the function is for that row of arguments.
So it's giving us a complete definition of the function.
Here's another one called NOR, or NOT, OR.
That one is one if they're both zero, otherwise it's zero.
it's one if they're different.
to define Boolean functions, and it's interesting.
they're giving us, they're working with every possibility.
checking what happens with each of the possibilities.
we're sure that we've checked everything.
So, for example, here's the proofs of DeMorgan's law using truth tables.
and that's X AND Y.
so all possibilities of X and Y.
then that's going to be zero.
If they're both zero, one otherwise.
So, there's all possibilities that gives us the value of the function NOT X or NOT Y.
they're full specifications of the function.
So, that's a proof for DeMorgan's law of NOT X and Y is equal to NOT X or NOT Y.
says NOT X or Y is equal to NOT X and NOT Y.
And we did an example like this also in our cryptography application.
It's a fine way to establish truths of identities for Boolean functions.
that's one effects are above zero and zero otherwise.
And we'll see that one come up again when we look at circuits.
how many different Boolean functions are there of two variables.
and they can each have either value zero or one.
So that's two to the fourth.
two variables. So that's X and Y.
And then we just start out at all zero zero zero one zero zero one zero.
And we've looked at some of these.
And the last one is called one.
So, we have zero and one.
We have AND. The next, OR, NOR, and so forth.
That's interesting, but let's think about three variables.
there's eight different possibilities of the three different variables.
So, then there's eight bits to define the Boolean function.
of three variables, which is 256.
but there's some that are interesting.
and that just generalizes our definition of AND.
It's going to be zero if any of the inputs is zero.
It's one if all the inputs are one.
And OR, again generalizes it's one if any input is one.
It's zero if all inputs are zero.
and that's the one after all zero zero otherwise.
And there's lots of different Boolean functions of three variables.
So here's one called the majority function.
So that one is a one if and only if more inputs are one and zero.
So that is if a majority of the arguments are one.
they have to be two of them are one or all three are one.
And those are the four ones in the column labelled majority.
Zero one one, there's two ones, Y and Z.
One zero one, there's two ones, X and Z.
One one zero, X and Y are one.
And one one one, they're all one.
and that's the definition of a Boolean Function that's useful as we'll see.
And there's another one, odd parity.
So that's one is a one if and only if an odd number of the inputs are one.
And actually, all of this generalized to any number of inputs.
you have two to the N different possibilities for the values of the variables.
So, that means there's two to the N rows.
you can give zero or one for every row.
So the total number of Boolean functions of N variables is two to the Nth power.
And that's a function that grows very quickly.
So, 16 for two, 256 for three.
Already for four, there's 65,000.
And for six, already we're getting to a very huge number of Boolean functions.
and we'll never ever even encounter almost all of them.
So, a little bit of a sobering thought that we'll get back to.
be represented with only a few operations.
There's a number of ways to prove this.
We're going to talk about the sum of products representation.
each one in the Boolean function and then all the terms together.
we can show how this works.
OR, and NOT to express the majority function.
is we're going to take a look at the function.
for that set of values of the variables.
So, the term X prime YZ is going to be one only if X is zero and Y and Z are one.
and then X prime Y Z is one.
Any other value, the variables that term X prime YZ is going to be zero.
then we're going to develop a term XY prime Z.
Y equals zero, Z equals one.
So, we have another column corresponding to that one in the majority function.
And then there's two more.
which is one if and only if all three of them are one.
So, now we have four functions that each have just one one in them.
And what we can do is just OR them all together.
So, ORing them all together just brings those ones back.
to exactly the same in every position as the majority function.
X prime YZ plus XY prime Z equals XYZ prime plus XYZ.
This idea is obviously going to work for any Boolean function.
universal if every Boolean function can be expressed using just those operations.
OR, and NOT is universal.
any Boolean function as long as we can implement AND, OR, NOT.
we'll talk about that in just a minute.