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.