Boolean Algebra 1 – The Laws of Boolean Algebra

This video is about the laws of Boolean algebra. You will see how these laws can be derived by examining simple logic circuits, and by considering some familiar properties of base 10 numbers. In the video that follows on from this one, you'll see how the laws of Boolean algebra can be applied to simplify complex Boolean expressions, and you will have an opportunity to practice the skills involved. Before looking in detail at the laws of Boolean algebra, let's briefly consider why we need them. Here's a complex combination of logic gates, and here's an expression that describes the output Z in terms of the inputs A, B and C. This Boolean expression is an accurate description of this particular circuit. Boolean algebra can be applied step by step to reduce a complex expression, like this one, into its simplest form. All of these expressions are equivalent. They each describe a different circuit, but all of these circuits do exactly the same thing. The behaviours of these circuits can be described with exactly the same truth table. So, this combination of logic gates does exactly the same job as the complex combination. But clearly, it is much simpler. It needs less components, so it's more reliable. It's faster, it generates less heat, and it's cheaper to make. Because Boolean algebra can be used to simplify complex expressions, and therefore the circuits they describe, Boolean algebra is an extremely powerful tool for designing computers. Before you can use Boolean algebra to simplify a complex expression, you first need to know the laws. Indeed, you need to be so familiar with these laws that you can easily spot where and how they can be usefully applied. Then, you will need plenty of practice at simplifying complex expressions to really master the skills involved. Consider this OR gate. One of the inputs is permanently set to 1. There is always at least one input of 1, so there will always be an output of 1, regardless of the value of A. With this AND gate, one of the inputs is fixed at 0, so the output will always be 0, regardless of A. These expressions are collectively known as the annulment law. You may have heard the term annulment with regards to a marriage that doesn't legally exist. To annul actually means to declare null and void. You can see in both of these cases that input A has no effect. Consider this OR gate. One of the inputs is always 0, so the output will always match the value of input A. If input A is 0, we have two 0s going in, so a 0 comes out. If input A is 1, we have a 1 and a 0 going in, so a 1 comes out. This AND gate arrangement is similar. With one of the inputs permanently set to 1, the output will always match input A. This pair of expressions are referred to collectively as the identity law. An input ORed with a 0 or ANDed with a 1 will always give an output that is equal to the input. Take a look at this arrangement. Here, both inputs of the OR gate are always the same. If A is 1, both inputs will be 1, so the output will be 1. If input A is 0, both inputs will be 0, so the output will also be 0. In the same way, if both inputs of an AND gate are always the same, then the output of the gate will match. This is known as the idempotent law. Put simply, an input that is ORed with itself will result in an output that is equal to that input. An input that is ANDed with itself will also result in an output that is equal to the input. The next few laws involve NOT gates. In this combination, the OR gate is being fed input A along with its inverse. So the OR gate is always being fed a 1 and a 0, regardless of the value of A. The output of the OR gate in this arrangement must therefore always be 1. In this combination, the AND gate is being fed input A along with its inverse. So the AND gate is always being fed a 1 and a 0, regardless of what A is. The output of the AND gate here must always be 0. Another name for the inverse of a Boolean value is its complement. So these expressions are known as the complement law. Here, we have two NOT gates in series. If the input is A, the output is NOT NOT A. If A is 1, the output is 1. If A is 0, the output is 0. In other words, the output always matches the input. This is called the double negation law. In fact, any even number of NOT gates in series will produce an output that matches the input. Now, you may be thinking at this stage that Boolean expressions that describe combinations of logic gates don't normally include 1s and 0s. They contain only letters and symbols that describe the outputs in terms of the inputs. However, once you start to apply the laws, you'll see that some of the intermediate steps of simplifying a complex expression may well include 1s and 0s that are eventually eliminated. Before continuing, let's take a look at the concepts of Boolean addition and Boolean multiplication. Consider this. 0 plus 0 equals 0, of course. 0 plus 1 equals 1. And 1 plus 0 also equals 1, of course. Now, in Boolean logic, there is only true and false. And a logic gate deals with binary 1s and 0s only. So when it comes to 1 plus 1, it must be equal to something, and that certainly isn't 0. So, 1 plus 1 equals 1. In fact, logically speaking, 1 plus 1 plus 1 plus 1 plus 1 equals 1. Look at the similarity between these addition sums and the truth table for an OR gate. We say that Boolean addition corresponds to the logical function of an OR gate. Now look at these multiplication operations. No surprises here at all. Compare these with the truth table for an AND gate. Here, you can see that Boolean multiplication corresponds to the logical function of an AND gate. By the way, there's no such thing as Boolean subtraction. That would imply the existence of negative numbers. But there is only 1 and 0. There's no such thing as Boolean division either, because division is actually repeated subtraction. In order to derive the next set of laws, we're going to review some basic properties of base 10 numbers. Namely, associative, commutative and distributive properties. These properties are particularly relevant to students of advanced mathematics. But you may well have been already applying these to base 10 arithmetic without a second thought. The associative property tells us something about the way numbers can be grouped. You know that 5 plus 2 plus 3 equals 10. And that 5 plus 2 plus 3 also equals 10. It doesn't matter which pair of values you add together first, you get the same result. This can be written algebraically as A plus B plus C equals A plus B plus C. Now, because addition corresponds to the Boolean OR operation, we can say that A OR B OR C equals A OR B OR C. The only difference between each side of the equation is the position of the brackets. And they make no difference. In terms of logic gates, we're saying that these two subtly different circuits behave in exactly the same way. In a similar fashion, we know that 5 times 2 times 3 equals 30. And that 5 times 2 times 3 is also 30. Algebraically, we can write A times B times C equals A times B times C. In base 10 algebra, we tend to omit the multiplication symbols. Now, because multiplication is like a Boolean AND operation, it follows that A AND B AND C equals A AND B AND C. To put it another way, the behaviours of these two gate combinations are identical. The commutative property refers to the way that numbers can be moved around in an expression. For example, 4 plus 8 equals 12, and so does 8 plus 4. Algebraically, we can say that A plus B equals B plus A. The Boolean equivalent is A OR B equals B OR A. The logic gate equivalent of this equation is rather trivial. All we're really saying is that it makes no difference if we swap around the inputs of an OR gate. In a similar example, 4 times 8 equals 32, as does 8 times 4. Hence, A times B equals B times A. So it follows that A AND B equals B AND A. Once again, we're really saying that it makes no difference if we swap the inputs of an AND gate. Moving on, you may have come across algebraic problems that require you to expand the brackets, or conversely, factorise an expression. Problems such as these rely on the distributive property of numbers. For example, 2 times 3 plus 4 is equal to 2 times 3 plus 2 times 4. In regular algebra, we can write A brackets B plus C equals AB plus AC. The Boolean equivalent is A AND brackets B OR C equals brackets A AND B or brackets A AND C. We can prove the correctness of the so-called AND distributive law by comparing the circuits described by either side of this equation. Inspect this carefully and you will see that they behave in the same way. They share the same truth table, so the law is quite correct. We can also derive the related OR distributive law in the same way. This law has no equivalence in standard algebra, but this visual proof is convincing enough. Our distributive law is now in place. We can now add another law, the so-called absorptive law, also known as the redundance law. The absorptive law can also be proved with truth tables. Notice here that only when input A is 1, can the output be 1. In fact, the output is always the same as A. So if you can spot the term A AND A OR B within a complex expression, it can be replaced with simply A. Here too, notice that input A must be 1 to get a 1 out. The output of this circuit is also always A. So the term A OR brackets A and B can be absorbed and replaced by A alone. Here are the laws we have so far. The last law we're going to mention gets its name from George Boole's esteemed friend and collaborator, Augustus De Morgan. The so-called De Morgan's theorem. De Morgan used the rules of Boolean algebra that you've now met to prove that the complement of the product of two variables is equal to the sum of their complements. In other words, he proved that this term is equivalent to this term. When we examine the corresponding logic gate circuits and their truth tables, we can see that both sides of the equation are indeed the same. De Morgan also showed that the complement of the sum of two variables is equal to the product of their complements. In other words, this equation. Examination of the circuits and their truth tables reveals that this equation is also correct. So now we have a full set of laws. In the video that follows on from this one, I'll show you how to start using them. Make sure you've got them handy.