 # Edward Slipszenko

## Programmer

### Boolean Algebra

November 11th, 2010

Boolean algebra a form of algebra developed by an English mathematician called George Boole (1815 - 1864) which is made up of:

• Elements, which are variables or constants with a value of 1 or 0,
• Three functions, which are:
• The logical OR represented by a "+" symbol (e.g. A + B),
• The logical AND represented by a "·" symbol (e.g. A · B),
• The act of inversion which is normally denoted by an exclamation preceding the variable or constant. The compliment of 0 (i.e. !0) is 1 and vice verse.

The priority of the AND operator is higher than that of an OR. So the expression A = X + Y · !Z means A = X + (Y · !Z).

Other denotations used are:

• A · B = AB = A & B
• A + B = A v B
• !A = NOT(A) = A* = /A

Boole probably used the dot and plus symbols due to his background in probability theory, where the rolling a 1 OR 2 = 1/6 + 1/6, and the probability of rolling a 1 AND 2 = 1/6 X 1/6.

The arithmetic operations of subtraction and division do not exist in Boolean algebra. For example, the Boolean expression A + B = A + C cannot be arranged in the form (A + B) - A = (A + C) - A, which would lead to B = C. This can be proved by considering the case:

```A = 1, B = 1 and C = 0
A + B = 1 + 1 = 1
A + C = 1 + 0 = 1
```

Meaning that the equation is valid even though B is not equal to C.

## Axioms and Laws

An axiom or postulate is a rule that must be taken for granted; the axioms of Boolean algebra define the framework of Boolean algebra from which everything else can be derived.

The first axiom is called the closure property, which states that Boolean operations on Boolean variables or constants always yield Boolen results. If variables A and B belong to a set of Boolean elements, the operations A · B, A + B and !A and !B belong to the set of Boolean elements.

Boolean variables obey the same commutative, distributive and associative laws as the variables of conventional algebra. These laws are taken for granted when we carry out everyday arithmetic. For example, the commutative law states that 4 X 7 = 7 X 4.

Commutative Associative ```A + B = B + A A · B = B · A``` The AND and OR operators are commutative: it does not matter what order the variables are in if all the operators are the same. ```A · (B · C) = (A · B) · C A + (B + C) = (A + B) + C``` The AND and OR operators are associative: so the sub-expressions can be evaluated in any order. ```A · (B · C) = A · B + A · C A + (B + C) = A + B + A + C``` The AND operator behaves in the same way as multiplication and the OR operator behaves in the same way as addition. ```A · A = A A + A = A``` If only the AND and OR operators are used and there is just one variable (and no constants or literals) the result will always have the same result as that variable.

All of these laws have two expressions where all the AND's, OR's, and 1's and 0's are swapped round, this is known as duality

These Boolean operators have the following effect on constants:

 NOT AND OR `!0 = 1` `0 · 0 = 0` `0 + 0 = 0` `!1 = 0` `0 · 1 = 0` `0 + 1 = 1` `1 · 0 = 0` `1 + 0 = 1` `1 · 1 = 1` `1 + 1 = 1`

This table can be extended to define the relationship between a Boolean operator, a variable and a literal.

 NOT AND OR `!!X = X` `0 · X = 0` `0 + X = X` ` ` `1 · X = X` `1 + X = 1` `X · X = X` `X + X = X` `X · !X = 0` `x + !X = 1`

This can be proven by substituting X with all the values it could possibly have. For example, for 0 · X:

```0 · X = 0
0 · 1 = 0     For X = 1
0 · 0 = 0     For X = 0```

Both of these statments are correct as an AND operator will only ever produce a 1 if all inputs are equal to 1. When a statement is proved in this way, by examining all the possibilities of combinations of values of all variables within that statement, it is called proof by perfect induction.

Another example could be 1 + X:

```1 + X = 1
1 + 1 = 1     For X = 1
1 + 0 = 1     For X = 0```

These two statements prove 1 + X = 1 by perfect induction.