boolean algebra for logic circuits and switching

Boolean Algebra

1. BOOLEANALGEBRA
AND
LOGICGATE
BY
Prof. K Adisesha

2. OUTLINEOFBOOLEANALGEBRA
2
2.1 Introduction to Boolean algebra
2.2 History of Boolean algebra
2.3 Logical Operators
2.4 Basic theorems and properties of Boolean algebra
2.5 Boolean functions
2.6 Canonical and standard forms
2.7 Digital logic gates
Prof. K Adisesha

3. INTRODUCTION
An algebra that deals with binary number
system is called “Boolean Algebra”.
It is very power in designing logic circuits used by
the processor of computer system.
The logic gates are the building blocks of all the
circuit in a computer.
Boolean algebra deals with truth table TRUE
and FALSE.
If result of any logical statement or expression is
always TRUE or 1, it is called Tautology and if
the result is always FALSE or 0, it is called
Fallacy
It is also called as “Switching Algebra”.
3
Prof. K Adisesha

4. GEORGEBOOLE
Father of Boolean algebra
Booleanalgebraderivesitsnamefromthe
mathematicianGeorgeBoole(1815-1864)who
isconsideredthe“Fatherofsymboliclogic”.
Hecameupwithatypeofbooleanalgebra,the
threemostbasicoperationsofwhichwere(and
stillare)AND,ORandNOT.
It was these three functions that formed the
basis of his premise, and were the only
operations necessary to perform comparisons
or basic mathematical functions.
George Boole (1815 -1864)
4
Prof. K Adisesha

5. BOOLEANALGEBRA
A variable used in Boolean algebra or Boolean
equation can have only one of two variables. The two
values are FALSE (0) and TRUE (1)
A Sentence which can be determined to be TRUE or
FALSE are called logical statements or truth
functions and the results TRUE or FALSE is called
Truth values.
Boolean Expression consists of
Literal:A variable or its complement
Product term:literals connected by •
Sum term:literals connected by +
•A truth table is a mathematical table used in logic to
computer functional values of logical expressions.
5
Prof. K Adisesha

6. LOGICALOPERATORS
There are three logical operator, AND, OR and NOT.
These operators are now used in computer
construction known as switching circuits.
B = {0, 1} and two binary operators, ‘+’and ‘.’
The rules of operations: AND, OR and NOT.
6
Prof. K Adisesha

7. AND OPERATOR
The AND operator is a binary operator. This operator
operates on two variables.
The operation performed by AND operator is called
logical multiplication.
The symbol we use for it is ‘.’
Example: X . Y can be read as X AND Y
The Truth table and the Venn diagram for the NOT
operator is:
7
Prof. K Adisesha

8. 8
Prof. K Adisesha

9. OR OPERATOR
The OR operator is a binary operator. This operator
operates on two variables.
The operation performed by OR operator is called
logical addition.
The symbol we use for it is ‘+’.
Example: X + Y can be read as X OR Y
The Truth table and the Venn diagram for the NOT
operator is:
9
Prof. K Adisesha

10. 10
Prof. K Adisesha

11. NOT OPERATOR
The Not operator is a unary operator. This operator
operates on single variable.
The operation performed by Not operator is called
complementation.
The symbol we use for it is bar.
??????means complementation of X
If X=1, X =0 If X=0, X =1
The Truth table and the Venn diagram for the NOT
operator is:
11
Prof. K Adisesha

12. 12

13. EVALUATION OFBOOLEANEXPRESSIONUSING
TRUTHTABLE
To create a truth table, follow the steps given below.
Step 1: Determine the number of variables, for n
variables create a table with 2
n
rows.
For two variables i.e. X, Y then truth table will need 2
2
or
4rows.
For three variables i.e. X, Y, Z, then truth table will need
2
3
or 8rows.
Step 2: List the variables and every combination of 1
(TRUE) and 0(FALSE) for the given variables
Step 3:Create a new column for each term of the
statement or argument.
Step 4: If two statements have the same truth values,
then they are equivalent. 13
Prof. K Adisesha

14. CONSIDERTHEFOLLOWINGBOOLEAN
EXPRESSIONF=X+Y
Step 1: This expression as two variables X and Y,
then 2
2
or 4 rows.
Step 2: List the variables and every combination
of X and Y.
Step 3: The final column contain the values of
F=X+ Y.
14
Prof. K Adisesha

15. 15
CONSIDERTHEFOLLOWINGBOOLEAN
EXPRESSIONBOOLEANALGEBRA
The truth table for the
Boolean function:
is shown at the right.
To make evaluation of the
Boolean function easier, the
truth table contains extra
(shaded) columns to hold
evaluations of subparts of
the function.
Prof. K Adisesha

16. OPERATORPRECEDENCE
The operator precedence for evaluating Boolean
Expression is
Parentheses
NOT
AND
OR
Examples
x y' + z
(x y+ z)'
16
Prof. K Adisesha

17. BOOLEANFUNCTIONS
A Boolean function
Binary variables
Binary operators OR and AND
Unary operator NOT
Parentheses
Examples
F
1= x y z'
F
2= x + y'z
F
3 = x' y' z + x' y z + x y'
F
4= x y' + x' z
17
Prof. K Adisesha

18. 18
Figure 2.5 (In book) Digital logic gates
DIGITALLOGICGATES
Prof. K Adisesha

19. 19
Prof. K Adisesha

20. 20
Prof. K Adisesha

21. 21

22. BOOLEANFUNCTIONS
Implementation with logic gates
F
4= x y' + x' z
F
3= x' y' z + x' y z + x y'
F
2= x+ y'z
22
Prof. K Adisesha

23. BASICTHEOREMS
23
Prof. K Adisesha

24. 24
Prof. K Adisesha

25. DUALITY
Theprincipleofdualityisanimportantconcept.Itstates
thateveryalgebraicexpressiondeduciblefromthe
postulatesofBooleanalgebra,remainsvalidifthe
operatorsidentityelementsareinterchanged.
Toformthedualofanexpression,replaceall+operators
with.operators,all.operatorswith+operators,allones
withzeros,andallzeroswithones.
Formthedualoftheexpression
a+(bc)=(a+b)(a+c)
Followingthereplacementrules…
a(b+c)=ab+ac
Takecarenottoalterthelocationoftheparenthesesif
theyarepresent.
25
Prof. K Adisesha

26. 26
Prof. K Adisesha
Indempotence Law: “This law states that when a variable is
combines with itself using OR orAND operator, the output is
the same variable”.

27. 27
Prof. K Adisesha

28. ABSORPTION LAW: “THISLAWENABLES AREDUCTION OF
COMPLICATED EXPRESSION TOASIMPLERONEBYABSORBING
COMMON TERMS”.
28
Prof. K Adisesha

29. DEMORGAN’STHEOREM
Theorem 5(a):Statement: “When the OR sum of two variables is inverted, this is same
as inverting each variable individually and then AND ingthese inverted variables”
 (x+ y)’= x’y’
Theorem 5(b): “When the AND product of two variables is inverted, this is same as
inverting each variable individually and then OR ingthese inverted variables”
 (xy)’= x’+ y’
 By means of truth table
x y x’ y’x+y(x+y)’x’y’xyx’+y'(xy)’
0 0 1 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0 1 1
1 0 0 1 1 0 0 0 1 1
1 1 0 0 1 0 0 1 0 0
Prof. K Adisesha29

30. DEMORGAN’SFIRSTTHEOREM
30
FIRSTLAW: “The complement of a logical sum equals the logical
product of the complements.

31. DEMORGAN’SSECONDTHEOREM
31
SECONDLAW: “The complement of a logical product equals the
logical sum of the complements.

32. SIMPLIFICATION OFBOOLEAN
EXPRESSION:
32
Simplification of Boolean expression can
be achieved by two popular methods:
o Algebraic Manipulation
o Karnaugh Maps (K Map)

33. ALGEBRAICMANIPULATION
To minimize Boolean expressions
Literal: single variable in a term (complemented or uncomplemented)
(an input to a gate)
Term: an implementation with a gate
The minimization of the number of literals and the number of terms → a
circuit with less equipment
It is a hard problem (no specific rules to follow)
Example 2.1
1.x(x'+y) = xx' + xy = 0+xy= xy
2.x+x'y= (x+x')(x+y) = 1 (x+y) = x+y
3.(x+y)(x+y') = x+xy+xy'+yy' = x(1+y+y') = x or x+yy’ = x+ 0 = x
4.xy + x'z + yz = xy + x'z + yz(x+x') = xy + x'z + yzx + yzx' = xy(1+z)
+ x'z(1+y) = xy +x'z
5. (x+y)(x'+z)(y+z) = (x+y)(x'+z), by duality from function 4.
33
Prof. K Adisesha

34. 34
Examples

35. 35
EXAMPLES
Example 2.2
F
1' = (x'yz' + x'y'z)'= (x'yz')'(x'y'z)'= (x+y'+z) (x+y+z')
F
2' = [x(y'z'+yz)]'= x'+ (y'z'+yz)'= x'+ (y'z')'(yz)’
= x' + (y+z) (y'+z')
Example 2.3:a simpler procedure
Take the dual of the function and complement each
literal
1.F
1= x'yz' + x'y'z.
The dual of F
1is (x'+y+z')(x'+y'+z).
Complement each literal: (x+y'+z)(x+y+z') = F
1'
2.F
2= x(y' z' + yz).
The dual of F
2is x+(y'+z')(y+z).
Complement each literal: x'+(y+z)(y' +z') = F
2'
Prof. K Adisesha

36. 36
Prof. K Adisesha

37. 37
Prof. K Adisesha

38. 38
CANONICALANDSTANDARDFORMS
Minterms and Maxterms
A minterm (standard product): an AND term
consists of all literals in their normal form or in
their complement form.
For example, two binary variables x and y,
xy, xy', x'y, x'y'
It is also called a standard product.
nvariables can be combined to form 2
n
minterms.
A maxterm (standard sum): an OR term
It is also called a standard sum.
2
n
maxterms.
Prof. K Adisesha

39. 39
MINTERMSANDMAXTERMS
Each maxtermis the complement of its
corresponding minterm, and vice versa.
Prof. K Adisesha

40. 40
MINTERMSANDMAXTERMS
Any Boolean function can be expressed by
A truth table
Sum of minterms
f
1= x'y'z + xy'z' + xyz = m
1 + m
4 +m
7= S(1, 4, 7) (Minterms)
f
2= x'yz+ xy'z + xyz'+xyz= m
3 + m
5 +m
6+ m
7(Minterms)
Prof. K Adisesha

41. 41
MINTERMSANDMAXTERMS
The complement of a Boolean function
The minterms that produce a (0)
f
1' = m
0+ m
2 +m
3+ m
5 + m
6
= x'y'z'+x'yz'+x'yz+xy'z+xyz'
f
1= (f
1')' = m’
0. m’
2 . m’
3. m’
5 . m’
6
= (x+y+z)(x+y'+z)(x+y'+z')(x'+y+z')(x'+y'+z)
=M
0M
2 M
3M
5M
6
f
2= (x+y+z)(x+y+z')(x+y'+z)(x'+y+z)=M
0M
1M
2M
4
Any Boolean function can be expressed as
A sum of minterms (“sum” meaning the ORingof terms).
A product of maxterms (“product” meaning the ANDingof
terms).
Both Boolean functions are said to be in Canonical form
(ىديلقت لكش) .
Prof. K Adisesha

42. 42
SUMOFMINTERMS
Sum of minterms: there are 2
n
minterms
Example 4: Express F = A+BC' as a sum of minterms.
F(A, B, C) = S(1, 4, 5, 6, 7)
Prof. K Adisesha

43. 43
PRODUCTOFMAXTERMS
Product of maxterms: there are 2
n
maxterms
Example 5: express F = xy + x'z as a product of
maxterms.
F(x, y, z)= P(0, 2, 4, 5)
Prof. K Adisesha

44. MINTERMSANDMAXTERMS
(WITHTHREEVARIABLES)
[ Figure 2.22 from the textbook ]

45. MINTERMSANDMAXTERMS
(WITHTHREEVARIABLES)
The function is
1 for these rows

46. MINTERMSANDMAXTERMS
(WITHTHREEVARIABLES)
The function is
1 for these rows
The function is
0 for these rows

47. 47
CONVERSION BETWEENCANONICAL
FORMS
The complement of a function expressed as the
sum of minterms equals the sum of minterms
missing from the original function.
F(A,B,C)= S(1, 4, 5, 6, 7)
Thus, F'(A,B,C) = S(0, 2, 3) = m
0+ m
2 +m
3
By DeMorgan's theorem
F(A,B,C)= (m
0+ m
2 +m
3)'= M
0M
2M
3 = P(0, 2, 3)
F'(A,B,C)=P (1, 4, 5, 6, 7)
m
j' = M
j
Interchange the symbols Sand Pand list those
numbers missing from the original form
Sof 1's
Pof 0's
Prof. K Adisesha

48. TWODIFFERENT WAYSTOSPECIFYTHESAME
FUNCTION FOFTHREEVARIABLES
f(x
1, x
2, x
3) = Σ m(0, 2, 4, 5, 6, 7)
f(x
1, x
2, x
3) = Π M(1, 3)

49. 49
Example
F= xy+ xz
F(x, y, z) = S(1, 3, 6, 7)
F(x, y, z) = P(0, 2, 4, 5)
Prof. K Adisesha

50. 50
STANDARDFORMS
ThetwocanonicalformsofBooleanalgebraare
basicformsthatoneobtainsfromreadingagiven
functionfromthetruthtable.
Wedonotuseit,becauseeachmintermormaxterm
mustcontain,bydefinition,allthevariables,either
complementedoruncomplementd.
Standardforms:thetermsthatformthefunction
mayobtainone,two,oranynumberofliterals.
Sumofproducts:F
1=y'+xy+x'yz'
Productofsums:F
2=x(y'+z)(x'+y+z')
Prof. K Adisesha

51. 51
IMPLEMENTATION
Two-level implementation
Multi-level implementation
nonstandard form standard form
F
1= y' + xy+ x'yz' F
2= x(y'+z)(x'+y+z')
Prof. K Adisesha

52. 52
KARNAUGH MAP:
oA graphical display of the fundamental products in a
truth table.
oInstead of using Boolean algebra simplification
techniques, you can transfer logic values from a
Boolean statement or a truth table into a Karnaugh
map.
oThe map method provides simple procedure for
minimizing the Boolean function.
oThe map method was first proposed by E.W. Veitch
in 1952 known as “VeitchDiagram”.
oIn 1953, Maurice Karnaugh proposed “Karnaugh
Map” also known as “K-Map”.
Prof. K Adisesha

53. 53
CONSTRUCTION OFK-MAP
•The K-Map is a pictorial representation of a truth
table made up of squares.
•Each square represents a Mintermor Maxterm.
•A K-Map for n variables is made up of 2n
squares.
Single Variable K-Map:
The map consists of 2 squares (i.e. 2
n
square, 2
1
= 2
square)
Two Variable K-Map
•The map consists of 4 squares (i.e. 2
n
square, 2
2
= 4 square)
ThreeVariable K-Map:
The map consists of 8 squares (i.e. 2
n
square, 2
3
= 8
square)
Four Variable K-Map
•The map consists of 16 squares (i.e. 2
n
square, 2
4
= 16
square)
Prof. K Adisesha

54. KARNAUGH MAPS
Karnaugh maps, or K-maps, are often used to simplify logic problems
with 2, 3 or 4 variables.BA
For the case of 2 variables, we form a map consisting of 2
2
=4 cells
as shown in Figure
A
B
0 1
0
1
Cell = 2
n
,where n is a number of variables
0010
0111
A
B
0 1
0
1
A
B
0 1
0
1BA BA AB BA BA BA BA
Maxterm Minterm
0 2
1 3

55. KARNAUGH MAPS
3 variables Karnaugh map
AB
C 00 01 11 10
0
1CBA CBA CAB CBA CBA BCA ABC CBA
0 2 6 4
531 7
Cell = 2
3
=8

56. KARNAUGH MAPS
4 variables Karnaugh map
AB
CD
00 01 11 10
00
01
11
10
5
3
1
7
62
0 4
9
15
13
11
1014
12 8

57. The Karnaugh map is completed by entering a
'1‘(or ‘0’) in each of the appropriate cells.
Within the map, adjacent cells containing 1's
(or 0’s) are grouped together in twos, fours, or
eights.
KARNAUGH MAPS

58. 58
Figure 2.5 (In book) Digital logic gates
DIGITALLOGICGATES
Prof. K Adisesha

59. 59
Figure 2.5 Digital logic gates
Summary of Logic Gates
Prof. K Adisesha

60. 60
Prof. K Adisesha

61. 61
NAND Gate is a Universal Gate:
To prove that any Boolean function can be implemented using only NAND
gates, we will show that the AND, OR, and NOT operations can be
performed using only these gates

62. 62
NAND Gate is a Universal Gate:
To prove that any Boolean function can be implemented using only NOR
gates, we will show that the AND, OR, and NOT operations can be
performed using only these gates

63. 63
MULTIPLEINPUTS
Extension to multiple inputs
A gate can be extended to more than two inputs.
If its binary operation is commutative and
associative.
AND and OR are commutative and associative.
OR
x+y = y+x
(x+y)+z = x+(y+z)= x+y+z
AND
xy = yx
(x y)z = x(y z)= x y z
Prof. K Adisesha

64. 64
MULTIPLEINPUTS
NAND and NOR are commutative but not associative
→ they are not extendable.
Figure 2.6 Demonstrating the nonassociativity of the NOR operator;
(x ↓ y( ↓ z≠ x↓)y↓ z)
z
Prof. K Adisesha

65. 65
MULTIPLEINPUTS
Multiple input NOR = a complement of OR gate,
Multiple input NAND = a complement of AND.
The cascaded NAND operations = sum of products.
The cascaded NOR operations = product of sums.
Figure 2.7 Multiple-input and cascaded NOR and NAND gates
Prof. K Adisesha

66. 66
TheXORandXNORgatesarecommutativeand
associative.
XORisanoddfunction:itisequalto1iftheinputs
variableshaveanoddnumberof1's.
Figure 2.8 3-input XOR gate
Prof. K Adisesha

67. 67
POSITIVEANDNEGATIVELOGIC
Positive and Negative Logic
Two signal values <=> two
logic values
Positive logic: H=1; L=0
Negative logic: H=0; L=1
The positive logic is used in
this book
Figure 2.9 Signal assignment and logic polarity
Prof. K Adisesha

68. 68
Figure 2.10 Demonstration of positive and negative logic
POSITIVEANDNEGATIVELOGIC
Prof. K Adisesha

69. THANKYOU
69
Prof. K Adisesha