Deriving Boolean expressions from logic gate diagrams
Introduction
Sometimes, we need to be able to derive the Boolean expression of a logic gate diagram. We might want to do this, for example, so that we can investigate simplifying the design. We will look at some examples of this now.
Example 1
Consider the following circuit gate diagram:
The first thing to do is to split up the logic gate diagram into more manageable parts. Sometimes, there are a number of ways you can do this. You should just divide up the diagram in what you think is the best way and see what happens!
Next, you need to start on the left and work your way through each part, working out what the output is after each gate.
After part 1, we have A.B and A + B
After part 2, we have inverted A.B so we now have A.B
After part 3, we have put the parts together in an AND gate from part 2 and have
(A.B)(A + B)
Let's draw out the truth table for this diagram, just for fun:
You may have noticed from this truth table that the output is exactly the same as an XOR gate. In an XOR gate, you get an output if both input signals are different. That's what we have here.
We didn't have to produce the truth table for the circuit diagram to see that all we needed to use was an XOR gate. We could have used our Boolean identities and rules. Let's do that now.
(A.B)(A + B) = Q
Applying the De Morgan's rule that states XY ≡ X + Y we get
(A + B)(A + B)
Expanding this out using the distributive rule, we get
A.A + A.B + B.A + B.B
Using the rule A.A = 0 and the commutative rule, we can eliminate the first and last terms, so we are left with
A.B + B.A = Q
Let's have a look at the truth table for this simplified Boolean equation:
You can see that the output of this truth table is the same as the previous truth table. Out simplified Boolean expression must therefore be equivalent to the original. Since we have already identified the output as the output of an XOR gate, we can replace the whole original circuit with just this:
and save a lot of money in components, complexity and construction!
Example 2
Consider the following logic gate diagram.
We started by splitting up our diagram into parts.
We started on the left, and worked out what the logic expression was after each gate.
We continued doing this from left to right until we got to the final logic gate.
This is a completely different design, yet purely by coincidence, we have again ended up with the logic for an XOR gate! There are always many different designs for a logic gate diagram that achieves a desired output. The trick is to find the simplest one. We would again replace the original design with just a single XOR gate.
Example 3
It doesn't matter how many inputs you have, or even if your circuit diagram includes NAND or NOR gates. Consider the following logic gate diagram.
You can see that have followed exactly the same procedure as before.
a) Make sure that you understand the logic for the NAND gate in the above diagram.
b) Study the output Boolean expression. Can you see any opportunities for applying any laws you know to simplify it?