We spent the weekend in NYC with the family and visiting friends so I wrote up this "Not So Simply Science" post and never got to publish it. Thus it will take Monday's post spot- hope you all enjoy it.
Today’s post is a detour from the pretty heavy climate talk
of the last two weeks. We’re going to
talk about something I truly love working with and basically spend most of my
day thinking about – Boolean logic. Since this is a Not So Simply Climate it legitimately has nothing to do with
climate science, however Boolean logic
is what defined the late 20th and early 21st century
so it can’t hurt to learn about it!
Boolean just means
any variable can only be in two
states. The two we typically use are
“True and False” or “0 and 1”. You have
most likely heard of it called “binary logic” and it is how we design almost
all consumer electronics. Using
electricity to do complex math and logic is tedious and fickle. Using electricity to do very very simple things
incredibly fast is easy and super repeatable.
Breaking everything down to the simplest form possible then, True/False,
is what we are trying to take advantage of.
If any of this seems interesting to you maybe pick up
programming or micro electronics as a hobby.
Or make your kids take up Computer or Electrical Engineering --- it’s a
pretty good time.
Operations
There are 7 basic “operators” in Boolean logic. An operator is something like ‘+’ or ‘x’ it tells
you what to do between two variable. If
we see “3+3” and “3x3” we know that one yields 6 and the next yields 9. However what does “True + True” mean? What
does “True+False” mean? What does “True * True” mean? We need to define these operators to then build
even more complex operations from them.
NOT
Not is the only logic operator which acts on a
single input. It simply “flips” the
input into whichever state it isn’t. So
a 0 becomes 1, 1 becomes 0, False become True, True becomes False. NOT is incredibly useful – it lets you figure
out a way to do something, and then whenever you need the “opposite” you just
throw a NOT on the end. NOT is denoted a
couple ways. In programming we put a “!”
in front of the variable or equation we are working with. In a logic equation we put a line over the
variable or equation. Finally in a logic
circuit it is represented by a triangle with a circle on the end:
Y = NOT(X)
| ||
X
|
--->
|
Y
|
0
|
--->
|
1
|
1
|
--->
|
0
|
AND
“AND” operates on two inputs (as will the rest of
the operators). AND will only ever be
“True” if both inputs are “True”. So if
one input is false and another true I cannot say “A is True AND B is True” So
it is false.
“AND” is denoted by “&” in programming, the
multiplication symbol in equations and this symbol:
“AND” has
the following truth table:
X*Y = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
0
|
0
|
1
|
--->
|
0
|
1
|
0
|
--->
|
0
|
1
|
1
|
--->
|
1
|
OR
“OR” is true if any input is True. If A is True and B is False I can say “A or B
is True” and be correct. Or is
represented by “|” in programming, an addition symbol in equations and this
symbol:
“OR” has
the following truth table:
X+Y = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
0
|
0
|
1
|
--->
|
1
|
1
|
0
|
--->
|
1
|
1
|
1
|
--->
|
1
|
Our next two operators are going to be the
“opposite” of the previous two. Their
names are not all that clever.
NAND
“NAND” is
simply the opposite of AND. NAND is
represented by:
You can think of it in two ways:
-
This will only be true when both inputs are
False
-
I can simply perform an “AND” and then a “NOT”
The truth table for NAND is:
!(X*Y) = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
1
|
0
|
1
|
--->
|
1
|
1
|
0
|
--->
|
1
|
1
|
1
|
--->
|
0
|
NOR
“NOR” is simply the opposite of OR. NOR is represented by:
You can think of it in two ways:
-
This will only be true when Neither input is
True
-
I can simply perform an “OR” and then a “NOT”
The truth table for NOR is:
!(X+Y) = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
1
|
0
|
1
|
--->
|
0
|
1
|
0
|
--->
|
0
|
1
|
1
|
--->
|
0
|
XOR
“XOR” is the “Exclusive OR” operator. I have always said it as “zore” like sore
with a Z. This is not how you say it but
I don’t care – it’s been 10+ years
and I’m not changing. The XOR is only
TRUE if one and only one of its inputs are TRUE. We think of it as A or B is TRUE, but NOT
both A and B. Later we’ll explain why it is important but it is the
foundational operation in our computer processors. Xor is represented by ⊕ or:
The Truth table for XOR is:
(X⊕Y) = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
0
|
0
|
1
|
--->
|
1
|
1
|
0
|
--->
|
1
|
1
|
1
|
--->
|
0
|
XNOR
Finally we have the “Exclusive NOR” or “Ex NOR”. Hopefully you can see the pattern… this is
the opposite of the Exclusive OR. It is
only True if both inputs are the Same.
We think of it as “Are A and B both True or Both False”. XNOR sadly doesn’t have a cool symbol, you
just put a line over an XOR equation, the circuit symbol looks like:
The truth table for XNOR is:
!(X⊕Y) = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
1
|
0
|
1
|
--->
|
0
|
1
|
0
|
--->
|
0
|
1
|
1
|
--->
|
1
|
Making Operators from other Operators
The easiest operator to make in the physical world are NAND
and NOR operators. This has to do with
how transistors are made and maybe we’ll go into it in a later post but for now
you need to know they take up the least amount of silicone, space, and can be
crammed next to each other easily. When we say “new computer chips have X
billion transistors” most of those transistors go to making NOR or NAND
operations.
Here is a super simple example. Lets imagine some variable X. What if I made X BOTH inputs to my NOR
function.
NOT
The truth table looks like this:
!(X+X) = Z
|
|||
X
|
X
|
--->
|
Z
|
0
|
0
|
--->
|
1
|
0
|
1
|
--->
|
0
|
1
|
0
|
--->
|
0
|
1
|
1
|
--->
|
0
|
So if X is False, then Z will be true. If X is True, Z will be FALSE. We have now made a NOT operator!
Well if we have a NOT operator, and we have a NOR operator…
you bet we can make an OR operator:
OR
This is simply a NOR followed by a NOT.
Finally let’s make an AND operator. Look at the truth tables for AND and NOR.
AND is only true if both inputs are TRUE. NOR is only true if both inputs are
FALSE. So if we can take two “1’s” make
them both “0” and input them into a NOR we will get a 1. The logic circuit looks like this then:
AND
After the first line both A and B will be !A and !B, and
finally Nor’d together. The truth table
looks like this:
!X = Z
|
!(X+Y)=Z
|
|||||
X
|
Y
|
--->
|
!X
|
!Y
|
--->
|
Z
|
0
|
0
|
--->
|
1
|
1
|
--->
|
0
|
0
|
1
|
--->
|
1
|
0
|
--->
|
0
|
1
|
0
|
--->
|
0
|
1
|
--->
|
0
|
1
|
1
|
--->
|
0
|
0
|
--->
|
1
|
We get exactly what we desire, the AND function!
The XOR function is more complicated and I do not think we
gain a ton walking through it but I’ll show it and you can figure it out for
yourself:
XOR
Addition
The last thing we’ll create is an Adder, i.e. we will be
adding A and B together. Remember we are
using binary numbers so:
-
0+0 =00
-
1+0 =01
-
0+1 = 01
-
1+1 = 10
o
Just like in our traditional base 10 system
5+5=10, in binary 1+1 = 10
Since we only have our logic operators we are going to use
our friend the truth table to see what we need.
For the “1s” digit we have:
X+Y = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
0
|
0
|
1
|
--->
|
1
|
1
|
0
|
--->
|
1
|
1
|
1
|
--->
|
0
|
I hope this looks familiar, as it is exactly the XOR
function. So the ones digit will be solved with an XOR operator.
Let’s look at the 2’s digit or the “Carry” digit (just like 5+5 is 0 “Carry the
1” so is 1+1). The look up table is:
Carry(X+Y) = Z
|
|||
X
|
Y
|
--->
|
Z
|
0
|
0
|
--->
|
0
|
0
|
1
|
--->
|
0
|
1
|
0
|
--->
|
0
|
1
|
1
|
--->
|
1
|
Ding ding ding! This is just our AND operator. So to make a single bit adder we need to put
together our XOR and AND operators:
Single Bit Adder
Here are some ways we can expand on the single bit adder;
how do we add in the carry bit so we can add more than 1 bit at a time i.e. add
3 bits together; how do we subtract two numbers; how do we multiply two
numbers? We can do all of these things
with just the logic operators we have laid out in this post. We just keep putting the small pieces
together to build larger and more complex pieces.
These 7 operators and the ADD are the foundations of our
computers – hell they are why computers are called computers. We are doing Boolean arithmetic millions to
billions of time per second to shape our world!
The One True Bot!
ReplyDelete