Maths in a minute: Boolean algebra

Every time you use a computer you are relying on Boolean logic: a system of logic established long before computers were around, named after the English mathematician George Boole (1815 - 1864). In Boolean logic statements can either be true or false (e.g. at the moment "I want a cup of tea" is false, but "I want a piece of cake" is always true), and you can string these together using the words AND, OR and NOT. To establish if these compound statements are true of false, you might create what's called a truth table, listing all the possible values the basic statements can take, and then all the corresponding values the compound statement can take. (You can find out more in Maths in a minute: Truth tables.)

Truth tables are useful for simple logic statements, but quickly become tiresome and error prone for more complicated statements. Boole came to the rescue by ingeniously recognising that binary logical operations behaved in a way that's strikingly similar to our normal arithmetic operations, with a few twists.

In this new kind of arithmetic (called Boolean algebra) the variables are logical statements (loosely speaking, sentences that are either true or false). As these can only take two values we can write 0 for a statement we know is false and 1 for a statement we know is true. Then we can rewrite OR as a kind of addition using only 0s and 1s:

0 + 0 = 0 (since "false OR false" is false)
1 + 0 = 0 + 1 = 1 (since "true OR false" and "false OR true" are both true)
1 + 1 = 1 (since "true OR true" is true).

We can rewrite AND as a kind of multiplication:

0 x 1 = 1 x 0 = 0 (since "false AND true" and "true AND false" are both false)
0 x 0 = 0 (since "false AND false" is false)
1 x 1 = 1 (since "true AND true" is true).

As the variables can only have the values of 0 and 1, we can define the NOT operation as the complement, taking a number to the opposite of its value:

If A = 1, then NOT A = 0
If A = 0, then NOT A = 1
A + NOT A = 1 (since "true OR false" is true)
A x NOT A = 0 (since "true AND false" is false).

Our new version of these operations is similar in many ways to our more familiar notions of addition and multiplication but there are a few key differences. Parts of equations can conveniently disappear in Boolean algebra, which can be very handy. For example, the variable B in

A + A x B

is irrelevant, no matter what value B has or what logical statement it represents. This is because if A is true (or equivalently A=1) then A OR (A AND B) is true no matter whether the statement B is true or false. And if A is false (that is, A=0) then (A AND B) is false no matter the value of B, and so A OR (A AND B) is false. So Boolean algebra provides us with a disappearing act: the expression A + A x B is equal to a simple little A:

A + A x B = A.

Also, in Boolean algebra there is a kind of reverse duality between addition and multiplication:

(A + B)' = A' x B' and (A x B)' = A' + B'.

These two equalities are known as De Morgan's Laws, after the British mathematician Augustus de Morgan (1806 - 1871). (You can convince yourself that they are true using the equivalent truth tables.)

These are just two of the tricks Boolean algebra has up its sleeves for simplifying complicated logical statements – thank you George!