Introduction

Now that we know the basic operators of Boolean algebra and we know the rules which govern their behaviour, it's time to put that to use. Typically we'll use the rules to simplify an expression, or to prove that two expressions are logically equal (that is, for a given set of inputs, both expressions will always give the same result).

Knowing how to do this can be very useful. An example of where this may be useful is that a boolean expression may be created as a formal representation of a set of rules. eg, there may be a set of conditions which must be met before someone is eligible to take out a loan at a bank. If there are many conditions and some of them are interrelated then we may benefit from being able to simplify them.

The general approach

For some people this will come easy. For others it may be confusing at first. If this is you, don't worry too much, with practice you will get better.

The general approach is to see if all or part of the expression looks like one side of one of our laws. If it does then we will try rewriting the expression with the other side of the law substituted in it's place. Then we repeat the process.

Some of the laws, such as the complement law allow us to replace part of the expression with either True or False, which is a good way to simplify the expression. Others such as the Identity or Idempotent laws allow us to replace an operator and two variables with a single variable. As we rearrange the expression we hope to create situations where these arise. This allows us to reduce the size and complexity of the expression.

Let's work through a few examples and hopefully the process will become clearer.

Example 1

x OR NOT(y AND x)

We may apply DeMorgan's Law to the second part of the expression.

x OR NOT(y AND x) becomes x or (NOT(y) OR NOT(x))

Because the operator outside the brackets is the same as the operator inside the brackets ( OR ), we may use the Associativity law to reorganise the brackets and variables.

(x or NOT(x)) OR NOT(y)

Now we may apply the Compliment law to the brackets.

(x or NOT(x)) OR NOT(y) becomes True OR NOT(y)

And finally, we may now apply the Identity law to arrive at:

True

From this we may conclude that no matter what the values are we feed into the original expression, the result will always be True.

Example 2

This one gets a little trickier. Make sure you pay attention to which parts are and aren't within which brackets.

NOT(r AND t) AND (NOT(r) OR t) AND (NOT(t) OR t)

First off, we can see that we can apply the Complement law to the bit at the end ( NOT(t) OR t ).

NOT(r AND t) AND (NOT(r) OR t) AND (NOT(t) OR t) = NOT(r AND t) AND (NOT(r) OR t) AND True

Following on from this we may now apply the Identity law:

NOT(r AND t) AND (NOT(r) OR t) AND True = NOT(r AND t) AND (NOT(r) OR t)

Then we apply DeMorgan's law to the first bit:

NOT(r AND t) AND (NOT(r) OR t)= (NOT(r) OR NOT(t)) AND (NOT(r) OR t)

We notice that NOT(r) is now in both sets of brackets. This allows us to apply the Distributivity law:

(NOT(r) OR NOT(t)) AND (NOT(r) OR t) = NOT(r) OR (NOT(t) AND t)

Using the Complement law we can see that the second bit ( NOT(t) AND t ) will always be False.

NOT(r) OR (NOT(t) AND t) = NOT(r) OR False

Applying the Identity law to this then gives us the following:

NOT(r) OR False = NOT(r)

And so we can see that what at first looked like quite a daunting expression may actually be simplified to something a lot more manageable.

Example 3

This time, instead of simplifying an expression, we'll aim to prove that two expressions are in fact equal.

NOT((v AND j) OR n) = (NOT(v) OR NOT(j)) AND NOT(n)

If we want to prove that the left hand expression does equal the right hand expression then we take the approach of starting with one and seing if we can transform it until it eventually looks like the other side. In this example I'll transform the left hand side into the right but there is really no reason why you couldn't do the other way if you prefer.

First off we could see that (v AND j) OR n may be transformed using the Distributivity law like so:

NOT((v AND j) OR n) = NOT((v OR n) AND (j OR n))

But this doesn't seem to be getting us closer. Sometimes this happens. There is an obvious transformation we may make but it kinda leads us to a dead end.

There is a second path we may take. This one is tricky to spot but once you are aware of them and with a bit of practice, they become easier to see.

What we are going to do is substitute part of the expression for another variable (or letter). We may do this because a variable may only be True or False and the result of an expression, or part of an expression will similarly always be only True or False.

B = (v AND j) Therefore NOT((v AND j) OR n) may be written as NOT(B OR n)

Whenever I do substitution in my expressions I like to use UPPERCASE letters so it is clear to me that it is a substitution and I don't forget to substitute it back at some point.

Now we can see that we have created an expression which we may apply DeMorgan's law to.

NOT(B OR n) = NOT(B) AND NOT(n)

The second part of the expression ( AND NOT(n) ) now looks like part of the original expression we are looking for. This is a good sign we are on the right track. We can leave this bit alone and see if we can transform the other bit into what we are after.

We can't do much with NOT(B) so maybe it's a good time to substitute B back to what it was originally and see what we get.

NOT(B) AND NOT(n) substituted back as NOT(v AND j) AND NOT(n)

And we see that we can apply DeMorgan's law again.

NOT(v AND j) AND NOT(n) = (NOT(v) OR NOT(j)) AND NOT(n)

Which is the expression on the right hand side of the original equation and hence we have proven that they are equal.

Summary