Imam Abdulrahman Bin Faisal University

College of Computer Science & IT

Department of CS
Term 2181

Welcome to
CS 314: Digital Hardware

Chapter#2: Boolean Algebra and Logic

Gates

Mehwash Farooqui mfarooqui@[Link]

1
 Algebras
 What is an algebra?
 Mathematical system consisting of
• Set of elements
• Set of operators
• Axioms or postulates
 Why is it important?
 Defines rules of “calculations”
 Example: arithmetic on natural numbers
 Set of elements: N = {1,2,3,4,…}
 Operator: +, –, *
 For example: consider a*b = c and * is a binary operator.
 Axioms: associativity, distributivity, closure, identity elements, etc.
 Note:
 Operators with two inputs are called binary
 Operators with one input are called unary
2
 George Boole
Father of Boolean algebra
• He came up with a type of linguistic algebra, the three most
basic operations of which were (and still are) AND, OR and
NOT. 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.

• Boole’s system (detailed in his 'An Investigation of the Laws

of Thought, on Which Are Founded the Mathematical
Theories of Logic and Probabilities', 1854) was based on a
binary approach, processing only two objects - the yes-no,
true-false, on-off, zero-one approach.
George Boole (1815 - 1864)
• Surprisingly, given his standing in the academic community,
Boole's idea was either criticized or completely ignored by
the majority of his peers.

• Eventually, one bright student, Claude Shannon (1916-

2001), picked up the idea and ran with it

3
 Basic Definitions
• Terminology:
 Literal: A variable or its complement
 Product term: literals connected by •
 Sum term: literals connected by +

• Binary Operators
 AND
z=x•y=xy
 OR
z=x+y
 NOT
 z = x = x’

4
 Boolean Algebra Postulates

Huntington postulates

Post. 1: (a) x+0=x (b) x·1=x Identity

Post. 2: (a) x+x’=1 (b) x·x’=0 Complement
Post. 3: (a) x+y=y+x, (b) x·y=y·x Commutative
Post. 4: (a) x.(y+z) = x.y+x.z (b) x+y.z = (x+y).(x+z) Distributive
Post. 5: (a) x+(y+z)= (x+y)+z (b) x·(y.z)= (x.y).z Associative

5
 Boolean Algebra Theorems
• Duality
– The dual of a Boolean algebraic expression is obtained
by interchanging the AND and the OR operators and
replacing the 1’s by 0’s and the 0’s by 1’s.
– x•(y+z)=(x•y)+(x•z)
– x+(y•z)=(x+y)•(x+z)
Applied to a valid
equation produces
a valid equation
• Theorem 1
– x•x=x x+x=x
• Theorem 2
– x•0=0 x+1=1
6
 Boolean Algebra Theorems
 Theorem 3: Involution

( x’ )’ = x (x)=x

 Theorem 4: Associative & Distributive


(x • y ) • z = x • ( y • z ) (x + y ) + z = x + (y + z )

x•(y+z)=(x•y)+(x•z) x + (y • z ) = ( x + y ) • ( x + z )

 Theorem 5: DeMorgan

( x • y )’ = x’ + y’ (x + y )’ = x’ • y’

 Theorem 6: Absorption

x•(x+y)=x x+(x•y)=x

7
 Proof of Distributive Theorem
By means of truth table
y x ． (y + (x ． y) + (x ．
x y z x．y x．z
+z z) z)
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1

8
 Operator Precedence

• Parentheses x [ y  z ( w  x )]
(...)•(...)
( w  x)
• NOT
x’ + y ( w  x)
• AND z ( w  x)
x+x•y y  z ( w  x)
• OR
x [ y  z ( w  x )]

9
 DeMorgan’s Theorem
• Theorem 5(a): (x + y)’ = x’y’
• Theorem 5(b): (xy)’ = x’ + y’
• By means of truth table

x y x’ y’ x+y (x+y) x’y’ xy x’+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

10
DeMorgan’s Theorem

a [b  c (d  e )]

a  [b  c (d  e )]
a  b (c ( d  e ))

a  b (c  (d  e ))
a  b (c  (d e))
a  b (c  d e)
11
Basic Theorems

12
 Algebraic Manipulation

• Literal: A single variable within a term that may be

complemented or not.
• Use Boolean Algebra to simplify Boolean functions to
produce simpler circuits

Example: Simplify to a minimum number of literals.

F = x + x’ y ( 3 Literals)
= x + ( x’ y )
= ( x + x’ ) ( x + y )
Distributive law (+ over •)
=(1)(x+y)
=x+y ( 2 Literals)

13
 Complement of a Function
• DeMorgan’s Theorm
F A  B  C
F A  B  C
F A  B  C
• Duality & Literal Complement
F A  B  C

F A  B  C 14
 Boolean Functions
Example 2.1

x(x'+y) = xx' + xy
= 0+xy = xy
x+x’y = (x+x')(x+y)
= 1 (x+y) = x+y
(x+y)(x+y’) = x+xy+xy'+yy’
= x(1+y+y') = x
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
15
 Boolean Functions

• Boolean Expression x y z F
0 0 0 0
Example: F = x + y’ z
0 0 1 1
• Truth Table
0 1 0 0
All possible combinations 0 1 1 0
of input variables
1 0 0 1
• Logic Circuit 1 0 1 1
x F 1 1 0 1
y
z 1 1 1 1

16
 Combinational Logic Circuit
from Logic Function
• Consider function F = A’ + B•C’ + A’•B’
• A combinational logic circuit can be constructed to implement F, by
appropriately connecting input signals and logic gates:
– Circuit input signals  from function variables (A, B, C)
– Circuit output signal  function output (F)
– Logic gates  from logic operations

A F

17
Boolean Functions

18
 Standard Forms:
Two types: SOP & POS
• Sum of Products (SOP)
F BC  A B  AC

• Product of Sums (POS)

F ( A  C )( A  B )( B  C )

19
 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.
– n variables con be combined to form 2n minterms.
• A maxterm (standard sums): an OR term
– It is also call a standard sum.
– 2n maxterms.

Note: Each maxterm is the complement of its corresponding minterm, and vice versa.
20
 Conversion of SOP from standard to
canonical form and find minterms

• Expand non-canonical terms by inserting

equivalent of 1 in each missing variable x:
(x + x’) = 1
• Remove duplicate minterms
f1(x,y,z) = xy + xz’ = xy (z+z’) + x(y+y’)z’
= xyz + xyz’ + xyz’ + xy’z’
= xyz + xyz’ + xy’z’
= 111 + 110 + 100
= m7+m6+m4 = ∑ m(4,6,7)

21
 Canonical Forms
Two types: SOP & POS
A B C Minterm
• Minterm (Canonical SOP) 0 0 0 0 m0 ABC
– Product (AND function) 1 0 0 1 m1 ABC
– Contains all variables 2 0 1 0 m2 ABC
– Evaluates to ‘1’ for a 3 0 1 1 m3 ABC
specific combination 4 1 0 0 m4 ABC
5 1 0 1 m5 ABC
6 1 1 0 m6 ABC
7 1 1 1 m7 ABC

22
 Canonical Forms
• Truth Table to Boolean Function
A B C F F  A BC  A BC  A BC  ABC
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 0
1 1 1 1
23
 Conversion of POS from standard to
canonical form and find maxterms
• Expand noncanonical terms by adding 0 in terms of missing
variables (e.g., xx’ = 0) and using the distributive law.
• Remove duplicate maxterms
f1(x,y,z) = x•(y+z’)
= (x+yy’)•(xx’+y+z’)
= (x+y+zz’)•(x+y’+zz’)•(x+y+z’)•(x’+y+z’)
= (x+y+z)•(x+y+z’).(x+y’+z).(x+y’+z’)•(x+y+z’)•(x’+y+z’)
= (000). (001). (010). (011). (001). (101)
= M0.M1.M2.M3.M5
= ∏(0,1,2,3,5)

24
 Canonical Forms

• Maxterm (Canonical POS) A B C Maxterm

– Sum (OR function) 0 0 0 0 M0 A  B  C
– Contains all variables 1 0 0 1 M1 A  B  C
– Evaluates to ‘0’ for a 2 0 1 0 M2 A  B  C
specific combination 3 0 1 1 M3 A  B  C
4 1 0 0 M4 A  B  C
5 1 0 1 M5 A  B  C
6 1 1 0 M6 A  B  C
7 1 1 1 M7 A  B  C

25
 Canonical Forms
Example: Obtain the canonical sum of product form of the
following function.
F (A, B, C) = A + BC

Solution:
F (A, B, C) = A + BC
= A (B + B′) (C + C′) + BC (A + A′)
= (AB + AB′) (C + C′) + ABC + A′BC
= ABC + AB′C + ABC′ + AB′C′ + ABC + A′BC
= ABC + AB′C + ABC′ + AB′C′ + A′BC

Hence the canonical sum of the product expression of the

given function is
Answer: F (A, B,C) = ABC + AB′C + ABC′ + AB′C′ + A′BC.
26
 Conversion Between Canonical
Forms
• Interchange the symbols ∑ and ∏ and list those numbers
missing from the original form.
• Example:
f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’
= m1 + m2 + m4 + m6
= ∑(1,2,4,6)
= ∏(0,3,5,7)
= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)
= M0 + M 3 + M 5 + M 6

27
Conversion between Canonical forms
Example 2.5: Express the Boolean function F = xy + x’z as a product of
maxterms.

28
 Canonical Forms
• Sum of Minterms A B C F
F  A BC  A BC  A BC  ABC 0 0 0 0 0
F m1  m4  m5  m7 1 0 0 1 1
F  (1,4,5,7) 2 0 1 0 0
3 0 1 1 0
• Product of Maxterms 4 1 0 0 1
5 1 0 1 1
6 1 1 0 0
F  (0,2,3,6) 7 1 1 1 1

F M 0 M2 M3 M6
F ( A  B  C )( A  B  C )( A  B  C )( A  B  C ) 29
 Two - Level Implementations
B’
• Sum of Products (SOP) C

F BC  A B  AC A
B’ F
A
C
• Product of Sums (POS) A
C
A
F ( A  C )( A  B )( B  C ) B’ F
B’
C
30
 Logic Operators

• AND x y AND
x x•y 0 0 0
y 0 1 0
1 0 0
1 1 1

• NAND (Not AND)

x y NAND
0 0 1
x x•y 0 1 1
y
1 0 1
1 1 0

31
 Logic Operators
• OR x y OR
x x+y 0 0 0
y 0 1 1
1 0 1
1 1 1

• NOR (Not OR)

x y NOR
0 0 1
x x+y 0 1 0
y
1 0 0
1 1 0

32
 Logic Operators

• XOR (Exclusive-OR) x y XOR

x 0 0 0
xÅ y 0 1 1
y xy+xy 1 0 1
1 1 0

• XNOR (Exclusive-NOR) x y XNOR

(Equivalence) 0 0 1
0 1 0
x xÅ y xy+xy 1 0 0
y x y 1 1 1

33
 Logic Operators

• NOT (Inverter) x NOT

x x 0 1

1 0

• Buffer x Buffer

0 0
x x
1 1

34
 Homework
M. Morris Mano
– Chapter 2
• 2-4
• 2-5
• 2-6
• 2-8
• 2-9
• 2-10
• 2-12
• 2-15
• 2-18
• 2-19
35
 Homework
M. Morris Mano
2-4 Reduce the following Boolean expressions to the indicated
number of literals:
(a) A’C’ + ABC + AC’ to three literals
(b) (x’y’ + z)’ + z + xy + wz to three literals
(c) A’B (D’ + C’D) + B (A + A’CD) to one literal
(d) (A’ + C) (A’ + C’) (A + B + C’D) to four literals

2-5 Find the complement of F = x + yz; then show that

FF’ = 0 and F + F’ = 1

36
 Homework
2-6 Find the complement of the following expressions:
(a) xy’ + x’y (b) (AB’ + C)D’ + E
(c) (x + y’ + z) (x’ + z’) (x + y)

2-8 List the truth table of the function:

F = xy + xy’ + y’z
2-9 Logical operations can be performed on strings of bits by
considering each pair of corresponding bits separately (this is
called bitwise operation). Given two 8-bit strings
A = 10101101 and B = 10001110, evaluate the 8-bit result
after the following logical operations: (a) AND, (b) OR, (c)
XOR, (d) NOT A, (e) NOT B.

37
 Homework
2-10 Draw the logic diagrams for the following Boolean
expressions:
(a) Y = A’B’ + B (A + C) (b) Y = BC + AC’
(c) Y = A + CD (d) Y = (A + B) (C’ + D)

2-12 Simplify the Boolean function T1 and T2 to a minimum

number of literals. A B C T T
1 2

0 0 0 1 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 0 1
38
 Homework
2-15 Given the Boolean function
F = xy’z + x’y’z + w’xy + wx’y + wxy
(a) Obtain the truth table of the function.
(b) Draw the logic diagram using the original Boolean
expression.
(c) Simplify the function to a minimum number of literals
using Boolean algebra.
(d) Obtain the truth table of the function from the
simplified expression and show that it is the same as
the one in part (a)
(e) Draw the logic diagram from the simplified expression
and compare the total number of gates with the
diagram of part (b).

39
 Homework
2-18 Convert the following to the other canonical form:
(a) F (x, y, z) = ∑ (1, 3, 7)
(b) F (A, B, C, D) = ∏ (0, 1, 2, 3, 4, 6, 12)

2-19 Convert the following expressions into sum of products and

product of sums:
(a) (AB + C) (B + C’D)
(b) x’ + x (x + y’) (y + z’)

40