Boolean Algebra
George Booles developed an algebraic system called Boolean Algebra.
Boolean Algebra { B, +, . } is an algebraic structure defined by set B of two elements B={0,1}, together with two binary operators + (OR) and . (AND).
Theorems and postulates
1. Boolean algebra is closed w.r.t + and . operation [Closure Law]
2. x+y=y+x , x.y=y.x [Commutative law]
3. x+0=0+x=x , x.1=1.x=x [Identity Element]
4. x.(y+z)=x.y+x.z , x+y.z=(x+y).(x+z) [Distributive Law]
5. x+x’=1 , x.x’=0 [Complement]
6. x+x=x ,x.x=x [Idempotent Law]
7. (x’)’=x [Involution Law]
8. x+(y+z)=(x+y)+z ,x.(y.z)=(x.y).z [Associative Law]
9. (x+y)’=x’.y’ ,(x.y)’=x’+y’ [De Morgan’s Law]
10. x+xy=x ,x.(x+y) [Absorption Law]
11. x+1=1 ,x.0=0
Duality Theorem
It states that every algebraic expression exists in pairs. We can obtain dual of a boolean algebra expression by interchanging + and . operation and 0 and 1 identity elements.
Dual of expression x+0=x is x+1=x
Boolean Algebra Operation
1. OR operation (x+y): x+y is 1 if either x or y is 1, otherwise 0.
2. AND operation (x.y): x.y is 1 if both x and y is 1, otherwise 0.
3. NOT operation (x’): x’ is 1 if x is 0 and 0 if x is 1.
Logic Gate : It is a digital circuit built from electronic components and implements Boolean algebra operation. OR gate implements OR operation, AND gate implements AND operation, NOT gate implements NOT operation.
AND, OR and NOT gates are called fundamental logic gates.
Truth Table and Circuit Diagram
Boolean Function
A Boolean function maps Boolean inputs to an output. It can be represented in three ways: Algebraic expression, truth table and circuit diagram.
Example
Boolean Function Simplification
Method I – Using theorems of Boolean algebra
Method II – Karnaugh Map simplification
Benefits of simplification
1. Less space requirement
2. Faster processing
3. Less wiring and logic gates requirement
4. Less manufacturing cost
5. Low power consumption
Using theorems of Boolean algebra
We have to apply right theorem at right step otherwise we may not be able to simplify fully.
Example
1. x.(x’+y)
=x.x’+x.y
=0+x.y
=x.y
2. (x+y).(x+y’)
=x+y.y’
=x+0
=x
3. xy+x’z+yz
=xy+x’z+yz(x+x’)
=xy+x’z+xyz+x’yz
=xy+xyz+x’z+x’yz
=xy.(1+z)+x’z(1+y)
=xy+x’z
4. (x’yz’+x’y’z’)’
=(x’yz’)’.(x’y’z’)’
=((x’)’+y’+(z’)’).((x’)’+(y’)’+(z’)’)
=(x+y’+z).(x+y+z)
Note – This method requires practice and skill.
Canonical terms
Canonical terms are used to convert Boolean function in truth table form to algebraic expression form. There are two types of canonical terms: minterms and maxterms.
Minterms
Minterms are product terms containing each and every variable either in complement (x’ for 0) or non complement form (x for 1).
Maxterms
Minterms are sum terms containing each and every variable either in complement (x’ for 1) or non complement form (x for 0).
Canonical form
Every Boolean function can be expressed in canonical forms. There are two canonical forms: sum of minterms and product of maxterms form.
Sum of minterms
It is obtained by forming a minterm for each combination of the inputs that produces a “1” in the function and then taking sum (OR) of theses minterms.
Product of maxterms
It is obtained by forming a maxterm for each combination of the inputs that produces a “0” in the function and then taking product (AND) of theses maxterms.
Conversion between canonical forms
1. Interchange ∑ and π
2. List those numbers missing from the original forms
Example – F(x,y,z)= ∑ (1,3,6,7) = π (0,2,4,5)
Converting a Boolean function to sum of minterms form
Method I - Using Truth Table
Steps
1. Draw truth table of the given function
2. Write sum of minterms notation form the truth table
Method II - Using Boolean algebra theorems
Apply distributive and complement law
F=x+y’z
=x.(y+y’)+y’z(x+x’)
=xy+xy’+xy’z+x’y’z
=xy(z+z’)+xy’(z+z’)+ xy’z+x’y’z
=xyz+xyz’+xy’z+xy’z’+ xy’z+x’y’z
=m1+m4+m5+m6+m7
Converting a Boolean function to product of maxterms form
Method I - Using Truth Table
Steps
1. Draw truth table of the given function
2. Write product of maxterms notation form the truth table
Method II - Using Boolean algebra theorems
Apply distributive and complement law
F=xy+x’.z
=(xy+x’).(xy+z)
=(x’+x.y).(z+x.y)
=(x’+x).(x’+y).(x+z).(y+z)
=(x’+y).(x+z).(y+z)
=(x’+y+zz’).(x+z+yy’).(y+z+x.x’)
=(x’+y+z).(x’+y+z’).(x+y+z).(x+y’+z).(x+y+z).(x’+y+z)
=(x+y+z).(x+y’+z).(x’+y+z).(x’+y+z’)
=M0.M2.M4.M5
Standard Forms
Every Boolean function can be expressed in standard forms. There are two standard forms: sum of product (SOP) and product of sum (POS) form.
SOP – It is a Boolean expression containing sum (OR) of product (AND) terms. Sum of Minterm notation is a type of sum of product term notation. It has two level gating structure.
POS – It is a Boolean expression containing product (AND) of sum (OR) terms. Product of Maxterm notation is a type of sum of product term notation. It has two level gating structure.
Example
Other logic gates
NAND GATE – (NOT OF AND) (x.y)’
Truth Table and Circuit diagram
NOR GATE – (NOT OF OR) (x+y)’
Truth Table and Circuit diagram
XOR GATE – (EXCLUSIVE OR)
(xΘy) is 1 if either x is 1 or y is 1 not both, otherwise 0.
(xΘy)=x’y+xy’
Truth Table and Circuit diagram
XNOR GATE – (NOT OF EXCLUSIVE OR)
(xΘy)’ is 0 if either x is 1 or y is 1 not both, otherwise 1.
(xΘy)=xy+x’y’
Truth Table and Circuit diagram
NAND as Universal gate
1. We can construct AND, OR and NOT gates from NAND gate only.
2. We can realize any digital circuit using NAND gates only, if Boolean function is represented in SOP form.
Why NOR gate is called Universal gate? Explore
K-Map (Karnaugh Map) Simplification
K-Map is graphical representation of truth table. It consists of squares. Each square represent one minterm. Boolean function is recognized graphically in the map from the area enclosed by those squares whose minterms are included in the function.
2 variable map, 3 variable map and 4 variable map
K-Map simplification (SOP form)
Steps
1. Construct prime implicants for Boolean function marked with 1 – A prime implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map. The number of minterms in prime implicant must grouped in the power of 2.
(Prime implicant of 1 minterm, 2 minterm (pair), 4 minterm (quad), 8 minterm (oct), 16 minterm etc.
2. Name each prime implicants by taking common variables from prime implicant.
3. Express Boolean function as sum of products (prime implicants) form.
Examples
Essential Prime Implicants – If a minterm in a square is covered by only one prime implicant, that prime implicant is called essential prime implicant.
Examples
Don’t care conditions
There are situation where a Boolean function is not specified for certain combination of inputs. For example unused BCD codes.
No outputs are specified for these input conditions. We simply don’t care what value is assumed by function for the unspecified minterms. These unspecified minterms are called don’t care conditions.
These can be used for further simplify the Boolean function. Don’t cares are marked with X in the map and are used to maximize the size of prime implicant.
Examples
K-Map simplification (POS form)
Steps
1. Construct prime implicants for Boolean function marked with 0
2. Name each prime implicants by taking common variables from prime implicant.
3. Express Boolean function F’ as sum of products (prime implicants) form.
4. Finally compute F=(F‘)’ to obtain POS form of F.
Examples
