Intro to Boolean Logic, Logic Gates, and Visualizing Gates in Minecraft

Most people are comfortable with the idea that a computer performs all its operations with 0s and 1s and do not concern themselves with understanding the fundamentals of how that is possible. Even though I've been a software developer for two years, this question just hasn't come up. That's because we're fortunate enough as software developers that most of the work that computers do is abstracted away from us, and we often need only worry about how to use our language of choice. This article will help explain how progressively more complex hardware can be built from a single hardware unit called a nand chip and it will use Minecraft to illustrate.

Introduction to Logic

If you're interested in computer science, you're probably aware of boolean operators. Software developers use them all the time in if statements. Just to reiterate the basic ones: AND operators take two boolean inputs and return one if and only if both inputs are 1. OR operators also take two inputs but return 1 if either is 1 or both are 1. NOT operators take a single boolean input and output its opposite value. You can find helpful representations of operations called truth tables.

With boolean operators, one can construct boolean expressions which are a series of boolean values and operators that can be simplified to a value. For example the expression NOT(0 or (1 AND 1)) is equal to 0. That's not particularly interesting, but it's important in the same way that you need to understand the expression 5 = 2 + 3 before you understand the function f(x) = x + 3.

So just like there are mathematical operators, expressions, and functions, there are boolean operators, expressions, and functions. Here's an example of a boolean function: f(x,y,z) = (NOT(x) AND z) OR (x AND y). That's an eyesore, how do we make it more human readable? Well fortunately theres only 3 boolean inputs so that's 2^3 or 8 outputs. We can just evaluate all possible values and create a truth table.

So we can go from boolean function to truth table. They both represent the same thing. Thus, you might not be surprised that there's a method to construct a function from a truth table. Let's take the truth table of the OR function since it is familiar to most people. f(x,y) = x OR y.

Here's how to convert a truth table to a function. First, only focus on the rows for which f = 1. Then, imagine the word AND between your input columns and the word OR between the rows you are focusing on. Now for each 0 and 1 in your input columns, replace that with 'NOT(input column name)' and '(input column name)', respectively. Here's an image to explain what I mean.

If you follow this method, you can read from left to right, top to bottom and you will have created what is called the canonical representation of the boolean function. So we have (NOT(x) AND y) OR (x AND NOT(y)) OR (x AND y). Wow that's a much worse version of the OR function! Why bother doing that? Well you could probably google 'Boolean Laws and Identities' and become decent at simplifying canonical representations, but personally I wouldn't. The real reason I showed this is that we have presented three ideas now that kind of 'prove' something. The following is probably not a sufficient real proof but should make the conclusion intuitive.

1. Boolean functions, no matter how complex, can always be translated into a truth table.
2. Truth tables can always be translated into the canonical representation.
3. The canonical representation uses just three operators AND, OR, NOT.

The conclusion is that all boolean logic can be represented using just those three operators.

I lied. You can derive all boolean logic from a single operator.

You're probably thinking: "Marc, stop toying with me". I'm almost done, I promise. Remember how I said don't bother learning boolean laws and identities. Well I'm gonna briefly mention two of them so I can get rid of our OR operator from our list of required operators. In other words, I'm going to define OR in terms of AND and NOT. The first law is called double negation and it's super obvious. x OR y = NOT(NOT(x)) OR NOT(NOT(y)). I'd say I'm not going to explain that, but instead I'll say I'm not not not going to explain that.

The next Law we need to talk about is one of the Demorgan Laws. It says: NOT(x) OR NOT(y) = NOT(x AND y). So let's go back to our doubly negated OR function and apply it.

NOT(NOT(x)) OR NOT(NOT(y) fits the form NOT(x) OR NOT(y) from Demorgan if we substitute x for NOT(x) and y for NOT(y). So lets start with the other side of the Demorgan equation NOT(x AND y) and substitute x for NOT(x) and y for NOT(y). We get NOT(NOT(x) AND NOT(y)). So the proof is:

1. x OR y = NOT(NOT(x)) OR NOT(NOT(y)).
2. NOT(NOT(x)) OR NOT(NOT(y)) = NOT(NOT(x) AND NOT(y)) by Demorgan's Law which says NOT(x) OR NOT(y) = NOT(x AND y).
3. Therefore x OR y = NOT(NOT(x) AND NOT(y)).

Okay that proof is confusing. Here's a much simpler way to prove it. Take the truth table from OR, use our regular canonical method, except instead of focusing on rows where f = 1 focus on rows where f = 0. You should have Not(x) and Not(y). Now put a Not in front of that because you are describing when f is false. Now you have NOT(NOT(x) and NOT(y))

So another proof thingy.

1. All boolean logic can be expressed in terms of AND, OR, NOT
2. OR can be expressed in terms of AND and NOT.
3. Therefore all boolean logic can be expressed in terms AND and NOT.

So I already gave away that we would get down to one operator to rule them all. So will it be AND or will it be NOT.

Neither. It's Nand.

Nand is just the opposite of AND. That is, it outputs 0 if and only if x and y are both 1. In all other cases it outputs 1. So defining AND in terms of NAND is simply (x AND y) = NOT(x NAND y).

NOT is just NAND that's been given only one input to operate on rather than two. NOT(x) = NAND(x, x). Write down a truth table for NAND and convince yourself of that.

At this point, we've defined NOT in terms of NAND. We've defined AND in terms of NOT and NAND. So we need to finish defining AND only in terms of NAND.

1. (x AND y) = NOT (x NAND y)
2. NOT(x) = x NAND x
3. By 1 and 2, NOT (x NAND y) = ((x NAND y) NAND (x NAND y))
4. (x AND y) = ((x NAND y) NAND (x NAND y))

Okay last proof, just to be super pedantic.

1. All boolean logic can be expressed in terms AND and NOT.
2. AND and NOT can be expressed in terms of NAND.
3. All boolean logic can be expressed in terms of NAND.

You might suppose if we can use NAND to express everything, we should just be able to use its opposite, AND. If you're thinking that please define NOT in terms of AND, and then read on.

If you tried that, you should have NOT(x) = NOT(AND(x, x)). Which is no good because it's circular reasoning. If you've ever heard someone define a word and use the same word in the definition, that person probably didn't know very well what that word means. Besides the problem with using NOT in the definition for NOT, there are still two operators in there and the goal was to get everything defined in terms of a single operator. Now we've just shown how to do it with NAND.

Ok great. What does this have to do with computer science.

The hardware in your computer needs to be able to achieve complex boolean operations, but given that we've already discussed that complex boolean logic can be described by just a few operators, which in turn can be described by NAND, it might not surprise you that there chips that perform NAND operations, and those chips can be combined together to make progressively more complex hardware. From one NAND chip you can make a NOT chip, then you can make an AND chip and then OR from NOT and AND (the opposite order of our proofs). From those chips you can make more interesting chips like XOR, MUX, DMUX. And so on, until you're making very complex hardware like ALUs and CPUs. RAM is similar, but building it from the "ground up" requires another primitive piece of hardware called Data Flip Flop. I've learned all this from a class I've listed in the article sources. I've only made the fifteen most elementary chips from project 1 in the class. The theme of the course is that you can make a computer by making progressively complex hardware from simple hardware that performs simple boolean logic.

Wait Marc, are you actually making hardware? Not by hand. I wouldn't trust my self with a soldering iron. The classwork involves writing what's called hardware description language. "Making" a chip just involves listing the parts that it will require, and connecting the inputs and outputs of the chip you are "making" to the chips it requires, and connecting the chips it requires to each other in some cases. Here's an example of a XOR implementation. The rest of my implementations for project 1 are here.

Will learning this stuff help your software developing skills

I think the answer depends on how far you delve in this topic. If you get to the point where you know how CPU, and RAM work, then I think it could help you write code that's "easy" on your hardware. But to reiterate, I haven't made it to that point yet. So far from project one, here's a couple of benefits to taking the course from my perspective.

1. You get to practice recursion and learn it's applications in hardware development. How do you make an 8 Way Mux chip? The same way you made a 4 Way Mux chip.
2. Certain boolean operations that can seem bizarre to junior software developers become obvious after implementing a chip that does the same thing. 5 && 4 == 4? Duh.
3. You will have a newfound appreciation that you work with high-level programming languages when you spend an hour trying to figure out how to implement a chip which performs an operations which can be written in javascript like so (a,b,c) => c ? b : a. (That's the Mux chip by the way).

Show me some Minecraft already

Why Minecraft?

Minecraft is great for learning this topic because there are materials in the Minecraft world that allow you to construct, and thus visualize these logic gates, without having to know anything about the electrical engineering that is involved when making a chip in real life. Thank goodness because I struggled in college Physics classes and I hardly remember anything about current, voltage, diodes, resistors, transistors, etc., and frankly I'm not interested in that stuff.

If you check my sources, you will find a youtube video from which I learned to make a nand gate in Minecraft. I don't play Minecraft and I only bought it to facilitate learning this topic, but I wouldn't have been able to do it without the help of the user who made that video.

Nand gate - Minecraft implementation

The levers at the bottom represent the inputs. The bright red and dark red lines represent where the lines are powered and not powered, respectively. So because the lines near the inputs are dark we know the inputs represent 0, 0. The torches act like inverters, so because the lines feeding into them are off, the torches are on. Both torches must be on for the line between them to also be on. The output is a block which emits light when it receives power.

Xor gate - Minecraft implementation

Instead of working my up to Xor by doing all its dependencies first, I'll just show Xor and then explain the dependencies. Also note, because of the properties of some Minecraft materials available, a much simpler and smaller Xor chip is possible. You can find a much simpler implementation in the video in my sources, I'm mainly doing this to show how Nand chips can be combined to make more complex chips.

Wow that's monstrous. Let's break it down.

Nothing new so far has been highlighted.

I confess I cheated a bit by allowing my Or chip to not be made out of nand chips. Instead it just uses two lines connected to each other. Just know that (x OR y) can be expressed in just nand chips with ((x NAND x) NAND (y NAND y). I encourage you to try to imagine what those connections would look like in Minecraft, and to make a truth table to prove those functions are equal. Also, notice that our inputs feed both the nand chip to the lower right, and the or chip.

That AND chip is made from two NAND chips. The lower half is simply a NAND chip like we looked at before. The output from that NAND chip is fed twice to the upper NAND chip. When you take a signal and feed it to both inputs of a NAND chip, you've made a NOT chip. Thus, the highlighted section is NOT(Nand) which is AND.

Taken together, these parts make up this function (x OR y) AND (x NAND y). If you make a truth table from that function you will see that it is in fact Xor (eXclusive Or). In the photo both inputs are on so we have (1 OR 1) AND (1 NAND 1 ) = 1 AND 0 = 0. And the light at the end is off as expected.

I hope you have enjoyed my article and that this topic has peaked your curiosity as it has mine. I'm considering building a Minecraft device capable of binary addition in the coming weeks. For example, I'd like to show how a computer is capable of calculating that 101 + 11 = 1000 (5+3=8). So stay tuned!

Sources

1. https://www.coursera.org/learn/build-a-computer/
2. https://youtube.com/watch?v=dg72sN7Qb4Y