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

5.4: Programming with AND, OR, NOT
- The AON Programming Language
- Defining MAJ
- Defining XOR

Nathan Brunelle and David Evans
University of Virginia
---

What we're going to be
doing next is we're going to be

using a simple programming
language in order to do majority.

We call this programming language AON for
and or not straight line programs.

It's going to look like Python and in fact
on my machine I'm just using Python.

The way this works is all of our functions
take in Boolean inputs.

So we have these Boolean functions only
within our programming language.

And the only ones we're allowed to use are
and or not.

That's where that AON comes from.

So what we can do is we can apply and or
not to inputs.

Assign those results to variables.

We can reuse those variables as inputs to
future and or nots.

And then eventually we're going to return
some resulting bits.

Let's look at an example of majority
implemented with and or not.

I'm trying to define this majority
function.

This majority function is going to take
three input bits ABC.

We need to give one output bit.

So first of all, let's see what we expect
the answer to be.

What should be the answer of majority on
001?

So the answer should be zero.

And then for 101, since we have two ones,
that answer ought to be one.

The majority of those are a one.

So we said that the way that we were going
to solve this was to check all pairs,

return true, or return one in this case,
if any pair had both ones.

So what we can do is we can have our first
pair.

We said that could be and applied to A
with B.

And then maybe we have the last pair is
equal to and applied on B and C.

And then we had maybe the first with the
last is equal to and applied to A with C.

We want to check if any of these ended up
being true.

If any of those was one, then our whole
answer should be one.

So we can say the first pair with the last
pair.

So the first last pairs
is going to be equal

to the or of the first
pair and the last pair.

And then we want to return
true for the majority, provided

that the first last or this result
here ended up being one.

So this is now in this and or not straight
line programming language, the equivalent

of that mathematical definition we saw for
majority.

Let's program some more things.

How can we program NAND?

What is NAND going to be?

Yes.

Yeah, so NAND is equal to like... so NAND
of let's say A and B.

That is equal to the not of the and.

This is violating our program rules
because we said you weren't allowed to

nest these, or we didn't say you were
allowed to.

So the not of the and of A and B.

If I wanted to define what
NAND meant in my straight line

program, I would, let's say,
define NAND on A with B.

We have A and B is equal to the and of A
with B.

And then we can return the not of that
result.

We can also do XOR.

So XOR is going to be true whenever
exactly 1 is true.

So exactly 1 of A and B is 1 is when we
make XOR 1.

So I'm going to start by maybe computing
not A and then not B.

And I want to make sure
that it's either the case that A is

true but not B, or it's the
case that B is true but not A.

And either one of those is sufficient for
the XOR being true.

So we have a programming language.

This is our programming language.

Thank you very much.