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

Summary

在这段视频脚本中，Carrie Anne带领观众开始了计算机科学的抽象层次之旅，从简单的机械开关和齿轮，过渡到使用晶体管的电子计算机。她解释了二进制的概念，即用两种状态（开和关）来表示信息，这与布尔代数紧密相关。布尔代数是一种专门处理真和假值的数学分支，由19世纪自学成才的英国数学家乔治·布尔发展而来。视频详细介绍了布尔代数的三个基本操作：非（NOT）、与（AND）和或（OR），并展示了如何使用晶体管构建这些基本的逻辑门。此外，还探讨了异或（XOR）门的构建，这是一种特殊的或门，当两个输入都为真时，输出为假。通过这些逻辑门，可以构建更复杂的逻辑电路，而无需深入了解底层的晶体管和电子流动。视频以一个幽默的结尾结束，Carrie Anne用逻辑门构建了一个关于John Green是否想吃披萨的复杂逻辑语句，并以自己饿了作为结束语，邀请观众下周再见。

Takeaways

• 📈 我们从具体事物（如开关和齿轮）的简单性，上升到抽象层次，能够构建越来越复杂的系统。
• 🔋 计算机从使用十进制表示数字的机电装置，发展到使用晶体管的电子计算机，晶体管可以控制电流的通断。
• 🔑 二进制表示法使用两个状态（开和关）来表示信息，分别用1和0表示，是计算机中表示“真”和“假”的基础。
• 🧲 晶体管不仅可以控制电流的通断，还可以允许不同级别的电流通过，但多状态系统在实际应用中存在稳定性问题。
• 📚 布尔代数是处理真和假值的数学分支，由19世纪的英国数学家乔治·布尔发展，为逻辑运算提供了系统化的规则。
• ⚙️ 基本的布尔运算包括非（NOT）、与（AND）和或（OR），这些运算对于构建逻辑电路至关重要。
• 🚿 使用晶体管可以构建布尔逻辑电路，例如通过控制电流的流向来实现NOT门的功能。
• 🔗 AND门需要两个输入都为真时输出才为真，类似于完全诚实的陈述。
• 🔄 OR门只要有一个输入为真，输出就为真，类似于只要有一个条件满足即可的陈述。
• 🔍 XOR（异或）门与OR门类似，但当两个输入都为真时，输出为假，只有在两个输入不一致时输出为真。
• 🛠️ 通过组合基本的布尔逻辑门，可以构建更复杂的逻辑电路，如XOR门，而无需考虑底层的晶体管和电子流动。
• 📝 计算机工程师在设计处理器时，通常不会在晶体管层面工作，而是使用更大的逻辑门组件，而程序员通常不需要考虑物理实现的细节。

Q & A

计算机科学中的抽象层次是什么？

抽象层次是指在计算机科学中，从具体的硬件实现到更高层次的逻辑和算法表示的一系列抽象过程。在这个层次结构中，我们能够忽略底层的复杂性，如电子开关和齿轮，而专注于构建更复杂的系统。

二进制表示法是如何与电子计算机的工作原理相联系的？

二进制表示法利用两种状态——开（1）和关（0）——来表示信息。在电子计算机中，这两种状态对应于电流的流动（开）和不流动（关），分别代表逻辑上的“真”和“假”。

为什么早期的电子计算机会使用三进制或五进制？

早期电子计算机使用三进制或五进制是为了允许不同的电流水平，从而能够表示更多的状态。然而，随着状态数量的增加，保持这些状态分离的难度也随之增加，尤其是在存在电池电量低或电磁干扰的情况下。

布尔代数是如何与计算机科学相联系的？

布尔代数是专门处理真和假值的数学分支，它包含了一套完整的规则和操作来处理这些逻辑值。布尔代数的逻辑运算符（如非、与、或）可以直接映射到电子元件（如晶体管）的电路设计中，这使得计算机能够执行逻辑运算。

晶体管在布尔逻辑中扮演什么角色？

晶体管在布尔逻辑中充当可控制的开关。它们通过控制电流的流动来实现逻辑运算。例如，当控制线通电时，电流可以从一个电极流向另一个电极，类似于水龙头控制水流。

非门（NOT gate）是如何用晶体管实现的？

非门可以通过改变晶体管的连接方式来实现。如果输入端接通（电流流动），晶体管允许电流流向地线，输出端则不会有电流流过，因此输出为“关”（0）。如果输入端断开（无电流流动），电流就会流向输出端，输出为“开”（1）。

与门（AND gate）的工作原理是什么？

与门需要两个输入端，并且只有一个输出端。只有当两个输入端都为“开”（1）时，输出端才会为“开”（1）。如果任一输入端为“关”（0），输出端也会为“关”（0）。

或门（OR gate）与与门（AND gate）有何不同？

或门（OR gate）的特点是只要有一个输入端为“开”（1），输出端就会为“开”（1）。与门（AND gate）则要求两个输入端都为“开”（1）时，输出端才会为“开”（1）。

异或门（XOR gate）是如何用基本的布尔逻辑门实现的？

异或门（XOR gate）可以通过结合基本的布尔逻辑门——或门（OR gate）、与门（AND gate）和非门（NOT gate）——来实现。当两个输入端相同（都为0或都为1）时，输出为0；当两个输入端不同（一个为0，另一个为1）时，输出为1。

为什么工程师在设计处理器时很少直接工作在晶体管级别？

工程师在设计处理器时很少直接工作在晶体管级别，因为他们通常使用更大块的逻辑结构，如逻辑门，以及由逻辑门组成的更大组件。这样可以在设计复杂的处理器时保持整体的复杂度相对不变。

逻辑门如何帮助我们构建更复杂的逻辑语句？

逻辑门允许我们构建复杂的逻辑语句，通过组合不同的逻辑操作，如与（AND）、或（OR）和非（NOT），我们可以评估涉及多个条件的复杂逻辑表达式，例如“如果名字是John Green并且在下午5点后或在周末且靠近比萨店，那么John想吃比萨”等于真。

Outlines

00:00

😀 计算机科学的抽象层次：从二进制到布尔代数

Carrie Anne 介绍了计算机科学的基础概念，从电子计算机的二进制表示法讲起，解释了二进制如何表示真值和假值。她提到了早期电子计算机的三进制和五进制系统，但指出了多状态系统在实际应用中的困难。接着，她介绍了布尔代数，这是专门处理真和假值的数学分支，由19世纪的英国数学家乔治·布尔创立。布尔代数中的三个基本操作是NOT、AND和OR，它们在逻辑电路设计中非常有用。通过使用晶体管，可以构建出实现这些逻辑操作的电路。

05:01

🤔 逻辑门的构建与抽象：从晶体管到处理器设计

Carrie Anne 继续深入讲解了如何使用晶体管构建基本的逻辑门，包括非门（NOT）、与门（AND）和或门（OR）。她通过比喻和实例解释了这些逻辑门的工作原理和它们在构建更复杂逻辑电路中的作用。此外，她还介绍了异或门（XOR），这是一种特殊的或门，当两个输入都为真时输出为假。她展示了如何通过组合基本的逻辑门来构建XOR门。最后，她强调了在计算机工程中，工程师们通常不会在晶体管层面工作，而是使用更大的逻辑门组件，以及由逻辑门组成的更大组件来设计处理器。她还提到，即使是专业的计算机程序员，也不需要经常考虑他们编写的逻辑是如何在物理世界中通过微小的组件实现的。

Keywords

💡二进制

二进制是一种数字表示法，仅使用两个状态，通常表示为1和0。在视频中，二进制用于表示计算机中的逻辑值“真”和“假”。例如，电流流动的状态代表真（1），而没有电流流动的状态代表假（0）。二进制是构建更复杂计算机系统的基础，因为它简单且易于电子设备处理。

💡晶体管

晶体管是现代电子设备的基本组件，可以控制电流的流动。在视频中，晶体管被描述为可以开关电流的小开关，它们是构建逻辑门和更复杂电路的基础。晶体管的开关状态与二进制的1和0相对应，是实现布尔代数运算的关键。

💡布尔代数

布尔代数是一种数学逻辑系统，专门处理逻辑值真和假。它由19世纪的英国数学家乔治·布尔创立，用于形式化逻辑运算。视频中提到，布尔代数包含了三种基本操作：非（NOT）、与（AND）和或（OR），这些操作在计算机科学中非常重要，因为它们可以用晶体管实现。

💡逻辑门

逻辑门是实现布尔代数基本操作的物理设备。视频中介绍了几种基本的逻辑门，包括非门（NOT gate）、与门（AND gate）和或门（OR gate）。这些逻辑门可以通过组合晶体管来构建，它们控制电流的路径，从而实现特定的逻辑功能。逻辑门是构建更复杂电路的基本构件。

💡与门（AND gate）

与门是一种逻辑门，它有两个输入和一个输出。只有当两个输入都为真（1）时，输出才为真。视频中通过比喻说明，如果两个陈述都为真，那么整个陈述也为真；如果任何一个陈述为假，整个陈述就为假。与门在计算机中用于确保所有条件都满足时才执行某个操作。

💡或门（OR gate）

或门是另一种逻辑门，它同样有两个输入和一个输出。只要有一个输入为真（1），输出就为真。视频中通过一个例子说明了这一点：如果一个陈述为真，即使另一个陈述为假，整个陈述也为真。或门在计算机中用于至少一个条件满足时执行操作。

💡非门（NOT gate）

非门是一种基本的逻辑门，它接受单个输入并反转它。如果输入为真（1），输出为假（0）；如果输入为假，输出为真。视频中通过构建一个简单的电路来说明非门的工作原理，展示了如何通过改变晶体管的连接方式来实现逻辑非操作。

💡异或门（XOR gate）

异或门是一种逻辑门，当且仅当输入不相同时，输出为真。视频中通过组合基本的逻辑门（包括或门、与门和非门）来构建异或门。异或门在计算机中用于比较两个二进制数是否不同，是一种非常有用的逻辑运算。

💡抽象

抽象是计算机科学中一个重要的概念，它允许工程师在不同的层次上工作，而不必关注底层的具体实现细节。视频中提到，通过使用逻辑门和更高层次的组件，工程师可以设计复杂的处理器，而不必直接处理单个晶体管。抽象使得复杂系统的管理和设计变得更加可行。

💡逻辑电路

逻辑电路是由逻辑门组成的电路，可以实现特定的逻辑功能。视频中通过构建非门、与门、或门和异或门等基本逻辑电路，展示了如何用晶体管来实现布尔代数中的逻辑运算。逻辑电路是构成计算机处理器和其他电子设备的基础。

💡电气信号

电气信号是计算机中用于表示和传输信息的电流。在视频中，电气信号的状态（开或关）被用来表示二进制值，这是计算机处理和存储信息的基础。电气信号的稳定性和准确性对于计算机的正常运行至关重要。

Highlights

计算机科学之旅从抽象层次的起点开始，我们离开简单的开关和齿轮，获得组装复杂系统的能力。

计算机从使用十进制表示数字的机电装置发展到使用晶体管的电子计算机，晶体管可以控制电流的开启和关闭。

二进制表示法，即仅使用两种状态来表示信息，类似于自行车有两个轮子或两足动物有两条腿。

在计算机中，电流流动的“开”状态代表真值，无电流流动的“关”状态代表假值。

晶体管不仅可以用于控制电流的开启和关闭，还可以允许不同的电流水平。

早期的电子计算机有的采用三态逻辑，甚至有的使用五态逻辑，但状态越多，保持它们分离的难度越大。

使用'开和关'两种信号，可以最大程度地减少信号干扰问题。

计算机使用二进制的另一个原因是，已经存在一个专门处理真和假值的数学分支——布尔代数。

布尔代数由19世纪的英国数学家乔治·布尔提出，旨在系统化和形式化地证明真理。

布尔代数中的三个基本操作是：非（NOT）、与（AND）和或（OR）。

晶体管可以构建出布尔逻辑，因为它们本质上是受电控制的小开关。

通过单个晶体管，我们可以实现非门（NOT gate），它控制电流的路径。

与门（AND gate）需要两个输入，只有在两个输入都为真时，输出才为真。

或门（OR gate）只需要一个输入为真，输出就为真。

异或门（XOR gate）类似于或门，但如果两个输入都为真，则输出为假。

通过基本的布尔逻辑门，我们可以构建出更复杂的逻辑电路，而不必关注底层的晶体管和电子流动。

计算机工程师在设计处理器时，通常不会在晶体管层面工作，而是使用更大的逻辑门块。

即使是专业的计算机程序员，也很少考虑他们编写的逻辑如何在物理世界中通过这些微小的组件实现。

我们已经从考虑原始的电信号转变为我们数据的第一个表示——真和假，并且已经对计算有了初步的了解。

仅凭本集中的逻辑门，我们就能构建出评估复杂逻辑语句的机器。

Transcripts

Hi, I’m Carrie Anne and welcome to Crash Course Computer Science!

Today we start our journey up the ladder of abstraction, where we leave behind the simplicity

of being able to see every switch and gear, but gain the ability to assemble increasingly

complex systems.

INTRO

Last episode, we talked about how computers evolved from electromechanical devices, that

often had decimal representations of numbers – like those represented by teeth on a gear

– to electronic computers with transistors that can turn the flow of electricity on or off.

And fortunately, even with just two states of electricity, we can represent important information.

We call this representation Binary -- which literally means “of two states”, in the

same way a bicycle has two wheels or a biped has two legs.

You might think two states isn’t a lot to work with, and you’d be right!

But, it’s exactly what you need for representing the values “true” and “false”.

In computers, an “on” state, when electricity is flowing, represents true.

The off state, no electricity flowing, represents false.

We can also write binary as 1’s and 0’s instead of true’s and false’s – they

are just different expressions of the same signal – but we’ll talk more about that in the next episode.

Now it is actually possible to use transistors for more than just turning electrical current

on and off, and to allow for different levels of current.

Some early electronic computers were ternary, that's three states, and even quinary, using 5 states.

The problem is, the more intermediate states there are, the harder it is to keep them all

seperate -- if your smartphone battery starts running low or there’s electrical noise

because someone's running a microwave nearby, the signals can get mixed up... and this problem

only gets worse with transistors changing states millions of times per second!

So, placing two signals as far apart as possible - using just ‘on and off’ - gives us the

most distinct signal to minimize these issues.

Another reason computers use binary is that an entire branch of mathematics already existed

that dealt exclusively with true and false values.

And it had figured out all of the necessary rules and operations for manipulating them.

It's called Boolean Algebra!

George Boole, from which Boolean Algebra later got its name, was a self-taught English mathematician in the 1800s.

He was interested in representing logical statements that went “under, over, and beyond”

Aristotle’s approach to logic, which was, unsurprisingly, grounded in philosophy.

Boole’s approach allowed truth to be systematically and formally proven, through logic equations

which he introduced in his first book, “The Mathematical Analysis of Logic” in 1847.

In “regular” algebra -- the type you probably learned in high school -- the values of variables

are numbers, and operations on those numbers are things like addition and multiplication.

But in Boolean Algebra, the values of variables are true and false, and the operations are logical.

There are three fundamental operations in Boolean Algebra: a NOT, an AND, and an OR operation.

And these operations turn out to be really useful so we’re going to look at them individually.

A NOT takes a single boolean value, either true or false, and negates it.

It flips true to false, and false to true.

We can write out a little logic table that shows the original value under Input, and

the outcome after applying the operation under Output.

Now here’s the cool part -- we can easily build boolean logic out of transistors.

As we discussed last episode, transistors are really just little electrically controlled switches.

They have three wires: two electrodes and one control wire.

When you apply electricity to the control wire, it lets current flow through from one

electrode, through the transistor, to the other electrode.

This is a lot like a spigot on a pipe -- open the tap, water flows, close the tap, water shuts off.

You can think of the control wire as an input, and the wire coming from the bottom electrode as the output.

So with a single transistor, we have one input and one output.

If we turn the input on, the output is also on because the current can flow through it.

If we turn the input off, the output is also off and the current can no longer pass through.

Or in boolean terms, when the input is true, the output is true.

And when the input is false, the output is also false.

Which again we can show on a logic table.

This isn’t a very exciting circuit though because its not doing anything -- the input

and output are the same.

But, we can modify this circuit just a little bit to create a NOT.

Instead of having the output wire at the end of the transistor, we can move it before.

If we turn the input on, the transistor allows current to pass through it to the “ground”,

and the output wire won’t receive that current - so it will be off.

In our water metaphor grounding would be like if all the water in your house was flowing

out of a huge hose so there wasn’t any water pressure left for your shower.

So in this case if the input is on, output is off.

When we turn off the transistor, though, current is prevented from flowing down it to the

ground, so instead, current flows through the output wire.

So the input will be off and the output will be on.

And this matches our logic table for NOT, so congrats, we just built a circuit that computes NOT!

We call them NOT gates - we call them gates because they’re controlling the path of our current.

The AND Boolean operation takes two inputs, but still has a single output.

In this case the output is only true if both inputs are true.

Think about it like telling the truth.

You’re only being completely honest if you don’t lie even a little.

For example, let’s take the statement, “My name is Carrie Anne AND I’m wearing a blue dress".

Both of those facts are true, so the whole statement is true.

But if I said, “My name is Carrie Anne AND I’m wearing pants” that would be false,

because I’m not wearing pants.

Or trousers.

If you’re in England.

The Carrie Anne part is true, but a true AND a false, is still false.

If I were to reverse that statement it would still obviously be false, and if I were to

tell you two complete lies that is also false, and again we can write all of these combinations

out in a table.

To build an AND gate, we need two transistors connected together so we have our two inputs

and one output.

If we turn on just transistor A, current won’t flow because the current is stopped by transistor B.

Alternatively, if transistor B is on, but the transistor A is off,

the same thing, the current can’t get through.

Only if transistor A AND transistor B are on does the output wire have current.

The last boolean operation is OR -- where only one input has to be true for the output to be true.

For example, my name is Margaret Hamilton OR I’m wearing a blue dress.

This is a true statement because although I’m not Margaret Hamilton unfortunately,

I am wearing a blue dress, so the overall statement is true.

An OR statement is also true if both facts are true.

The only time an OR statement is false is if both inputs are false.

Building an OR gate from transistors needs a few extra wires.

Instead of having two transistors in series -- one after the other -- we have them in parallel.

We run wires from the current source to both transistors.

We use this little arc to note that the wires jump over one another and aren’t connected,

even though they look like they cross.

If both transistors are turned off, the current is prevented from flowing to the output,

so the output is also off.

Now, if we turn on just Transistor A, current can flow to the output.

Same thing if transistor A is off, but Transistor B in on.

Basically if A OR B is on, the output is also on.

Also, if both transistors are on, the output is still on.

Ok, now that we’ve got NOT, AND, and OR gates, and we can leave behind the constituent

transistors and move up a layer of abstraction.

The standard engineers use for these gates are a triangle with a dot for a NOT,

a D for the AND, and a spaceship for the OR.

Those aren’t the official names, but that's howI like to think of them.

Representing them and thinking about them this way allows us to build even bigger components

while keeping the overall complexity relatively the same - just remember that that mess of

transistors and wires is still there.

For example, another useful boolean operation in computation is called an Exclusive OR - or XOR for short.

XOR is like a regular OR, but with one difference: if both inputs are true, the XOR is false.

The only time an XOR is true is when one input is true and the other input is false.

It’s like when you go out to dinner and your meal comes with a side salad OR a soup

– sadly, you can’t have both!

And building this from transistors is pretty confusing, but we can show how an XOR is created

from our three basic boolean gates.

We know we have two inputs again -- A and B -- and one output.

Let’s start with an OR gate, since the logic table looks almost identical to an OR.

There’s only one problem - when A and B are true, the logic is different from OR,

and we need to output “false”.

To do this we need to add some additional gates.

If we add an AND gate, and the input is true and true, the output will be true.

This isn’t what we want.

But if we add a NOT immediately after this will flip it to false.

Okay, now if we add a final AND gate and send it that value along with the output of our

original OR gate, the AND will take in “false” and “true”, and since AND needs both values

to be true, its output is false.

That’s the first row of our logic table.

If we work through the remaining input combinations, we can see this boolean logic

circuit does implement an Exclusive OR.

And XOR turns out to be a very useful component, and we’ll get to it in another episode,

so useful in fact engineers gave it its own symbol too -- an OR gate with a smile :)

But most importantly, we can now put XOR into our metaphorical toolbox and not have to worry

about the individual logic gates that make it up, or the transistors that make up those gates,

or how electrons are flowing through a semiconductor.

Moving up another layer of abstraction.

When computer engineers are designing processors, they rarely work at the transistor level,

and instead work with much larger blocks, like logic gates, and even larger components

made up of logic gates, which we’ll discuss in future episodes.

And even if you are a professional computer programmer, it’s not often that you think

about how the logic that you are programming is actually implemented in the physical world

by these teeny tiny components.

We’ve also moved from thinking about raw electrical signals to our first representation

of data - true and false - and we’ve even gotten a little taste of computation.

With just the logic gates in this episode, we could build a machine that evaluates complex logic statements,

like if “Name is John Green AND after 5pm OR is Weekend

AND near Pizza Hut”, then “John will want pizza” equals true.

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