Boolean Algebra Laws!

Live by the X. Die by the X.

Introduction

Now that we understand the basic building blocks of Boolean Algebra it's time to take a look at how they behave and interact. Several of these laws are kinda similar to normal mathematical laws but slightly different so just be aware of that. In the next section we'll look at how these laws may be applied to expressions to modify and simplify them.

These laws are sometimes also referred to as boolean algebra rules.

Some of these laws may appear a little bit confusing at first. The best way to help make things clearer is to work through a few examples, replacing the terms with different sets of actual values and working out the result. This will help you to see how the process works and why it behaves the way it does.

There may seem like quite a bit of content on this page but don't be daunted. The laws are actually quite simple. Most of the content is just many examples to reduce any ambiguity.

Boolean Commutativity

This law of Boolean Algebra states that the order of terms for an expression (or part of an expression within brackets) may be reordered and the end result will not be affected.

a OR b = b OR a

Or with multiple terms:

a AND b AND c AND d = b AND d AND c AND a

This is also the case for part of an expression within brackets:

a AND (b OR C) = a AND (c OR b)

The brackets may be considered a single term themselves (remember, everything in Boolean Algebra always results in either True or False).

x OR (y AND z) = (y and z) OR x

Commutativity works for any operation which accepts two or more terms (eg. AND, OR, NOR, NAND, XOR).

Boolean Identity

The identity law observes how certain expressions will behave when one of the terms is fixed.

A term in an OR operation with a fixed value of False will result in the term:

g OR False = g

Similarly, a term in an AND operation with a fixed value of TRUE will result in the term.

h AND True = h

Boolean Complement Law

The complement law has to do with the relationship between a variable ( eg. c ) and the negation of that variable ( not(c) ). Let's consider the following expression:

c OR NOT(c) = True

If c is False then Not(c) must be True. And vice versa. Either way, one of them is always going to be True so the result will always be True.

Alternatively:

c AND NOT(c) = False

Taking into account the observation above it is impossible for both c and Not(c) to be True at the same time so this is always going to be False.

Boolean Idempotent Law

This law has to do with if a variable is repeated within an expression. Effectively it may be simplified to itself. So for instance:

r OR r = r and r AND r = r

If you think about it this makes sense as both sides of the expression are always going to be the same value if they are the same variable.

Boolean Double Negation Law

This law also makes sense once you think about it. This law states that if you negate a negation (ie if you have a NOT within a NOT) they effectively cancel each other out.

NOT(NOT(b)) = b

The first NOT flips the value of b, then the second NOT flips it back again.

This is only the case when both NOT's are applied to the same item.

NOT(NOT(d AND f)) = d AND f

But

NOT(NOT(v) OR t) ≠ v OR t

This is because the outer NOT applies to NOT(v) OR t but the inner NOT applies only to v. They apply to different parts of the expression and so may not be cancelled out.

Boolean Associativity

This law looks at brackets (or groupings) within an expression and how they may be reorganised or even removed. If all the operators within an expression (or part of an expression) are the same then this may be done. So:

a OR b OR c = (a OR b) OR c = a OR (b OR c) = (a OR c) OR b

And:

a AND b AND c = (a AND b) AND c = a AND (b AND c) = (a AND c) AND b

It may also be done for just part of an expression which fits. So:

a AND (b OR c OR d) = a AND (b OR (c OR d))

But if the operators are mixed then this may not happen.

a AND (b OR c) ≠ (a AND b) OR c

If this doesn't quite make sense then try assigning some values to a, b and c and create a truth table to observe the outcome for both expressions. This will help to make it clearer.

Boolean Distributivity

This law is similar to distributivity in normal mathematics and has to do with expanding or simplifying brackets. This may be done when one of AND or OR is inside the brackets and the other is outside.

e AND (f OR g) = (e AND f) OR (e AND g) and e OR (f AND g) = (e OR f) AND (e OR g)

Notice that the two variations are the inverse of each other and that in both situations the operation which is inside the brackets on one side of the expression is outside the brackets on the other side (and vice versa).

de Morgans' Laws

de Morgans' laws may seem a little odd at first but in later sections you will see that they actually become very useful when attempting certain types of manipulations.

Like I've suggested for a few of the laws above, try putting some values into a truth table for both sides of the above expressions and this will help you to gain a better feel for how they operate.

Here they are:

NOT(p AND k) = NOT(p) OR NOT(k) and NOT(p OR k) = NOT(p) AND NOT(k)

Boolean Absorptive Law

The Absorptive law is another one which is useful in simplification (normally after rearranging the expression using other laws).

s AND (s OR w) = s and s OR (s AND w) = s

Remembering the Laws

Remembering the laws can be useful. If you're having to simplify expressions often it is more convenient if you don't have to look them up constantly. Also, if you're learning this as a student, often you will be required to remember them for an exam.

Practice is the best way to achieve this. As with a lot of things in Boolean Algebra, the laws are logical. You will have a much better time remembering them if you understand why they work.

You'll also note that there is a reflection between AND and OR in a lot of the laws. This is known as duality. You can take advantage of this to reduce the amount you need to remember in order to recreate the laws.

For example...

Summary

Commutativity
a OR b = b OR a
Identity
a OR False = a, h AND True = h
Complement
a OR NOT(a) = True, a AND NOT(a) = False
Idempotent
a OR a = a, a AND a = a
Double Negation
NOT(NOT(a)) = a
Associativity
a OR b OR c = (a OR b) OR c = a OR (b OR c)
a AND b AND c = (a AND b) AND c = a AND (b AND c)
Distributivity
a AND (b OR c) = (a AND b) or (a AND c), a OR (b AND c) = (a OR b) AND (a OR c)
de Morgans'
NOT(a AND b) = NOT(a) OR NOT(b), NOT (a OR b) = NOT(a) AND NOT(b)
Absorptive
a AND (a OR b) = a, a OR (a AND b) = a
Duality
Notice the patterns and reflections of AND's and OR's in the rules and this will help you to more easily remember them.

Can't you just put the Truth Tables here for us?

On several occassions in this chapter I have suggested you create a truth table to observe how the rule behaves. You may be of the opinion that it would be easier and more convenient if I just put the truth tables here on the page. The reason I have not done this is that Boolean Algebra is quite an abstract beast and you can really only fully comprehend it by doing it yourself.

I have had many many students tell me that 'they can just look at an example, they get it, it's fine'. When it came to actually implementing the laws however, with the exception of a very few talented students, all have found that they didn't quite understand to the extent they thought they did.

Learning Boolean Algebra is like learning to ride a bike, or to juggle. You may read all the reference material you like but you won't stand a chance of mastering it until you get in and start doing.