PROCESSOR FUNDAMENTALS
3.6 BOOLEAN ALGEBRA

WHAT IS BOOLEAN ALGEBRA

Boolean algebra is used in computer science to represent logic gate circuits. Rather than draw the logic gate diagram the circuit can be written like a normal math algebra expression and can be simplified using a few boolean algebra rules. Simplifying an expression will help you to reduce the number of logic gates needed in a circuit.

Logic gate circuits can be expressed with an algebraic expression. Whilst there are various ways to represent each logic gate, this section will only deal with OR, AND and NOT and the gates will be represent as follows.

OR - The OR gate is represented with a Plus sign. For example A+B  
AND - The AND gate is represented with a dot. For example A​·B
NOT - The NOT gate is represented with a overbar. For example Ā

METHODS TO SIMPLIFY BOOLEAN EXPRESSIONS

Although there are many methods of simplifying boolean expressions, here we will focus on the following 6 methods/laws.
Double Negation Law
Applying Identity
Commutative property Law
Change the line, change the sign
Distributive property Law
Associative property Law
Each of these methods are explained in more detail below with logic gate examples

DOUBLE NEGATIVE LAW

Rule: Double negatives cancel each other out. Looking at the logic gate circuit, when NOT A is NOTED again it becomes what is was at the start, so double not gates cancel each other out. In boolean algebra where a representation has two lines over it then this represents a double NOT. These cancel each other out as can be seen in the boolean expression below.

APPLYING IDENTITY

Applying identity is the rule that looks at - a term OR´ed with a “0” or AND´ed with a “1” will always equal that term
A + 0 = A
A . 1 = A

COMMUTATIVE PROPERTY LAW

Commutative property Law ​of addition and multiplication - It does not matter which way around the variables go.
A + B = B + A
A . B = B . A

ASSOCIATIVE PROPERTY LAW

​Associative property law covers the removal of brackets and regrouping, for example: 
Circuit 1: A + (B + C) = (A + B) + C 
Circuit 2: A(BC) = (AB)C 
As can be seen both circuits have the same outcome but use different logic gates 

ABOVE CIRCUIT SHOWING:  A + (B + C) = (A + B) + C 

ABOVE CIRCUIT SHOWING: A + (B + C) = (A + B) + C 

DISTRIBUTIVE PROPERTY LAW

​Distributive property law covers multiplying or factoring out an expression, for example: 
A(B + C) = A . B + A . C (OR Distributive Law) 
A + (A . B) = (A + B).(A + C) (AND Distributive Law) 

ABOVE CIRCUIT SHOWING: ​A(B + C) = A . B + A . C (OR Distributive Law)

CHANGE THE LINE - CHANGE THE SIGN

If terms are NOT'ed together then, you can follow the rule of ' Break the line, change the sign'. This rule is very popular in simplifying expressions and a rule that often comes up in examination questions. 

​The truth tables above show how breaking the line and changing the sign work for the example expression. 

WRITING A BOOLEAN EXPRESSION

The illustration below shows how to breakdown a logic statement into a boolean expression.

When writing an expression from a given logic circuit it is often useful to work from the last gate and work backwards breaking the circuit up into smaller expression where possible.

SOME SIMPLIFYING EXPRESSION EXAMPLES

EXAMPLE 1
Using the double negative law covered in this section to simplify algebra expressions and reduce the amount of logic gates needed to complete a task. 

IMAGE ABOVE SHOWING: Logic Gate circuit showing before and after simplification 

EXAMPLE 2
Looking at the expression: X = A + ( A · B ). From the Logic Gate diagram below it is clear to see that the value of B will not effect the outcome. If A is 0 then B will not pass the AND gate. If a is 1 then A will pass the OR gate. So as can be seen in the simplified expression X will always equal A. 

The logic circuit simplified is:
X = A + ( A · B )
X = A

EXAMPLE 3
The below simplification shows Associative law regrouping, then uses the fact that A + Ā = 1 and finally because we are dealing with boolean 1 + 1 = 1, therefore X = 1 

EXAMPLE 4
The below expression shows Identity law being applied to simplify a boolean expression.
X = A · B + B    Identity Law - A term OR'ed with itself is the term itself. (B OR'ed with B = B) 
X = A · B 

EXAMPLE 5
​The example below shows that A + NOT A will always equal 1 (or True) and B and'ed with 1 will always equal B, so the expression can be simplified to X = B
X = B(A + Ā)    A + Ā = 1 
X = B · 1  Applying Identity Law 
X = B 

EXAMPLE 6
The example in the illustration below show a chain of changes being made, it is recommended that you only change one thing per step. Below is an example of breaking the task down, by changing one item at a time you are less likely to make mistakes, you are also more likely to receive full marks in your test even if just one stage of your working is incorrect and in some cases even if the end result is not as expected by the examiner. 

Always show your working out

NEXT: DATA STORAGE