Boolean Logic & Logic Gates

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

英文

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.

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.

中文

Hi,这里是CarrieAnne,欢迎来到计算机科学速成课~

今天,我们的旅程从抽象阶梯开始,这次我们抛弃了简单的开关和装置,却拥有了组建复杂系统的能力。

上集,我们讲述了计算机如何从电机设备一步步演变。

它们通常能够表示10进制的数值。例如通过装置上的一个单位,或者通过晶体管控制电流开关的电子计算机。幸运的是,即便我们只有‘’开‘’和‘’关‘’两个状态,我们仍然可以表现出很多重要的信息。我们将其称之为‘’二进制‘’,字面意思理解就是‘’两个状态‘’,

就像自行车有两个轮子、人有两条腿^-^你也许认为只有两个状态无法完成多复杂的工作,你是对的……

但是它能够准确的表示你所需要的值：'true'和'false'。

计算机中,状态设为”开“时,电流流通,表示为true,

状态设为”关“时,电流停止,表示false。

它们只是相同信号的不同表达方式,我们将在下一节了解更多相关内容。

其实现在我们不仅仅能用晶体管来控制电流的开启和关闭,还可以控制不同的电流水平。

早期某些电子计算机为三进制,甚至五进制的,它们分别有3种状态或5种状态,问题是,状态的层级越多,状态之间的区分也就越模糊。

当你的智能手机电池低电位运行时,会由于附近正在运行的微波炉产生电气噪音。因为这些信号可能会混在一起。

而晶体管中每秒有数百万次的变化,问题会变得更加糟糕。所以,将两个信号放在尽可能远的地方。只使用"开"和"'关"。提供区分最明显的信号以解决干扰问题。

在计算机中使用二进制的另一个原因,是因为二进制在数学中有着成熟的分支,专门用来处理'true'和'false'的问题。

数学家们已经研究出了所有必要的规则和方法去操作二进制,这个分支被称为“布尔代数”。该名称来源于一位19世纪自学数学的英国数学家'GeorgeBoole',他致力于“了解,深入,并超越”亚里士多德的逻辑理论,亚里士多德逻辑法毫无疑问以哲学为基础,布朗的方法则允许使用逻辑方程式的方法去系统且正式证明真伪,这一方法首次于1847年由他的第一本书《逻辑的数学分析》中提出。

在高中学习到的常规代数中,变量值为数字,并对这些数字进行进行类似加法或乘法……

而在布尔代数,变量值为true和false,并对这些变量进行逻辑处理。

布尔代数中有三个基本操作：“非”,“与”,“或”。

这些操作都有自己独特的作用,让我们来分别看看它们。

一个“非”作用于单个布尔值,无论其是true或false,都会将其反转：

将true转换为false,将false转换为true。

我们可以画个逻辑表单,显示我们输入的原始值,然后显示进行操作后生成的结果。

现在进入关键部分,我们可以轻松的在晶体管外构建出布朗逻辑。

正如我们上一节所说,晶体管的本质只是一些电控开关,里面是三根电线:两个电极,一个控制线。

当控制线通电,电流从一侧电极流通,通过晶体管,抵达另一端电极。

这很像是常见的水龙头,打开龙头,水流出；关闭龙头,水流关闭。

你可以将控制线视为输入,而底部电极作为输出。

于是,单个晶体管里面我们有一个输入和输出。

如果我们输入on,输出也会是on,因为电流可以通过底部电极。

如果我们输入off,输出也会是off,电流无法通过底部电极。

而在布尔值中,当输入为true时,输出为true；

而当你输入false时,输出false。

让我们重新回到逻辑表上。

这并不是一个令人兴奋的电路,它没有进行任何操作,只是输出和输入相同的东西。

但是我们可以对其稍作修改,例如创建一个“非”,

我们在晶体管的顶部接入一条输出电路替代之前的底部输出。

若我们输入true,晶体管里的电流直接通向地线,

输出电路无法接收到电流,所以输出off。

用水来比喻的话大致就是水都从一个巨大的管道排出了,结果没有任何水压可以让你在家洗白白。

那么,在这种情况先如果输入on,则输出为false。

有趣的是,当我们在晶体管中输入off,虽然电流无法流动到地线,但是输出线的电流会被接通。

所以当我们输入off时,输出将会是on。

这个现象刚好匹配的逻辑表中的“非”,恭喜,我们刚刚构建了一个使用“非”计算的电路。

我们称其为“非”门；之所以称其为门,是因为它控制着我们的电流前进的道路。

“与”操作作用于最少两个输入,但是它只有一个输出。

这种情况下只有当所有输入都为true时,它才会输出true。

想想这样一个定论,如果你不会说任何谎言,那么你是个绝对是个诚实的人。

举个例子,让我们来说个命题。“我的名字是CarrieAnne,并且我穿了一件蓝色连衣裙。”

由于这两件事都是真实的,所以这整个命题也是正确（true）的。

但是如果我说：“我的名字是CarrieAnne,并且我穿了一条裤子”,这句命题就是错误（false）的。

因为我根本就没有穿裤裤！>///<(pants在英试英语中为内裤,美式英语里为长裤,额……长裤……(trousers纯粹指长裤,如果你在英国(:з」∠)

其中CarrieAnne部分是真实的,但是之后的部分为错误的,所以该命题依旧为错误（false）。

如果我直接将这个命题取反,它依旧是错误（false）。

并且如果我直接告诉你两段谎言,它依旧是错误。

那么让我们将这种情况组合到之前的逻辑表中。

要建立一个与门,我们需要将两个晶体管相互连接,并提供两个输入和两个输出。

如果我们只打开晶体管A,电流是不会流通的。因为晶体管B是关闭的。又或者晶体管B打开,晶体管A关闭,情况也是一样,电流不会流通。

只有当晶体管A和晶体管B同事打开时,输出电路才会有电流输出。

最后一个布尔运算为”或“：只要有一个输入为true,那么输出为true。

举个例子,我的名字是MargaretHamilton或我穿了一件蓝色连衣裙。这是一个正确的命题,虽然我并不是Hamiltonunfortunately,但是我确实穿了一件蓝色连衣裙,所以该命题是正确的。

如果两个命题都是true,”或“运算依旧返回true。只有当两个输入都为false时,”或“命题才会返回false。

在晶体管中构建一个或门需要一点额外的电路。我们拿出之前出现过的两个晶体管,但是用并联来代替之前的串联。我们将电流传入两个晶体管中。然后用这个小弧线来表示该电流跳过了另一条电路,两条电路没有直接连接,即便他们看起来像是交叉在一起的。如果两个晶体管同时关闭,电流无法流向输出端,所以输出为off。

现在,如果我们只打开晶体管A,电流则会向输出端流动。如果将晶体管A关闭,但是晶体管B打开,情况同上。简单来讲,只要A或B打开,输出就为on。若两个晶体管同时打开,输出依旧为on。Ok,现在我们有了非、与、或门。现在我们放下这些晶体管,进入更高的抽象层。

对于这些门的表示,标准工程师们使用三角形加小圆点表示非。

一个D形状的图标表示与,一个像宇宙飞船一样的图标表示或。

这些都不是什么官方的描述,但是我喜欢这样描述它们~

这些图标和思想可以使我们在构建更大组件的同时,去保持整体复杂度相对可控。只是别忘了那些晶体管和电路的混乱依旧存在。

举个例子：在其他有用的布尔运算中有个被称之为”异或“的方法。（全称ExclusiveOR,简写为XOR）

异或和或很像,只是当所有的输入都为true时,异或输出的是false。

只有一种情况下异或会输出true,就是当一个输入为true,另一个输入为false时。

这就像是你去外面吃的晚餐,你可以吃一份沙拉或者汤,然而……你却不能同时吃两份……😭

还有,在晶体管中构建异或是一件十分头晕的问题,但是我们可以试着通过三个基本的布尔门去创建一个异或。

我们这次依旧需要两个输入：A和B,以及两个输出。

我们先从或门开始,因为这个逻辑表看起来几乎和之前的”或“相同。只有一点差异,当A和B同时为true时,其逻辑和”或“相反,它会输出false,

为此我们需要添加一些额外的门。如果我们添加一个”与“门,并且输入两个true,则会输出true。这并不是我们想要的结果。

但是我们在这之后立刻加一个”非“,将输出转化为false。

现在我们最后添加一个与门,将之前非门和或门的值一起向前发送,与门将接收到一个true和一个false,由于与门需要接收两个true才会返回true,所以这里输出为false。这对应了我们逻辑表上的第一行。

如果我们处理剩余的输入组合,可以看见这个布尔逻辑电路确实实现了一个异或。

而异或是一个非常有用的组件,我们将在其他章节详细说明,他是如此有用,以至于工程师们也给了它一个单独的标志：一个带着笑脸的或门:)

但最重要的,我们现在可以将异或放入工具箱中不需要太过于操心其中各个逻辑门的构成,以及这些门该如何用晶体管去制作,又或者如何让这些电子在半导体中流通。

而直接向更高阶的抽象层移动当计算机工程师在设计处理器时,很少会在晶体管这个层面工作,作为替代,他们通常使用更大的区块,例如逻辑门,或者由逻辑门组成的更大的组件,我们将在未来的章节中讨论这些。

即便你是专业的程序员,也很少去思考如何直接在物理层面用这些极小的组件去实现你的程序逻辑。

我们也将思考的重心从原始的电子流动,转移到了以数据表示作为为替代:如true和false,这让我们的思维方式更贴近计算机本身。

这一章中我们获得了逻辑门,我们可以用用它构建一个鉴定复杂逻辑命题的机器,如“名字为JohnGreen与下午5点之后或周末时与披萨小屋附近”,那么“John想要披萨”等于true

以上,下周见咯~