---
Video Title: Boolean Circuits
Description: Theory of Computation
https://uvatoc.github.io

5.6: Boolean Circuits
- Defining Boolean Circuits
- MAJ using Boolean Circuit
- Equivalence of Boolean Circuits and AON Programs

Nathan Brunelle and David Evans
University of Virginia
---

We already talked about the function and,
or the function or, the function not,

and so forth, as one possible way of
realizing Boolean logic, of one possible

way of writing down Boolean logic with
that straight line program.

These are what we call logical gates.

This is just a second way of writing down
that same math.

The Boolean circuits that we're going to
be talking about next are just a different

way of taking that same background
mathematical idea of Boolean logic that we

used for the straight
line programs, and

representing those as
these logical gates instead.

So the way this works, we have these wires
that are coming into the gate.

In this case, if we had a 0 and 1 as the
values of the wires coming into the gate,

then since this does an AND, its output is
going to be a 0.

Or with OR, if we have 1 with 0,
then its output is going to be a 1.

Typically, any time you
see a little circle, little

circles tend to mean
invert, take the opposite of.

So if I have like a 1
as an input to this NOT

gate, then we end up
with a 0 as the output.

So these are just different ways of
writing down these same functions.

We like this way of writing down
computations, because these actually tend

to have a very, very direct translation to
actual hardware.

That we can use transistors to actually do
some of these things pretty directly.

For instance, typically a way that you can
draw an AND gate with transistors,

it'll look something like this.

We can think of this one as the
electricity that's coming from the wall.

I am terrible at drawing electricity.

Let me try this one more time.

Nope, give up.

They say VCC.

Basically, that's where
you plug your computer into

the wall, or a battery,
or something like that.

And then these might be your inputs.

So this is maybe A and B.

And the way that the transistor is going
to work is that this is only conductive.

So that transistor will conduct
electricity, provided A has power,

provided A has voltage.

Otherwise, it will be an electrical
resistor.

So that means that the only way we can
actually get power going all the way

through this path of two
transistors is when both.

A and B had power
going through them as well.

So we can pretty directly translate each of
these gates into one or more transistors.

I'll leave it to you to look up how OR
versus NOT works as well.

But we like writing
things down in this way

because they very
easily become electricity.

What we're going to do is
we're going to use this second

method, the second model of
computation, as Boolean circuits.

So we're going to talk about what this is,
how it works.

And then we're going to
demonstrate that that is equivalent

in this you-can-compute sense
to our straight-line programs.

So here is majority with Boolean circuits.

The rounded tip gate, that was an AND.

The weird curvy one, that's an OR.

And then the triangle with the little
circle, that one's NOT.

This is the majority with Boolean
circuits.

Let's evaluate this for some input.

So let's say that we have 0, 1,
1.

These X's, X0, X1, X2.

That means our input bit string.

This Y0, that is the first bit of our
output bit string.

In this case, we only have 1.

The way that this is going
to work is that everything

that connects to this X0
is going to have value X0.

So that one's going to be 0.

This one's going to be 0.

This input will be 1.

That one will be 1.

All of those are 1s.

The ones connected to X0 are both 0s.

Once I have all of the inputs
defined for my gates, then I

can figure out what the
output for that gate ought to be.

So this gate is going to perform an AND on
0 and 1.

So that should be a 0.

This will be an AND on 0 and 1.

So that's a 0.

This is an AND on 1 and 1.

So that is a 1.

And now I know that that's a 0 and that's
a 1.

We're going to do the OR on that.

So that will give us a 1.

So this is 0 and this is 1.

So the result is a 1.

So we give us our output 1.

The basic idea for how we operate this is
we actually have to go in these layers to

make sure that we've
figured out what the values of

certain wires are in order
to use them in future gates.

Our first layer is the input.

So we do all of these first.

And then everything that depends only on
the input is what we do next.

So that's going to be the second thing
that we do.

And then everything that
depends only on things

in layer 1 or the input
are done kind of next.

So that will be layer 2.

And then anything that depends on only layers
0, 1, or 2, that's going to be layer 3.

And so forth.

So what we'll do is we'll start with layer
0, which is the input, then calculate the

values for all of the
gates in layer 1, and

then all of the gates
in layer 2, and so forth.

This is the formal
definition of that same

procedure that we use
for evaluating these circuits.

So let's look at, side by side, this is
our straight-line program for majority.

This is our Boolean circuit for majority.

Let's look at some of the relationships
that we have between these things.

If you look at the
straight-line program, we have

three inputs, just like
we had in our circuit.

We have A, B, C, our three inputs.

Notice that we also had
one, two, three uses of this.

AND operation, and we have
one, two, three AND gates.

This is an AND gate, which takes input A,
which we said basically matched X0,

and input B, which is basically matching
X1.

So this first AND gate here
looks like it's doing basically

the same thing as that
first function AND over here.

You can see that we also have two OR
gates.

There's one OR gate, and there's two OR
gates, and so forth.

So it looks like they have all of the same
components.

It is not at all surprising
that they might be

equivalent, and that is
possible to compute sort of way.

Basically, what we can do is we can take
every single one of the components that

you saw in that straight-line
program here, and map

it to a different component
in this Boolean circuit.

That variable first two,
that was going to be

whatever the value was
of that first AND gate.

The return was the same
as the OR gate that we

said gave us our return
value from the circuit.

Every single component
you saw in your program, you

can match that with some
component in the circuit.

We're going to more formally demonstrate
exactly how they're equivalents.

We're going to show
that circuits are equivalent

to our AND or NOT
straight-line programs.

Just like we did before, just like we did
to show that AND or NOT straight-line was

equivalent to NAND
straight-line, we need to

show two things to show
that they're equivalent.

We need to show how it
is that we can convert any

circuit to an AND or NOT that
computes the same function.

And we need to show how
we can convert any AND or.

NOT to some circuit that
computes the same function.

If we can do both of these
things, then that means that

any function that we could
write the process to compute.

So essentially, what
we're going to do is to

convert our circuit to
a straight-line program.

We can say that each of the inputs that
the circuit is going to have is going to

be, let's say, an input to that
straight-line program.

Every single gate that our circuit has,
it's going to receive its own variable.

So gates map to variables in our
straight-line program.

The value that we assign to
a variable is going to be that

same value that we got by
applying the operation of the gate.

The output is given... the
return value is whatever that

output gate or those output
gates ended up returning.

So that is our mapping from circuits to
straight line.

Here I've provided for you a circuit for
XOR.

And then we can convert this circuit for
XOR into one of our straight line programs.

An and or not straight line program.

Here our inputs are X0 and X1.

So if I define my
program for XOR, its inputs

are the same as the
inputs for the circuit.

So that's going to be X0 and X1.

When we process the circuit, we did it in
these layers.

So that was layer 0 that we just did with
the inputs.

This is going to be layer 1.

Those NOT gates.

So we're going to start by giving
variables for our NOT gates.

We're going to call this NOT 1.

And then this is going to be NOT 2.

So NOT 1.

What is NOT 1 equal to?

Well, we did the NOT on input 0 for NOT 1.

So this is NOT X0.

And then N2 is equal to NOT X1.

The next layer we do is these AND gates.

We can say this is AND 1 and this is AND
2.

So AND 1 is equal to the result of,
we said, doing an AND on X0.

And then also the result of that second
NOT gate.

So N2.

Variable N2.

And then AND 2.

That is now going to be AND of X1 with N1.

Finally, the thing we return is the result
of this OR gate here.

So we're going to return OR applied to AND
1 with AND 2.

These two things are equivalent to one
another.

That is how we can translate our circuit
to an AON straight line program.

If you kind of compare this back to what
we did earlier in this lecture,

you'll see that this is an equivalent
program.

If you just change some variable names,
you'll get exactly what we had before.

Let's get started.

Let's go.