Logic Gate Expressions

In this video, you'll see how a logic gate diagram can be described with an expression. You'll see how to come up with a valid expression for a given combination of logic gates, and how to draw a logic gate diagram for a given expression. It was the British-born mathematician George Boole who, in the mid-19th century, long before digital computers were even dreamt of, described complex logical arguments using algebraic expressions that could be manipulated and simplified. Almost 70 years later, the American mathematician and electrical engineer Claude Shannon showed that Boolean algebra could be applied to the design of switching circuits, circuits that effectively handled binary 1s and 0s. It was these men whose work laid the foundations for the invention of the modern digital computer. And this video will give you some insight into how their work came together. These logic gates are the building blocks of computer circuits, NOT, AND and OR. If you label the inputs and the outputs, you can describe the operation of each gate with a simple expression. With the NOT gate, Z is the output of a NOT operation on input A. Z equals NOT A. With the AND gate, Z is the output of an AND operation on inputs A and B. In this case, Z equals A AND B. With the OR gate, Z is the output of an OR operation on inputs A and B. This time, Z equals A OR B. Here, an OR gate has been combined with a NOT gate. The output Z can be described with the expression Z equals NOT A OR B. The brackets in this expression are essential. They specify that the OR operation should be performed first, and that the result of this is then the input for a NOT operation. If the brackets had been positioned here instead, the expression would not accurately describe this particular combination of gates. It would be wrong. Indeed, if the brackets had not been included in the expression at all, it would also be wrong. Why? Because there's an order of precedence that applies when it comes to combining logical operations in an expression. If an expression contains a mixture of operations, the rule is that any NOT operations have the highest priority. These are performed first. Then, any AND operations can be performed, and finally any OR operations. However, if an expression contains brackets, the operations described within the brackets supersede everything else. Here, you can see the same two gates combined together in a different way. This particular arrangement is correctly described by this expression. The expression is almost identical to the one above, but the brackets are in a different place. These brackets indicate that a NOT operation should be performed on A before anything else happens to A. You can clearly see that this is what's going on in the diagram. Then, the result of NOT A is combined with B through an OR gate to give us Z. In fact, because the NOT operation has a higher precedence than the OR operation, the brackets can be left out if you wish. These are both valid expressions for the lower combination of gates. Here's another combination of gates, and here's the expression to match. Once again, the brackets are essential for correctness. A and B are ANDed together first. Then, the output of the AND operation is passed through a NOT gate. This expression, on the other hand, doesn't describe this combination of gates, because NOT has a higher precedence than AND. Here, we are accurately describing the circuit shown. The operation described in the brackets happens first, in this circuit, NOT A. Then, NOT A is combined with B through an AND gate. Because the NOT operation has a higher precedence than AND, this too is a valid expression for this particular combination of gates. It's up to you whether or not to include the brackets. Some people like to, just for clarity. Now take a look at this combination. Here is a valid expression. You can clearly see from the diagram that the NOT operations are performed first. First, NOT A. Then, NOT B. Only then does the OR operation occur. You don't need brackets in this expression, because NOT is the highest priority operation. But you can include them here if you wish. This version of the expression is perfectly valid and, arguably, somewhat clearer. This version is also valid. Z equals NOT B or NOT A, rather than NOT A or NOT B. It doesn't matter which of the two NOT operations is performed first, as long as they've both happened before the OR operation. Indeed, this is also a perfectly valid way to describe this particular circuit. Why not give this one a try yourself? How many valid expressions can you come up with for this particular combination of gates? Pause the video now if you want to have a go, and I'll show you some solutions in a moment. And here's the solution. Notice the use of brackets, making it clear that the AND operation on B and C is performed before the OR operation. This is also correct, because the AND operation would happen first anyway. It has the highest precedence. Strictly speaking, this is correct as well. And so is this. How about this example? Pause the video if you want to give it a try. Don't forget the order of precedence. You'll see the solution in a moment. And here's the solution. This time, you can't get away without the brackets. You can clearly see in the diagram that the output of B or C is fed into the AND gate along with A. But because the OR operation has a lower priority than AND, it must be written in brackets. But this is a valid alternative. Now let's attempt to derive a diagram from an expression. First of all, notice there are four inputs in this expression, A, B, C and D. Also notice that there are two AND operations along with one OR operation. This means you're going to need two AND gates and one OR gate. Because an AND operation has a higher priority than an OR operation, the ANDs must be performed first. So you should start by drawing the AND gates. First, A and B. Then, C and D. Now, the outputs of these AND gates can be passed through an OR gate to give Z. By the way, if you were given this expression instead, you should have come up with the same diagram. Strictly speaking, the brackets can be left out. Let's see another example. This time, notice that there are only three inputs in this expression, A, B and C. Input A appears twice. Also notice that there are two AND operations along with one OR operation. This means you're going to need two AND gates and an OR gate. You could add some brackets before you begin. These brackets don't redefine the order of operations. AND has a higher priority than OR, so the AND operations will be performed first one way or the other. These brackets do, however, offer some clarity and suggest what you need to do next. Start by drawing the AND gates. First, A and B. Then, A and C. There's only one input called A, but a junction allows the same input to be fed into both AND gates. Finally, the outputs of the AND gates are then processed by an OR gate. And there you have it. Try this one yourself. Pause the video to give it a try, and I'll show you the solution in a moment. Here's the solution. Let's work through it. The expression has two inputs, A and B. The expression also suggests three gates. Two ANDs and a NOT. Whatever's inside the brackets should be considered first. So A and B are fed into an AND gate. The NOT operation is the next highest priority, so draw a NOT gate to invert B. There's only one B, so a junction is needed to split it. Then, pass the outputs of the AND and the NOT gates through another AND gate to give Z. For clarity only, the expression might have been written with an extra pair of brackets. There's no difference in the circuit being described here. Now, it might be that the diagram you came up with isn't identical to this one, but it may well be correct. What matters most is the connectivity, and therefore the order of operations, not the exact layout. For example, this is actually the same circuit. And so is this. Try this example. It's more challenging, but a methodical approach should get you there. Solution in a moment. Here's the solution. Your layout might not be identical, but the connectivity should be the same. This is actually a very special combination of gates that an expert would recognise, and you'll probably come across it again. It's called an exclusive OR circuit, or XOR for short. It's so useful it has its own symbol. Finally, each of the three main logical operations can be represented with its own special symbol in an expression. In fact, there are several alternative symbols for each of these, but the ones you can see here are commonly used in the field of computer science. This means that each of these expressions, which you've now met, can be rewritten in a shorter form. Each expression not only describes a combination of logic gates, it can be manipulated using the laws of Boolean algebra. Because Boolean algebra can be used to simplify complex expressions of this type, and therefore the circuits that they describe, Boolean algebra is an extremely powerful tool for designing computers. More about Boolean algebra in a later video.