Digital Logic Design

EE-221

Chapter 2:
Boolean Algebra and Logic Gates

1
 Boolean Algebra : Basics
• Algebra: Mathematics of generalized arithmetical operations - Reunion of broken
parts
– Study of mathematical symbols and the rules for manipulating these symbols
in formulas; it is a unifying thread of almost all of mathematics.
– Elementary, Linear algebra

• Boolean algebra : The values of the variables are the truth values true and false,
usually denoted 1 and 0, respectively.
– Instead of elementary algebra, where the values of the variables are numbers and
the prime operations are addition and multiplication, the main operations of
Boolean algebra are the conjunction (and) denoted as ∧, the disjunction (or)
denoted as ∨, and the negation (not) denoted as ¬.
– A formalism for describing logical operations, in the same way that elementary
algebra describes numerical operations.
– A convenient and systematic way of expressing and analyzing the operations of
digital logic circuits
 WHY Boolean Algebra with Binary Logic?
• Binary Logic is used in all digital devices:

– The cost of digital circuits is an important factor to be addressed by the designers

– Simpler, cheaper, but equivalent realization of a circuit can reduce overall cost of
digital devices
– Boolean Algebra helps in doing so by simplifying circuits
 Objectives

– To understand basic vocabulary and foundation of Boolean Algebra

– To apply the basic rules and theorems of Boolean Algebra and their applications
to digital circuits
– To learn how to optimize and simplify circuits using the Postulates and theorems
of Boolean Algebra
– To understand purpose of algorithms used by software tools to optimize
complex digital circuits involving million of logic gates
 Boolean Algebra : Basics
• Boolean Algebra may be defined with:
– A set of elements “S” containing a set of any objects with common properties
– A set of operators defined on a set “S” of elements are rules that assigns to each
pair of elements from “S”
– A set of axioms or postulates forming a basis from which we can deduce rules,
theorems and properties of the system
• Axiom: Proposition that is not susceptible of proof or disproof; its truth is assumed to
be self-evident-- (x * y) * z = x * (y * z)
• Proposition: Statement that affirms or denies something and is either true or false
• An axiom or a postulate is considered to be Self-evident, true without any proof or
demonstration. Something that is obvious or declared to be true and accepted but have
no proof for that.
• Axioms can be true for any field of science, while Postulates can be specific to a
particular field
• Theorem: A statement that has been proven on the basis of previously established
statements, such as postulates and other already proved theorems
 Basic Postulates
• Postulates form the basic assumption from which it is possible to deduce other rules,
theorems, and properties of the system. Following are the most common postulates:
1. Closure. A set S is closed w.r.t a binary operator if this operation only produces
results that are within the set of elements defined by the system

2. Associative Law. A binary operator “*” on a set S is said to be associative when:

» (x * y) * z = x * (y * z) for all x, y, z ϵ S

3. Commutative Law. A binary operator “*” on a set S is said to be commutative when:

» x*y=y*x for all x, y ϵ S

4. Identity Element. A set S is said to have an identity element w.r.t a binary operation
“*” on set S if there exists an element, e ϵ S with the property:
» e * x = x * e = x for every x ϵ S
• Additive “+” identity is “0” and multiplicative “.” identity is “1”
 Basic Postulates

5. Inverse. A set S having the identity element “e” w.r.t a binary operator “*”
is said to have an inverse whenever, for every x ϵ S, there exists an element
y ϵ S such that
» x*y=e
• The additive inverse of element “a” is “–a” and it defines subtraction, since
a + (–a) = 0. Multiplicative inverse of “a” is “1/a” and defines division,
since a . 1/a = 1

6. Distributive Law. If “*” and “.” are two binary operators on a set S, “*” is
said to be distributive over “.” when
» x * ( y · z) = (x * y) · (x * z)

– Distributive law of “.” over “+”:

» a . (b + c) = (a . b) + (a . c)
 Two-valued Boolean Algebra and Huntington Postulates

• Huntington postulates include the identity law, the complement law, the
commutative law and the distributive law. The theorems of boolean algebra
can be proved using these postulates. Each postulate and theorem of boolean
algebra has two parts; one is dual of another.

• Show that Huntington Postulates are valid for the set B= {1,0} and the two
operators “+” “.”:
1. Closure
a) with respect to the binary operation OR (+)
b) with respect to the binary operation AND (·)
2. Identity
a) with respect to OR (+) is 0:
x + 0 = 0 + x = x, for x = 1 or x = 0
b) with respect to AND (·) is 1:
x · 1 = 1 · x = x, for x = 1 or x =0
Two-valued Boolean Algebra and Huntington Postulates
3. Commutative Law
a) With respect to OR (+):
x + y = y + x
b) With respect to AND (·):
x · y = y · x
4. Distributive Law
a) with respect to the binary operation AND (.):
 x . (y + z) = (x . y) + (x . z) “.” is distributive over “+”
b) with respect to the binary operation OR (+):
 x + (y . z) = (x + y) . (x + z) “+” is distributive over “.”
5. Complement
a) x + x’ = 1, for x = 1 or x = 0
b) x · x’ = 0 , for x = 1 or x = 0
6. Membership
 There exists at least two elements, x and y, of the set such that x ≠ y
0 ≠ 1
 Two-valued Boolean Algebra
• Boolean Algebra with two elements “0” and “1”
• “Two-value Boolean Algebra” which is defined by:
– set of two elements B = {0, 1}
– operators of “·” and “+”
– Can be used for Gate type circuits

• Operator Tables
x y x.y x y x+y x x’
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
• Rules are exactly the same as the three operations
• AND “.”
• OR “+”
• NOT (‘) complement
 Proving the Distributive Law 4(a)

4. Distributive Law
a) with respect to the binary operation AND (.):
 x . (y + z) = (x . y) + (x . z) “.” is distributive over “+”
b) with respect to the binary operation OR (+):
 x + (y . z) = (x + y) . (x + z) “+” is distributive over “.”
 Proving the Distributive Law 4(b)
x y z y.z x+(y.z) x+y x+z (x+y).(x+z)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1

4. Distributive Law
a) with respect to the binary operation AND (.):
 x . (y + z) = (x . y) + (x . z) “.” is distributive over “+”
b) with respect to the binary operation OR (+):
 x + (y . z) = (x + y) . (x + z) “+” is distributive over “.”
 Two-valued Boolean Algebra Established
• Based on these postulates now we can develop the Theorems and properties of
Two-valued Boolean Algebra

• Duality
– The duality principle states that every algebraic expression deducible from
the postulates of Boolean algebra remains valid if the operators and identity
elements are interchanged
– If the dual of an algebraic equation is required, we interchange the OR and
AND operators and replace 1’s by 0’s and 0’s by 1’s
 Postulates and Basic Theorems of Boolean Algebra

– Postulates are the basic axioms of the algebraic structure and need no proof
– Theorems must be proved from the postulates or other theorems

P2 x+0 =x x1=x
P5 x+x‘ = 1 x x‘ = 0
T1 x+x=x xx=x
T2 x+1=1 x0=0
T3 involution (x‘)’ = x
P3 commutative x+y = y+x xy = yx
T4 associative x+(y+z)=(x+y)+z x(yz) =(xy)z
P4 distributive x(y+z)=xy+xz x+yz=(x+y)(x+z)
T5 DeMorgan (x+y)‘ =x’y‘ (xy)‘=x’+y‘
T6 absorption x+xy = x x(x+y) =x
 Basic Theorems of Boolean Algebra
• The following six theorems can be deduced from the Huntington
postulates:
– Theorem 1(a): x+x=x
– Theorem 1(b): x·x=x
– Theorem 2(a): x+1=1
– Theorem 2(b): x·0=0
– Theorem 3 (involution): (x’)’ = x
– Theorem 4(a) (associative): x + ( y + z) = (x + y) + z
– Theorem 4(b) (associative): x · (y · z) = (x · y) · z
– Theorem 5(a) (DeMorgan): (x + y)’ = (x’ · y’)
– Theorem 5(b) (DeMorgan): (x · y)’ = (x’ + y’)
– Theorem 6(a) (absorption): x+x·y=x
– Theorem 6(b) (absorption): x · (x + y) = x
 Proving Theorem 1(a)

x+x=x P2 x+0 =x x1=x

LHS = x + x p5 x+x‘ = 1 x x‘ = 0
= (x + x) · 1 By postulate: 2(b) T1 x+x=x xx=x
= (x + x) · (x + x’) T2 x+1=1 x0=0
5(a) T3 (x‘)’ = x
= x + x · x’ 4(b) p3 x+y = y+x xy = yx
T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
=x+0 P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
5(b) T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
=x 2(a) T6 x+xy = x x(x+y) =x
LHS = RHS
 Proving Theorem 1(b)

x.x=x P2 x+0 =x x1=x

p5 x+x‘ = 1 x x‘ = 0
x.x=xx+0 By postulate: 2(a) T1 x+x=x xx=x
T2 x+1=1 x0=0
= x x + xx‘ T3 (x‘)’ = x
p3 x+y = y+x xy = yx
5(b)
T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
= x (x + x') P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
4(a) T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
T6 x+xy = x x(x+y) =x
=x.1 5(a)
=x
2(b)
 Proving Theorem 2(a)

x+1=1 P2 x+0 =x x1=x

x + 1= 1 . (x + 1) By postulate: p5 x+x‘ = 1 x x‘ = 0
2(b) T1 x+x=x xx=x
= (x + x’)(x + 1) T2 x+1=1 x0=0
5(a) T3 (x‘)’ = x
= x + x' 1 p3 x+y = y+x xy = yx
4(b) T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
= x + x' T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
2(b)
T6 x+xy = x x(x+y) =x
=1
5(a)
• Theorem 2(b) can be proved by duality:
x.0=0
 Proving Theorem 2(b)

x.0=0 P2 x+0 =x x1=x

x . 0 = 0 + (x . 0) By postulate: p5 x+x‘ = 1 x x‘ = 0
2(a) T1 x+x=x xx=x
= (x . x’) + (x . 0) T2 x+1=1 x0=0
5(b) T3 (x‘)’ = x
= x . (0 + x' ) 4(a) p3 x+y = y+x xy = yx
= x . x' T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
2(a) P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
=0
T6 x+xy = x x(x+y) =x
5(b)
• Or Theorem 2(b) can also be proved by
duality:
• Theorem 2(a) was x + 1 = 1, now using
duality rule replace OR with AND and “1”
with “0”
x.0=0
 Proving Theorem 6(a)

x+x.y=x P2 x+0 =x x1=x

LHS =x+x.y p5 x+x‘ = 1 x x‘ = 0
T1 x+x=x xx=x
=x.1+x.y by postulate:
T2 x+1=1 x0=0
2(b)
T3 (x‘)’ = x
= x . (1 + y) p3 x+y = y+x xy = yx
4(a) T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
= x . (y + 1) P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
3(a) T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
=x.1 by theorem: T6 x+xy = x x(x+y) =x
2(a)
=x by postulate:
2(b)
LHS = RHS
 Proving Theorem 6(b)

x · (x + y) = x P2 x+0 =x x1=x
= (x + 0) · (x + y) by p5 x+x‘ = 1 x x‘ = 0
postulate:2(a) T1 x+x=x xx=x
T2 x+1=1 x0=0
=x+0·y
T3 (x‘)’ = x
4(b)
p3 x+y = y+x xy = yx
=x+y·0 T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
3(b) P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
=x+0 by theorem: T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
2(b) T6 x+xy = x x(x+y) =x
=x by
postulate:2(a)
 Proving Theorem by Truth Table
• Boolean Algebra Theorems can be proved by means of Truth Tables
• Specially in case the Algebraic proofs are long we can use truth
tables to verify
• Both sides of the relation are checked to see whether they yield
identical results for all possible combinations of the variables
involved:
Theorem 6(a) & (b)
Theorem 4(a) & (b) (long algebraic proof)
Theorem 5(a) & (b)
 Proving Theorem 6(a) by Truth Table

• With truth table the validity of Theorem 6(a) can be shown

• x + xy = x

x y x.y x+xy x
0 0 0 0 0
0 1 0 0 0
1 0 0 1 1
1 1 1 1 1
 Proving Theorem 6(b) by Truth Table

• With truth table the validity of Theorem 6(b) can be shown

• x (x+y) = x

x y x+y x(x+y) x
0 0 0 0 0
0 1 1 0 0
1 0 1 1 1
1 1 1 1 1
 Proving Theorem 4(a) by Truth Table

x y z x+y y+z x+(y+z) (x+y)+z

0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 1 0 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
 Proving Theorem 4(b) by Truth Table

x y z x.y y.z x.(y.z) (x.y).z

0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 1 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 1 0 0 0
1 1 1 1 1 1 1
 DeMorgan’s Theorem 5(a)

• The validity of first DeMorgan’s Theorem can be shown

• (x + y)’ = x’. y’

x y x+y (x+y)’ x' y' x'y'

0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0
 DeMorgan’s Theorem 5(b)

• (x. y)’ = x’ + y’

x y x+y xy x' y' (xy)' x’+y’

0 0 0 0 1 1 1 1
0 1 1 0 1 0 1 1
1 0 1 0 0 1 1 1
1 1 1 1 0 0 0 0
 Operator Precedence

• The operator precedence for evaluating Boolean expressions is:

1. Parentheses
2. NOT
3. AND
4. OR
 Boolean Functions
• A Boolean function is an expression described by:
– binary variables
– Constants or elements 0 and 1
– logic operation symbols
• For a given value of the binary variables the result of the
function can either be 0 or 1
• An example of Boolean function:
– F1 = x + y’z
– F1 is equal to 1 if x is equal to 1 or if both y’ and z equal to 1.
– F1 is equal to 0 otherwise
 Function as a Truth Table
• A Boolean function can be represented in a truth table
– A truth table is a list of combinations of 1’s and 0’s assigned
to the binary variables and a column that shows the value of
the function for each binary combination
 Function as a Gate Implementation
• A Boolean function can be transformed from algebraic expression into circuit diagram composed of logic gates
– F1 = x + y’z
– The logic-circuit diagram for this function is shown below
– The logic-circuit diagram is also called schematic
– The variables (x, y, z) are taken as inputs of the circuit and the Boolean function (F 1) is taken as the output
– In truth table the function F can be represented in only one way
– In algebraic form, same can be expressed in variety of ways
– Each algebraic form has equivalent logic circuits comprises of logic gates

– Boolean Algebra can help in simplifying the same expression and thus reducing the complexity of a circuit
by reducing the number of gates in the circuit and the number of inputs to the gates. This significantly
reducing the cost of the digital logic circuits
 Gate Implementation (Examples)

A A B C F
B 0 0 0 0
F 0 0 1 0
A 0 1 0 0
C F = AB + AC
0 1 1 0

B 1 0 0 0
C 1 0 1 1
F 1 1 0 1
A
F = A(B + C) 1 1 1 1
 Gate Implementation (Examples)

A
A B F
F
0 0 1
B F = A’ B’ 0 1 0

1 0 0
A 1 1 0
F
B
F = (A + B)’
 Minimization of Algebraic Expression
• Functions in algebraic form can be
represented in various ways P2 x+0 =x x1=x
– Remember the postulates and theorems p5 x+x‘ = 1 x x‘ = 0
that allows us to represent a function in T1 x+x=x xx=x
various ways T2 x+1=1 x0=0
• We must keep in mind that the algebraic T3 (x‘)’ = x
expression is representative of the gates and p3 x+y = y+x xy = yx
circuitry used in a hardware piece T4 x+(y+z)=(x+y)+z x(yz) =(xy)z
– We want to be able to minimize circuit P4 x(y+z)=xy+xz x+yz=(x+y)(x+z)
T5 (x+y)‘ =x’y‘ (xy)‘=x’+y‘
design to reduce cost, power
consumption, and package count, and to T6 x+xy = x x(x+y) =x
increase speed
• By manipulating a function using the
postulates and theorems, we may be able to
minimize an expression
 Non-Minimized F2
F2 = x’y’z+x’yz+xy’

where, F2= 1 when

xyz=001 or 011 or xy=10
F2 = 0 otherwise
contains 3 terms and 8
literals
x y z x’ y’ xy’ x’yz x’y’z F2
0 0 0 1 1 0 0 0 0
0 0 1 1 1 0 0 1 1
0 1 0 1 0 0 0 0 0
0 1 1 1 0 0 1 0 1
1 0 0 0 1 1 0 0 1
1 0 1 0 1 1 0 0 1
1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
 Minimization of F2
x’y’z + x’yz + xy’ = x’zy’+ x’zy + xy’
= x’z · (y’ + y) + xy’ by postulate:4(a)
= x’z · 1 + xy’ 5(a)
F2 = x’z + xy’ 2(b)

where, F2= 1 when xz=01 or xy=10

F2 = 0 otherwise x y z x’ y’ xy’ x’yz x’y’z F2
contains 2 terms and 4 literals 0 0 0 1 1 0 0 0 0
0 0 1 1 1 0 0 1 1
0 1 0 1 0 0 0 0 0
0 1 1 1 0 0 1 0 1
1 0 0 0 1 1 0 0 1
1 0 1 0 1 1 0 0 1
1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
Implementation of Boolean Function
• Since both truth tables produces
same 1’s for F2, they are equivalent

• The two logic circuits has the same

outputs for all possible
combinations of inputs

• Non-minimized F2 has 3 terms and

8 literals, 6 gates with 3 inputs,

• Minimized F2 has 2 terms and 4

literals, 5 gates with 2 inputs

• Circuit with fewer gates and fewer

inputs to the gates is preferable
because it requires fewer wires and
components
 Algebraic Manipulation
• For Boolean expression implemented with logic gates
– Each term requires a gate
– Each variable within the term designates an input to the gate
– Literal. A single variable within a term in complement or un-complement form
– F2 = x’y’z + x’yz + xy’ contains 3 terms and 8 literals
– F2 = x’z + xy’ contains 2 terms and 4 literals

• By reducing the number of terms, or the number of literals or both in a Boolean

function, it is possible to obtain a simpler circuit

• Map Method can simplify functions up to 5 variables

• Computer minimization algorithms (Quine-McCluskey or QM method) used to
optimize complex functions with millions of logic gates
• Manual methods “cut-and-try” uses basic postulates and theorems, is subject to
human error
 Example Manipulations
• The following are some example manipulations:

1. x(x’ + y) = xx’ + xy = 0 + xy = xy (2 terms, 3 literals to 1 term, 2 literal)

2. x + x’y = (x + x’)(x + y) = 1(x + y) = x + y (2 terms, 3 literals to 1 term, 2 literal)

3. (x + y)(x + y’) = x + xy + xy’ + yy’ = x(1 + y + y’) = x

4. xy + x’z + yz = xy + x’z + yz(x + x’)

= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y)
= xy + x’z

–Consensus Theorem. The consensus or resolvent of the expressions AB and A'C is

BC. It is the union of all the unique literals of the terms, except the literal, that occurs
unnegated in one term and negated in the other.
 Complement of a Function
• The complement of a function F is F’.
• Derived algebraically through DeMorgan’s theorem.
– Theorem 5(a) (DeMorgan): (x + y)’ = (x’ · y’)
– Theorem 5(b) (DeMorgan): (x · y)’ = (x’ + y’)
• DeMorgan’s Theorem can be extended to three / any number of variables
• If F1 = A+B+C
• Then F1’
=(A+B+C)'
= (A+X)’ let B+C = X
= A'X' by DeMorgan's (2 variable)
= A'(B+C)’ substitute X=B+C

= A'(B'C') by DeMorgan's (2 variable)

F1’= A'B'C' associative
(A+B+C)’ = A’B’C’
 Complement of a Function
• If F1 = A.B.C
• Then F1'
=(A.B.C)'
= (A.X) ‘ let B.C = X
= A'+X' by DeMorgan's (2 variable)
= A'+(B.C)’ substitute X=B.C
= A'+(B'+C’) by DeMorgan's (2 variable)
F1'= A'+B'+C' associative
(A.B.C)' = A'+B’+C’

• For any number of variables

(A+B+C+…+F)‘ = A’.B’.C’.….F’
(A.B.C…F)’ = A’+B’+C’+…+F’

• The complement of a function is obtained by interchanging “AND” & “OR” and

complement each literal
 Representation Conversion
• Need to transition between Boolean expression, truth table, and
circuit (symbols)
• Converting between truth table and expression is easy
• Converting between expression and circuit is easy
• More difficult to convert to truth table

Circuit Boolean
Expression

Truth
Table