---
Video Title: AND-OR-NOT
Description: Theory of Computation
https://uvatoc.github.io

5.3: AND-OR-NOT
- Modeling Computing with Logic
- AND, OR, NOT
- Building MAJ (Majority) with AND, OR, NOT

Nathan Brunelle and David Evans
University of Virginia
---

We're starting with logic.

All the forms of computation that you
might want to see have some sort of

underlying math that they're actually
doing.

Python is doing some sort of math.

It is just human-readable, nice-looking
math.

And your CPU is doing math as well.

It is just math done by electricity.

The underlying model that we're going to be
looking at to start with is Boolean logic.

Ands, ors, nots, and so forth.

When we have Boolean logic, we have these
operators, or, and, not.

Or is just a function.

What is that function?

Well, that is a function that maps bit
strings of length 2 to 1 bit.

So, or is a function that takes 2 bits as
input and gives 1 bit as output.

And the way that it does that is to define
or of A and B.

That's going to be 0, provided that A and
B are both 0.

A is equal to B, which equals to 0.

In any other situation, it's going to be
1.

So it's going to be 1 otherwise.

And is also a function that maps 2 bits to
1 bit.

And the way that that one works is if we
have and of A with B.

That is going to be 1 in the case that
both A and B were 1.

If A equals B, and they are both 1.

And then it's going to be 0 in all other
circumstances.

Who can tell me what not is going to be?

What is the type of input for not?

Yes.

Not is going to take 1 bit and map it to
how many bits?

Yeah, to 1 bit again.

And the way that not works
is we say not applied to.

A is going to give us 1 if
A was 0 and 0 otherwise.

So this is going to be our
underlying math that we're going

to use to build a couple of
different models of computation.

And what we're going to
do is we're going to use.

AND, OR, AND NOT in
order to write some algorithms.

And in particular, we're
going to use AND, OR, AND.

NOT to write an algorithm
for this function majority.

So majority will be 1 if most of 3 bits
were 1.

The type of input for majority is 3 bits.

And the type of output for majority is 1
bit.

Order for sets doesn't matter,
so ignore that.

Don't let that confuse you, please.

I don't know why I did it.

So that is the type of majority.

It is a function that maps 3 bits to 1
bit.

And we want it to be true whenever at
least 2 of those 3 bits were 1.

How would I compute majority with,
let's say, math, with Boolean logic?

So I want to compute the majority function
on A, B, and C.

So how would I do that?

So basically, we have, let's say,
3 bits.

So we have A, we have B, we have C.

And to figure out whether or not at least
2 of them ended up being a 1, what we

could do is we could just look at,
let's say, all of the possible pairs.

And if we looked at all of the possible
pairs and saw that in any of them,

both were 1, then that means that the
majority were 1.

So what we can do is we can say,
are A and B both 1?

How can we check if A and B are both 1?

And, yeah.

So I can say, I can do and on A with B.

And then let's just say that I know how to
do ors on lots and lots of things.

We haven't talked about that yet.

We only have or operating on two things
right now.

But let's just pretend that we can do it
on as many as we want for the moment.

One option for how I can satisfy the
majority is for A and B to both be 1.

Or it could have been that maybe B and C
were both 1.

Or it could have been that A and C were
both 1.

So that is how we can do an or on three
things with only two things, is you have

to split it up into two
ors, where you have like

a temporary variable
or something in between.

That's exactly what we're going to be
doing next.