The twelve basic equivalences in Boolean logic
Introduction
We need to become proficient in manipulating Boolean expressions. There are quite a few rules and techniques that can helps us do this. We will begin at the beginning and look at the first twelve identities that are going to help us. We you look at each example, remember that any of the variables A, B or C can be a single variable or a combination of variables. We will see examples of this later on.
AND Λ
When we have a Boolean expression involving AND, there are some things to look out for. These are as follows:
A Λ 0 (This means A AND 0)
A Λ 1 (This means A AND 1)
A Λ A (This means A AND A)
A Λ ¬A (This means A AND (NOT A))
Unfortunately, the exam board OCR have said that they will set questions using this notation so we need to get used to it. Let's look at each of these in turn.
A Λ 0 can be represented using this logic diagram. If one of the inputs is fixed to be a 0, then it really doesn't matter what the other input is; the output Q can never become a 1 as our AND truth table says that both inputs into an AND gate must be a 1 for the output to be a 1, else the output is a 0. So we can say that A AND 0 is equivalent to 0 and we can write that in notation like this:
A Λ 0 ≡ 0
A Λ 1 can be represented using this logic diagram. If one of the inputs is fixed to be a 1, then if A is a 1, both inputs are 1 and the output is a 1. If A is 0, then the output is 0. The output is in fact whatever A is. So we can say that A AND 1 is equivalent to A and we can write that in notation like this:
A Λ 1 ≡ A
A Λ A can be represented using this logic diagram. If both inputs are A, then if A is a 1, both inputs are 1 and the output is a 1. If A is 0, then the output is 0. The output is in fact whatever A is. So we can say that A AND A is equivalent to A and we can write that in notation like this:
A Λ A ≡ A
A Λ ¬A can be represented using this logic diagram. Note the bar over the A. This is a common way of showing NOT. If one input is A and the other input is the opposite of A, then the output Q can never become a 1 as our AND truth table says that both inputs into an AND gate must be a 1 for the output to be a 1, else the output is a 0, and that just can't happen. The output is in fact 0. So we can say that A AND (NOT A) is equivalent to 0 and we can write that in notation like this:
A Λ ¬A ≡ 0
OR V
When we have a Boolean expression involving OR, like AND there are some things to look out for. These are as follows:
A V 0 (This means A OR 0)
A V 1 (This means A OR 1)
A V A (This means A OR A)
A V ¬A (This means A OR (NOT A))
A V 0 can be represented using this logic diagram. If one input is fixed at 0, then if A is a 1, the output is a 1. If A is a 0, the output is a 0. The output is in fact whatever A is. We can say that A OR 0 is the equivalent of A. We can write that in notation like this:
A V 0 ≡ A
A V 1 can be represented using this logic diagram. If one input is fixed at 1, then it doesn't matter what A is. The output will always be 1. We can say that A OR 1 is the equivalent of 1. We can write that in notation like this:
A V 1 ≡ 1
A V A can be represented using this logic diagram. If both inputs are A, then the output will be whatever A is. We can say that A OR A is the equivalent of A. We can write that in notation like this:
A V A ≡ A
A V ¬A can be represented using this logic diagram. Note the bar over the A. This is a common way of showing NOT. If one input is fixed at NOT A, then if A is a 1, the output is a 1. If A is a 0, the output is still 1. The output is in fact always 1. We can say that A OR (NOT A) is the equivalent of 1. We can write that in notation like this:
A V ¬A ≡ 1
Double negation
What hapens if you do NOT NOT A? The alternative notation for this would be ¬ ¬A. If you consider the logic circuit for a double negation, showing what happens when you feed the circuit a 0 and what happens when you feed the circuit a 1, you would hopefully draw something like this:
You can see in the top circuit, if you feed in a 0, the first NOT gate makes it a 1 and the second not gate makes it a 0.
You can see in the bottom circuit, if you feed in a 1, the first NOT gate makes it a 0 and the second not gate makes it a 1.
If you have a double negation, it's like not having the double negation at all. The output is the same as whatever it was to start with. This is another thing to look out for when working with or simplifying expressions. We can represent this using notation:
¬ ¬A ≡ A
A OR (A AND B) ≡ A
So far in this section, we have specified nine of the twelve standard equivalences (you can just call them rules if you want) that you need to know to be able to start simplifying Boolean equations. These twelve are the starting twelve. There are others, which we will come to in later sections. We have three more equivalences to cover in this section. Let's look at A OR (A AND B) ≡ A which we can also write in notation as A V (A Λ B) ≡ A. You can see the equivalent logic gate diagram for this on the left.
If A is a 1, then because of the OR gate, the output Q will be a 1. If A is a 0, then the AND gate output can never be 1 and both inputs to the OR gate will be 0. The output will therefore be 0. In other words, Q is always the same as whatever A is, or A V (A Λ B) ≡ A.
You can also prove this using Boolean algebra.
A OR (A AND B), using the distributive law to factorise this, we get
≡ A AND (1 + B), using our law that A OR 1 = 1, we get
≡ A AND 1, using our law that A AND 1 is always A, we get
≡ A
A OR ((NOT A) AND B) ≡ A OR B
Let's look at A OR ((NOT A) AND B) ≡ A OR B which we can also write in notation as A V (¬A Λ B) ≡ A V B. You can see the equivalent logic gate diagram for this below.
Now this is a little more complicated so we are going to prove this identity using a truth table. The point C in the diagram is the opposite of whatever A is. D is B AND C. The output Q is A or D. If you look at the output for Q, this is identical to the output for A OR B so we have proven the equivalence. We can also prove this using Boolean algebra. This time, we will introduce another notation, that many people find easist to use when manipulating Boolean algebra.
For AND, (which remember is the same as multiplication in normal algebra), we just omit the AND, so for example, instead of writing A AND B, we write AB There are occasions when a dot is used as well for AND, so we might also write A.B
For OR, which remember is the same as addition in normal algebra, we use the plus sign. For example, instead of writing A OR B, we write A + B.
For NOT, we overscore the variable. for example, NOT A becomes A.
A + AB = (A + AB) + AB using the rule that A - A + AB
≡ (AA + AB) + AB using A = AA
≡ AA + AB + AA + AB adding AA = 0
≡ (A + A)(A + B) taking out factors
≡ 1(A + B) using A + A = 1
≡ (A + B) removing the 1.
(A OR B) AND (A OR C) ≡ A OR (B AND C)
We will prove this by looking at the two logic diagrams on each side of the equivalence, working out the truth table for each one and then comparing them.
As you can see, we proven that (A OR B) AND (A OR C) ≡ A OR (B AND C) and in notation, (A V B) Λ (A V C) ≡ A V (B Λ C)
We can prove this using Boolean algebra.
(A + B)(A + C) = AA + AC + AB + BC using the distributive law
≡ A + AC + AB + BC using AA = A
≡ A( 1 + C) + AB + BC using 1 + C = 1
≡ A. 1 + AB + BC using factoring (distributive law)
≡ A(1 + B) + BC using 1 + B = 1
≡ A. 1 + BC using A . 1 = A
≡ A + BC
We have now got 12 rules that we can use when specifying Boolean equations, or when we want to look at an existing equation and try to simplify it. There are, however, a few more that we need to know! These are the commutative, associative and distributive laws, and we also need to know and be able to use De Morgan's laws. We will deal with this in future sections.