Today we're going to revise logic gates
first of all
AND, OR and NOT
Let's take a look to AND, first of all
I am going to write out a so called a truth table
in my old way which it might be slightly different
to the way other people lay it out
I like to lay these things out as in a sort of
square matrix
Let's call here on the left
input A
into my "AND" gate
and up at the top I'm going to talk about input B. It has two inputs and one output and the output
from the gate is represented inside this square area here. So, the A input we're working
in binary as ever
can take on values of 0 and 1 so can be okay - AND is very simple.
It says the outcome is true which is normally denoted by a 1 nowadays in binary,
the outcome is true only if both of the inputs are true of course that's
what and means in English that must be true and that must be true
so let's do 1 and 1 first of all, 1 and 1 is like true and true
yes the outcome is true but if you take 0 and 0, given that 0 means false then
the AND can't be true because you're saying it's false and it's false
so the outcome is false - it's a zero and equally if one of them is true and one
of them is false
the outcome still is false because the outcome of an AND gate, for it to be true,
both of them have got to be true. So you end up with a result matrix here look
with three 0s
in it and only one 1. Now, just this once I won't do it for all of the others but
just this once I shall say, feel free to write it down like this with a f and a t,
standing for true and false, but it's still the case that under AND logic
for the outcome to be true
you must have a couple of true inputs here.
So that's exactly the image of that using fs and ts rather than 1s and 0s.
If you're an electronics engineer and you're building some electronics to do
these logic functions, what you would draw is your AND gate with two
inputs A and B one output and yeah the thing to remember is that the AND is a
fairly rounded kind of shape at the front. But the point here is that the
outcome of doing A and B together can be written in lots of ways you can write it
as A AND B. Sometimes if you look in logic textbooks you'll find that they use
a thing looking like a little spike down on the baseline that is the mathematical
logicians favorite way of saying AND but it's the same thing as writing A N D.
Very occasionally you'll also see A dot B. That dot is like the one that
some of you will have been taught at high school to denote multiplication rather
than using the multiplying symbol.
It was noted early on that AND is a bit like doing multiplication. Because if you
say, what happens if I just multiply the two inputs
instead of doing this AND nonsense. Well 0 times 0 is 0, 1 times 0 is 0, that 1 multiplied by 1,
1 times 1 is 1!
You get the same outcome there as if you'd be multiplying the 1s
and 0s with each other and that is why AND is sometimes called: logical product.
OK now we've got the notation established, we can go ahead fairly
quickly now on the other possibilities here.
Let's take a look at the OR gate. Well, for this which is the so-called
INCLUSIVE OR, if you want to give it it's full name.
The rule is that the outcome is true if either or both of the inputs are true.
1 INCLUSIVE ORed with 1 - 1 OR 1, well, they're both true,
so the outcome is true. 1 ORed with 0, if either one of them is true
the outcome is true
so you put a 1 there. Similarly 0 ORed with 1
well, one of them is true so the outcome is true and only 0 ORed with 0 gives
you a 0 or a false.
So it's called an inclusive OR because it includes this situation here where
they really are both true to start with writing it down in... what an electronics
engineer likes to see
Here you come, fast back go faster tail fin there and it slips around like this
There is your OR gate with the A and a B inputs here it comes the output and again
we can either write it down as A ORed with B or we could say A notice it's
the opposite way around to the AND it looks like a little V on the baseline
so you can write it like that or many people noted very early on when studying
mathematical logic that OR does more or less behave like addition
not quite, I mean look at it 0 plus 0 is 0, 0 plus 1 is 1, 1 plus 0 is 1, 1 plus 1
ah... really referring back to the binary adder video I did a week or two ago
1 added to 1 should really put down a 0 and carry a 1 but here it's
as if the carried bit's retained and held inside but as far as logicians are concerned
a lot of them like to call this the logical sum. Whereas AND is the logical product.
To complete these three
there's a very familiar indeed now, there is a very special one and that's our
good old friend NOT, it's special in that it doesn't take two operands, it only
takes one operand. NOT is a simple inverter, give it a 0 - it will turn it
to a 1, give it a 1 -
it'll turn it to a 0. So we've only got one input let's call it a day.
What's the outcome? Well, the outcome is a single column now. It's not a square.
Because what you're saying is, if you apply NOT to 0 - you get a 1, if you apply NOT to 1 -
you get a 0. It just flips it, as simple as that. And the circuit diagram, electronics
type notation which is a triangle with a little circle at the end and what
comes out of here.
Well, there's lots of... ways of writing NOT A, you can write it as NOT A,
sometimes you'll see it written as twiddle A. Sometimes you'll see that some
logicians like to use a thing like this little bent crowbar to denote
NOT so that can also be used to call the output NOT A. Those three
taken together are what's called logically sufficient to do anything you
want in logic AND, OR and NOT taken together. Dr. "Heartbleed" - bless his cotton socks -
has done even more advanced stuff with you now which I just mention.
If you want to glue a NOT gate onto the output of an OR gate say, so you do the
INCLUSIVE OR but then the moment you get it's result you flip its direction
you turn it over instead of just taking that and gluing it onto there
you're allowed to abbreviate by putting the circle on the end of the OR gate
it's still got the A and B inputs and it's still got output but notice the
moment you do the OR you turn it the other way around
that's what the circle says so that is a NOR gate and I know for a fact that Dr.
Bagley has done that with you in one of his videos
we'd like to thank
audible.com for sponsoring this computerphile video
they've got over a hundred thousand titles to choose from and if you'd like
to try one out for free
go over to audible.com/computer file today I'd like to recommend red mars by
Kim Stanley Robinson
there's been a lot of hype recently about visiting in colonizing Mars and
Kim Stanley Robinson really captures what this might be like to do it... it
feels very realistic not the sort of utopian vision you get in some science
fiction
so check out red mars go to audible.com/computer file
try it out for free and thanks once again to them for sponsoring this
computer video will be useful to refresh our memory of how an or gate works
so that's an order and he has two inputs which were labeled as A and B