Boolean Algebra | Truth Tables | Expressions from Truth Tables | Universal Functions | Function Reduction | Functions Classified

Invented by George Boole, Boolean Algebra deals with situations where there are only two possibilities. These possibilities can be named anything as long as they are opposites. For instance, true and false, yes and no, or 0 and 1¹. These situations arrive frequently in digital systems such as computers, and thus Boolean Algebra has become vital to the day-to-day operations of the entire civilized world, whether those living there realise it or not. Boolean Algebra is also used by people as a decision making process, though you probably don't think of it as that.

Overview of Boolean Operations

There are several Boolean operations:

AND

The Boolean AND operator returns true if all operands are true, and false if any are false. AND is equivalent to binary multiplication.

• 0 AND 0 = 0
• 1 AND 0 = 0
• 1 AND 1 = 1

OR

Boolean OR is true if any operands are true, and false only if all operands are false. OR is equivalent to binary addition, with the both true case resulting in true, instead of in false with a true carried over.

• 0 OR 0 = 0
• 1 OR 0 = 1
• 1 OR 1 = 1

NOT

NOT is a unary operator, meaning it acts on a single Boolean value instead of on two. Operators which act on two values are Binary operators, which may seem confusing.

NOT changes a Boolean value to its opposite.

• NOT 1 = 0
• NOT 0 = 1

NOR

NOR is defined as NOT OR, and its action is just what it suggests: it returns true if the operands are both false, that is, if neither operand 1 NOR operand 2 are true, and returns false if either are true.

• 0 NOR 0 = 1
• 1 NOR 0 = 0
• 1 NOR 1 = 0

Equivalent to A NOR B are NOT (A OR B) and (NOT A) AND (NOT B). These are useful in systems where an explicit NOR is not available.

NAND

NAND means NOT AND, and returns false if both operands are true, and true if any are false.

• 0 NAND 0 = 1
• 1 NAND 0 = 1
• 1 NAND 1 = 0

A NAND B is the same as NOT (A AND B) and (NOT A) OR (NOT B). As with NOR, these are useful when a specific NAND is not available, but as will be discussed later, this is rarely the case.

XOR

XOR is short for Exclusive-OR, and is like a merger of AND and NOR. XOR returns true, essentially, if the two operands are different. That is, if one or the other is true, it returns true, but not if both are true. It is OR with an Exclusion; thus, Exclusive OR.

• 0 XOR 0 = 0
• 1 XOR 0 = 1
• 1 XOR 1 = 0

XOR is like binary addition, with the carried bit ignored.

XNOR

XNOR means NOT XOR, and it returns true if both operands are the same, and false otherwise. (You may have guessed this from the name by now.)

• 0 XNOR 0 = 1
• 1 XNOR 0 = 0
• 1 XNOR 1 = 1

Notation

Using the words for the operations is excessively verbose, so shorter notation is available. OR is +, AND is a dot, NOT is a bar over a value, NOR is the OR expression with a bar over the whole thing, NAND is the AND expression with a similar bar, and XOR and XNOR are like OR and NOR, but with the + in a small circle.

Since computer programming languages also use Boolean logic for many operations, they have their own notation. The symbols used by C and C++ are &(AND), |(OR), ~(NOT)², and ^(XOR). Since these characters are easiest to type, they will be used here.

Boolean Tricks

NAND is the most useful operator, because any other operation can be done with some number of NANDs. While not always useful, in small circuitry, a single NAND IC can perform the functions of a number of other ICs, thus saving in cost and size. For this section only, lower case 'n' will be the operator for NAND, so it is perfectly clear where its use is.

• NOT A = AnA
• A AND B = ~(AnB) = (AnB)n(AnB)³
• A OR B = (~A)n(~B) = (AnA)n(BnB)
• A NOR B = (AnB)n(AnB)
• A XOR B = (An(AnB))n(Bn(AnB))
• A XNOR B = (An(AnB))n(Bn(AnB))

XOR is a useful operator because (A^B)^B = A. This can be used on long strings of bits to obscure them to anyone without the correct key. This is decidedly weak encryption, but it is a clever trick which has other applications in computer programming.

---

¹ Technically the opposite of zero is non-zero. In single digit systems, 1 is the only non-zero value, but when multiple binary digits are taken as a single value, the whole is considered non-zero if any value is one, true, or whatever.
² These are the symbols for bitwise operations, which act on each bit respectively, instead of on the sum of the bits. Logical operators acting on all the bits are: &&(AND), ||(OR), !(NOT), and ^^(XOR). These use 0 and non-0 as their logical values, instead of 0 and 1.
³ You only need two leads in the IC for this, since you can connect the output for the AnB operation to both inputs of another NAND gate on the chip. A similar trick can be used in any case where two identical Boolean operations are performed at about the same time.