==Boolean Logic==
So today we're starting our journey
of actually building a computer. You've probably all heard that computers
internally only have 0s and 1s. And the reason that they only have 0s and 1s is because that's what
they can get away with. It's simplest to have only two possible
values that you need to maintain. And that's going to be
enough as we will see today. We're starting with actual,
the completely theoretical logical kind of analysis of
how to deal with 0s and 1s. And later in this later in unit three
we'll actually talk about how these abstract 0 and 1 signals directly are
implemented as chips inside a computer. So let's talk about the abstract 0 and 1. On and off, true or false,
not, no and yes, 0 and 1. In general, we can use all these names to refer to
each one of two different physical values. That are maintained
somewhere in the system. We will use 0 and 1 for the rest of this the rest of this unit,
but that's completely general. So what can we do with kind with,
if we only have 0s and 1s? Well, we can do some kind of
basic operations on them. For example, the AND
operation takes two 0 1 signals, and returns 1 only if both of them were 1. So if you have 0 and 1, the result is 0,
but if you have 1 and 1, the result is 1. We can actually see all of
the different possibilities for combining two values of 0s and
1s into the result, which is the end of them, in a little
table that is called the Truth Table. Because it actually gives all
the different possibilities of the inputs, of x and of y, and for
each one of these possibilities, it lists what is the output,
what is x and y. So AND
is a one of the possible operations. Here's another very popular one, OR. It returns 1 if any one of
the two inputs is true. Is one. Or even if both of them are one. The only time to return to
0 is if both x and y are 0. And here's a third interesting operation. This one is a unary operation. It only takes a single input. Bit as input, x, and
returns the opposite of it. So returns for,
if the input is 0 the output is 1. If the input is 1 the output is 0. So these are possible, very simple
operations and Boolean numbers. Sort of like addition and multiplication,
and maybe other kind of operations, or operations on integers or on real numbers. These are operations on Boolean numbers. Once we have operations,
we can start combining them, just like we combine arithmetic
operations in arithmetic formulas. So for example, let us try to evaluate
what would be the expression of NOT 0 OR 1 AND 1? Notice that we have parenthesis to gi,
to give us the priority here. So the way we value it is very simple. We know how to evaluate 1 AND
1, which is 1. So the whole thing simplifies to NOT 0 AND
1 OR 1. We know how to evaluate 0 OR 1. That's going to be 1 because it's an OR
operation so that's equal to NOT 1. And now we know how to evaluate NOT 1,
that's simply 0. All very simple and we can do that. Now once we know how to evaluate
a Boolean expression over values, over 0, 1 values, then we can actually get general
expressions, general functions that takes indeterminates, XYZ as inputs, and for
each value of XYZ, produce an output. So for example, I can define a function,
a function of three inputs, XY and Z. That basically turns x AND y OR NOT x AND z and look in the parenthesis to see
the priority that I was thinking about. Of course I could use,
I could define any other function by any other Boolean formula and
that would give me a function. If we want to know what
kind of function is that, well we can actually list all
the possible values of x, y and z. And for each one of them, try to write
down what is the value of the function? The really nice thing about Boolean values
is the fact there are only a finite number of possible inputs and
we can actually list each one of them. This is completely different from
functions that you've learned in third grade. Where you have function from
integer through integer, then there are infinitely many integers. So you can never write down the function
in a complete specification of all the possible values. But here, we can actually write down
all the possible values that x, that the triplet x,y,z can have. We can have x 0, y 0 and z 0 that corresponds to
the first row in the table and so on. Until the last row of the table that
corresponds to all three of them being 1. Now for each one of these rows,
we can just evaluate the function. What is the function f of x, y, z defined
by the previous formula for these values? For example let's look at the second row. In the second row we have x equals 0,
y equals 0, z equals 1 and we can just plug in the numbers 0,
0 1 into the formula. Every time we have an x we put a 0 there. Every time we have a y we put a 0 there. Every time we have a z we put a 1 there. And now we just get formula
with constants in it and we can evaluate it just like
we did in the previous slide. And we can figure out that is 1, that
the second row should get a value of 1. We can do this similarly for each one
of the possible rows and we get a, we can completely fill the table. And now notice that this table of values completely gives you the same information
as the previous expression did. It completely specifies the functions,
the Boolean function that we just had. The first day, the first way we
described the function was as a formula. The second way we describe
the function was as a Truth Table. These are two completely identical,
def, def, eh, definitions. Ways to describe the same
Boolean function. So now, eh, once we know we can describe
Boolean functions using formulas and we are thinking we have general Boolean
expressions, we can actually try to find what are a bunch of Boolean identities
that always give us equality. For example, we can always see that x AND
y, whatever the values of x and y is, is exactly equal to y AND x. This is called the Commutative Law. We have the same similar phenomena for
x OR y equals y OR x. So these are like commutative
laws that hold for this Boolean algebra, in this,
in this Boolean algebra. There are a bunch of
other kind of identities. For example, the use, the use,
the well-known Associative Law. If you have x AND y AND z, it's the same thing if you first do x
AND y, or whether you first do y AND z. Similar thing happens for all. Another well-known law,
well-known law is the Distributive Law. If you have x AND y OR z,
that turns out to be exactly equal, equal to x AND y, all that, OR x and z. Now as opposed to the usual arithmetic,
where we only have the Distributive Law of multiplication over addition, here we have
both of the Distributive Law of multi, AND over OR and the dual law of
Distributive Law of OR over AND. The same trick works if you
want to do x OR y AND z. That x OR y AND x OR z. [COUGH] Now there are also laws called
De Morgan laws, that govern how NOTs work. How they interrelate with AND and OR. These are called loo,
laws are called De Morgan laws, and they say the following into,
interesting thing. If you take x AND y and
do a NOT on all of that, that's equivalent to first doing NOT
of x and ORing that to NOT of y. And we have the dual one
that if you have NOT of x OR y, that's exactly equal to NOT of x AND
NOT of y. Now all these laws can be easily proved,
if you wish. Not if you wish. Really proved by simply listing all
the possibilities in a Truth Table. And verifying that they get
the same Truth Table for the left-hand side and
the right-hand side. Now there are a bunch of other laws and we can use them to actually do
manipulations and Boolean algebra. So for example, once we have a formula. For example the formula that you see here. NOT of, NOT x, AND NOT x OR y. For example,
it could be any other formula. We can now start applying
some of these identities to change its form to simplify it or
to just bring it into a different format. So for
example the first thing we can do here is look at the second part of last
sub expression, the NOT x OR y. We can use De Morgan Law here and
basically convert it to NOT x AND NOT y. Now if you look what we have here,
we can use Associative Law. Because we have NOT x AND NOT x AND NOT y
we can change the order of doing the AND. And we get another expression which is
identical using the Associative Law. At this point we have something
really interesting at the beginning. We have NOT x AN NOT x. That can be just simplified to NOT x. Why is that? Because we can know, we can actually see, also that's another identity
that we didn't explicitly list. But it's easy to verify in the same
way that, if you take any value, w. In our case, w is NOT x. And do w AND w,
that's completely equivalent to w. Now this is called the Idempotence Law and
we can thus simplify the previous expression by simply removing one
of these w's, one of these NOT x's. Now we are ready to use
De Morgan Law again, and now we got into NOT NOT x OR NOT NOT y. Now again, here's another law that
we didn't list explicitly, but you obviously all know,
that NOT NOT x is always equal to x. So using Double Negation Law,
we can simplify that to x OR y. So that just gives you some kind of
a demonstration that you can basically, just manipulate Boolean expressions, sort of like you manipulate arithmetic
expressions in elementary school. There's another way to get the same
conclusion, the same equivalence, without actually going through
these algebraic manipulations, simply by actually looking
at the Truth Table. We take the expression,
we build the Truth Table for it. And we've already seen how to take
an expression and find its Truth Table. And then we get the Truth Table
that you see on the board. Now, once you have this Truth Table,
you can say I know this Truth Table. This is exactly the Truth Table of the OR
function. And then that immediately proves that
the expression on the top is completely equivalent to x OR y as we've derived
using an algebraic methods previously. Now of course it's not completely eh, you
won't always be so lucky to do some kind of big Truth Table and recognize what
it is and immediately see a better and nicer and simpler expression give,
that gives you the same table. Eh, sometimes you will have to
algebraic manipulations, but on the other hand it's not always
true that algebraic manipulations are easy to do in the sense of
finding a very simple expression. So, but in general, in principle, you can use both of these methods to
actually simplify Boolean expressions or find alternative forms that give
you the same Boolean expressions. So we've just finished our first unit
describing how to man, how to eh, manipulate logical values. Notice that we are still keeping
our abstract point of view of just logical values and not thinking
about any physical realization that we will have inside our computer. In the third unit, we'll actually
switch our point of view and start talking about the same
kind of phenomena but from the point of view of real chips and
real gates that we have inside a computer. But before we get to that,
in the next unit, we'll keep maintaining [COUGH] our theoretical point of view and
start talking about the following problem. How can we construct a function
from basic operations? How does that, this is exactly the kind of thing we will
need to do when constructing hardware. We know what it wants to do, but we'll have to actually construct
it from Boolean operations. And we'll try to see how that is done,
first from a theoretical point of view, in the next unit.
==Boolean Functions==
==Logic Gates==