Boolean math

Introduction

This page covers some of the most interesting things we know about booleans and how they behave.

Boolean Numbers

There are only two numbers in the Boolean universe: 0 (false) and 1 (true).

Math Operations

NOT (complement)

The NOT operator is a unary operator. It behaves as:

A	NOT A
1	0
0	1

NOT changes the number to the other number. It is like the negative operator in a way.

AND (product)

The AND operator is a binary operator. It behaves as follows:

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

It is true only when both inputs are true.

It is like the product in normal arithmetic because:

0 × 0 = 0
0 × 1 = 0
1 × 0 = 0
1 × 1 = 1

OR (sum)

The OR operator is a binary operator. It behaves as follows:

A	B	A OR B
0	0	0
0	0	1
1	0	1
1	1	1

It is true if either or both its inputs are true.

It is like adding, in a way, except that 1 + 1 = 1.

XOR

The XOR operator is a binary operator. It behaves as follows:

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	0

It is true if either its inputs are true, but not both. In other words, it is true only when the inputs are different.

It is expressed simply as:

A XOR B
  = (A AND (NOT B)) OR ((NOT A) AND B)

NOR, NAND

A NOR B is defined as NOT (A OR B). A NAND B is defined as NOT (A AND B). These two operations are sufficient to describe all of the above operations. In hardware (the circuits in your microchips), either NOR or NAND is used to describe all that happens inside.

Identities

The following identities exist:

1. A AND 1 = A
2. A OR 0 = A
3. A XOR 0 = A
4. A XOR 1 = NOT A

Boundings

1. A AND 0 = 0
2. A OR 1 = 1
3. A XOR 1 = NOT A

Complements

1. A AND (NOT A) = 0
2. A OR (NOT A) = 1
3. NOT (NOT A) = A

Also, note the following:

1. If A AND B = 0, and A OR B = 1, then A = NOT B.

Idempotence

1. A AND A = A
2. A OR A = A
3. A XOR A = 0

Commutation

All of the binary operators above are commutative. That is, you can switch A or B and the result doesn't change.

1. A AND B = B AND A
2. A OR B = B OR A
3. A XOR B = B XOR A

Association

The order of applying operations of the same kind don't matter for some of the operators.

1. (A OR B) OR C = A OR (B OR C)
2. (A AND B) AND C = A AND (B AND C)

Distribution

1. A AND (B OR C) = (A AND B) OR (A AND C)
2. A OR (B AND C) = (A OR B) AND (A OR C)

Absorption

These rules come in handy quite often. It is best to look for them where you can to simplify your code.

1. A AND (A OR B) = A
2. A OR (A AND B) = A

DeMorgan's Law

I use this about once or twice a week while programming.

1. A AND B = NOT ((NOT A) OR (NOT B))
2. A OR B = NOT ((NOT A) AND (NOT B))

These usually show up as:

1. (NOT A) AND (NOT B) = NOT (A OR B)
2. (NOT A) OR (NOT B) = NOT (A AND B)

Or even:

1. (NOT A) AND B = NOT (A AND (NOT B))
2. (NOT A) OR B = NOT (A AND (NOT B))

Short-Circuiting

When you are calculating a long equation, you can work left to write and stop when:

1. Something is 0 for a series of ANDs => 0.
2. Something is 1 for a series of ORs => 1.

Most programming languages obey this short-circuiting, allowing you to branch on certain values without using an if statement. Some languages may optimize the series of ANDs or ORs to try out the easiest ones first and short-circuit there, so make sure that your language behaves the way you expect it to.

Applications to Logic

Almost every language uses the above operators to help you describe when to branch or not to branch for if, for, and while statements.

See Also

• First-order logic
• http://mathworld.wolfram.com/BooleanAlgebra.html
• http://www.rwc.uc.edu/koehler/comath/24.html