Boolean Algebra

Please don’t let the word Algebra frighten you… it’s pretty straight forward once you get used to the ideas.

What is Boolean Algebra

In short, it is a means of writing and assessing boolean logic statements using a kind of mathematical notation. The term boolean comes from George Boole, the inventor of Boolean Algebra, and is normally used in reference to a computer programming datatype that has two states. TRUE and FALSE. So, as you can see, it should be pretty easy as we only have two possible input and output values.

The Operations

As with maths, there are various operations that can be performed using Boolean Algebra, but they are much fewer in number than in maths. The basic operators are AND, OR and NOT. AND and OR are binary operators (that is they take two values – they can take more, but for the sake of this explanation, I’ll restrict them to two) while NOT is a unary operator (that is it takes only one value).

The AND Operator
The result from the AND operator will be true if input A AND B are both true.

The OR Operator
The result from the OR operator will be true if input A OR B are true. What happens if they are both true? The result is true.

The NOT Operator
The result from the NOT operator will be true if it’s input is false.

Truth Tables

Whilst the text descriptions above illustrate the basic point, we can illustrate the full operation of the basic gates using what is called a ‘Truth Table’. See if you can guess which operator this table descibes:-

Inputs  
A B Output
0 0 0
0 1 0
1 0 0
1 1 1

If you guessed it was the AND operator, you’d be correct. The other operators are outlined below.

OR Operator

Inputs  
A B Output
0 0 0
0 1 1
1 0 1
1 1 1

NOT Operator

Input Output
0 1
1 0

Writing Boolean Algebra Quickly

Obviously, writing A AND B OR C is easy enough when you are working with simple statements, but the bigger the statement, the more long winded it becomes. So, just like maths, Boolean Algebra uses a set of symbols to represent the operators. Unfortunately, NOT is represented by a line above the operands or operators, thats a bit tricky to represent when typing, so NOT is usually represented using the ! (exclamation mark) character. Well, when I say usually, I usually use it (C, C++, PHP… amongst others… also use ! to represent NOT, so it does make sense).

AND as a symbol
If we write ‘A AND B’, using a symbol, it becomes A . B

OR as a symbol
If we write ‘A OR B’, using a symbol, it becomes A + B

NOT as a symbol
If we write ‘A = NOT B’, using symbols it becomes A = ! B

So, OUTPUT = (A AND NOT B) OR (NOT A AND B), becomes:-

OUTPUT = ( A . (!B) ) + ( (!A) . B )

The brackets add clarity by explicitly stating operator precedence (i.e. what you do first). Ordinarily, NOT takes priority over AND, which in turn takes priority over OR.

Derived Operators

There are numerous derived operators (Check out the Wikipedia page on Boolean Algebra for more information), but the three most common ones you may encounter are NAND, NOR and XOR.

NAND – NOT AND
I shall write NAND like this ‘!( A . B )’. It’s truth table is as follows:-

Inputs  
A B Output
0 0 1
0 1 1
1 0 1
1 1 0

NOR – NOT OR
I shall write NOR like this ‘!( A + B )’. It’s truth table is as follows:-

Inputs  
A B Output
0 0 1
0 1 0
1 0 0
1 1 0

And finally…

XOR – EXclusive OR
I shall write XOR like this ‘A * B’. This is a special case as it isn’t simply an inversion of it’s basic operator cousin, rather it is a complex statement that returns true if A or B is true. Sounds like an OR gate, with one notable exception… if both inputs are the same, it returns false.

The long winded way of writing this is:- ( A . (!B) ) + ( (!A) . B )

Look familiar?

It’s truth table is as follows:-

Inputs  
A B Output
0 0 0
0 1 1
1 0 1
1 1 0

Problems with XOR… as you can see, with two inputs, XOR makes perfect sense. But, unlike the other binary operators (AND, OR, NAND and NOR), there exist multiple definitions of XOR’s with more than two inputs. The two most common are:-

  • A gate whose output is true when exactly one input is true
  • A gate whose output is true when an odd number of inputs are true

The later is the most common, and is easily implemented by cascading a series of two input or gates. i.e. ‘A * B * C’ becomes ‘( ( A * B ) * C )’. Only the final application of the gate will be able to decide which of these two options you need.

Conclusion

That concludes my very brief tutorial on Boolean Algebra and the basic logic gates I’ll be using later on. If you want to know more, I would check out the links to Wikipedia I’ve included on the tutorial, in particular the two about Boolean Algebra and Karnaugh Maps (a very useful, if a little daunting, tool for simplifying complex logic).

You can skip to the end and leave a response. Pinging is currently not allowed.

Leave a Reply

 

Bad Behavior has blocked 73 access attempts in the last 7 days.