IAN LANG ELECTRONICS
In true digital logic a component can be in one of two states: on or off. If it is on a voltage of (usually) 5V is present across the component, if off the voltage is nominally zero, though it never quite attains that. The way to achieve this is through a logic device, and this is commonly a gate or chain of gates. Logic gates can be ready purchased in the form of integrated circuits. We can analyse the behaviour of any logic gate by constructing a truth table, which is a grid listing all possible input combinations and then the resulting output. Let us begin then with the following circuit for which we shall construct a truth table:
There are two immediately apparent questions. The first is what kind of gates are these? The symbols are British Standards 3939 and a table of them appears below:
Apparently then what we have here is an And gate and an Xor gate. Do not confuse the Xor with the Xnor. If you look closely at the Xnor, on the right hand side you will see a little circle. This circle is in fact called a "bubble" and it signifies an inversion; or a "not". A not means the gate does the opposite of its counterpart. Do not worry if you do not understand the concept thus far, it should become clear as we progress further into this study.
The second question to present itself is how we may mathematically model the behaviour of the gate. To do this we use Boolean Expressions. We will learn more about these as we come to look at De Morgan's Law in the next topic, but for now we shall just look at the expressions for the gates we have.
Boole was an English mathematician and philosopher who applied mathematical principles to philosophy and postulated that any argument could either be true or false. Moreover whichever state the argument, this would either validate or invalidate any argument following. This is in fact the basis of binary logic, but Boole published this in his 1854 work " An Investigation of the Laws of Thought". This is some 82 years before Turing began to investigate computable numbers and 87 years before Turing and Flowers created the first digital computer, and yet Boole's mathematical philosophy played an invaluable part.
Let us look at the circuit again:
You will notice that each gate has two inputs, and one input of the Xor gate is in fact the output of the And gate. Where there is one gate the inputs are known as A and B but here for clarity the input to the Xor gate resulting from the output of the And gate is labelled x, and the other input to the Or gate is labelled C.
The Boolean Expression for an And gate is:
Output = AB
(that is A multiplied by B) and so if 5V is present at input A then input A is in logic condition 1. If 0V is present, then input A is logic condition 0 (and remember that in true logic it can be in either one or the other but not between). Logic condition 0 is therefore off, and condition 1 is on. Let us assume A=1 and B=0. Multiplying anything by 0 gives a product of 0, and so the logic condition of the output is 0. The same would be true if A=0 and B=1. If both are equal to zero, we are multiplying two zeroes, and output is condition zero. If however both are equal to 1, we are multiplying 1 by 1; this gives us an output at logic condition 1.
You can see that A and B need to be on (i.e. at logic condition 1) for the output to be at logic condition 1 too. This is how the And gate gets its name. We can record this in table format by listing all the possible combinations that both input A and input B can be in at the same time and then listing the output. This is called a truth table.
The table on the left is the truth table for the And gate and as you can see it gives in a graphic format the possible logical conditions in which the gate may find itself. In constructing this table we have in fact analysed half of our example circuit, and now we must construct a similar table for the Xor gate.
The Boolean expression for an Xor gate is:
The small bars at the top of the letters indicate an inversion, i.e. if A=1 then bar A=0. Because of the practical problems in doing this in computerised typeface, it is often written as ¬AB + A¬B.
We however, have declared one input to be x and the other to be C for our Xor gate. Our expression then is Output = ¬xC + x¬C. Let us assume that x=1 and C=0. Substituting we have (0 times 0) + (1 times 1) and that is equal to 0+1 which in turn is equal to 1, and so our output is logic condition 1. Using the same method for all possible input combinations we can now construct a truth table for the Xor gate:
And as you can see the output is logic condition 1 only when either (but not both) inputs are in logic condition 1. The name Xor is an abbreviation for Exclusive Or and it is easy to see how the gate got its name. We have now analysed the behaviour of both gates and it remains only to combine the truth tables to show the final output of the circuit. We shall do this step by step.
We know that the input x in the Xor truth gate is the output of the and gate. Therefore if we now write down all the possible combinations of Aand B in the And gate that produce logic condition 0 at the output. and then those that produce 1, we can begin our final analysis. Remember that we are going to compare with the logic states of input C and so each needs to be written twice:
Step 1: The conditions that produce (in red) a zero output and therefore a zero input to the Xor gate, input x. In black, those that produce a logic condition 1.
Step 2: Adding in all the possible combinations of A, B, and C. Now remember, the output condition of A and B is the input condition x of the Xor gate. The truth table we worked out for the Xor gate tells us that when conditions to both inputs are equal, we get logic condition 0 as the output. We have made the red print here equal to 0, and the black to 1. It is now a simple matter to compare and insert our final output conditions: where the inputs are the same put logic zero and where not put logic 1, and you get the table shown below:
Step 3: The finished table.
By breaking down like this any size of logic circuit can be quickly analysed, and any branch that flows into any other can be broken down into the constituent parts. Truth tables can be used to quickly "see" the path of a decision making circuit under any circumstance.