Boolean Logic & Logic Gates: Crash Course Computer Science #3

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 of being able to see every switch and gear,

0:13 but gain the ability to assemble increasingly complex systems.

0:16 INTRO Last episode, we talked about

0:27 how computers evolved from electromechanical devices,

0:29 that often had decimal representations of numbers–

0:32 like those represented by teeth on a gear–

0:35 to electronic computers with transistors that can

0:37 turn 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 are

1:10 just different expressions of the same signal– but we’ll

1:13 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 on and off,

1:20 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 seperate— if your smartphone battery

1:33 starts running low or there’s electrical

1:35 noise because someone's running a microwave nearby,

1:37 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- using just

1:46 ‘on and off’- gives us the most distinct signal to minimize these issues.

1:51 Another reason computers use binary is that an entire branch

1:54 of mathematics already existed that dealt

1:56 exclusively with true and false values.

1:58 And it had figured out all

1:59 of the 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, over,

2:13 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 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

2:49 useful 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 electrode,

3:21 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, the output is

3:40 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 because its

3:57 not doing anything— the input 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, the transistor

4:09 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 all the water in your house was

4:17 flowing out of a huge hose so there

4:19 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 ground,

4:28 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

4:41 gates 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, “My name is Carrie

5:05 Anne AND I’m wearing pants” that would be false, 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 tell you two complete lies that is also false,

5:22 and again we can write all of these combinations out in a table.

5:25 To build an AND gate, we need two transistors connected together so

5:29 we have our two inputs and one output.

5:31 If we turn on just transistor A, current won’t

5:34 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

6:22 that the 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, 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, and OR gates,

6:50 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 while keeping

7:08 the overall complexity relatively the same- just remember

7:10 that that mess of transistors and wires is still there.

7:13 For example, another useful boolean operation in computation

7:16 is called 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

7:28 one input is true and the other input is false.

7:31 It’s like when you go out to dinner and your meal

7:33 comes with a side salad OR a soup– sadly, 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 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,

7:53 the logic is different from OR, 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 original OR gate,

8:14 the AND will take in “false” and “true”,

8:17 and since AND needs both values 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 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 symbol

8:35 too— an OR gate with a smile:) But most importantly,

8:38 we can now put XOR into our metaphorical toolbox and not

8:41 have to worry 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 made up of logic gates,

9:00 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 about how the logic that you are

9:07 programming is actually implemented in the physical

9:09 world by these teeny tiny components.

9:11 We’ve also moved from thinking about

9:13 raw 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 AND near Pizza Hut”,

9:30 then “John will want pizza” equals true.

9:33 And with that, I'm starving, I'll see you next week.