0:02

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.

1:05

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.

2:48

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.

7:06

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,

8:19

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.

9:48

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.

11:10

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.