× back Boolean algebra Axioms of boolean algebra Basic theorem Theorem prove Simplification of boolean expression using Algebraic method SOP and POS Normal form
Next Topic → ← Previous Topic

Boolean Algebra

A non-empty set B with two binary operations "+" and "." a unary operation " ' ", and two distinct element 0 and 1 is called a boolean algebra, denoted by (B, +, ., ', 0, 1) if and only if the following 4 properties are satisfied.

Axioms of boolean algebra-
If a,b,c ∈ B then

  1. Commutative laws
    • a + b = b + a
    • a . b = b . a
  2. Distributive laws
    • a + (b . c) = (a + b) . (a + c)
    • a . (b + c) = (a . b) + (a . c)
  3. Identity laws
    • a + 0 = a
    • a . 1 = a
  4. Complement laws
    • a + a' = 1
    • a . a' = 0

Basic Theorem

Let a, b and c ∈ B then

  1. Idempotent laws
    • a + a = a
    • a . a = a
  2. Boundedness laws
    • a + 1 = 1
    • a . 0 = 0
  3. Absorption laws
    • a + (a . b) = a
    • a . (a + b) = a
  4. Associative laws
    • (a + b) + c = a + (b + c)
    • (a . b) . c = a . (b . c)
  5. Uniqueness of complement
    • a + x = 1 and a . x = 0, then x = a'
  6. Involution laws
    • (a')' = a
  7. Complement laws
    • 0' = 1
    • 1' = 0
  8. De-Morgan's laws
    • (a + b)' = a' . b'
    • (a . b)' = a' + b'

Theorems prove

To prove the basic theorems we use the help of axioms.

Idemponent laws

  • Let a ∈ B, then
    • a + a = a
    • a . a = a
                       
                        proving a + a = a
                        R.H.S = a 
                        = a + 0 by Identity laws
                                 [ a + 0 = a]
                        = a + a.a' using complement law
                                     [a.a' = 0]
                        = (a + a) . (a + a') using distributive laws
                        = (a + a) . 1 using complement laws
                                        [a + a' = 1]
                        = (a + a)  using Identity laws
                                     [x . 1 = x, here x = (a + a)]
                        = L.H.S
                        Hence, a + a = a
                       
                   
                       
                        proving a.a = a
                        L.H.S = a.a 
                        = a.a + 0       by Identity laws
                        = a.a + a.a'    using Complement laws
                        = a.(a + a')    using distributive laws
                        = a.1           using Complement laws
                        = a             using Identity laws
                        = R.H.S 
                        Hence, a.a = a
                       
                   

Boundedness laws prove

  • Let a ∈ B, then
    • a + 1 = a
    • a.0 = 0
                       
                        proving a + 1 = 1
                        R.H.S = 1 
                        = a + a'                by Complement laws 
                        = a + a'.1              using Identity laws
                        = (a + a').(a + 1)      using Distributing laws
                        = 1.(a + 1)             using Complement laws 
                        = (a + 1).1             using commutative laws
                        = a + 1                 using Identity laws
                        = L.H.S 
                        Hence, a + 1 = 1
                       
                   
                       
                        proving a.0 = 0
                        R.H.S = 0 
                        = a.a'              by Complement laws
                        = a.(a' + 0)        using Identity laws
                        = (a.a') + (a.0)    using Distributive laws
                        = 0 + (a.0)         using Complement laws
                        = (a.0) + 0         using Commutative laws
                        = a.0               using Identity laws
                        = L.H.S 
                        Hence, a.0 = 0
                       
                   

Absorption laws prove

  • Let a, b ∈ B, then
    • a+(a.b) = a
    • a.(a+b) = a
                       
                        proving a+(a.b) = a 
                        L.H.S = a+(a.b)
                        = a.1 + (a.b) by Identity laws
                        = a.(1 + b)     using Distributive laws 
                        = a.(b + 1)     using Commutative laws
                        = a.1           using Boundedness laws
                        = a             using Identity laws
                        = R.H.S 
                        Hence, a+(a.b) = a
                       
                   
                       
                        proving a.(a+b) = a
                        L.H.S = a.(a+b)
                        = a + 0 . (a+b)     using Identity laws
                        = a+(0.b)           using Distributive laws
                        = a                 using Boundedness laws
                        = L.H.S 
                        Hence, a.(a+b) = a 
                       
                   

Associative law prove

  • a, b, & c ∈ B, then
    • (a+b)+c = a+(b+c)
    • (a.b).c = a.(b.c)
                       
                        proving (a+b)+c = a+(b+c)
                        R.H.S = a+(b+c)
                        = [a+(b+c)].1                              by Identity law
                        = [a+(b+c)].(c+c')                         by Complement law
                        = {[a+(b+c)].c} + {[a+(b+c)].c'}           by Distributive law 
                        = {c.[a+(b+c)]} + {c'.[a+(b+c)]}           by Commutative law
                        = [c.a+c.(b+c)] + [c'.a+c'(b+c)]           by Distributive law
                        = (c.a + c) + (c'.a+c'(b+c))               using Commutive law and Absorption law 
                        = c + (c'.a+c'(b+c))                       using Commutive law and Absorption law 
                        = c + (c'a + c'.b + c'.c)                  using Distributive law 
                        = c + (c'.a + c'.b + c.c')                 using Commutative law
                        = c + (c'.a + c'.b + 0)                    using Complement law
                        = c + (c'.a + c'.b)                        using Identity law
                        = c + (c'.(a+b))                           using Distributive law 
                        = (c+c').(c+(a+b))                         using Distributive law 
                        = 1.[c+(a+b)]                              using Complement law 
                        = [c+(a+b)].1                              using Commutative law 
                        = c + (a + b)                              using Identity law
                        = (a+b) + c                                using commutative law 
                        = L.H.S 
                        Hence (a+b)+c = a+(b+c)
                       
                   
                       
                        proving (a.b).c = a.(b.c)
                        R.H.S = a.(b.c)
                        = [a.(b.c)]+0                                    using Identity law 
                        = [a.(b.c)] + (c.c')                             by Complement law
                        = {[a.(b.c)]+c} . {[a.(b.c)]+c'}                 using Distributive law
                        = {c+[a.(b.c)]}.{c'+[a.(b.c)]}                   using Commutative law
                        = {(c+a).[c+(b.c)]}.{(c'+a).[c'a+(b.c)]}         using Distributing law
                        = {(c+a).c}.{(c'+a).[c'+(b.c)]}                  using Commutative & Absorption law 
                        = {c.(c+a)}.{(c'+a).[c'+(b.c)]}                  using Commutative law
                        = c . {(c'+a).[c'+(b.c)]}                        using Absorption law 
                        = c . {(c'+a).[(c'+b).(c'+c)]}                   using distributive law 
                        = c . {(c'+a).[(c'+b).1]}                        using Commutative and Complement laws
                        = c . {(c'+a).(c'+b)}                            using Identity law
                        = c . [c'+(a.b)]                                 using Distributive law
                        = (c.c')+[c.(a.b)]                               using Distributive law
                        = 0 + [c.(a.b)]                                  using Complement law
                        = c.(a.b)                                        using Identity law 
                        = (a.b).c                                        using Commutative law
                        = L.H.S 
                        Hence, (a.b).c = a.(b.c)
                       
                   

De-Morgan's laws prove

  • (a+b)' = a'.b'
  • (a.b)' = a'+b'
                       
                        proving (a+b)' = a'.b'
                        we know a + a' = 1 and a.a' = 0 
                        So, if we can prove that (a+b) + (a'.b') = 1 and (a+b).(a'.b') = 0 that means complement of (a+b) is a'.b'

                        First we will prove (a+b) + (a'.b') = 1
                        L.H.S = (a+b) + (a'.b')
                        = (a+b+a').(a+b+b')     using Distributive law
                        = (b+a+a').(a+b+b')     using Commutative law
                        = (b+1).(a+1)           using Complement law
                        = 1.1                   using Boundedness law
                        = 1                     using Idemponent law
                        = R.H.S 

                        Now we'll prove (a+b).(a'.b') = 0
                        L.H.S = (a+b).(a'.b')
                        = (a.a'.b') + (b.a'.b')    by Distributive law from right side
                        = (a.a'.b') + (b.b'.a)     using Commutative law
                        = (0.b') + (0.a)           [as a.a' = 0]
                        = 0 + 0                    [as a.0 = 0]
                        = 0                        using Idemponent law
                        = R.H.S 

                        Hence, as we have prove both the condition so we can say (a+b)' = a'.b'
                       
                   
                       
                        proving (a.b)' = a' + b'
                        we know a + a' = 1 and a.a' = 0 
                        So, if we can prove that (a.b) + (a' + b') = 1 and (a.b).(a' + b') = 0 that means complement of (a.b) is a'+b'

                        First we will prove (a.b) + (a'+b') = 1
                        L.H.S = (a.b) + (a'+b')
                        = (a'+b')+(a.b)         by Commutative law
                        = (a'+b'+a).(a'+b'+b)   by Distributive law 
                        = (a'+a+b').(a'+b'+b)   by Commutative law 
                        = (1+b').(a'+1)         by Complement law
                        = 1.1                   by Boundedness law
                        = 1                     by Idempodent law
                        = R.H.S 

                        Now we will prove (a.b).(a'+b') = 0
                        L.H.S = (a.b).(a'+b')
                        = (a.b.a') + (a.b.b')   by Distributive law
                        = (a.a'.b) + (a.b.b')   by Commutative law
                        = (0.b) + (a.0)         by Complement law 
                        = 0 + 0                 by Boundedness law 
                        = 0                     by Idempodent law
                        = R.H.S

                        Hence, as we have prove both the condition so we can say (a.b)' = a' + b'
                       
                   

Simplification of Boolean Expression using Algebraic method

1. (CB + CC).(A + B + C)

                               
                            (C.B + C.C).(A + B + C)
                            = (CB + C).(A + B + C)   [∵ C.C = C]
                            = C . (A + B + C)        [∵ CB + C = C]
                            = C.A + C.B + C.C        by distributive law
                            = C.A + C.B + C          [∵ C.C = C]
                            = C.A + C                [∵ C.B + C = C]
                            = C                      [∵ C.A + C = C]
                           
                       

xy + x'z + yz

                               
                            xy + x'z + yz
                            = xy + x'z + yz(x+x')       [∵ x+x' = 1]
                            = xy + x'z + xyz + x'yz
                            = xy + xyz + x'z + x'yz
                            = xy(1+z) + x'z(1+y)
                            = xy + x'z                  by Boundedness
                           
                       

A+B(A+B) + A(A'+B)

                       
                        A+B(A+B) + A(A'+B)
                        = A + AB + BB + AA' + AB
                        = A + AB + B + 0 + AB        [∵ BB = B & AA' = 0]
                        = A + AB + B                 [∵ X+X = X here X = AB]
                        = A + B                      [∵ A + AB = A]
                       
                   

SOP and POS

Normal Form

Minterm

  • A minterm of n variables is a product of n literals in which each variable appears exactly once in either true or complemented form, but not both.
                       
                        Minterm of the two variables x & y are :
                         xy    m3
                         x'y   m1
                         xy'   m2
                         x'y'  m0

                         For three terms x, y & z        [here x = 1 and x' = 0]

                         Product term           minterm representation
                           x'y'z'                        m0
                           x'y'z                         m1
                           x'y z'                        m2
                           x'y z                         m3
                           x y'z'                        m4
                           x y'z                         m5
                           x y z'                        m6
                           x y z                         m7
                       
                   

Maxterm

  • A maxterm of n variable is a sum of n literals in which each variable appears exactly once in either true or complimented form, but not both.
                       
                        Sum terms         Maxterm representation       [here x' = 1 and x = 0]
                        x  + y  + z            M0
                        x  + y  + z'           M1
                        x  + y' + z            M2
                        x  + y' + z'           M3
                        x' + y  + z            M4
                        x' + y  + z'           M5
                        x' + y' + z            M6
                        x' + y' + z'           M7
                       
                   

References ↓