Boolean Logic & Logic Gates: Crash Course Computer Science #3
CrashCourse
0:03 Hi, I’m Carrie Anne and welcome to Crash Course Computer Science!
0:06 Today we start our journey up the ladder of abstraction,
0:09 where we leave behind the simplicity
0:10 of being able to see every switch and gear,
0:13 but gain the ability to assemble increasingly
0:15 complex systems.
0:16 INTRO Last episode,
0:26 we talked about how computers evolved from electromechanical devices, that
0:30 often had decimal representations of numbers– like those
0:33 represented by teeth on a gear– to
0:35 electronic computers with transistors that can turn
0:37 the flow of electricity on or off.
0:39 And fortunately, even with just two states of electricity,
0:42 we can represent important information.
0:44 We call this representation Binary— which literally means “of two states”,
0:47 in the same way a bicycle has two wheels or a biped has two legs.
0:52 You might think two states isn’t a lot to work with, and you’d be right!
0:55 But, it’s exactly what you need for representing the values “true” and “false”.
0:59 In computers, an “on” state, when electricity is flowing, represents true.
1:03 The off state, no electricity flowing, represents false.
1:06 We can also write binary as 1’s and 0’s instead of true’s and false’s– they
1:10 are just different expressions of the same signal– but
1:12 we’ll talk more about that in the next episode.
1:15 Now it is actually possible to use transistors
1:17 for more than just turning electrical current
1:19 on and off, and to allow for different levels of current.
1:22 Some early electronic computers were ternary,
1:24 that's three states, and even quinary, using 5 states.
1:27 The problem is, the more intermediate states there are,
1:29 the harder it is to keep them all
1:31 seperate— if your smartphone battery starts
1:33 running low or there’s electrical noise
1:35 because someone's running a microwave nearby, the signals can get mixed up...
1:38 and this problem only gets worse with transistors
1:41 changing states millions of times per second!
1:43 So, placing two signals as far apart as possible-
1:46 using just ‘on and off’- gives us the
1:48 most distinct signal to minimize these issues.
1:51 Another reason computers use binary is that
1:53 an entire branch of mathematics already existed
1:55 that dealt exclusively with true and false values.
1:58 And it had figured out all of the
2:00 necessary rules and operations for manipulating them.
2:01 It's called Boolean Algebra!
2:03 George Boole, from which Boolean Algebra later got its name,
2:06 was a self-taught English mathematician in the 1800s.
2:09 He was interested in representing logical statements that went “under,
2:13 over, and beyond” Aristotle’s approach to logic,
2:15 which was, unsurprisingly, grounded in philosophy.
2:18 Boole’s approach allowed truth to be systematically and formally proven,
2:21 through logic equations which he introduced in his first book,
2:25 “The Mathematical Analysis of Logic” in 1847.
2:27 In “regular” algebra— the type you probably learned
2:29 in high school— the values of variables
2:31 are numbers,
2:32 and operations on those numbers are things like addition and multiplication.
2:36 But in Boolean Algebra, the values of variables are true and false,
2:40 and the operations are logical.
2:41 There are three fundamental operations in Boolean Algebra:
2:44 a NOT, an AND, and an OR operation.
2:47 And these operations turn out to be really useful
2:49 so we’re going to look at them individually.
2:51 A NOT takes a single boolean value, either true or false, and negates it.
2:55 It flips true to false, and false to true.
2:58 We can write out a little logic table that shows the original value under Input,
3:01 and the outcome after applying the operation under Output.
3:04 Now here’s the cool part— we can easily build boolean logic out of transistors.
3:08 As we discussed last episode,
3:10 transistors are really just little electrically controlled switches.
3:13 They have three wires: two electrodes and one control wire.
3:16 When you apply electricity to the control wire,
3:19 it lets current flow through from one
3:21 electrode, through the transistor, to the other electrode.
3:24 This is a lot like a spigot on a pipe— open the tap,
3:27 water flows, close the tap, water shuts off.
3:29 You can think of the control wire as an input,
3:32 and the wire coming from the bottom electrode as the output.
3:34 So with a single transistor, we have one input and one output.
3:38 If we turn the input on,
3:39 the output is also on because the current can flow through it.
3:42 If we turn the input off,
3:44 the output is also off and the current can no longer pass through.
3:46 Or in boolean terms, when the input is true, the output is true.
3:50 And when the input is false, the output is also false.
3:53 Which again we can show on a logic table.
3:55 This isn’t a very exciting circuit though
3:57 because its not doing anything— the input
3:58 and output are the same.
4:00 But, we can modify this circuit just a little bit to create a NOT.
4:03 Instead of having the output wire at the end of the transistor,
4:06 we can move it before.
4:07 If we turn the input on,
4:08 the transistor allows current to pass through it to the “ground”,
4:11 and the output wire won’t receive that current- so it will be off.
4:14 In our water metaphor grounding would be like if
4:16 all the water in your house was flowing
4:17 out of a huge hose so there wasn’t any water pressure left for your shower.
4:21 So in this case if the input is on, output is off.
4:24 When we turn off the transistor, though,
4:26 current is prevented from flowing down it to the
4:28 ground, so instead, current flows through the output wire.
4:31 So the input will be off and the output will be on.
4:34 And this matches our logic table for NOT,
4:36 so congrats, we just built a circuit that computes NOT!
4:38 We call them NOT gates- we call them gates
4:41 because they’re controlling the path of our current.
4:43 The AND Boolean operation takes two inputs, but still has a single output.
4:48 In this case the output is only true if both inputs are true.
4:51 Think about it like telling the truth.
4:53 You’re only being completely honest if you don’t lie even a little.
4:56 For example, let’s take the statement,
4:57 “My name is Carrie Anne AND I’m wearing a blue dress".
5:01 Both of those facts are true, so the whole statement is true.
5:03 But if I said,
5:04 “My name is Carrie Anne AND I’m wearing pants” that would be false,
5:08 because I’m not wearing pants.
5:09 Or trousers.
5:10 If you’re in England.
5:11 The Carrie Anne part is true, but a true AND a false, is still false.
5:15 If I were to reverse that statement it would still obviously be false,
5:18 and if I were to
5:19 tell you two complete lies that is also false,
5:22 and again we can write all of these combinations
5:24 out in a table.
5:25 To build an AND gate,
5:27 we need two transistors connected together so we have our two inputs
5:30 and one output.
5:31 If we turn on just transistor A,
5:33 current won’t flow because the current is stopped by transistor B.
5:36 Alternatively, if transistor B is on, but the transistor A is off,
5:40 the same thing, the current can’t get through.
5:41 Only if transistor A AND transistor B are on does the output wire have current.
5:46 The last boolean operation is OR— where only one input
5:49 has to be true for the output to be true.
5:51 For example, my name is Margaret Hamilton OR I’m wearing a blue dress.
5:55 This is a true statement because
5:57 although I’m not Margaret Hamilton unfortunately,
5:59 I am wearing a blue dress, so the overall statement is true.
6:02 An OR statement is also true if both facts are true.
6:06 The only time an OR statement is false is if both inputs are false.
6:09 Building an OR gate from transistors needs a few extra wires.
6:12 Instead of having two transistors in series— one
6:15 after the other— we have them in parallel.
6:17 We run wires from the current source to both transistors.
6:20 We use this little arc to note that the
6:22 wires jump over one another and aren’t connected,
6:24 even though they look like they cross.
6:26 If both transistors are turned off,
6:28 the current is prevented from flowing to the output,
6:30 so the output is also off.
6:32 Now, if we turn on just Transistor A, current can flow to the output.
6:36 Same thing if transistor A is off, but Transistor B in on.
6:39 Basically if A OR B is on, the output is also on.
6:43 Also, if both transistors are on, the output is still on.
6:47 Ok, now that we’ve got NOT, AND,
6:49 and OR gates, and we can leave behind the constituent
6:52 transistors and move up a layer of abstraction.
6:54 The standard engineers use for these gates are a triangle with a dot for a NOT,
6:58 a D for the AND, and a spaceship for the OR.
7:01 Those aren’t the official names, but that's howI like to think of them.
7:03 Representing them and thinking about them this way
7:05 allows us to build even bigger components
7:07 while keeping the overall complexity relatively the
7:09 same- just remember that that mess of
7:11 transistors and wires is still there.
7:13 For example, another useful boolean operation in computation is called
7:17 an Exclusive OR- or XOR for short.
7:20 XOR is like a regular OR, but with one difference:
7:23 if both inputs are true, the XOR is false.
7:26 The only time an XOR is true is when one
7:29 input is true and the other input is false.
7:31 It’s like when you go out to dinner and your
7:33 meal comes with a side salad OR a soup– sadly,
7:35 you can’t have both!
7:36 And building this from transistors is pretty confusing,
7:38 but we can show how an XOR is created
7:41 from our three basic boolean gates.
7:43 We know we have two inputs again— A and B— and one output.
7:46 Let’s start with an OR gate,
7:47 since the logic table looks almost identical to an OR.
7:50 There’s only one problem- when A and B are true, the logic is different from OR,
7:55 and we need to output “false”.
7:56 To do this we need to add some additional gates.
7:59 If we add an AND gate, and the input is true and true, the output will be true.
8:03 This isn’t what we want.
8:04 But if we add a NOT immediately after this will flip it to false.
8:08 Okay, now if we add a final AND gate and send
8:11 it that value along with the output of our
8:13 original OR gate, the AND will take in “false” and “true”,
8:17 and since AND needs both values
8:19 to be true, its output is false.
8:21 That’s the first row of our logic table.
8:22 If we work through the remaining input combinations,
8:24 we can see this boolean logic
8:26 circuit does implement an Exclusive OR.
8:28 And XOR turns out to be a very useful component,
8:31 and we’ll get to it in another episode,
8:33 so useful in fact engineers gave it its own
8:35 symbol too— an OR gate with a smile:)
8:38 But most importantly,
8:38 we can now put XOR into our metaphorical toolbox and not have to worry
8:42 about the individual logic gates that make it up,
8:44 or the transistors that make up those gates,
8:46 or how electrons are flowing through a semiconductor.
8:49 Moving up another layer of abstraction.
8:51 When computer engineers are designing processors,
8:53 they rarely work at the transistor level,
8:55 and instead work with much larger blocks,
8:57 like logic gates, and even larger components
8:59 made up of logic gates, which we’ll discuss in future episodes.
9:02 And even if you are a professional computer programmer,
9:04 it’s not often that you think
9:05 about how the logic that you are programming
9:07 is actually implemented in the physical world
9:09 by these teeny tiny components.
9:11 We’ve also moved from thinking about raw
9:13 electrical signals to our first representation
9:15 of data- true and false- and we’ve even gotten a little taste of computation.
9:20 With just the logic gates in this episode,
9:22 we could build a machine that evaluates complex logic statements,
9:25 like if “Name is John Green AND after 5pm OR is Weekend
9:29 AND near Pizza Hut”, then “John will want pizza” equals true.
9:33 And with that, I'm starving, I'll see you next week.