 |
| Boolean Algebra as an Algebraic Structure |
|
| Boolean Algebra is an algebraic structure defined by a set of elements B, together with two operations, + and . satisfying the following axioms (Hunington postulates) . |
| |
| Axiom 1: |
| |
(a) Closure with respect to +, that is if x, y  B, x + y  B. |
| |
(b) Closure with respect to, that is x, y  B  x . y  B. |
| |
| Axiom 2: |
| |
(a) There exists element 0 B such that: x + 0 = 0 + x = x, x  B. |
| |
| (0 is the identity for +) |
| |
(b) There exists element 1  B such that: x . 1 = 1 . x = x. |
| |
| (1 is the identity for ' . ') |
| |
For all x, y, z  B. |
| |
| Axiom 3: |
| |
| (a) Commutative w.r.t + : x + y = y + x |
| |
| (b) Commutative w.r.t . : x . y = y . x |
| |
| Axiom 4: |
| |
| (a) . is distributive over + : x . (y+z) = x . y + x . z |
| |
| (b) + is distributive over . : x + (y . z) = (x+y) . (x+z) |
| |
| Axiom 5: |
| |
" x  B, $ x'  B such that (a) x + x' = 1 and (b) x.x' = 0. |
| |
| x' is called the complement or negation of x. |
| |
| Axiom 6: |
| |
There exists at least two elements x and y such that x  y. |
| |
| Note: |
| |
| To prove a set to be a Boolean algebra, we have to prove all the above six properties to be true. |
| |
| Whenever we say B is a Boolean algebra, it should be understood that B is accompanied with two operations satisfying all the above six properties. |
| |
| Two-valued Boolean Algebra |
| |
| A two valued Boolean algebra is defined on a set of two elements B = {0, 1}, with rules for + and . as shown in the following tables. |
| |
 |
| |
 |
| |
 |
| |
| These rules are exactly the same as the AND, OR and NOT operations. |
| |
| Note: |
| |
 Closure is obvious from the tables, since the results of each operation is either 1 or 0. |
| |
|
Also observe from the tables: |
| |
(a) 0 + 0 = 0, 0 + 1 = 1 + 0 = 1  0 is the identity w.r.t +. |
| |
(b) 1.1 = 1, 1.0 = 0.1 = 0  1 is the identity w.r.t  . |
| |
For 0, 1 B, 0 + 1 = 1 + 0 |
| |
| 0 . 1 = 1 . 0 |
| |
 Commutative law is satisfied for both + and . |
| |
|
(a) |
| |
 |
| |
| Since the last two columns are identical x.(y + z) = (x.y) + (x.z) |
| |
| (b) Similarly it can be shown that |
| |
| x + (y.z) = (x + y) . (x + z) |
| |
|
Also from the complement table |
| |
 |
| |
 |
| |
 |
| |
| x . x' = 0 |
| |
| (a) x + x' = 1. since 0 + 0' = 0 + 1 = 1, 1 + 1' = 1 + 0 = 1 |
| |
| (b) x.x' = 0, since 0.0' = 0.1 = 0, 1.1' = 1.0 = 0 |
| |
 |
| |
| Thus, we have a two valued Boolean algebra having a set of two elements 1 and 0. |
| |
