Boolean Algebra and De Morgan's Theorems

Transcript

0:00Introduction

Hello everyone! Let us begin with a line that looks completely wrong. One plus one equals one. In your maths class, that would cost you marks, right? But in the world of logic gates, it is perfectly correct. We will solve this puzzle in a few minutes. And by the end, you will see a long expression full of bars shrink into one simple gate. Questions on these rules do come up in JEE Main, so let's begin.

0:28Only 0 and 1: OR, AND and NOT

So, first, the language of logic gates. Every input and output here is only zero or one. The plus sign between A and B means OR. It is not ordinary addition. So A plus B is one if at least one input is one. Okay? Next, the dot between A and B means AND. So A dot B is one only if both inputs are one. Right? And the bar, the short line drawn above the letter, means NOT. We read it as A bar. It is simply the opposite of A, so when A is one, A bar is zero, and the other way round. Clear? Now, back to our puzzle. Remember, plus means OR. So what is one plus one here? It is one, yes, exactly! One OR one has at least one input equal to one, so the output is one. So here, one plus one equals one, not two. And that solves our puzzle. With me?

1:30Rules with 0, 1 and the bar

Now the rules of Boolean algebra. First, A plus zero. An OR with a zero input changes nothing, so A plus zero is just A, okay? And A plus one? One input is already one, so the answer is one, whatever A may be. Got it? Now the dot. With AND, A dot zero is zero, since AND needs every input to be one. And A dot one is just A, because the one changes nothing. Right? Next, a variable with itself. So A plus A is just A, not two A, and A dot A is also just A, not A squared. Clear? Now take A with its own opposite. What is A plus A bar? It is always one, correct, because one of the two is surely one. And A dot A bar is always zero, because one of the two is surely zero. With me? And the last rule here has two bars on top of A, a double bar. NOT of NOT A brings you back to A itself. Two bars cancel each other, okay?

2:32Distributive and absorption laws

Now the distributive law. On screen, A dot, in brackets, B plus C, equals A B plus A C, just like ordinary algebra. Two letters written side by side, like A B, mean A dot B, an AND, right? Is A plus B C equal to, in brackets A plus B, dot, in brackets A plus C? In ordinary algebra, that is completely wrong. So what about Boolean algebra? It is true here, and that is the surprise! Check the truth table of both sides, and every row matches. So Boolean algebra has a second distributive law, which ordinary algebra does not have. Clear? Now the absorption laws. So A plus A B equals A, and here is why. Take A common, and you get A dot, in brackets, one plus B, and one plus anything is one, so this is just A, okay? In the same way, A dot, in brackets, A plus B, is also A, because the single A absorbs the bigger term. Got it? Now a tricky one, A plus A bar B, with the bar over A only. It looks just like the absorption law, so the answer is A, right? That is the trap, because the answer is not just A, it is A plus B, as you see on screen. By the second distributive law, it becomes, in brackets A plus A bar, dot, in brackets A plus B, and A plus A bar is one, so only A plus B is left. Remember this one, okay?

4:03De Morgan's theorems

Now the key part of this lesson, De Morgan's theorems. Take A plus B, and put one long bar over the whole of it. So it means NOT of A OR B, all together. Many students just put a bar on each letter and keep the plus sign. Is that correct? It is not correct, and this is the classic trap. The right result is this: the long bar over A plus B equals A bar dot B bar. See, the plus has changed into a dot. Okay? And the second theorem goes the other way. The long bar over A dot B equals A bar plus B bar. Here the dot changes into a plus. Right? So here is the trick to remember both, break the bar and change the sign. The long bar breaks into small bars on each letter, and the sign flips, plus to dot, or dot to plus. Got it? And you can check any identity like this by writing the truth table of both sides. With two inputs, there are only four pairs, written in brackets with A first, and they are zero zero, zero one, one zero, and one one. Clear? The long bar over A plus B is one only when both inputs are zero, so its column reads one, zero, zero, zero. And A bar dot B bar is one only when both inputs are zero, too. So it also reads one, zero, zero, zero. Both columns are the same, so the first theorem holds. With me?

5:28Example 1: simplify AB + A B-bar by taking A common

Now, example one, an easy one from the course. Simplify A B plus A B bar, where the bar is over the B only, okay? Pause the video and try it first. Done? Okay, let's check. Both terms contain A, so take A common, by the distributive law. We get A dot, in brackets, B plus B bar. Right? And B plus B bar, a variable OR its own opposite, is always one. So we have A dot one, which is just A, the answer in the course. Nice and short, isn't it?

6:04Example 2: break the long bar with De Morgan, get Y = A + B

Now a harder one, JEE level. Here Y is the output, and it equals one long bar over everything. Under that long bar, two pieces are joined by a dot: A B with its own bar, and A plus B with its own bar. Pause the video and simplify it. Here is a hint: break the long bar first. Done? Okay, let's check. We break the long bar using De Morgan. So what happens to the dot in the middle? It becomes a plus, yes, exactly! Break the bar and change the sign. So Y equals the double bar over A B, plus the double bar over A plus B, okay? And two bars cancel each other. So Y equals A B, plus, in brackets, A plus B, and look, no bars are left at all. Right? Now group the two terms with B in them. Here, A B plus B is B dot, in brackets, A plus one. So Y equals A, plus B dot, in brackets, A plus one. Clear? And what is A plus one? We met it right at the start. It is one, correct. So B dot one is just B, and Y equals A plus B, the answer in the course. That long expression is just an OR gate, as promised at the start. This is why we simplify, okay?

7:27Quick revision: basic rules, absorption and De Morgan

So, quick revision. The basic rules: A plus one is one, A dot zero is zero, A plus A is A, A plus A bar is one, and two bars cancel. Absorption: A plus A B is A, but A plus A bar B is A plus B, remember that. And De Morgan: break the bar and change the sign. Now go and try the practice problems on this page. All the best!