Video Transcript
The diagram shows a logic circuit consisting of three AND gates. How many different possible combinations of input values are there for this circuit?
So we’ve been given a diagram of a logic circuit which has three AND gates in it. This circuit has four inputs which are labeled as A, B, C, and D. We can see that inputs A and B are the two inputs to this top AND gate, while inputs C And D are the two inputs to this lower AND gate here. The outputs from these two AND gates then become the two inputs for this third AND gate on the right-hand side of the circuit. And then, the output from this third AND gate becomes the overall output of the logic circuit. Now, it turns out that in this question, we’re not actually concerned about this output value at all. We are only asked to consider these four input values. Specifically, we need to work out how many different possible combinations of input values that there are.
To do this, we need to recall that when we’re talking about logic circuits, there’re only two possible values, and these are zero and one. This means that in our circuit, each of the inputs can either have a value of zero or a value of one. So input A could either have a value of zero or a value of one. This means that there’re two possibilities for the value of input A. In exactly the same way, input B can either be equal to zero or one. So there’s two possibilities for the value of input B.
Likewise, input C can also be either of these two possibilities zero or one. And finally, of course, the same is true for input D. It can also be either zero or one, so again, that’s two possibilities. We can summarize this by saying that each of the inputs A, B, C, and D can either have a value of zero or a value of one, in other words, that each of four inputs can take either one of two possible values.
We are being asked to find how many different possible combinations of these input values that there are. Now, one possible approach to this would be to go through and try and list out explicitly all of the different combinations. We could do this, for example, by starting with the case where all four of the inputs A, B, C, and D have a value of zero. Of course, each of these four inputs could also have a value of one, and the value of each individual input is completely independent of the values of the others. So from here, we would need to methodically work through and find all the different possible combinations of zeros and ones. We could have the case where inputs A, B, and C are all zero, but input D is one. Alternatively, we could have A is zero, B is zero, C is one, but D is zero.
Now, we could continue on in this way until we’ve listed every possible combination. And from there, we’d need to count up the number of combinations we’d come up with in order to get our answer. However, we’re not going to do this because it turns out that there’s a better approach we can use. The problem with trying to write out every possible combination like this is not just that it could take us a while but also that it would be easy to accidentally miss out one of the possibilities.
So, let’s now have a look at this better approach which doesn’t share this potential pitfall. We have four different inputs, each of which can take either of two possible values. These four inputs are completely independent of each other, which means that for each of the two values zero or one that input A can take, input B can be either zero or one, input C can be either zero or one, and input D can also be either zero or one. So the total number of different possible combinations must be equal to the two possibilities for input A multiplied by the two possibilities for input B multiplied by the two possibilities for input C and, finally, multiplied by the two possibilities for input D.
So then, this total number of combinations is equal to two times two times two times two, where that’s one factor of two for each of the four inputs to the logic circuit. We can rewrite this product of factors of two as two raised to the power of four. If we look at this expression for the number of combinations, we can identify two as the number of different values that each input could have because each of the inputs could either be zero or one. We can also identify four, the power that two is raised to, as the number of different inputs because we’ve got the four inputs A, B, C, and D.
In fact, as a bit of an aside, this result generalizes so that if we had a logic circuit with 𝑁 inputs, then there would be two to the power of 𝑁 different combinations of input values. That’s because each of these 𝑁 inputs could have either of the two input values zero or one. So just as when we had four inputs and we had two times two times two times two, that’s four factors of two, and this gave us two to the power of four, then for 𝑁 inputs we have 𝑁 factors of two which we can write as two to the power of 𝑁. In our case of four inputs, we know that the number of combinations is two to the power of four. Evaluating this gives us our answer that the number of different possible combinations of input values for this circuit is 16.
There’s one final comment worth making about our initial approach, which was to try and write out all of the different combinations. In this case we were given, which is a circuit with four inputs, we found that the number of combinations we’d have had to write out would be 16. That’s a fair few combinations, but it would have been a manageable task. But how about if we’ve been given a circuit with eight inputs rather than four? Well, we know from our general expression for a circuit with 𝑁 inputs that the number of combinations is two to the power of 𝑁, and in this case, 𝑁 is equal to eight. So then, the number of different combinations for a circuit with eight inputs would be two to the power of eight, which works out as 256.
By using this general expression, we were able to find this result pretty quickly, while we can clearly see that writing out the 256 different possible combinations of the eight inputs just wouldn’t have been feasible. So then, another reason to use this second approach rather than trying to list out the different possible combinations explicitly is that this approach works no matter how many inputs the circuit has.
