Boolean algebra

Loading...

Del curso dictado por Princeton University

Computer Science: Algorithms, Theory, and Machines

41 calificaciones

Princeton University

Computer Science: Algorithms, Theory, and Machines

41 calificaciones

This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others.

De la lección

COMBINATIONAL CIRCUITS

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.

Boolean algebra13:34

Digital circuits21:54

Adder circuit8:00

Arithmetic/logic unit7:19

Conoce a los instructores

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Senior Lecturer
Computer Science

To help us, we're going to use a little bit of math,

mathematical formalism called Boolean algebra,

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.

I was interested in working with

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.

And then there's basic operations that are involved in such statements like AND,

OR, and NOT, and those are very familiar with us.

And ever since it was developed,

Boolean algebra has been widely used in mathematics,

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.

So we've already seen Java notation for Boolean variables,

and we have the idea of a Boolean variable in Java.

In mathematical logic, they use different notation

involving Vs and upside down Vs. And in circuit design,

we use yet another one that we're going to use in this lecture,

where the AND operation is like

multiply with Boolean variables and the OR operation is like sum,

and we say NOT, we say x prime.

So that's one notation that we're going to use in this lecture.

And then within this algebraic system,

then we can prove and manipulate these things as algebraic formulas,

just bearing in mind the simple rules

that we have for Boolean variables and Boolean formulas,

then you have a traditional algebra where the variables are numbers.

And so, for example,

this is DeMorgan's laws,

which we can work on and prove in just a minute.

Now, the relevance to circuits is that this is really going to be the basis for us to

build up circuits that are a little bit more

than switches that we can understand what they're doing.

And of course, this standard Boole cartoon is that,

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.

So, one thing that is

an important part of the Boolean algebra formalism

is the idea of a function. So, what's a function.

A function is the thing that takes arguments and it has a value.

And for Boolean functions,

we can use something called a truth table to

systematically describe or define a Boolean function.

And what we do is, we keep one row for each possible set of argument,

the values of the arguments,

and then each one of those rows is going to give

the function value for the specified arguments.

So if you have N inputs,

each of the variables can take one of two values.

So there's going to have to be two to the N rows.

So, for example, for NOT,

there's just one input.

So there's two 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.

For AND, it's the X Y,

which is X AND Y is one.

If they're both one, otherwise it's zero.

And OR is zero.

If they're both zero, otherwise it's one.

So those tables, there's functions that take two arguments.

We're giving all possible values of the arguments,

either they're both zero or X is zero Y is one or X is one Y zero or they're both one.

And then on the right side of the line is

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.

And XOR, which we saw back in our cryptography example,

it's zero if they are the same,

it's one if they're different.

So, this is a completely well-specified way

to define Boolean functions, and it's interesting.

One of the big applications of truth tables is,

they're giving us, they're working with every possibility.

So, with truth tables,

we can establish identities in Boolean logic just by writing down

one row for each possibility and then

checking what happens with each of the possibilities.

And with truth tables,

we're sure that we've checked everything.

So, for example, here's the proofs of DeMorgan's law using truth tables.

So if we have X and Y,

that's again all possibilities of X and Y,

and that's X AND Y.

So, if we take the NOT of that, that's X and Y,

NOT X and Y, then that's one one one zero,

that's the value that function definition of that function,

so all possibilities of X and Y.

Now, on the other hand,

if we take NOT X and NOT Y,

and we look at the OR of those,

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.

And now you see that those columns are the same,

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.

And similarly, we can do for the complimentary version of it that

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.

By the way, this function that is the NOR function on the right,

that's one effects are above zero and zero otherwise.

And we'll see that one come up again when we look at circuits.

Now, it's interesting to think about

how many different Boolean functions are there of two variables.

Well, there's four bits in the true table column,

and they can each have either value zero or one.

So that's two to the fourth.

There's 16 different possibilities.

And actually, we can just enumerate all Boolean functions of

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.

Actually, all have names.

And the last one is called one.

So, we have zero and one.

We have AND. The next, OR, NOR, and so forth.

So, 16 different possibilities.

That's interesting, but let's think about three variables.

Well, for three variables,

there's eight different possibilities of the three different variables.

So, then there's eight bits to define the Boolean function.

So, that means there's two to the eighth different Boolean functions

of three variables, which is 256.

So, we're not going to look at all of those,

but there's some that are interesting.

So, for example, AND is a multi-way AND,

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.

NOR is the not of the OR,

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.

In the case of three,

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.

Those are the rows for which the majority function is 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.

So, either exactly one of them as one or all three is one,

another different Boolean function.

And actually, all of this generalized to any number of inputs.

And if we start thinking about more variables though,

it's interesting to contemplate.

If you have N variables,

you have two to the N different possibilities for the values of the variables.

So, that means there's two to the N rows.

And to define the function,

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.

For five, there's two to the 32nd,

which is four billion.

And for six, already we're getting to a very huge number of Boolean functions.

So, there's a lot of Boolean functions out there,

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.

But one thing that's important and basic outgrowth of

Boole's study is that every Boolean function can

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.

So, the idea is to form an AND term for

each one in the Boolean function and then all the terms together.

Now, with the true table proof,

we can show how this works.

So, the majority function,

we want to write down an algebraic expression that just uses AND,

OR, and NOT to express the majority function.

So, the way we're going to do it,

is we're going to take a look at the function.

And for every one in the function,

we're going to create an AND term that's one only

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.

Then X prime is one,

and then X prime Y Z is one.

Any other value, the variables that term X prime YZ is going to be zero.

Similarly, if we look at the next to one in the majority function,

then we're going to develop a term XY prime Z.

Again, that function is one only for the values X equals one,

Y equals zero, Z equals one.

Otherwise, it's zero.

So, we have another column corresponding to that one in the majority function.

And then there's two more.

And the last one is XYZ,

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.

And now our column is equivalent

to exactly the same in every position as the majority function.

So that's a proof that the majority function is equal to

X prime YZ plus XY prime Z equals XYZ prime plus XYZ.

This idea is obviously going to work for any Boolean function.

So there's the concept that a set of operations is

universal if every Boolean function can be expressed using just those operations.

And what this amounts to is a proof that AND,

OR, and NOT is universal.

So, with regard to circuits,

it means that we can implement

any Boolean function as long as we can implement AND, OR, NOT.

But we're getting ahead a little,

we'll talk about that in just a minute.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play