Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Boolean Algebra
Description: These notes are sufficient to give you complete knowledge of Boolean algebra.
Description: These notes are sufficient to give you complete knowledge of Boolean algebra.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 60
Chapter 6: Boolean Algebra and Logic Circuits
Slide 2/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Boolean Algebra
§ An algebra that deals with binary number system
§ George Boole (1815-1864), an English mathematician, developed
it for:
§
Simplifying representation
§
Manipulation of propositional logic
§ In 1938, Claude E
...
Page 60
Chapter 6: Boolean Algebra and Logic Circuits
Slide 3/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Fundamental Concepts of Boolean Algebra
§ Use of Binary Digit
§ Boolean equations can have either of two possible
values, 0 and 1
§ Logical Addition
§ Symbol ‘+’, also known as ‘OR’ operator, used for
logical addition
...
’, also known as ‘AND’ operator, used for
logical multiplication
...
Follows law of binary compliment
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 62
Chapter 6: Boolean Algebra and Logic Circuits
Slide 5/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Operator Precedence
(Continued from previous slide
...
Page 62
2nd 3rd
Chapter 6: Boolean Algebra and Logic Circuits
Slide 6/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Postulates of Boolean Algebra
Postulate 1:
(a) A = 0, if and only if, A is not equal to 1
(b) A = 1, if and only if, A is not equal to 0
Postulate 2:
(a) x + 0 = x
(b) x ⋅ 1 = x
Postulate 3: Commutative Law
(a) x + y = y + x
(b) x ⋅ y = y ⋅ x
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
Postulate 4: Associative Law
(a) x + (y + z) = (x + y) + z
(b) x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z
Postulate 5: Distributive Law
(a) x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z)
(b) x + (y ⋅ z) = (x + y) ⋅ (x + z)
Postulate 6:
(a) x + x = 1
(b) x ⋅ x = 0
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
(AND) and +
(OR), and the digits 0 and 1
...
’
and ‘0’ with ‘1’
Column 1
Column 2
Column 3
Row 1
1+1=1
1+0=0+1=1
0+0=0
Row 2
0⋅0=0
0⋅1=1⋅0=0
1⋅1=1
Therefore, if a particular theorem is proved, its dual theorem
automatically holds and need not be proved separately
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
No
...
Page 63
=x
= x y⋅
Idempotent Law
Absorption Law
Involution Law
x +x ⋅ y = x + y
x⋅y
= x y+
De Morgan’s
Law
Chapter 6: Boolean Algebra and Logic Circuits
Slide 10/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Methods of Proving Theorems
The theorems of Boolean algebra may be proved by using
one of the following methods:
1
...
H
...
= R
...
S
2
...
H
...
and R
...
S
...
By the Principle of Duality where the dual of an already
proved theorem is derived from the proof of its
corresponding pair
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
H
...
=
=
=
=
=
=
=
Ref
...
H
...
by
by
by
by
by
postulate 2(b)
postulate 5(a)
postulate 3(a)
theorem 2(a)
postulate 2(b)
Chapter 6: Boolean Algebra and Logic Circuits
Slide 12/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Proving a Theorem by Perfect Induction
(Example)
Theorem:
x + x ·y = x
=
x
x⋅y
x+x⋅y
0
0
0
0
0
1
0
0
1
0
0
1
1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
H
...
=x+x
= (x + x) ⋅ 1
= (x + x) ⋅ (x + X)
= x + x ⋅X
=x+0
=x
= R
...
S
...
Page 63
Chapter 6: Boolean Algebra and Logic Circuits
Slide 14/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Proving a Theorem by the
Principle of Duality (Example)
(Continued from previous slide
...
H
...
=x⋅x
=x⋅x+0
= x ⋅ x+ x⋅X
= x ⋅ (x + X )
=x⋅1
=x
= R
...
S
...
Page 63
by
by
by
by
by
postulate
postulate
postulate
postulate
postulate
2(a)
6(b)
5(a)
6(a)
2(b)
Notice that each step of
the proof of the dual
theorem is derived from
the proof of its
corresponding pair in
the original theorem
Chapter 6: Boolean Algebra and Logic Circuits
Slide 15/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Boolean Functions
§ A Boolean function is an expression formed with:
§ Binary variables
§ Operators (OR, AND, and NOT)
§ Parentheses, and equal sign
§ The value of a Boolean function can be either 0 or 1
§ A Boolean function may be represented as:
§ An algebraic expression, or
§ A truth table
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 67
Chapter 6: Boolean Algebra and Logic Circuits
Slide 17/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Representation as a Truth Table
X
Y
Z
W
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
§ The number of rows in the table is equal to 2n, where
n is the number of literals in the function
§ The combinations of 0s and 1s for rows of this table
are obtained from the binary numbers by counting
from 0 to 2n - 1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 68
Chapter 6: Boolean Algebra and Logic Circuits
Slide 20/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Minimization of Boolean Functions
(Continued from previous slide
...
Page 68
Chapter 6: Boolean Algebra and Logic Circuits
Slide 21/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Minimization of Boolean Functions
(Continued from previous slide
...
Page 68
Chapter 6: Boolean Algebra and Logic Circuits
Slide 22/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Try out some Boolean Function
Minimization
(a ) x + x ⋅ y
(
(b ) x ⋅ x + y
)
(c) x ⋅ y ⋅ z + x ⋅ y ⋅ z + x ⋅ y
(d ) x ⋅ y + x ⋅ z + y ⋅ z
(e)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
+A = A ⋅ A ⋅ A ⋅
...
⋅ A = A +A +A +
...
Page 70
2
2
3
3
n
n
1
1
2
2
3
3
Chapter 6: Boolean Algebra and Logic Circuits
n
n
Slide 24/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Complementing a Boolean Function (Example)
F = x ⋅ y ⋅ z+ x ⋅ y ⋅ z
1
To obtain F1 , we first interchange the OR and the AND
operators giving
( x + y +z ) ⋅ ( x + y + z )
Now we complement each literal giving
F = ( x+ y +z) ⋅ ( x+ y+ z )
1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 71
Chapter 6: Boolean Algebra and Logic Circuits
Slide 26/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Minterms and Maxterms for three Variables
Variables
x
y
z
0
0
0
0
0
1
0
1
0
Minterms
Term
Maxterms
Designation
m
0
x+y+z
M
0
x ⋅y ⋅z
m
1
x+y+z
M
1
x ⋅y ⋅z
m
2
x+y+z
M
2
x+y+z
M
3
x+y+z
M
4
x+y+z
M
5
x+ y+z
M
6
x+y+z
M
7
1
1
x ⋅y ⋅z
m
3
1
0
0
x ⋅y ⋅z
m
4
x ⋅y ⋅z
m
5
x ⋅y ⋅z
x ⋅y ⋅z
m
6
m
7
1
1
0
1
1
1
0
1
Designation
x ⋅y ⋅z
0
1
Term
Note that each minterm is the complement of its corresponding maxterm and vice-versa
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Examples are:
x
x+ y ⋅ z
x⋅y + x⋅y
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Construct a truth table for the given Boolean
function
2
...
The desired expression is the sum (OR) of all the
minterms obtained in Step 2
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 73
Chapter 6: Boolean Algebra and Logic Circuits
Slide 30/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Expressing a Function in its
Sum-of-Products Form (Example)
(Continued from previous slide
...
Page 72
Chapter 6: Boolean Algebra and Logic Circuits
Slide 31/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Product-of Sums (POS) Expression
A product-of-sums (POS) expression is a sum term
(maxterm) or several sum terms (maxterms) logically
multiplied (ANDed) together
...
Page 74
( x+ y )⋅( x+ y )⋅( x+ y )
( x + y )⋅( x+ y+z )
( x+ y )⋅( x+ y )
Chapter 6: Boolean Algebra and Logic Circuits
Slide 32/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Steps to Express a Boolean Function
in its Product-of-Sums Form
1
...
Form a maxterm for each combination of the variables,
which produces a 0 in the function
3
...
Page 74
Chapter 6: Boolean Algebra and Logic Circuits
Slide 33/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Expressing a Function in its
Product-of-Sums Form
x
z
F1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
§
y
1
1
1
The following 5 combinations of variables produce a 0:
000,
010,
011,
101,
and
110
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
§
Their corresponding maxterms are:
( x+y+ z ) , ( x+ y+ z ), ( x+ y+ z ) ,
( x+y+ z ) and ( x+ y+ z )
§
Taking the AND of these maxterms, we get:
F1 = ( x+y+z ) ⋅ ( x+ y+z ) ⋅ ( x+y+z ) ⋅ ( x+ y+z ) ⋅
( x+ y+z ) =M ⋅M ⋅M ⋅ M ⋅M
( x,y,z ) = Π( 0,2,3,5,6 )
0
F1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Example:
( ) (
) (
)
F( x,y,z ) = Σ (1,4,7 ) = Σ ( 0,2,3,5,6 )
F x,y,z = Π 0,2,4,5 = Σ 1,3,6,7
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 77
Chapter 6: Boolean Algebra and Logic Circuits
Slide 37/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
AND Gate
§ Physical realization of logical multiplication (AND)
operation
§ Generates an output signal of 1 only if all input
signals are also 1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 77
B
1
1
Chapter 6: Boolean Algebra and Logic Circuits
Slide 39/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
OR Gate
§ Physical realization of logical addition (OR) operation
§ Generates an output signal of 1 if at least one of the
input signals is also 1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 78
B
1
1
Chapter 6: Boolean Algebra and Logic Circuits
Slide 41/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
NOT Gate
§ Physical realization of complementation operation
§ Generates an output signal, which is the reverse of
the input signal
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 79
Output
0
Chapter 6: Boolean Algebra and Logic Circuits
Slide 43/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
NAND Gate
§ Complemented AND gate
§ Generates an output signal of:
§
§
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 79
B
1
0
Chapter 6: Boolean Algebra and Logic Circuits
Slide 45/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
NOR Gate
§ Complemented OR gate
§ Generates an output signal of:
§
§
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 80
B
1
0
Chapter 6: Boolean Algebra and Logic Circuits
Slide 47/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Logic Circuits
§ When logic gates are interconnected to form a gating /
logic network, it is known as a combinational logic circuit
§ The Boolean algebra expression for a given logic circuit
can be derived by systematically progressing from input
to output on the gates
§ 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
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 80
Chapter 6: Boolean Algebra and Logic Circuits
Slide 49/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Finding Boolean Expression
of a Logic Circuit (Example 2)
OR
A +B
A
B
(
C= ( A +B ) ⋅ A ⋅ B
A ⋅B
A ⋅B
AND
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 83
Chapter 6: Boolean Algebra and Logic Circuits
Slide 51/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Constructing a Logic Circuit from a Boolean
Expression (Example 2)
Boolean Expression =
AND
A ⋅B
A
B
NOT
A ⋅B + C ⋅D + E ⋅F
A ⋅B
AND
AND
C ⋅D
C
D
A ⋅B + C ⋅D + E ⋅F
AND
E
F
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 84
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
Chapter 6: Boolean Algebra and Logic Circuits
Slide 53/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Implementation of NOT, AND and OR Gates by
NAND Gates
A
A ⋅A = A + A = A
(a) NOT gate implementation
...
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
A
B
A ⋅A = A
A ⋅B = A + B = A + B
B ⋅B = B
(c) OR gate implementation
...
Page 85
Chapter 6: Boolean Algebra and Logic Circuits
Slide 55/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Method of Implementing a Boolean Expression
with Only NAND Gates
Step 1: From the given algebraic expression, draw the logic
diagram with AND, OR, and NOT gates
...
Also remove inverters connected to
single
external
inputs
and
complement
the
corresponding input variable
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 87
Chapter 6: Boolean Algebra and Logic Circuits
Slide 57/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Implementing a Boolean Expression with Only
NAND Gates (Example)
(Continued from previous slide
...
Page 87
Chapter 6: Boolean Algebra and Logic Circuits
Slide 58/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Implementing a Boolean Expression with Only
NAND Gates (Example)
(Continued from previous slide
...
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 89
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
Chapter 6: Boolean Algebra and Logic Circuits
Slide 60/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Implementation of NOT, OR and AND Gates by
NOR Gates
A + A = A ⋅A = A
A
(a) NOT gate implementation
...
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
A
A +A=A
A + B = A ⋅B = A ⋅B
B
B + B =B
(c) AND gate implementation
...
Page 89
Chapter 6: Boolean Algebra and Logic Circuits
Slide 62/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Method of Implementing a Boolean Expression
with Only NOR Gates
Step 1: For the given algebraic expression, draw the logic
diagram with AND, OR, and NOT gates
...
Also remove inverters connected to
single
external
inputs
and
complement
the
corresponding input variable
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
A
B
Boolean Expression A ⋅ B + C ⋅ ( A +B ⋅D )
=
A ⋅B
B
D
A
C
A ⋅ B + C ⋅ ( A +B ⋅D )
B ⋅D
A +B ⋅D
C ⋅ ( A +B ⋅D )
(a) Step 1: AND/OR implementation
...
Page 90
Chapter 6: Boolean Algebra and Logic Circuits
Slide 64/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Implementing a Boolean Expression with Only
NOR Gates (Examples)
(Continued from previous slide
...
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
A
B
1
5
B
D
6
A ⋅ B + C ⋅ ( A +B ⋅D )
2
A
C
3
4
(c) Step 3: NOR implementation
...
Page 91
Chapter 6: Boolean Algebra and Logic Circuits
Slide 66/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Exclusive-OR Function
A ⊕ B =A ⋅ B + A ⋅ B
C = A ⊕ B = A ⋅B+ A ⋅B
A
B
A
B
⊕
C = A ⊕ B = A ⋅B+ A ⋅B
Also, ( A ⊕ B ) ⊕ C = A ⊕ (B ⊕ C ) = A ⊕ B ⊕ C
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
Inputs
Output
A
C =A ⊕B
0
0
0
0
1
1
1
0
1
1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 91
Chapter 6: Boolean Algebra and Logic Circuits
Slide 69/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Equivalence Function (Truth Table)
Output
Inputs
C=A€B
A
0
0
1
0
1
0
1
0
0
1
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
State the given problem completely and exactly
2
...
Assign a letter symbol to each input and output variables
4
...
Obtain the simplified Boolean function for each output
6
...
Page 93
Chapter 6: Boolean Algebra and Logic Circuits
Slide 71/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Designing a Combinational Circuit
Example 1 – Half-Adder Design
Inputs
Outputs
A
B
C
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
S = A ⋅B+ A ⋅B
C = A ⋅B
Ref
...
Chapter 6: Boolean Algebra and Logic Circuits
Slide 72/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Designing a Combinational Circuit
Example 1 – Half-Adder Design
(Continued from previous slide
...
Page 94
Chapter 6: Boolean Algebra and Logic Circuits
Slide 73/78
Computer Fundamentals: Pradeep K
...
Sinha & Priti Sinha
Designing a Combinational Circuit
Example 2 – Full-Adder Design
Inputs
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
Outputs
D
0
1
0
1
0
1
0
1
C
0
0
0
1
0
1
1
1
Truth table for a full adder
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
Boolean functions for the two outputs:
S = A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D
C = A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D
= A ⋅B+ A ⋅D+B ⋅D (when simplified)
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
A
B
A ⋅B ⋅ D
D
A
B
D
A ⋅B ⋅ D
S
A
B
D
A ⋅B ⋅ D
A
B
A ⋅B ⋅ D
D
(a) Logic circuit diagram for sums
(Continued on next slide)
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
)
A
A ⋅B
B
A
A ⋅D
C
D
B
B⋅D
D
(b) Logic circuit diagram for carry
Ref
...
Sinha & Priti Sinha
Computer Fundamentals: Pradeep K
...
Page 97
§ Equivalence function
§ Exclusive-OR function
§ Exhaustive enumeration
method
§ Half-adder
§ Idempotent law
§ Involution law
§ Literal
§ Logic circuits
§ Logic gates
§ Logical addition
§ Logical multiplication
§ Maxterms
§ Minimization of Boolean
functions
§ Minterms
§ NAND gate
§
§
§
§
§
§
§
§
§
§
§
§
§
NOT gate
Operator precedence
OR gate
Parallel Binary Adder
Perfect induction
method
Postulates of Boolean
algebra
Principle of duality
Product-of-Sums
expression
Standard forms
Sum-of Products
expression
Truth table
Universal NAND gate
Universal NOR gate
Chapter 6: Boolean Algebra and Logic Circuits
Slide 78/78
Title: Boolean Algebra
Description: These notes are sufficient to give you complete knowledge of Boolean algebra.
Description: These notes are sufficient to give you complete knowledge of Boolean algebra.