For (hopefully) the last time in the next three years, I’m moving! It’s only one city over, but I want to try and keep up a semblance of work productivity while I pack up and hop. So for the next two weeks or so, the blog will be on hiatus. Sorry all!

I will try to put up some fun content sporadically. And hopefully a guest post.

This is the fifth part in my multi-part series on how computers work. Computers are thinking machines, and the first four parts of my series have been on how we teach computers to think. But all of this logic, electronic or otherwise, is useless unless our computers can remember what they did. After logicking something out, a computer needs to remember the result of all that logicking!

In this post, I describe how to use the logic gates described in part four to electronically implement computer memory.

This post depends heavily on my last few posts, so if you haven’t read them, you might want to.

In the first and second parts, I describe the language of logic that computers use, called Boolean algebra.

Before we talk about exactly how we implement computer memory, let’s talk about what we want out of it.

In the world of Boolean logic, there is only true and false. So all we need to do is record whether the result of a calculation was either true or false. As we learned in part three, we represent true and false (called truth values) using the voltage in an electric circuit. If the voltage at the output is above +5 volts, the output is true. If it’s below +5 volts, the output is false.

So, to record whether an output was true or false, we need to make a circuit whose output can be toggled between + 5 volts and, say, 0 volts.

Logic Gate, Logic Gate

To implement this, we’ll use the logic gates we discussed in part four. Specifically, we need an electronic logic gate that implements the nor operation discussed in part two. A nor B, which is the same as not (A or B), is true if and only if neitherAnorB is true. We could use other logic gates, but this one will do nicely.

As a reminder, let’s write out the truth table for the logical operations or and nor. That way, we’ll be ready to use them when we need them. Given a pair of inputs, A and B, the truth table tells us what the output will be. Each row corresponds to a given pair of inputs. The right two columns give the outputs for or and nor = not or, respectively. Here’s the table:

Let’s introduce a circuit symbol for the nor gate. This will be helpful when we actually draw a diagram of how to construct computer memory. Here’s the symbol we’ll use:

Crossing the Streams

Okay, so how do we make computer memory out of this? Well, we take twonor gates, and we cross the streams…

We define two input variables, which we call S (standing for set) and R (standing for reset), and two output variables, which we call Q and not Q. The reasons for this peculiar naming scheme will become clear in a moment. Then we wire the output of each of our nor gates so that it feeds back into the other nor gate as an input, as shown below.

For reasons that will eventually become clear, this circuit is called an SR-Latch, and it’s part of a class of circuits called flip-flops. Now let’s see if we can figure out what’s going on. Assume that both S and R are false for now. And let’s assume that Q is true and not Q is (as the name suggests) false, as shown below.

Is this consistent with the truth table we listed above?

S nor Q is false, because if Q is true, then (obviously) both S and Q aren’t false. Since we gave the name “not Q” to the output of S nor Q, this means not Q must be false. That’s what we expected. Good.

R nor (not Q) is true, because R is falseand not Q is false. The output of R nor (not Q) is the same as Q, so Q must be true. Also what we expected!

Okay, so what does this mean? It means that if we start our circuit in this state, with R and S as false, Q as true, and not Q as false, our circuit perpetuates itself in this state. Nothing changes.

Toggle Me This, Toggle Me That

Now let’s alter the state described above a little bit. Let’s change R to true. Since R is true, this changes the output of R nor (not Q) to false.So now Q is false…and since S is still false, the output of S nor Q is now true. Now our circuit looks like this:

And if we wait a moment further, the cross-wiring takes effect so that both inputs to R nor (not Q) are true. This doesn’t change the output, though, as shown below.

Now we can set R to false again, and Q will stay false and not Q will stay true, as shown below.

Look familiar? This is the mirror image of the state we started with! And it’s self-sustaining, just like the initial state was. With both R and S set to false, not Q will stay true as long as we like.

Although R is falsenow, the circuit remembers that we set it to true before! It’s not hard to convince ourselves that if we set S to first true and then false, the circuit will revert to its original configuration. This is why the circuit is called a flip-flop. It flip-flops between the two states. Here’s a nice animation of the process I stole from Wikipedia:

In general, clocks are something I didn’t touch on. Real computers use a clock to sync the flipping of memory with the computations they perform using the logic gates I talked about earlier. (Clocks can also be generated using logic gates. This is the speed of your CPU clock.) I figured I wouldn’t go into that here because it’s a bit too technical and, in my opinion, not necessary for understanding.

Next Time

We now have enough tools to understand the essentials of how a computer works. It performs logical operations using logic gates, and it remembers what it did using flip-flops. Next time, we’ll take a break from electronic computers to discuss some other ways you can make a computer. Did you know you can make a computer with gears? With ropes and pulleys? With dominoes? With card games? Find out more next time.

Further Reading

Flip-flops are the domain of electrical engineers, so there’s not much non-technical material on them. Here’s what I could find.

A flip-flop is a special case of a class of circuits called “bi-stable vibrators.” If you like, you can learn about them on their Wikipedia page.

Here’s a fairly technical video lecture on flip-flops.

This set of lecture notes is at about the same level as my post, but it goes into substantially more depth.

If you want to understand clocked flip-flops, you might start here.

Related Reading

If you liked this article, you might enjoy reading my previous entries on computing:

In this article, I describe the basics of Boolean logic, starting with truth tables.

In this article, I describe how to make composite logical statements using Boolean logic.

In this article, I introduce the triode vacuum tube and describe how it works.

In this article, I show how to use triodes to make logic gates.

If you like explanations of how hardware works, here are some similar articles:

In this article, I describe one way to make a transistor.

If the presence of electricity
can be made visible
in any part of the circuit,
I see no reason why intelligence
may not be transmitted
instantaneously by electricity.
~Samuel Morse

This is the fourth part in my multi-part series on how computers work. Computers are thinking machines, but they can’t do this on their own. We need to teach them how to think. And for this, we need a language of logic. In the first part of the series, I introduced this language of logic, Boolean algebra. In the second part, I described how to formulate complex logical statements using Boolean algebra. In the third part, I described how some of the electronics in old-school computers worked.

This time, I finally get to the meat of things. I describe how you can use the circuits described in part 3 to actually implement Boolean logic electronically.

Voltages

The following discussion is going to depend heavily on an understanding of the triode vacuum tubes that I discussed last time. So if you haven’t already, you probably want to last week’s article before you read this one.

That said, some review is probably in order. First let’s review electric voltage. The salient points are this. Electrons want to flow from places in a circuit that are at low voltage to places that are at high voltage. Voltage is measured in volts. We want to use voltage as a stand-in for the truth values described in parts one and two of my series on how computers work.

There are a number of ways we can use voltage to represent truth values. But let’s pick the most common way. Let’s say we have a circuit. We’ll connect a voltage-measuring device to a spot on our circuit—perhaps where two wires intersect—and say that, if it reads any voltage higher than +5 volts, then our circuit represents true at that spot. If it reads any lower, then our circuit represents false there.

(There’s an important detail I’m skipping here. Voltages are not absolute numbers. We know that electrons flow from low voltage to high voltage. But we need a baseline for what “zero volts” means. In every circuit, this “zero volts” value might be different, but we always have to set it and choose a value. We usually call “zero volts” ground.)

Vacuum Review

Now let’s review the basics of a triode. As the name suggests, a triode is a circuit component with three terminals, called the cathode, anode, and filament, as shown below. There’s another piece called the called the heating element that we won’t discuss in much detail.

I discuss the triode in great detail in last week’s article. But for now, here’s what you need to know. The filament controls the flow of electrons from the cathode to the anode. Suppose that I hook up the triode in a circuit so that the anode is at a high voltage, and the cathode is at a low voltage. Then if the filament is at a low voltage like the cathode, then no current will flow. If the filament is at a high voltage like the anode, then current will flow.

Fiddly Names

It’s worth noting that the pieces of a triode can have other names. The cathode is often called the plate and the filament is often called the grid. In this naming scheme, confusingly, the heating element is often called the filament.

It’s also worth noting that these days triodes have been almost completely replaced by transistors.But transistors have different names for these parts. In a transistor, the cathode is called the source, the anode is called the drain, and the filament (or grid) is called the gate. A transistor does not have a heating element. To avoid confusion, I’ll use vacuum tubes instead of transistors. And I’ll use the names in my diagram.

Boolean Circuity

Now let’s implement Boolean logic! To do this, let’s chain some triodes together, as shown below.

Here we keep the anodes at a very high voltage, much higher than the cathodes could possibly be at. We then connect both cathodes to a terminal that we call C. We name the filament terminals A and B respectively.

Now let’s manipulate the terminals A and B and see what terminal C does.If bothA and B are at a low voltage (i.e., false), then current won’t flow through either triode. The result is that C stays at a low voltage, which we’ll call false. But now let’s put terminal A at a higher voltage, say true. (For now we’ll leave B as false.) Then current will flow through the left-most triode and raise the voltage at terminal C so that it becomes true.

Similarly, if we keep A at a low voltage (i.e., false) but raise the voltage at B so that it becomes true, then current will flow through the right-most triode. This too will raise the voltage at terminal C and make it true. And of course, if bothAandB are true, then current will flow and raise the voltage at C, making it true.

So if bothAandB are false, then C is false.But if eitherA or B or bothA and B are true, then C is true too. The astute among you might recognize C as the result of the logical operation A or B. We’ve just made the logical or work electronically! The circuit we just constructed is called an or gate.

More Gates

Can we do the same thing to make a logical and? Let’s try. We’ll still use two triodes. But now let’s connect them in a different way, as shown below. We put the anode of the first triode at a very high voltage. But we connect its cathode to the anode of the second triode. We label the filaments A and B respectively and the cathode of the second triode C.

Now current will be unable to flow unless bothterminals A and B are at a high voltage. In other words, C will be true only if both A and B are true. You might then recognize C as the output of the logical A and B, which we’ve now implemented electronically! This circuit is called an and gate.

Gates in Practice

I showed you how to electronically implement the boolean operations and and or described in George Boole and the Language of Logic, Part 1. If we wanted to make composite statements as we did in part 2, then we’d also need the not operator. But that’s actually a bit trickier (though not impossible) to make electronically. So I won’t describe it.

Usually, in practice, people use nand and nor gates as opposed to and, or, and not. These are harder to make, however, so I won’t describe them. Hopefully the gates I did describe, however, give you a feel for how this works.

Electronic Caveats

In my description of the and and or gates, I claimed that when current flowed through a triode, the voltage at the cathode changed. In practice things are a lot more complicated. Voltage and current are related. In simple cases, the relationship is given by Ohm’s law, which many of you are probably familiar with. In more complicated cases, where the current changes quickly, you need to take more things into account, like the travel time of electrical signals.

That said, the description I gave gets the basic idea across and, if we added more circuit components (such as, capacitors, inductors, and resistors), the gates I described would work.

Next Time

Performing a logical calculation is useless unless you can record your findings. Next time, I’ll describe how to use logic gates to teach computers how to remember.

Further Reading

If you want to know more, here are some resources on how logic gates are implemented.

This is the third part in my multi-part series on how computers work. Computers are thinking machines, but they can’t do this on their own. We need to teach them how to think. And for this, we need a language of logic. In the first part of the series, I introduced this language of logic, Boolean algebra. In the second part, I described how to formulate complex logical statements using Boolean algebra.

Now, in part three, I lay the groundwork for how we can implement simple Boolean logic using electronics. In this part, I describe the old-school electronics that people used for the first electronic computers.

Circuit Basics

Before we talk about logic in electronics, let’s take a moment to quickly discuss electronics as a whole. An electric circuit drives and takes advantage of the motion of electric charge. There are two flavors of electric charge, positive and negative. As the old adage goes, opposites attract and like-charges repel. So two positive (or negative) charges are repelled from each other, while a negative charge is attracted to a positive charge.

There are two important quantities we need to think about: current and voltage. Current describes the number of charges passing through a given piece of metal, like a wire, per second. If we imagine that charges make up a fluid like water, then electric current is exactly analogous to speed of the flow of the liquid. We measure current in amperes, or amps, after Andre-Marie Ampere.

Voltage is current’s desire to flow. In science lingo, it’s the potential energy per unit of charge at a given point in space. This is hard to visualize, so let’s talk concretely. If I have several positive charges near each other, they all repel and they want to move away from that point. So this is a place of high voltage. Voltage is always described in terms of positive charges. So if I have several negative charges next to each other, then even though the negative charges are repelling each other, a positive would just love to get near that negative action and it will go towards the spot. This is a place of low voltage.

We can generate voltage in a number of ways. But the one you’re probably familiar with is a battery. The positive terminal on a battery is a place of high voltage and the negative terminal is a place of low voltage.

We all know that water flows downhill. So in our water analogy, voltage is the height of the water. High voltage is a hill and low voltage is a valley. Positive charges like to flow from hills to valleys. But if a positive charge is already sitting in a valley, it’s probably not going anywhere. (If you like, you could instead think of it as the pressure of the water.) We measure voltage in volts, after Alessandro Volta.

In physical electric circuits, electrons, which have negative charge, are the charges moving through the circuit. By convention, current is defined in terms of positive charge, so current flows in the opposite direction that the electrons are moving. And similarly, electrons travel from low voltage to high voltage. Electrons flow uphill.

The Voltage of Truth

If we want to use electronics to implement Boolean logic, we need something to represent the values true and false. There are a number of choices, but a common one is to use voltage. Let’s say we have a circuit. We’ll connect a voltage-measuring device to a spot on our circuit—perhaps where two wires intersect—and say that, if it reads any voltage higher than +5 volts, then our circuit represents true at that spot. If it reads any lower, then our circuit represents false there.

But how can we control voltage? Well, fortunately, it’s just how attracted a positive charge is to a given area. In other words, it’s the density of electrons! (Or the density of protons if the positive charge is repelled from a region.) For example, (very roughly) electrons can move completely freely inside conductive metal like copper. So, since electrons repel each other, they will tend to distribute themselves evenly along a wire. This means that the wire will be at the same voltage all along its length.

Electrically Powered Electric Switches

So to control voltage, we just have to control the number of charges. How do we do that? Well, one way is a mechanical wall switch. If you flip a wall switch, you’ve probably closed a circuit allowing current to flow, adding charge, and changing a voltage. But this isn’t terribly useful for us because it requires us to take action. We want our circuit to behave like a Boolean truth table. The output voltage (or truth value) should depend on the input voltage(s).

The trick is that we place the burden of flipping the switch onto the electronics. In the olden days, we used a specific type of vacuum tube, called a triode, shown below. It’s called a vacuum tube because there’s no air inside the glass. It’s called a triode because there are thee terminals that you connect to when you make a circuit.

Here’s what it looks like inside:

The three terminals are called the cathode, the anode, and the filament respectively. The cathode and anode are connected to metal plates, while the filament is connected to a a wire mesh that electrons can pass through. Near the cathode, there’s a heating element which heats the cathode up.

Let’s ignore the filament for a moment. If we put the cathode at a low voltage and the anode at a high voltage, the heating element heats up the cathode, and boils electrons off of it. They’re then attracted by the anode and they fly to it. So an electric current flows from the anode to the cathode, as shown below. (Remember current flows in the direction opposite to the direction the electrons travel.) Since electrons are traveling into the anode, this might change the voltage from high to low.

But now let’s say we put the filament at a low voltage too. It repels the electrons. So now after we boil them off of the filament, they won’t want to travel. This means that if we put the filament at a low enough voltage we can stop the flow of current completely, as shown below.

In other words, we can control the current between the anode and the cathode by using the filament!

Naming Conventions

+Hamilton Carter at Copasetic Flow (who both uses Ham radios and used to design microchips and knows much more about the innards of computers than I) pointed out that there’s another common nomenclature for the terminals on a triode. The terminal I labeled the anode is often called the plate and the terminal I labeled the “filament” is often labeled the grid. This is important because then people call the heating element that boils off electrons a filament.

Sorry. It’s confusing, I know. Anyway, thanks Hamilton!

(By the way, if you haven’t already, you should check out Hamilton’s blog, Copasetic Flow. Like me, he’s a physicist in training and he posts some awesome stuff.)

Wishy-Washy Wibbly Wobbly Electronics

I feel the need to warn you that I’ve taken a _lot_ of liberties with my explanation of how the electronics work, especially in my electronics basics section. I wanted to say just enough so that you could understand the implementation of Boolean logic, which comes next time.

The biggest liberty I’ve taken is with the relationship between current and voltage. In simple circuits, there’s a simple relationship based on the resistivity of the wire, called Ohm’s Law. But in circuits where currents are changing very quickly, the relationship is much more complicated.

Perhaps at some point I’ll do a post on this.

Along Came the Transistor

Nowadays of course, no one uses triode vacuum tubes. Instead we use transistors, which are made using quantum mechanics, nanofabrication, and badass science wizardry. I’m not discussing transistors here because they’re a bit complicated and I didn’t want to muddy the discussion. The triode gets the idea across, and it’s a neat bit of computer history.

That said, transistors are dramatically better than vacuum tubes in basically every way. They’re millions, possibly billions, of times smaller and cheaper to produce. And they react to electrical signals much much faster. The only disadvantage is that transistors aren’t as durable as vacuum tubes and they can’t handle voltages nearly as high.

I wrote about transistors a while back. If you’re interested I suggest you check out the following articles in order:

The Charming Doubleness, where I motivate quantum mechanics by discussing particle-wave duality.

Unreal Truths, where I discuss the quantum energy levels in the Bohr model of the Atom.

William Beaty also has a beautiful and simple article on how a different type of transistor, the bipolar junction transistor, works. Check it out here.

Further Reading

Still curious about vacuum tubes? Here are some resources:

The easiest resource is probably this article by PBS.

This nice article by Eric Barbour is a little more technical, but still pretty accessible.

Anything that thinks logically
can be fooled by something else
that thinks at least as logically as it does.
~Douglas Adams

This is the second post in a multi-part series explaining how computers work. A computer is a thinking machine, a device which applies logic to any problem we ask it to. However, computers don’t know how to do this automatically. We have to teach them. And to teach them, we need a language of logic.

Last time, we introduced one such language of logic, Boolean algebra. This time, we learn how to make composite statements in Boole’s system.

This post will depend heavily on the preceding one, so if you didn’t read last week’s post, check it out here.

Let’s pick up where we left off. We’d just written out the truth tables for not, and, or, and if-then.

More Complex Statements

We can use the truth tables we’ve written out to construct statements of arbitrary complexity. All we have to do is combine them!

For example, we noticed earlier that the truth table for the word or is a bit outside of the colloquial use. The reason was that if both statements A and B are true, then the statement A or B is also true. It would be much more intuitive if the statement A or B was true if A was true or B was true, but false if bothA and B were true. This would certainly describe a coin flip better!

The word for this operation is called xor, meaning exclusive or. Like and, or, not, and if-then, it has a truth table. We could simply define xor‘s truth table to have the properties we want, but instead, let’s try to get it by combining other truth tables.If we want to compute A xor B, we know we’ll need A or B and A and B—so let’s tabulate those first, all together in the same table:

All I’ve done for now is copied the truth tables for A and B and A or B onto a single table, then left some additional columns suggestively blank.

Since xor means we want one and only one input to be true–that is, we want either A or B to be true, but not both—let’s first write out what happens when we negate A and B. To do this, we look at its true/false values, found in the third column. On every row where we see a True in that column, we write a False in the fifth column (the first blank column). Likewise, every time we see a False in the third column, we write a True in the fifth column. The results are tabulated below. I added parentheses to Not (A and B) to emphasize that we’re negating the combined statement A and B, not just negating A.

We’re almost there! To finish, let’s calculate what (A or B) and (Not (A and B)) is, since that “compound operation” fully describes what we mean when we say xor. To do this, we use the and truth table from before. But instead of starting all the way back at the A and B columns, like we did before, we use the truth results we tabulated in the A or B and Not (A and B) columns of our new truth table:

Let’s look at the last column. Now that looks like an intuitive “xor” statement! If A and B are both true, then the statement A xor B—which is the same as (A or B) and not (A and B)—is false. If either A or B is true and the other input is false, A xor B is true. And if both A and B are false, A xor B is false. Perfect!

It turns out that we only need not and and oror to construct any other composite statement. Even the if A then B causality statement we introduced before can be written as a combination of the more elementary words: if A, then B is the same as not (A and not B). Try it out for yourself and see!

Truth Arithmetic

Earlier, I mentioned that we often use the numbers 1 and 0 for the values true and false respectively. Let’s try that now. In fact, let’s take it one step further and assign some familiar symbols to the words and and xor. Let’s make and a multiplication sign (x) and xor a plus sign (+).

This allows us to write out statements as equations whose right-hand sides tell us the true/false value of their left-hand sides. For example, true xorfalse becomes 0 + 1, and since 0 + 1 = 1, this means that true xor false is true. For another example, we can write true and false as 0 x 1 = 0, or false. If we concede that 1 + 1 = 0, then we can do this arithmetic with every combination of true and false. We only have to remember that when we negate, we replace every zero with a one and every one with a zero.

This is why binary is famously written as ones and zeroes!

Logic and Mathematics

A lot has happened in mathematics since Boole first described his language of logic. Mathematicians have carefully rebuilt the entire field from the solid foundation of these simple logical ideas. It’s not an exaggeration to say that all of mathematics is an intricate application of this kind of logic.

The way I like to think about it, mathematics is a way for us to keep ourselves honest. It’s a careful set of rules and a language to go with them, made so that when we think carefully about something, we know we’ll get the right answer. And it all starts with Boolean logic.

…Well, sort of. It doesn’t have to be this way. Boole chose to use two values of truth: true and false. But mathematicians have since discovered that we can do just as well with three truth values: true, false, and sort of. Or infinite truth values ranging from completely true to completely false. Thinking in this way is much harder, of course, so most people don’t. But it is possible. If there is an alien counterpart to Boole on an alien world somewhere, maybe those aliens think in terms of “yes,” “no,” and “sort of.”

Next time I’ll explain how we implement Boole’s logic electronically to build a computer.

Related Reading

After my previous post, many people suggested some excellent resources. Here they are.

+Jean-Baptiste Queru has an absolutely wonderful post on how dizzyingly complicated computers are. You can find it here.

Boolean logic is the topic of many first-year college computer science and mathematics courses around the world. If you’re interested in learning it at a deeper level, here’s an online course you can take.

Some math bloggers have attempted to describe Boolean logic with more depth. I particularly like professional math tutor John M.’s article. You can find it here.

You May Also Enjoy

If you liked this post, you might enjoy my other posts on mathematics:

Logic takes care of itself;
all we have to do is to look
and see how it does it.
~Ludwig Wittgenstein

Contrariwise,
if it was so, it might be;
and if it were so, it would be;
but as it isn’t, it ain’t.
That’s logic.
~Lewis Carroll

This is the first post in a multi-part series explaining how computers work. At its heart, a computer is a logical-thinking machine. It’s very good at starting with several assumptions and deducing a conclusion from those assumptions.

Of course, a computer can’t do any of that on its own. We need to teach it how to think first. And to teach it how to think, we need a language of logical thought. Fortunately, logic has a language we can use, first proposed by George Boole (pictured above) in his 1854 treatise An Investigation of the Laws of Thought. In his honor, this language is called Boolean Logic or Boolean Algebra.

Since the very construction of computers is based on this language of logic, our very first post will be on Boole’s laws of thought.

True and False. One and Zero.

George Boole was a mathematician who wanted his language to be as precise as mathematical law. He did away with fuzzy ideas like “kind of” and “maybe.” In Logic, Boole argued, every statement is either true or false. Something can’t be “kind of true,” “maybe true,” or “probably true.”

Suppose that I flip a coin without looking and say, “Maybe it landed on heads and maybe it landed on tails.” That statement may be technically true, but it’s too vague to communicate anything of value. The most correct—and true—statement, Boole would argue, is “the coin landed on heads or the coin landed on tails.” When talking about events like that, there’s no room for “maybe.”

Nowadays, we often use the number 1 to symbolize true and 0 to symbolize false. (Hence the name “binary logic.”) For reasons we will see, this is very convenient, especially in computers. But for now, as we introduce the topic, we’ll use T for true and F for false.

Note that I will be using the words “true” and “false” and the letters “A” and “B” a lot below. To make them stand out and make my paragraphs easier to read, I will be bolding important words and symbols. I’m not yelling at you or emphasizing those specific words. I’ll italicize for emphasis.

Tabulating The Truth

Intuitively, we know that if a statement is not true, it’s false. However, a computer doesn’t know that. It has no idea what words like “and,” “or,” or “not” mean… or what any words mean, for that matter. But we can teach it by defining things called truth tables. This will be easiest to explain by example, so let’s look at the truth table for and:

Each column describes the value for a different statement. Statements A and B in the first two columns could be anything. Statement A might be “I have a dog” and statement B might be “I have a cat.” The third column is the statement A and B. So in our case, “I have a dog and I have a cat.”

Each row tells us the truth value of the statement in question. So, for example, if we look at the second row, if A is true and B is false, the statement A and B is false. To continue our pet example: The second row describes a situation in which I have a dog but not a cat. Note that, in order for the statement A and B (“I have a dog and I have a cat”) to be true, both statement A (“I have a dog”) and statement B (“I have a cat”) need to be true—it’s not enough to have only one or the other.

Let’s look at another truth table…this time for the word “or:”

Unlike A and B, fulfilling A or B only requires one statement to be true. But note that if both statements are true, then the statement A or B is also true. We usually think of the word “or” as exclusive—something has to be either, not both. In Boolean logic, however, the only way that “I have a dog or I have a cat” is false is if I have neither pet.

The truth table for the word “not” (below) is very simple, since we only negate one statement, rather than combining two statements. If A (“I have a dog”) is true, then not A (“I don’t have a dog”) is false. The converse is also correct: If A is false, then not A is true.

We can even encode the notion of causality into our truth tables. Let’s try making a truth table for the idea of “if A, then B“—for example, “If I am blogging, then I am using a computer.” Here’s the table:

So statement A is “I am blogging” and statement B is “I am using a computer.” The first row says that, if I’m both blogging and I’m using a computer, then the statement “If I’m blogging, then I’m using a computer” isn’t disproved and is therefore true in this scenario. The second row says that, if I’m somehow blogging without using a computer, this means that if A, then B is false because it makes a wrong assumption: that the only possible way to blog is to use a computer. The third and fourth rows are fail-safes against logical fallacy. Even if I use a computer for activities other than blogging, that has nothing to do with whether or not I blog on a computer. Thus, the third row tells me that, if I’m not blogging but I am using a computer, the statement “If I’m blogging, then I’m using a computer” is still true. Similarly, the fourth row tells me that, if I’m neither blogging nor using a computer at the moment, the statement “If I’m blogging I’m using a computer” is still true.

Resist the urge to object, “But we can’t come to any conclusion about the relationship between blogging and computer use unless you’re blogging!” Unlike in real life, there is no “maybe” or “it depends” or “I don’t know” option in Boolean logic. That’s because the only thing we’re examining when we look at if A, then B is the idea that B must happen if A happens. Therefore, the only way to get a false is to disprove that assumption by showing that A can happen without B happening. If that assumption isn’t tested, our evaluation stays at its “default” value of true.

The third and fourth rows of this truth table are interesting for another reason. They open the door to what logicians call a vacuously true statement, which is an if A, then B statement whose A is never true. Since A is never true, then the truth table tells me that the statement if A, then B is always true. For example, if I said “if there is a tree on the moon, then that tree is purple,” then Boole would tell me that my statement is completely true. The reason is that, of course, there are no trees on the moon.

This sort of reasoning is wildly unintuitive to people not used to thinking in terms of Boolean logic. It doesn’t seem logical at all! However, if we want to be consistent, we are forced to think in this way.

Next time, I’ll continue the story of Boolean logic by telling you how to build up complex statements like you might encounter in real life.

Related Reading

Boolean logic is the topic of many first-year college computer science and mathematics courses around the world. If you’re interested in learning it at a deeper level, here’s an online course you can take.

Some math bloggers have attempted to describe Boolean logic with more depth. I particularly like professional math tutor John M.’s article. You can find it here.

You May Also Enjoy

If you liked this post, you might enjoy my other posts on mathematics:

Taming Infinity, wherein I describe how mathematicians deal with the infinite.

Panning For Primes, wherein I describe the Sieve of Eratosthenes, one way to generate prime numbers.

The Heavenly Spheres make music for us, The Holy Twelve dance with us, All things join in the dance! Ye who dance not, know not what we are knowing
~Gustav Holst

By the sweat of your brow you will eat your food until you return to the ground, since from it you were taken; for dust you are and to dust you will return.
~Genesis 3:19

Many months ago, Richard Green posted an article on Google+ that described how life on a toroidal planet would work. The discussion in the comments eventually led to speculation as to whether or not it’s possible for such a toroidal structure to actually form. That discussion is what inspired this post. Today, I’ll tell you about the nebular hypothesis, astrophysicists’ current best theory about how planets form. (Fun historical fact: One of the first people to propose the nebular hypothesis was philosopher Immanuel Kant.)

In The Beginning, Dust

Our solar system probably started as a huge cloud of gas and dust, like a nebula (hence the name “nebular hypothesis”). The particles of dust and wisps of gas gravitationally attracted each other, and other time, the denser clouds of matter collapsed into themselves. As the density of each cloud increased, so did its temperature. Eventually it became so dense and so hot that it became what we call a protostar—a young, vigorous, and confused star.

But not all of the gas and dust had become part of the protostar yet. As the protostar began to age, it began to attract and eat the remainder of the gas. Over time, as the remaining gas fell into the star, it formed a disk, as shown below. Near where the disk touched the star, the compression of its gas superheated it, generating jets of energy pointing out from the star. (For experts: The reason the gas formed a disk is because it had to jet its angular momentum before it could fall in.)

It’s All In The Disk

Let’s talk about the disk some. For reasons that will soon become clear, these disks are called protoplanetary disks. Not everything in the disk orbited around the star at the same speed. As dust and gas particles whizzed past each other, sometimes they collided…and sometimes they stuck to each other, forming bigger particles.

Over millions of years and trillions of sticky collisions, these dust particles grew to several kilometers in diameter, forming small objects that we call planetesimals. At this size, these planetesimals had a gravitational pull strong enough to attract many dust particles, allowing them to grow even faster. Very likely, planetesimals also collided with each other to form even larger objects. Eventually, these bodies were large enough to be called planets.

This description tells us that toroidal planets cannot form. Planetesimals grow in size from collisions with dust and with each other. It seems very unlikely that they would form a shape other than “roughly spherical.”

The End of the Disk

After enough time passed and the protostar had feasted sufficiently, it would begin to emit a blast of light and subatomic particles called the solar wind. This pressure blew away all remaining gas and dust in the disk that hadn’t already coalesced into large objects—leaving behind the collection of planets we know as the solar system.

Evidence

Obviously, we can’t look back in time to see how our own solar system formed. But we can look out into space to try and find solar systems that are in the process of forming. Protostars are easy to capture on film because the jets that they fire have a characteristic shape. We call them Herbig-Haro objects, and they produce some staggeringly beautiful images. See the photos below:

We can also observe the protoplanetary disks that are feeding the protostar. At first, they were hard to spot and we had to use some fancy image enhancement techniques to see them, as in the figure below. The top row shows the unenhanced images and the bottom row shows the enhanced images.

However, the Hubble got an upgrade, and we’ve been looking a while. We now have some much better images. Look at the figures below. See those little tadpole-like objects? Those are protoplanetary disks.

Hubble has now captured more than 150 images of protostars and their jets and disks. A few more for your viewing pleasure:

Sadly, we’re far too distant to see if the disks contain planetesimals.

Issues

I want to emphasize that the nebular hypothesis of planet formation is currently still a hypothesis. It’s the best description we have for how planets formed in our solar system, but it still has some important issues that need to be worked out.

For example, we still don’t know how gas giants like Jupiter form. The planetesimal description relies on the planetesimals being made of rock, so this only describes the formation of terrestrial planets like Earth and Mars. Additionally, the nebular hypothesis predicts that planets should emerge from the disk in very erratic orbits. It’s not clear how they form their current elliptical orbits, which are very regular.

Only time will tell, I suppose, if the nebular hypothesis is correct.

About a year ago, astronomers snapped an image of what they think is a gas giant forming in an alien protoplanetary disk. I don’t know what this means for the nebular hypothesis, but it’s interesting. Here’s an article on this topic.

For the brave, Professor Michael Richmond at the Rochester Institute of Technology wrote a nice little article on early star and planet formation for his astrophysics class. (I found a lot of the photos in this post there.) You can find it here.

Say we have a beam of light—maybe we made it with a laser. We’d like be able to change the intensity of the beam so that we can alternately brighten and dim it. Moreover, we’d like to be able to do so quickly. Physically blocking and unblocking the beam just isn’t fast enough. So what do we do?

The solution is to make an electric switch so we can change how the light behaves via electrical signals. This is an electro-optic modulator (EOM). Two weeks ago, I introduced graphene to you all. And last week, I described some of the work I did on graphene as an undergraduate student in the Schibli lab. This time, I’ll explain the ultimate product of that research: a graphene-based electro-optic modulato like the one shown in the figure above. I want to emphasize that I didn’t build this device and I take no credit for its design. I did, however, do some experiments that helped prove that such a device was possible. I’ll talk about all of that today.

(Important side note: one can also make an acousto-optic modulator, which uses sound to change how light behaves.)

The Strange Dance of Light and Matter

Before I can tell you how a graphene EOM works, I need to briefly discuss how a material absorbs light. I’ve given fairlydetailedexplanations of absorption in the past. But today I want to focus on other things, so I’ll only be presenting a very rough, inaccurate picture of what goes on. Take it with a grain of salt.

We know from James Clerk Maxwell that light is a wave made of electric and magnetic fields. These fields feed into each other and wiggle back and forth, as shown below.

Electrons carry negative charge and are thus affected by electromagnetism. So when light passes through a material, its wiggling pushes the electrons around, accelerating them. But when an electron is accelerated, it leeches energy out of the light. This is absorption.

(Things are much more complicated than this, of course. In insulators, this wiggling causes all sorts of other things to happen to the light. It can bend, slow down, or change direction. We call this refraction, which I’ve written about before here. In a conductor, the light will probably be reflected. Also, absorption is actually a quantum-mechanical effect.)

The Obstacles

To absorb the light, our electrons must be free to wiggle around. But many electrons aren’t free to wiggle in this way. The material might be too crowded, so that an electron that “wanted” to move would be trapped by all the other electrons in its way. Or an electron might be too tightly bound to the atomic nucleus to be able to wobble. This means that, if we can figure out how to control how mobile electrons are in a material, we can control how absorptive it is!

Chemical Doping

Now let’s talk about graphene. In its natural state, graphene has many electrons that are free to wobble (and thus absorb light). However, let’s say we pour some nitric acid on our graphene. Acid eats things because each acid molecule breaks into two pieces: a negatively charged anion and a single hungry proton (a positive hydrogen ion) that wants to chemically react with anything it can find.

Graphene is too tough for the acid to eat, but the proton still has an effect. It lands on the surface of the graphene, attracts one of the electrons within the graphene, and bonds to it. The electron stays within the graphene, but becomes immobilized so that it can’t wiggle around anymore, as shown below. One less electron to wiggle means one less electron to absorb any light that passes through the graphene, so this causes the whole graphene piece to become less absorptive. This process is called p-doping because we place positive charge on the surface of the graphene.

If we had used a base instead of an acid, we could have played the same game. The base’s negatively charged ion would have latched onto the graphene and bonded with one of its protons, which would free up an electron. If the graphene had already been p-doped, this might make the graphene more absorptive. If the graphene started in its natural state, the newly freed electron might crowd out its peers and make the material less absorptive. This process is called n-doping because we place a negative charge on the surface of the graphene.

(I’m glossing over a lot. The real story of doping involves the band structure of a material. I wrote about that here.)

So if we shine light through a graphene sheet, we can control how much of the light it absorbs by adding protons (p-doping) or removing them (n-doping).

Electrostatic Doping

Now remember, we’re trying to make an electro-optic modulator: a device that lets us quickly control how much light passes through it depending on an electrical signal. For our purposes, adding acids and bases is much too slow. We need a new trick. Is there any way we can mimic chemical doping?

As it turns out, there is! Say we place a sheet of graphene on top of some glass and sandwich our glass between two metal places, as shown below. If we apply a voltage across the plates, we can push electrons onto the graphene and charge it up. The result is that graphene now has more electrons, and they crowd each other out, preventing them from moving or absorbing.This process is called electrostatic doping, and it’s exciting because we can turn its effects on and off as fast as we can turn the voltage on and off.

Electro-Optic Modulator

Now this is an effect fast enough to make an electro-optic modulator. In the Schilbi Lab, where I worked as an undergraduate student, Professor Thomas Schibli and his students Chien-Chung Lee and Seiya Suzuki placed a piece of tantalum oxide—which has nicer properties than glass—on top of an aluminum mirror. On top of that, they put a sheet of graphene. And on top of that, they placed a ring of aluminum, as shown below. (The shape was a ring so that light could pass through the center.) When they applied a voltage between the ring of aluminum and the mirror, they were able to electrostatically dope the graphene and change how much light it absorbed.

It worked beautifully! Below is one of the devices actually made in the lab. On the left is an optical photograph of the device through a microscope. On the right is a two-dimensional color-plot of the “modulation depth,” which is a measure of how much the graphene’s absorption changes over time. The brighter the color, the bigger the modulation depth in that spot.

My Part in All of This

I take no credit for the idea of using graphene for an electro-optic modulator—that was all Professor Schibli. I also take no credit for tackling the engineering challenges of designing and building one—that was all Chien-Chung Lee and Seiya Suzuki. What I did was help prove this device could work before they started building it. I grew graphene samples and then Chien-Chung doped them with acid and measured their absorption. While the samples were still doped, I measured their Raman spectra to prove that the acid was having the expected doping effect. Afterwards, I looked at the Raman spectra again to look for signs of acid damage.

I did have the privilege, however, of seeing a working device. The team managed to get one functional while I was writing my undergraduate honors thesis on what I’d done. Pretty neat, huh?

Further Reading

This is part three of a three-part series on graphene. If you missed them, you can find the first and second parts of the series here and here.

I glossed over many, many details here. The true story of how doping works is rooted in the band structure of a material. I talk about that here.

I also glossed over important aspects of how light and matter interact. I’ve covered these in several articles, but a good place to start is my article on refraction.

I also talk about the interaction of light and matter in my article on lasers, my article on mode-locking, and my articles on scattering, which you can find here and here.

If you’re very brave, you can look at my honors thesis, which explains all of this in extreme detail.

I am a co-author on a paper detailing the proof-of-concept work. Sadly, it’s behind a paywall, but you can get it here if you have a journal subscription.

The Schibli group also published a paper on the modulator. It’s behind a paywall too, but if you have a journal subscription, you can find it here.

Graphene, a two-dimensional honeycomb lattice of carbon atoms, has made waves in science and technology circles. Last week, I gave a brief overview of the history of the stuff and why it’s special. This week, I’d like to continue the story by talking about applications. Unfortunately for us—and fortunately for society as a whole—graphene has spawned so many new technologies that it’s impossible for me to discuss them all. So instead, I thought I’d talk a single application that has personal value to me.

As an undergraduate student, I spent two years in a laser lab studying graphene’s applications in ultrafast optics. Today, I’ll tell you part of that story.

We followed the example of Bae et al., who had been funded by Samsung to develop a method for chemically growing very large sheets of graphene. We used a technique called chemical vapor deposition (CVD): First, we put a piece of pure copper foil in a very high-temperature, low-pressure chamber. The air pressure around the foil is one one-millionth of an atmosphere and the temperature is one thousand degrees Celsius. We then blow tiny amounts of methane and hydrogen gas over the copper foil. Methane is one carbon atom and four hydrogen atoms, and the copper foil catalyzes a reaction that causes the molecule to break apart. The carbon atoms deposit on the copper in a hexagonal pattern, leaving the hydrogen to be blown away. Because copper is the catalyst, the reaction stops when the foil is covered up—in our case, when a single layer of carbon atoms has been deposited. The figure below shows the Schibli group’s CVD setup. The orange thing is the vacuum pump which reduces the pressure in the glass tube. The white thing is the furnace.

After we grow the graphene, we’re faced with a problem: How precisely do we get such a delicate sheet off the copper wire without damaging it? In the Schibli lab, we followed the technique of Li et al., who etched their copper away with acid. The transfer method is a bit more complicated than that, because the graphene can’t survive on its own and because the acid must be cleaned off with great care. However, in the interest of space, I’m going to skip these details.

Measurements

After growing and separating out the graphene, we would observe the flakes in an electron microscope and measure how the amount of light it absorbed varied with intensity. The figure below shows a pair of such measurements. On the left, I plot the percent of light absorbed by a single layer of graphene as a function of the light’s intensity. (As you can see, the graphene burns before we can shine enough light on it to reach its maximum transparency.) On the right is an image of the same graphene under a scanning electron microscope.

Because the graphene burned at the highest intensities, we weren’t able to use it to generate the pulses in a laser. However, graphene still proved itself useful; this research led to the development of a tool called an electro-optic modulator. But that’s a story for next week.

If you missed my introduction to graphene last week, you might want to check it out here.

Graphene is special because it’s a semiconductor with a band structure. You can find my article on band structure here.

If you’re brave, you can find my undergraduate honors thesis on graphene here. I try to introduce specialized topics, so it should be accessible to someone who remembers their college physics courses.

I’m a co-author on a paper the Schibli group published on the saturable absorption in graphene. Sadly, it’s behind a paywall, but can find it here.

I call our world Flatland, not because we call it so,
but to make its nature clearer to you, my happy readers,
who are privileged to live in Space.
~A. Square

Graphene was first discussed in 1946, by Canadian physicist Philip Russel Wallace. Wallace didn’t believe it was possible to make graphene; what he was interested in studying was graphite, the stuff in pencil lead. Graphite, a three-dimensional honeycomb structure of carbon atoms, was a bit too difficult to handle with the tools Wallace had available to him. Ever resourceful, Wallace invented a two-dimensional analog, graphene, from which he argued he could extract the properties of graphite.

Graphene is a two-dimensional grid of carbon atoms arranged in hexagons. Wallace showed that, if you stack enough sheets of graphene on top of each other, you get graphite. So he used his calculations for graphene to extrapolate information about graphite. Little did Wallace know that his theoretical material could actually be constructed in the real world.

Scotch Tape Makes it Real

In 2004, physicists Andre Geim and Konstantin Novoselov were playing with graphite cubes and Scotch tape. They would apply tape to a piece of graphite, then rip the tape off, pulling flakes of graphite with it. They did this again and again with the flaked-off graphite, separating it into thinner and thinner flakes, until (after ten or twenty or a hundred iterations), they ended up with graphite flakes only one atom thick. Materials don’t get any thinner than one atom thick, so this stuff was as close to two-dimensional as is physically possible. Geim and Novoselov had invented Wallace’s graphene.

Since then, many other groups have replicated Geim and Novoselov’s technique, called the “Scotch tape method.” You can even watch graphene being made this way on Youtube:

(It is debatable whether or not Novoselov and Geim were actually the first to use this technique, or even the first to discover graphene. Graphene historians–this is apparently a job now–have uncovered a fair number of earlier efforts. See the Wikipedia article for more details.)

Graphene Fever

Geim and Novoselov’s discovery made waves in the scientific community. Physicists were excited to test how the laws of physics changed if electrons were forced to live in two dimensions instead of three, so people put a lot of effort into understanding graphene. What they found was incredible.

Graphene’s unique band structureforces electrons in the material to always travel the same speed and never stop, no matter what’s happening to the material. This makes them behave a lot like light does in special relativity. It also means we can turn graphene into an absurdly good conductor that responds very quickly to an applied voltage. Even better, because graphene is so thin, it’s what’s called a transparent electrode: a conducting material that we can see right through. This is a huge deal! By the very nature of conductivity, things that can conduct electricity are usually opaque. However, graphene is so thin that it can’t possibly block, reflect, or absorb all the light that hits it.

Physicists have also discovered that the honeycomb structure of graphene’s carbon atoms is ridiculously strong. In fact, graphene is one of the strongest materials ever.

At this point, proposed applications for graphene started to appear everywhere. The gold rush had begun.

Some Words of Caution

Graphene made waves in the financial world as well as the scientific world. Many, many people have already invested in graphene-based businesses. And when there’s money at stake, people tend to oversell their ideas. This means that there are a lot of advertisements and publicity campaigns for graphene-based ideas that may not pan out.

Some commercial graphene ventures certainly will succeed. A few might even cause a sea change in technology. (And all commercial graphene ventures are cool.) However, you should take all the graphene hype with a grain of salt.

Related Articles

One of the things that makes graphene so special is its band structure. I’ve written about band structure before, and you can find my article here.

The band structure means that electrons in graphene behave like photons. You can see why that’s strange in my article on how the speed of light is constant.

That’s it for now. Next time, I’ll talk about my own personal experience with graphene.