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

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.