------------
PAGE 1
------------
Boolean Algebra and Logic Circuits
------------
PAGE 2
------------
Learning Objectives
„R In this chapter you will learn about:
„Ï Boolean algebra
„Ï Fundamental concepts and basic laws of Boolean algebra
„Ï Boolean function and minimization
„Ï Logic gates
„Ï Logic circuits and Boolean expressions
„Ï Combinational circuits and design
------------
PAGE 3
------------
Boolean Algebra
„R An algebra that deals with binary number system
„R George Boole ( 1815- 1864), an English mathematician, developed it for:
„R Simplifying representation
„R Manipulation of propositional logic
„R In 1938, Claude E. Shannon proposed using Boolean algebra in design of relay switching circuits
„R Provides economical and straightforward approach
„R Used extensively in designing electronic circuits used in computers
3
------------
PAGE 4
------------
Fundamental Concepts of Boolean Algebra
„R Use of Binary Digit
„R Boolean equations can have either of two possible values, 0 and 1
„R Logical Addition
„R Symbol ‘ ’, also known as ‘ OR ’ operator, used for logical addition.
„R Follows law of binary addition
„R Logical Multiplication
„R Symbol ‘ . ’, also known as ‘ AND ’ operator, used for logical multiplication.
„R Follows law of binary multiplication
„R Complementation
„R Symbol ‘ - ’, also known as ‘ NOT ’ operator, used for complementation.
„R Follows law of binary compliment
4
------------
PAGE 5
------------
Operator Precedence
„R Each operator has a precedence level
„R Higher the operator’s precedence level, earlier it is evaluated
„R Expression is scanned from left to right
„R First, expressions enclosed within parentheses are evaluated
„R Then, all complement ( NOT) operations are performed
„R Then, all ‘ · ’ ( AND) operations are performed
„R Finally, all ‘ ’ ( OR) operations are performed
5
------------
PAGE 6
------------
Operator Precedence
6
------------
PAGE 7
------------
Postulates of Boolean Algebra
„R Postulate 1:
‡@ A = 0, if and only if, A is not equal to 1
‡A A = 1, if and only if, A is not equal to 0
„R Postulate 2:
‡@ x 0 = x
‡A x · 1 = x
„R Postulate 3: Commutative Law
‡@ x y = y x
‡A x · y = y · x
Postulates - are the basic structure from which lemmas and theorems are derived.
Theorem - a mathematical statement that is proved using rigorous mathematical reasoning.
Lemma - a minor result whose sole purpose is to help in proving a theorem. It is a stepping stone on the path to proving a theorem.
7
------------
PAGE 8
------------
Postulates of Boolean Algebra
„R Postulate 4: Associative Law
‡@ x ( y z) = ( x y) z
‡A x · ( y · z) = ( x · y) · z
„R Postulate 5: Distributive Law
‡@ x · ( y z) = ( x · y) ( x · z)
‡A x ( y · z) = ( x y) · ( x z)
„R Postulate 6:
‡@ x x = 1
‡A x · x = 0
8
------------
PAGE 9
------------
The Principle of Duality
9
------------
PAGE 10
------------
Some Important Theorems of Boolean Algebra
------------
PAGE 11
------------
Methods of Proving Theorems
„R The theorems of Boolean algebra may be proved by using one of the following methods:
‡@ By using postulates to show that L. H. S. = R. H. S
‡A By Perfect Induction or Exhaustive Enumeration method where all possible combinations of variables involved in L. H. S. and R. H. S. are checked to yield identical results
‡B By the Principle of Duality where the dual of an already proved theorem is derived from the proof of its corresponding pair
11
------------
PAGE 12
------------
Proving a Theorem by Using Postulates ( Example)
„R Theorem: x x · y = x
„R Proof:
L. H. S.
= x x · y
= x · 1 x · y by postulate 2( b)
= x · ( 1 y) by postulate 5( a)
= x · ( y 1) by postulate 3( a)
= x · 1 by theorem 2( a)
= x by postulate 2( b)
= R. H. S.
12
------------
PAGE 13
------------
Proving a Theorem by Perfect Induction ( Example)
„X Theorem: x x · y = x
13
------------
PAGE 14
------------
Proving a Theorem by Perfect Induction ( Example)
„X Theorem: x x = x
14
------------
PAGE 15
------------
Proving a Theorem by Perfect Induction( Example)
15
------------
PAGE 16
------------
Boolean Functions
„R A Boolean function is an expression formed with:
• Binary variables
• Operators ( OR, AND, and NOT)
• Parentheses, and equal sign
„R The value of a Boolean function can be either 0 or 1
„R A Boolean function may be represented as:
• An algebraic expression, or
• A truth table
16
------------
PAGE 17
------------
Representation as an Algebraic Expression 17
------------
PAGE 18
------------
Representation as a Truth Table
„R The number of rows in the table is equal to 2 n , where n is the number of literals in the function
18
------------
PAGE 19
------------
Minimization of Boolean Functions
„R Minimization of Boolean functions deals with
„« Reduction in number of literals
„« Reduction in number of terms
„R Minimization is achieved through manipulating expression to obtain equal and simpler expression( s) ( having fewer literals and/ or terms)
19
------------
PAGE 20
------------
Minimization of Boolean Functions 20
------------
PAGE 21
------------
Minimization of Boolean
Functions
„R Both F 1 and F 2 produce the same result
0 0 0 0 0
0 0 1 1 1
0 1 0 0 0
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 0 0
1 1 1 0 0
Both F 1 and F 2 produce the same result
x y z F 1 F 2
M i in i im i iza t t i ion o f f Boo l lean Func t t i ions
( Continued from previous slide..)
21
------------
PAGE 22
------------
Try out Some Boolean Function Minimization 22
------------
PAGE 23
------------
Logic Gates
„R Logic gates are electronic circuits that operate on one or more input signals to produce standard output signal
„R Are the building blocks of all the circuits in a computer
„R Some of the most basic and useful logic gates are -
„R AND,
„R OR,
„R NOT,
„R NAND and
„R NOR gate
23
------------
PAGE 24
------------
AND Gate
„R Physical realization of logical multiplication ( AND) operation
„R Generates an output signal of 1 only if all input signals are also 1
„R AND Gate ( Block Diagram Symbol and Truth Table)
24
------------
PAGE 25
------------
OR Gate
„R Physical realization of logical addition ( OR) operation
„R Generates an output signal of 1 if at least one of the input signals is also 1
„R OR Gate ( Block Diagram Symbol and Truth Table)
25
------------
PAGE 26
------------
NOT Gate
„R Physical realization of complementation operation
„R Generates an output signal, which is the reverse of the input signal
26
------------
PAGE 27
------------
NAND Gate
„R Complemented AND gate
„R Generates an output signal of:
‡@ 1 if any one of the inputs is a 0
‡A 0 when all the inputs are 1
27
------------
PAGE 28
------------
NOR Gate
„R Complemented OR gate
„R Generates an output signal of:
‡@ 1 only when all inputs are 0
‡A 0 if any one of inputs is a 1
28
------------
PAGE 29
------------
Logic Circuits
„R When logic gates are interconnected to form a gating / logic network, it is known as a combinational logic circuit
„R The Boolean algebra expression for a given logic circuit can be derived by systematically progressing from input to output on the gates
„R The three logic gates ( AND, OR, and NOT) are logically complete because any Boolean expression can be realized as a logic circuit using only these three gates
29
------------
PAGE 30
------------
Finding Boolean Expression of a Logic Circuit ( Example 1)
30
------------
PAGE 31
------------
Finding Boolean Expression of a Logic Circuit ( Example 2) 31
------------
PAGE 32
------------
Constructing a Logic Circuit from a Boolean Expression ( Example 1)
32
------------
PAGE 33
------------
Constructing a Logic Circuit from a Boolean Expression ( Example 2)
33
------------
PAGE 34
------------
Universal NAND Gate
„R NAND gate is an universal gate, it is alone sufficient to implement any Boolean expression
„R To understand this, consider:
• Basic logic gates ( AND, OR, and NOT) are logically complete
• Sufficient to show that AND, OR, and NOT gates can be implemented with NAND gates
34
------------
PAGE 35
------------
Implementation of NOT, AND and OR Gates by NAND Gates
35
------------
PAGE 36
------------
Universal NOR Gate
„R NOR gate is an universal gate, it is alone sufficient to implement any Boolean expression
„R To understand this, consider:
• Basic logic gates ( AND, OR, and NOT) are logically complete
• Sufficient to show that AND, OR, and NOT gates can be implemented with NOR gates
36
------------
PAGE 37
------------
Implementation of NOT, OR and AND Gates by NOR Gates 37
Back to top of page