Binary Addition

Before, I talked about how to use binary to represent a number using only two values. But what if you want to actually do something with those numbers? How do you add numbers using Boolean operations?

Well, let's start with a simple case: adding two one-bit numbers. We'll call them X and Y, and since they each only have one binary digit they can only have the values 0 or 1. So here are the cases we need to account for: 0+0=0, 0+1=1, 1+0=1, 1+1=10.

Notice the answer for that final case has two digits. A Boolean function can only return one value, so how can get that? By having two functions, one for each digit.

So, the function for the rightmost digit has to satisfy this truth table:

X	Y		Z0
0	0		0
0	1		1
1	0		1
1	1		0

What Boolean operation does that look like? XOR.

The function for the next digit will have to satisfy this truth table:

X	Y		Z1
0	0		0
0	1		0
1	0		0
1	1		1

That's the same as the AND operation.

I'm using the subscripts here to indicate which digit in the overall number. So our two bit answer Z has the individual bits Z₁Z₀, where Z₁ = X AND Y, and Z₀ = X XOR Y;

So, that's how you can add two one-bit numbers. But what if you want to add bigger numbers? Well, the way you add the second bits together is pretty much the same as the first bits, with one major difference: You need to account for the bit that got carried from the sum of the first bits. If that carry bit was 0, then the result of the next bit will be same as the first. But if it's one, then the result is increased by one. So, 0+0+1=1, 0+1+1=10, 1+0+1=10, 1+1+1=11.
So, now we have these two truth tables:

X1	Y1	C		Z1
0	0	0		0
0	1	0		1
1	0	0		1
1	1	0		0
0	0	1		1
0	1	1		0
1	0	1		0
1	1	1		1

X1	Y1	C		Z2
0	0	0		0
0	1	0		0
1	0	0		0
1	1	0		1
0	0	1		0
0	1	1		1
1	0	1		1
1	1	1		1

So, Z₁ = X₁ XOR Y₁ XOR C and Z₂ = (X₁ AND Y₁) OR (X₁ AND C) OR (Y₁ AND C). C, the carry bit, comes from the second bit of the result of the sum of the first two bits, that is C = X₀ AND Y₀.

Each subsequent bit works just like the second, with the second bit of the previous result being carried over. Generally, and Z_n = (X_n AND Y_n) OR (X_n AND C_n-1) OR (Y_n AND C_n-1), and C_n = X_n XOR Y_n XOR C_n-1.

Here's another challenge for you: How do you do subtraction in a similar manner?

De Morgan's Law and Duality

Before, I gave the challenge of replicating the boolean OR function using only NANDs (and replicating AND using only NORs). I'm going to show you the solution, using truth tables. A truth table is a table where you list out every possible combination of values of the inputs, and the corresponding value of the output. Here's a truth table showing the AND, OR, NAND and NOR functions.

X	Y		X∧Y	X∨Y	X NAND Y	X NOR Y
F	F		F	F	T	T
F	T		F	T	T	F
T	F		F	T	T	F
T	T		T	T	F	F

You can show that two functions are equivalent by showing that they have the same output as each other for every possible combination of inputs. Here's a simple example to show that ¬X = X NAND X.

X		¬X	X NAND X
F		T	T
T		F	F

If you're not sure what one of the outputs should be, plug in the input values and evaluate it. F NAND F = T, and T NAND T = F, which you can see from the first truth table.

So, here's the solution to the first part of the challenge: X∨Y = (X NAND X) NAND (Y NAND). Here's the truth table.

X	Y		X NAND X	Y NAND Y	(X NAND X) NAND (Y NAND Y)
F	F		F NAND F = T	F NAND F = T	T NAND T = F
F	T		F NAND F = T	T NAND T = F	T NAND F = T
T	F		T NAND T = F	F NAND F = T	F NAND T = T
T	T		T NAND T = F	T NAND T = F	F NAND F = T

Try to figure out the second part of the challenge (That is replicate the AND function using only NOR) using a truth table now. I'll wait.

.

.

.

.

.

.

.

.

The solution to the second part is X∧Y = (X NOR X) NOR (Y NOR Y). Interestingly, it's exactly the same as the first part, except with ∨ replaced by ∧ and NAND replaced by NOR. I'll talk about that more in a bit, but first notice that since (X NAND X) = ¬X, the solution to the first part can be rewritten as X∨Y = ¬X NAND ¬Y. Also, since (X NAND Y) = ¬(X∧Y), it can be further changed to X∨Y = ¬(¬X∧¬Y). The same way, the solution to the second part can be rewritten as X∧Y = ¬(¬X∨¬Y).

This is an example of De Morgan's Law, which says that ¬(X∧Y) = ¬X∨¬Y and ¬(X∨Y) = ¬X∧¬Y. De Morgan's Law is a very important thing to remember when doing Boolean algebra. It's a useful way of simplifying expressions, and it's vital for programmers to know.

De Morgan's Law also ties back into the other point I made. Notice that the two forms of De Morgan's Law are the same, except with ∧ and ∨ swapped? In fact, you can take any boolean expression, swap ∧ and ∨, and swap T and F, and the expression will mean the same thing.* For example, X∧T=X, swapped X∨F=X. Also, X∧F=F, swapped X∨T=T. This property is called duality.

Why does this happen? Keep in mind that the labels we use are arbitrary. It doesn't matter if we use T and F or 1 and 0, or if we use ∧ and ∨ or AND and OR. What matters is the relationships that hold between the symbols. And the way we've defined them, the relationships between T and ∧ are exactly the same as the relationships between F and ∨. That is, X AND Y is true if and only if both X and Y are true. X OR Y is false if and only if both X and Y are false. Those say exactly the same things, just with the names changed.

*If the expression contains XOR, or other functions besides ∧, ∨ and ¬, those need to be rewritten to use only ∧, ∨ and ¬. Or they can be swapped with their own dual, for example, the dual of XOR is XNOR. ¬ is it's own dual.

Boolean Algebra

You may have heard that computers only use the numbers 0 and 1. It's true. Everything computers do is done using electronic switches, and those switches can only be either on or off. (That's not strictly necessary. It's possible to make an electronic switch that has in-between states, but on/off is the simplest and easiest way to make a switch.) But how can computers calculate larger numbers or do all the cool things computers do, if they can only use 0 and 1? Well, one of the fundamental ideas behind how computers work is Boolean algebra.

Boolean algebra is a type of math that only uses two values. These two values are usually called true and false, or 1 and 0. There are three basic operations of Boolean algebra.

NOT X, also written as ¬X is simply the opposite of X. If X is true, ¬X is false. If X is false ¬X is true. Unsurprisingly, ¬¬X=X.

X AND Y, also written as X∧Y is true if both X and Y are true. Otherwise, it's false. The AND operation is also sometimes written as multiplication, because it works the same way. 0*0=0, 0*1=0 and 1*1=1. And just as with multiplication X*0=0 and X*1=X, no matter what X is, X∧F=F and X∧T=X, no matter what X is.

X OR Y, also written as X∨Y is true if X is true, Y is true or both are true. The OR function is sometimes written as addition. Similar to normal addition, 0+0=0, 0+1=1 and 1+1=... Well, there's no 2, so 1+1=1. This has the properties that X∨F=X, just like X+0=X, and X∨T=T, unlike normal addition.

You can put these operations together to get more complicated operations. For example X XOR Y, also written as X⊕Y, is true if X is true, or Y is true, but not both. It can be built out of the other operations like this (X∨Y)∧¬(X∧Y). Similarly, NAND, NOR and XNOR are made by putting a NOT in front of an AND, OR and XOR, respectively.

Although I said there are three basic operations of Boolean algebra, there really only needs to be one. You can make every single Boolean operation out of just NAND or just NOR. For example, ¬X = X NAND X. X∧Y = ¬(X NAND Y) = (X NAND Y) NAND (X NAND Y).

Here's a challenge for you: How can you make the OR operation, using or NAND, or complementarily, how can you make AND using only NOR?

Tautologies and Rhetoric

Today, I read PZ Myers's response to this argument against evolution. PZ does a fine job of taking it down, but there is one point I'd like to make, and this is something that shows up in many places. Egnor says that evolution is a tautology and is therefore false or fallacious. The problem is that a tautology is not a fallacy. In fact, by definition, a tautology is always true.

That's what a tautology is. Something that's always true, no matter what. For example, if x is true, then x is true. That statement is always true whether or not x is. It's just not interesting. There's no real claim or anything there. A tautology is only interesting when it gets combined with something else, which is what Darwin did with evolution by combining the tautology of "survivors survive" with variation and heritability.

And of course that doesn't mean that tautologies can't be used fallaciously. They're frequently used to sneak in a fallacy such as begging the question. But pointing out a tautology doesn't in and of itself show an argument to be fallacious.