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.