Thursday, November 21, 2013

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?

2 comments:

  1. X∧Y = -[X NAND X] NAND -[YNANDY]
    X∨Y =[X NOR X] NOR [YNORY]

    ReplyDelete
  2. You mixed up ∧ and ∨. ∧ means AND, and ∨ means OR. A good way to remember is that ∧ is like A without the crossbar.

    Did you mean to include the "-"? If not, your answer is correct.

    ReplyDelete