Continuing from this post, where I wrote about playing Rimworld a bit. My goal was to create a logic circuit of some kind within the game, which I will describe in a follow-up post.

Logic Gates

Logic gates are like, how a computer thinks? They work with channels, or wires, which typically have one of two states at any time. The wire can be “on” or “off.” These are often represented as the familiar 1s and 0s. In an electronic circuit, a wire is on if it has a voltage above a threshold, and off if it’s below.

A gate looks at two of these wires’ states, the inputs, and applies a state on an output wire. The output state depends on the specific type of logic gate and the two input states.

AND gates accept two inputs, both either ON or OFF, and spit out a single output. ANDs only output ON if both inputs are ON. The rectangle isn’t the normal symbol for this kind of gate, but who cares right now.

An And gate outputs “on” if both of the inputs are on, and “off” otherwise. An Or gate outputs “off” if both of the inputs are off, and on otherwise. We can summarize all of the possible responses by one of these gates in a table.

$\begin{array}{cc} \text{And} & \text{Or} \\ \begin{tabular}{|c|c|c|}\hline \text{In 1}& \text{In 2} & \text{Out} \\ \hline \hline \text{off} & \text{off} & \text{off} \\ \hline \text{off} & \text{on} & \text{off} \\ \hline \text{on} & \text{off} & \text{off} \\ \hline \text{on} & \text{on} & \text{on} \\ \hline \end{tabular} & \begin{tabular}{|c|c|c|}\hline \text{In 1}& \text{In 2} & \text{Out} \\ \hline \hline \text{off} & \text{off} & \text{off} \\ \hline \text{off} & \text{on} & \text{off} \\ \hline \text{on} & \text{off} & \text{off} \\ \hline \text{on} & \text{on} & \text{on} \\ \hline \end{tabular} \end{array}$

We can shorten this up by calling the inputs A and B, and the outputs the name of the gates. I’ll also tack on the outputs for a third gate, XOR, the exclusive OR.

$\begin{tabular}{|c|c||c|c|c|}\hline \text{A} & \text{B} & \text{AND} & \text{OR} & \text{XOR} \\ \hline\hline 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 0 \\ \hline \end{tabular}$

XOR is “output 1 if A or B is 1, but not both.” These gates can be chained; the output of one can be sent into another. We can also split the output of any gate so it can be an input for multiple gates. Linking these together allows us to take multiple input wires and interpret them. You can then just shove these all into a black box and not care about what it’s made of. For both our sakes take a look at Wikipedia page. They can be used to add binary digits.

A Half Adder. This thing uses an XOR and an AND gate to add two single bit numbers. The result is two bits. The S sum is the 1s place and the C carry is the 2s place of the 2 bit sum. So A + B = CS, 0 + 0 = 00, 0 + 1 = 01, and 1+1 = 10. From the Adder Wikipedia page.

So that’s cool. So here’s the thing. With only ANDs, ORs, or XORs, there’s no way you can start with only 0s as inputs and end up with any 1s. This leads us to the idea of functional completeness: we want to be able to chain together these gates to create any output given any collection of inputs. You do not have functional completeness with those three only. The best option to add on at that point is a NOT — a gate that accepts only one input, and inverts it. It turns a 1 input into a 0 output, or a 0 into a 1. With a bucket of NOTs available, as well as only one of those three, you can make whatever you want.

There are two “universal” gates — ones that on their own are sufficient to make any kind of circuit. These are NAND and NOR, the negation of AND and OR.

$\begin{tabular}{|c|c||c|c|}\hline \text{A} & \text{B} & \text{NAND} & \text{NOR} \\ \hline\hline 0 & 0 & 1 & 1 \\ \hline 1 & 0 & 1& 0 \\ \hline 0 & 1 & 1 & 0 \\ \hline 1 & 1 & 0 & 0 \\ \hline \end{tabular}$