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)
= (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’).(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)
