MorkaLork Development

Interesting stuff I've picked up over the years...

Boolean Algebra

2009-05-14 13:00:04 | 1091 views | boolean algebra

What this article is about and what it's not



This article will not explain everything about boolean algebra or even go deep into the subject. It will not show the greater use of boolean algebra or go into the areas where it may be applied.

This article will not go into the history of George Boole or his work.

It will however connect to the previous article regarding Set theory and Venn diagrams and explain boolean algebra from a perspective where it is hopefully clear how it can be used together with those concepts.


What is boolean algebra?


Boolean algebra is an algebra where only two values are used, true or false. When working with boolean algebra you have three operators, ∩ (AND), U (OR) and ¬ (NOT). The NOT operator can also be described with a ' (apostroph), an overline, or, in some cases, a ! (exlamation mark).
The ∩ (AND) operator can be translated into the general * operator from normal algebra and the U (OR) operator can be translated into +.
A∩B is often shortened down to A.B or just AB. Thus AB + B means A AND B OR B

These operators can be used to manipulate the values at hand in order to get logical results regarding the states of the values.
For example:

A∩B can be translated into A AND B.

Now, as variables these are quite pointless, but if they were to have real values such as
A = I'm blind
B = I can see

then this would be correct:

A∩B = false

This is false since I can't be blind and see at the same time (unless this is some philosophical mumbo-jumbo article, which this isn't). We can read the equation like this: "I'm blind AND I can see".
What we want here is actually to use the OR operator:

AUB = true

This is true since with the OR operator, you only get a true value if one of the values is true. We can read this equation like this: "I'm blind OR I can see". It's a silly statement, I admit that, but I'm either blind or I can see, both statements can't be true.
We can also use the negation, or NOT sign here:

¬A = true

This is true since I'm not blind (now, you didn't know that, but that's how it is, I'm not) and this simply means that statement A is not true, which it isn't.


Truth tables


Oh hell, nobody expected the spanish inquisition in this article. Well, good thing they aren't comming then. Truth tables are used to display the composition of logical expressions, and they are very handy when it comes to boolean algebra.

This is what they look like:

A truth table with explanation below

To translate this table, we take a look at the first row.
It tells us that X = 0 and Y = 0. This can be read in several ways, but if we look at the ∩ operator column it goes like this:

X∩Y
or
X AND Y
or
0 AND 0

And the answer we get is of course 0, cause 0 and 0 gives us 0 (false AND false equals false).
The U operator columne goes like this:

XUY
or
X OR Y
or
0 OR 0

Regardless, we get zero, cause 0 or 0 leaves us with either 0 or 0.

If we look at the second line too we can see that we are actually getting some values.
It tells us that X = 1 and Y = 0. This can be read in the following way (starting with the AND operator):

X∩Y
or
X AND Y
or
1 AND 0

The AND operator need to equal values to obtain a true outcome, but here we only have on, so the outcome is false, 0 (true AND false equals false).
The OR operator however gives us another answer:

XUY
or
X OR Y
or
1 OR 0

Here we get true because it's either 1 or 0. The values are not the same, thus we get a true reading.

With this help you should be able to understand the last two rows.

When it comes to the negation part there are only two posibilities, either it's true or it's false. If we negate 0 we get 1 and vice versa.


Boolean laws


As in most math there are some rules to follow, boolean algebra doesn't deviate from that pattern.

The rules are as follows: Associativity, Distributivity, Commutativity and De Morgan's Laws. The first three apply only to the AND or OR operator. DeMorgan's law will deal with negation parts.


Associativity
From wikipedia: Associativity is the property of algebra that the order of evaluation of the terms is immaterial.
In plain language this law stipulates that the order in which the equation is done is irrelevant. This applies only as long as one operand is used:

A∩(B∩C) = (A∩B)UC
AU(BUC) = (AUB)UC

They way to read this is that whatever equation is inside the parentheses is handled prior to anything else. This law shows us that this is irrelevant and that the parentheses can be placed anywhere.

Distributivity
From wikipedia: Distibutivity is the property that an operator can be applied to the terms within the brackets.
This means that the operator in use applies to both elements withing the parentheses:

A∩(BUC) = (A∩B)U(A∩C)
AU(B∩C) = (AUB)∩(AUC)

Commutativity
From wikipedia: Commutativity is the property that order of application of an operator is immaterial.
This means that it doesn't matter in what order the variables come:

A∩B = B∩A
AUB = BUA

De Morgan's Law
From wikipedia: De Morgan's Law is a consequence of the fact that the not or negation operator is not distributive.
This is a way to understand negations and the fact that you cannot distribute the operator. The operator is negatedif you do:

¬(A∩B) = (¬A) U (¬B)
¬(AUB) = (¬A) ∩ (¬B)

If you translate this it becomes clear. The first one (¬(A∩B) = (¬A) U (¬B)) reads "NOT A AND B equals NOT A OR NOT B" which means that both A and B can't be true.
The second one translates into "NOT A OR B equals NOT A AND NOT B"


Boolean algebra and Venn diagrams


As I hinted in the beginning of this article, boolean algebra and Venn diagrams can be used together, so let's take a look at how to use Venn diagrams to explain the logic behind boolean algebra:

AB


A venn diagram highlighting the AB area

What we see here is a Venn diagram with two circles, A and B. They share a common area in the middle, AB.
AB is the same as A∩B which means A AND B. The marked area is exactly the area which fulfills that requirement, namely "the area belonging to both A and B".

Let's take more examples:

A'B


A venn diagram highlighting the A'B area

In this image only the area belonging directly to B is shown.

(A+B')'


A venn diagram using DeMorgan's law

Right, now we're gonna use DeMorgan's law since we have a double negation on our hands. (A+B')' means that we negate both A and B (apostrophe being used as negation sign in text, overline in picture), but B is also negated inside the parenthesis. Thus we have a double negation. The picture has 4 steps, let's comment each step:

1. (A+B')' Means NOT A OR NOT NOT B
2. We remove the parentheses and distribute a negation sign to each variable thus having A' AND B'' left (notice the switch of operands)
3. Since two minuses equals positive the B drops the negations and what we have left is:
4. NOT A AND B, which is what we highlight in the picture.



Phew, that about does it for now...





Article comments

Feel free to comment this article using a facebook profile.

I'm using facebook accounts for identification since even akismet couldn't handle all the spam I receive every day.