0Logic Simplification
Simplification of Boolean functions is mainly used to reduce the gate count of a design. Less number of gates means less power consumption; sometimes the circuit works faster and also when the number of gates is reduced, cost also comes down. There are many ways to simplify a logic design; some of them are given below.
Algebraic Simplification Simplify symbolically using theorems/postulates.
Karnaugh Maps Diagrammatic technique using 'Venn - diagram.'
De Morgan's Theorems
I Theorem statement
The complement of a sum is equal to
the product of the complements.
_____
_
_
A + B = A . B
Proof
____
_
_
To prove
A + B = A . B
Case 1: A=0, B=0 _____
_____
_
L.H.S => A + B = 0 + 0 = 0 = 1
_
_
_ _
R.H.S=>
A . B = 0 . 0=
1 .1 = 1
Case 2: A=0, B=1
_____
_____
_
L.H.S => A + B = 0 + 1 =
1 = 0
_
_
_ _
R.H.S =>
A . B = 0 . 1
= 1 .0 = 0
Case 3: A=1, B=0
____
_____
_
L.H.S => A + B = 1 + 0 =
1 = 0
_
_
_ _
R.H.S =>
A . B = 1 . 0
= 0 .1 = 0
Case 4: A=1, B=1
_____
_____
_
L.H.S => A + B = 1 + 1 =
1 = 0
_
_
_
_
R.H.S =>
A . B = 1 . 1 = 0 .0 = 0
Truth table
____
_
_
A
B
A. B
A + B
0
0
1
1
0
1
0
0
1
0
0
0
1
1
0
0
II Theorem Statement
The complement of a product is equal to the sum of the complements.
____
_
_
A . B = A + B
Proof of the second theorem:
____ _ _
To prove A . B = A + B
Case 1: A=0, B=0
____
___
_
L.H.S => A . B = 0 . 0 = 0 = 1
_
_
R.H.S => A +B = 0 + 0
= 1 + 1 = 1
Case 2: A=0, B=1
____ ____ _
L.H.S => A . B = 0 . 1 = 0 = 1
_ _ _ _
R.H.S => A + B = 0 + 1
= 1 + 0 = 1
Case 3: A=1, B=0
____
____
_
L.H.S => A . B = 1 . 0 =
0 = 1
_
_
_
_
R.H.S => A + B = 1 + 0
= 0 +1 = 1
Case 4: A=1, B=1
____
____
_
L.H.S => A . B = 1 . 1 =
1 = 0
_
_
_
_
R.H.S => A + B = 1 + 1
= 0 +0 = 0
Truth table
____
_
_
A
B
A + B
A. B
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
0
Basic Laws of Boolean Algebra
Commutative law
A + B = B + A
A . B = B . A
Associative law
A + (B + C) = (A + B) + C
(B.C) = (A.B).C
Distributive law
(B + C) = A.B + A.C
Other laws of Boolean algebra
A + 0 = A
A + 1 = 1
A + A = A
A + Ā = 1
A .0 = 0
A .1 = A
A .A = A
A . Ā = 0
=
A = A
A + A.B =A
A.(A + B) = A
(A + B).(A+C) = A +B.C
A + Ā.B =A + B
A.(Ā +B) = A.B
(A + B).(Ā + C) = A.C + Ā.B
(A + C).(Ā + B) = A.B + Ā.C
