Boolean algebra a form of algebra developed by an English mathematician called George Boole (1815 - 1864) which is made up of:
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:
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.
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 | 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. |
|---|---|---|
| Associative | 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. |
| Distributive | 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. |
| Idempotence | 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.