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.

Great!