Wednesday, 8 February 2012

Fundamental Theorems of Boolean Algebra


Theorem 1 (Idempotency):
a+a=a(theorem)
a.a=a (dual)
Proof:
a+a = (a+a)1
        = (a+a)(a+a’)
        = a+aa’+a+aa’
        = a+aa’
        =a (since aa’=0)

Theorem 2(Involution):
(a’)’=a (theorem)
Proof:
a+a’ = 1, a.a’ = 0
so, a’ is complement of a, again complementing a’ results in a

Theorem 3(Absorption):
a+ab=a (theorem)
a.(a+b)=a (dual)
proof:
a+ab=a.(1)+ab
         =a.(1+b)
         =a.1
         =a
Theorem 4(Null elements for + and . Operators):
a+1=1
a.0=0 ( dual )
proof:
a+1=(a+1).1
       =(a+1).(a+a’)
       =a+a’.1
       =a+a’
       =1
Theorem 5:
a+a’b=a+b
a(a’+b)=ab (dual)
proof:
a+a’b=(a+a’)(a+b)
          =1.(a+b)=a+b
Theorem 6:
ab+ab’=a
(a+b)(a+b’)=a (dual)
Proof:
ab+ab’=a(b+b’)
             =a.1
            =a
Theorem 7:
ab+ab’c=ab+ac
(a+b)(a+b’+c)=(a+b)(a+c) (dual)
Proof:
ab+ab’c=a(b+b’c)
               =a((b+b’)(b+c))
               =a(b+c)
                =ab+ac
Theorem 8 (Demorgan’s law):
(a+b)’=a’.b’
(a.b)’=a’+b’ (dual)
Proof:
(a+b).(a’.b’)=(a’.b’)(a+b)
                        =a’ab’+a’bb’
                        =(a’a)b’+(b’b)a’
                        =0.b’+0.a’
                        =0
(a+b)+(a’.b’)=a+b+a’b’
                        =b+(a+a’b’)
                         =b+[(a+a’)(a+b’)]
                         =b+[1.(a+b’)]
                         =b+a+b’
                         =a+(b+b’)
                         =a+1
                         =1
From above two results a+b and a’b’ are complement to each other
Hence (a+b)’=a’.b’
Note: (a+b+c+….)’=a’.b’.c’………….
            (a.b.c…….)’=a’+b’+c’+………….
Theorem 9 (consensus theorem):
ab+bc+a’c=ab+a’c
(a+b)(b+c)(a’+c)=(a+b)(a’+c) (dual)
Proof:
ab+bc+a’c=ab+a’c+1.bc
                    =ab+a’c+(a+a’).bc
                                =ab+a’c+abc+a’bc
                                =ab+abc+a’c+a’bc
                                =ab(1+c)+a’c(1+b)
                                =ab+a’c
Theorem 10 (Shannon’s expansion theorem):
f(x1,x2,……..xn)=x1f(1,x2,x3,…….,xn)+x1’f(0.x2.x3…………..xn)
f(x1,x2,………xn)=[x1+f(0,x2,x3,………..xn)][x1’+f(1,x2,x3,……………xn)]

Back                                            Contents                                                 Next

No comments:

Post a Comment