Tuesday, October 9, 2012

Boolean Algebra - Laws and Theorems



POSTULATES AND THEOREMS

Postulate 1  :- Definition

Boolean Algebra is a closed algebraic system containing a set of two or more elements and three operator., +, ’; alternatively for every A and B in set S, A . B belongs to S and A’ belongs to S(+ is OR operator,   .  is AND and   ’  is NOT operator)

Postulate 2  :-Law of substitution.

In the given closed algebraic system two expressions are said to be equal ( = ) if one can be replaced by the another.

Postulate 3  :- Existence of  1 and 0.

Three exist unique elements 1 and 0 in a set S such that for every A in S.
(i)                 A + 0 = A
A
0
A + 0
1
0
1
0
0
0
(ii)               A . 1 = A
A
1
A . 1 = A
1
1
1
0
1
0

Postulate 4  :- Commutativity.

For every A and B in S
(i)                 A + B = B + A
A
B
A + B

B
A
B + A
0
0
0

0
0
0
1
0
1

1
0
1
0
1
1

0
1
1
1
1
1

1
1
1

(ii)               A . B = B . A
A
B
A . B

B
A
B . A
0
0
0

0
0
0
1
0
0

1
0
0
0
1
0

0
1
0
1
1
1

1
1
1

Postulate 5:-   Distribution Law

For every A and B in S
A . (B + C) = (A . B) + (A . C)
A + (B . C) = (A + B) . (A + C)
A

B

C
B + C
A.(B+C)

A.B
A.C
(A.B)+(A.C)
0
0
0
0
0

0
0
0
0
0
1
1
0

0
0
0
0
1
0
1
0

0
0
0
1
0
0
0
0

0
0
0
0
1
1
1
0

0
0
0
1
0
1
1
1

0
1
1
1
1
0
1
1

1
0
1
1
1
1
1
1

1
1
1
Similarly second one is proved.

Postulate 6:-   Associativity

For every A and B in S
A + (B + C) = (A + B) + C
A . (B . C) = (A . B) . C
A
B
C
B + C
A+(B+C)

A+B
C
(A+B)+C
0
0
0
0
0

0
0
0
0
0
1
1
1

0
1
1
0
1
0
1
1

1
0
1
1
0
0
0
1

1
0
1
0
1
1
1
1

1
1
1
1
0
1
1
1

1
1
1
1
1
0
1
1

1
0
1
1
1
1
1
1

1
1
1
Similarly second one is proved.

Postulate 7  :- Existence of the complement

For every A in S there exists a unique element called ‘A’ (complement of A) such that
(i)         A + A’ = 1                               (ii)     A . A’ = 0
A
A’
A + A’
1
0
1
0
1
1
A
A’
A . A’
1
0
0
0
1
0


 

Principle of Duality:-

According to the principle of Duality, for every valid expression in Boolean Algebra there exists an equally valid dual expression. The formation of dual expression is carried out by the following three steps.
STEP I:-          Replace all 1’s by 0’s and 0’s by 1’s.
STEP II:-         Replace all AND’s by OR’s and OR’s by AND’s
STEP III:-       Leave NOT’s unchanged.

Consider following example   A + (B . C) = (A + B) . (A + C)
Its dual expression is   A . (B + C) = (A . B) + (A . C)

THEOREMS

Theorem 1      The Boolean Algebra is Idempotent.

(i)         A + A = A
            L.H.S. = (A + A) . 1                                                   ( since A . 1 = A )
                        = (A + A) . (A + A’)                                       ( since A + A’ = 1 )
                        = A + A . A’                                                   ( Distributive Law )
                        = A + 0                                                            ( since A . A’ = 0 )
                        = A                                                                  ( since A + 0 =A )

(ii)        A . A = A
            L.H.S.   = (A . A) + 0                                                 ( since A + 0 =A )
                        = (A . A) + (A . A’)                                        ( since A . A’ = 0 )
                        = A . (A + A’)                                                 ( Distributive Law )
                        = A . 1                                                             ( since A + A’ = 1 )
                        = A                                                                  ( since A . 1 = A )


Theorem 2     

(i)                  A + 1 = 1
             L.H.S. = A + 1
                                    = ( A + 1 ) . 1                                                  ( since A . 1 = A )
                                    = ( A+ 1 ) . ( A + A’ )                                     ( since A + A’ = 1 )
                                    = A + ( A’ . 1 )                                                ( Distributive Law )
                                    = A + A’                                                         ( since A . 1 = A )s
                                    = 1  =  R.H.S.                                                  ( since A + A’ = 1 )
(ii)                A . 0 = 0
L.H.S. = A. 0
                  = A . (A . A’)                                                  ( since A . A’ = 0 )
                  = (A + 0) . (A . A’)                                         (since A + 0 = A)
                  = (A + 0) . (A + 0) . A’                                   (since A + 0 = A)
                        = (A + 0) . A                                                   (since A + A = A)
                        = A . A’                                                           (since A + 0 = A or Distributive Law)
                        = 0 = R.H.S.                                                    (since A . A’ = 0)

Theorem 3: The Boolean Algebra is absorptive

(i)         A + (A . B) = A
            L.H.S. = A + (A . B)
                        = A . (1 + B)                                                   (Taking A as common)
                        = A . 1                                                             (since A + 1)
                        = A = R.H.S.
(ii)        A . (A + B) = A
            L.H.S. = A . (A + B)
                        = A . A + A . B                                               (since A . (B + C) = A . B + A . C)
                        = A + A . B                                                     (since A . A = A)
                        = A . (1 + B)                                                   ( Taking A as common)
                        = A . 1                                                             (since A + 1 = A)
                        = A = R.H.S.

Theorem 4: This theorem allows the elimination of an extra element from a Boolean expression.

(i)         A + A’ . B = A + B
            L.H.S. = A + A’ . B
                        = (A + A’) . (A + B)                                       (since A + (B . C) = (A + B) . (A + C))
                        = 1 . (A + B)                                                   (since A + A’ = 1)
                        = A + B = R.H.S.
(ii)        A . (A’ + B) = A . B)
            L.H.S. = (A . A’) + (A . B)                                         (since A . (B + C) = (A + B) . (A + C))
                        = 0 + (A . B)                                                   (since A . A’ = 0)
                        = A . B = R.H.S.                                             (since A + 0 = A)

Theorem 5: The Boolean Algebra is involuted

                        ( A’)’ = A
            A                                 A’                                (A’)’
            0                                  1                                  0
            1                                  0                                  1

 

Theorem 6: De Morgan’s theorem

De Morgan’s was a great logician and mathematician. He gave two theorems that deal with process of negating AND and OR  expressions of multiply terms. The first of these states “Complement of sum equals the product of the complements” and the second states “Complement of the products equals the sum of the complements.
(i)                 (A + B)’ = A’ . B’
(ii)               (A . B)’ = A’ + B’
(i)         (A + B)’ = A’ . B’  
            Adding both side by A + B
            (A + B’) + (A + B)      = A’ . B’ + (A + B)
                        1                      = A’ . B’ + (A + B)                 (since A + A’ = 1)
            R.H.S. = A’ . B’ + (A + B)
                        = (A’ + A) . (B’ + A) + B                               since A + (B . C) = (A + B) . (A – C)
                        = 1 . (B’ + A) + B                                           (since A + A’ = 1)
                        = A + B’ + B                                                   (since A . 1 = A)
                        = A + 1                                                            (since A + A’ = 1)
                        = 1 = L.H.S.                                                    (since A + 1 = A)

(ii)        Multiplying both sides by A + B
            (A + B)’ . (A + B) = (A’ . B’) . (A + B)
            0                                  = (A’ . B’) . (A + B)                (since A . A = 0)
            R.H.S.                         = (A’ . B’) . (A + B)
                                                = A’ . B’ . A + A’ . B’ . B      (opening the brackets)
                                                = 0 + 0                                     (since A . A’ = 0)
                                                = 0 = L.H.S.
Similarly we can prove the second part of the theorem.

Theorem 7: Consensus theorem

(i)                 A . B + A’ . C + B . C = A . B + A’ . C
(ii)               (A + B) . (A’ + C) . (B + C) = (A + B) . (A’ + C)

(i)         A . B + A’ . C + B . C = A . B + A’ . C
            L.H.S. = A . B + A’ . C + B . C
            {Multiply the quantity to be deleted by 1}
            = A . B + A’ . C + B . C . (A + A’)                            (since A + A’ = 1)
            = A . B + A’ . C + B . C . A + B . C . A’                   (opening the brackets)
            = A . B + A.B.C + A’.C + A’ . B. C.                         (rearranging the terms)
            = A.B.(1+C) + A’.C.(1+B)                                         (taking common)
            = A.B.1 + A’.C.1                                                        (since A+1 = A)
            = A.B + A’.C = RHS                                                  (since A.1=A)

(ii)        L.H.S = (A + B) . (A’ + C) . (B + C)
= (A.A’ + A.C+B.A’.B’+C) . (B+C)                          (opening brackets)
= (0+A.C+B.A’+B.C).(B+C)                                     (since A.A’ = 0)
= A.B.C + B.A’.B + B.C.B + A.C.C + B.A’.C + B.C.C       (opening brackets)
= A.B.C + A’.B + B.C + A.C + A’.B.C + B.C          (since A.A = A)
= A.B.C +A’.B + A.C + B.C                                     (rearranging the terms)
= A.C.(B+1) + A’.B + B.C                                         (taking common)
= A.C + A’.B+B.C                                                     (since A+1 = 1)
= A.C+A’.B+B.C + 0                                                 (adding 0)
= A.C+A’.B+B.C+A.A’                                             (substituting 0 as A.A’)
= A.C+B.C+A’.B+A.A’                                             (rearranging the terms)
= C.(A+B) + A’.(A+B)                                                           (taking common)
= (A’+C).(A+B) = R.H.S.

 

Theorem 8:

(i)                 A.B + A.B’ = A
(ii)               (A+B).(A+B’) = A
(i)         L.H.S = A.B + A.B’
            = A.(B+B’)                                                                 (taking common)
            = A.1                                                                           (since A+A’ = 1)
            = A = R.H.S.                                                               (since A.1 = A)

(ii)        L.H.S. = (A+B).(A+B’)
            = A+(B.B’)                                                                 (since A+(B.B’) = (A+B).(A+B’))
            = A + 0                                                                        since A.A’ = 0)
            = A = R.H.S.                                                               (since A+0 = 0)

Theorem 9:

(i)                 A.B + A.B’.C = A.B + A.C
(ii)               (A+B).(A+B’+C) = (A+B).(A+C)
(i)         L.H.S = A.B + A.B’.C
            = A.(B+B’.C)                                                              (taking common)
            = A.(B+B’).(B+C)                                                      (distributive law)
            = A.(B+C)                                                                   (since A+A’ = 1)
            = A.B +A.C = R.H.S.                                                 (distributive law)

(ii)        L.H.S. = (A+B).(A+B’+C)    
            = A.(A + B’+C) +B.(A+B’+C)                                  (since A+(B.C) = (A+B).(A+C))
            = A.A + A.B’ + A.C +A.B +B.B’+B.C                    ( Opening brackets)
            = A + A.B’ + A.C + A.B + 0 + B.C                                       (since A.A’ = 0, A.A = A)
            = A.(1+B’) + A.C + A.B + B.C                                 ( taking A as common)
= A + A.C + A.B + B.C                                             ( since A+1=1)
            = A.(1+C+B) + B.C
            = A.1 + B.C
           = A. = R.H.S.                                                              (since A+0 = 0)

Theorem 10:

(i)                 A.B + A’.C = (A + C).(A’ + B)
(ii)               (A + B).(A’ + C) = A.C + A’.B

(i)         L.H.S. = A.B + A’.C
            = A.B + A’.C.1                                               (since anything multiplied by 1 remains same)
            = A.B + A’.C.(B + B’)                                               (since A + A’ = 1)
            = A.B + A’.B.C + A’.B’.C                                         (opening the brackets)
            = B.(A + A’.C) + A’.B’.C                                          (taking B as common)
            = B.((A + A’).(A + C)) + A’.B’.C                              (since A + (B.C) = (A + B).(A + C))
            = B.(A + C) + A’.B’.C                                               (since A + A’ = 1)
            = A.B + B.C + A’.B’.C                                              (opening the brackets)
            = A.B + C.(B + A’.B’)                                               (taking C as common)
            = A.B + C.((B + A’).(B + B’))                                   (since A + (B.C) = (A + B).(A + C))
            = A.B + C.(B + A’)                                                    (since A + A’ = 1)
            = A.B + B.C + A’.C                                                   (opening the brackets)
            = A.B + B.C + A’.C + A.A’                                       (adding A.A’ which equals to 0)
            = A.B + A.A’ + B.C + A’.C                                       (rearranging the terms)
            = A.(B + A’) + C.(B + A’)                                         (taking common)
            = (A + C).(A’ + B) = R.H.S.

(ii)        L.H.S. = (A + B) . (A’ + C)
            = A.A’ + A.C + A’.B + B.C                                       (opening the brackets)
            = 0  + A.C + A’.B + B.C                                            (since A.A’ = 0)
            = A.C + A’.B + B.C.1                                                (since anything multiplied by 1 remains same)
            = A.C + A’.B + B.C.(A + A’)                                                (since A + A’ = 1)
            = A.C + A’.B + A.B.C + A’.B.C                               (opening the brackets)
            = A.C + A.B.C + A’B + A’.B.C                                (rearranging the terms)
            = A.C.(1 + B) + A’.B.(1 + C)                                     (taking common)
            = A.C + A’.B = R.H.S.                                               (since A + 1 = 1)