Skriptd

Boolean Logic

Daniel Fone | October 17, 2008 on 1:00 pm | In Hello World | 1 Comment

The foundation upon which all computing lies is the Boolean. A Boolean is a simple concept, in fact, the simplest of concepts. To quote from the film Antitrust:

You’re either a one or a zero. Alive or dead

And that’s just it, we’re talking either true or false. Simple. Every task from the most complex mathematics to the latest 3D games are simply a series of yes/no decisions. One of the objectives of this series is to understand how these complex programmatic solutions can be built on top of such trivial beginnings. Let’s build a real-life decision making process.

Shall I make the tea? Yes, if it’s Tuesday OR Wednesday OR Thursday AND my wife reminded me to get the meat out of the freezer. We do this all the time - take a series of yes/no “inputs” and produce a yes/no “output”. As it turns out, computers are very good at this (It’s the only thing they’re any good at at all!) because it can be done by tiny wee bits of electronics called transistors. But before we get to the stuff you can touch, let’s keep our head in the clouds and take a look at this Boolean logic stuff.

Simple Boolean Operators

The simplest thing we can do to make a decision is to combine two Booleans in different ways and produce a Boolean result. If we have two inputs and two options for each (yes/no) we get four possible combinations that require an outcome. Let’s check out some important examples.

AND - Simple enough, if both inputs are true the output will be true. You can buy icecream if you can afford it AND you’re not lactose intolerant.

OR - If either input is true, the output will be true. You stay out of jail by keeping the law OR bribing the cops.

NOT - Simply inverts (produces the opposite) of the input. Someone is alive if they are NOT dead. Mostly.

These are our three primary logical operations. From combinations of these all other* operands can be produced.

Composite Boolean Operators

XOR - If the inputs are *different* (only *one* of the inputs are true) the output will be true. It’s a little more complex to apply XOR to an everyday situation but we’ll see what we can do.

Imagine you’re in a car and you’ve got to turn two corners. You can either turn Right or Left (Not Right) at each. Commonsense dictates that if we turn Right twice, or Not Right twice, we’ll be going back the way we came. If we turn a different way each time, we’ll be going straight ahead. You’re still going straight ahead if you turn right 1st AND (NOT right 2nd ) OR (NOT right 1st ) AND right 2nd.

Ok, I’ll admit that’s a stretch of the imagination, but it shows how these operators can be combined. ( a XOR b ) == ( ( a AND NOT b ) OR ( b AND NOT a ) ). In order to understand what’s going on here, we can use a device called a truth table. This is done by having each input in a column, then producing the output beside them. To continue our example from above:

Are we going straight ahead?

1st Right	2nd Right	1st XOR 2nd (Straight)
True	False	True
True	True	False
False	False	False
False	True	True

Two other very important operators are NAND and NOR.

NAND - Simply an inverted AND. You can choose NOT to take the bus if it’s raining AND you have petrol.

Is Raining	Have Petrol	Is Raining NAND Have Petrol (Take The Bus?)
True	True	False
False	True	True
True	False	True
False	False	True

As you can see, they are simply the opposites of their regular cousins and, in fact, any logical operator can be produced simply by using combinations of NAND or NOR. When we start implementing this logic with electronic components, we’ll see why this is important.

• NOT a = a NAND a
• a AND b = ( a NAND b ) NAND ( a NAND b )
• a OR b = ( a NAND a ) NAND ( b NAND b )

To see how this works, you can put the statements together using truth tables. Alternatively, you can check out this site, but you’ll have to understand the concept of gates, which we’ll get to next time.

Summary

Because we are dealing with the very simplest of information, it is trivial for a physical system to “compute” the outcome of our decisions. This week we’ve looked at:

• The fundamental unit of information - true|false
• Basic logic statements - NOT, AND, OR
• More complex logic - XOR, NAND, NOR
• How we can use combinations of operands like NAND to mimic any other operand

Next time we’ll look at how we can create a physical system to imitate these logical operands.

–

* There are actually 16 different Boolean operators. There are two possible outcomes for every combination of inputs (4). Logically, 2⁴ is 16.