Boolean Algebra

© IT - TDT Boolean Algebra 2

Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck
Choy for kindly sharing these materials.
© IT - TDT Boolean Algebra 3

Policies for students

• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these
contents to anywhere or anyone for any purpose.
© IT - TDT Boolean Algebra 4

Recording of modifications
• Minor change in slide 13 (replace new picture)
• Currently, there are no modification on these contents.
CS2100 Boolean Algebra 5

WHERE ARE WE NOW?

• Number systems and codes Preparation: 2 weeks
• Boolean algebra
• Logic gates and circuits
• Simplification Logic Design: 3 weeks
• Combinational circuits
• Sequential circuits
• Performance
• Assembly language
• The processor: Datapath and control Computer
organisation
• Pipelining
• Memory hierarchy: Cache
• Input/output
CS2100 Boolean Algebra 6

CHECK LIST
• Have you done the Quick Review Questions for
Chapter 2 Number Systems and Code?
• Have you attempted the Self-Assessment
Exercise #1 on IVLE Assessment?
• Have you clarified your doubts on IVLE forum?
• Ready to do a pop quiz?
CS2100 Boolean Algebra 7

BOOLEAN ALGEBRA
• Boolean Algebra
• Precedence of Operators
• Truth Table
• Duality
• Basic Theorems
• Complement of Functions
• Standard Forms
• Minterms and Maxterms
• Canonical Forms
CS2100 Boolean Algebra 8

DIGITAL CIRCUITS (1/2)

• Two voltage levels
• High, true, 1, asserted
• Low, false, 0, deasserted

High

Low

Signals in digital circuit Signals in analog circuit

A digital watch
CS2100 Boolean Algebra 9

DIGITAL CIRCUITS (2/2)

• Advantages of digital circuits over analog circuits
• More reliable (simpler circuits, less noise-prone)
• Specified accuracy (determinable)
• Abstraction can be applied using simple mathematical
model – Boolean Algebra
• Ease design, analysis and simplification of digital circuit
– Digital Logic Design
CS2100 Boolean Algebra 10

TYPES OF LOGIC BLOCKS

• Combinational: no memory, output depends
solely on the input
• Gates
• Decoders, multiplexers
• Adders, multipliers

• Sequential: with memory, output depends on both

input and current state
• Counters, registers
• Memories
CS2100 Boolean Algebra 11

BOOLEAN ALGEBRA
• Boolean values: n Truth tables
• True (1) A B A×B A B A+B A A'
• False (0) 0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
• Connectives
1 0 0 1 0 1
• Conjunction (AND)
1 1 1 1 1 1
• A × B; A Ù B
• Disjunction (OR)
n Logic gates
• A + B; A Ú B
A
• Negation (NOT) A×B
B
• ;A¬A; A' A A'
A
A+B
B
CS2100 Boolean Algebra 12

AND (∙)
• Do write the AND operator ∙ instead of omitting it.
• Example: Write a∙b instead of ab
• Why? Writing ab could mean it is a 2-bit value.
CS2100 Boolean Algebra 13

LAWS OF BOOLEAN ALGEBRA

• Identity laws
A+0=0+A=A; A×1=1×A=A

• Inverse/complement laws
A + A' = 1 ; A × A' = 0

• Commutative laws
A+B=B+A; A×B=B×A

• Associative laws
A + (B + C) = (A + B) + C ; A × (B × C) = (A × B) × C

• Distributive laws
A × (B + C) = (A × B) + (A × C) ; A + (B × C) = (A + B) × (A + C)
CS2100 Boolean Algebra 14

PRECEDENCE OF OPERATORS
• Precedence from highest to lowest
• Not
• And
• Or

• Examples:
• A × B + C = (A × B) + C
• X + Y' = X + (Y')
• P + Q' × R = P + ((Q') × R)

• Use parenthesis to overwrite precedence. Examples:

• A × (B + C)
• (P + Q)' × R
CS2100 Boolean Algebra 15

TRUTH TABLE
• Provide a listing of every
possible combination of x y z y+z x × (y + z)

inputs and its 0 0 0 0 0

0 0 1 1 0
corresponding outputs.
0 1 0 1 0
• Inputs are usually listed in
binary sequence. 0 1 1 1 0
1 0 0 0 0
• Example 1 0 1 1 1
• Truth table with 3 inputs and 2 1 1 0 1 1
outputs 1 1 1 1 1
 CS2100 Boolean Algebra 16

PROOF USING TRUTH TABLE

• Prove: x × (y + z) = (x × y) + (x × z)
• Construct truth table for LHS and RHS

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

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

q Check that column for LHS = column for RHS

±
CS2100 Boolean Algebra 17

DUALITY
• If the AND/OR operators and identity elements 0/1 in a
Boolean equation are interchanged, it remains valid
• Example:
• The dual equation of a+(b×c)=(a+b)×(a+c) is a×(b+c)=(a×b)+(a×c)

• Duality gives free theorems – “two for the price of one”.

You prove one theorem and the other comes for free!
• Examples:
• If (x+y+z)' = x'×y'×z' is valid, then its dual is also valid:
(x×y×z)' = x'+y'+z'
• If x+1 = 1 is valid, then its dual is also valid:
x×0 = 0
CS2100 Boolean Algebra 18

BASIC THEOREMS (1/2)

1. Idempotency
X+X=X; X×X=X

2. Zero and One elements

X+1=1; X×0=0

3. Involution
( X' )' = X

4. Absorption
X + X×Y = X ; X×(X + Y) = X

5. Absorption (variant)
X + X'×Y = X + Y ; X×(X' + Y) = X×Y
CS2100 Boolean Algebra 19

BASIC THEOREMS (2/2)

6. DeMorgan’s
(X + Y)' = X' × Y' ; (X × Y)' = X' + Y'
DeMorgan’s Theorem can be generalised to more than two
variables, example: (A + B + … + Z)' = A' × B' × … × Z'

7. Consensus
X×Y + X'×Z + Y×Z = X×Y + X'×Z
(X+Y)×(X'+Z)×(Y+Z) = (X+Y)×(X'+Z)
CS2100 Boolean Algebra 20

PROVING A THEOREM
• Theorems can be proved using truth table, or by algebraic
manipulation using other theorems/laws.
• Example: Prove absorption theorem X + X×Y = X
X + X×Y = X×1 + X×Y (by identity) = X×(1+Y) (by distributivity)
= X×(Y+1) (by commutativity) = X×1 (by one element)
= X (by identity)

• By duality, we have also proved X×(X+Y) = X

 CS2100 Boolean Algebra 21

BOOLEAN FUNCTIONS
• Examples of Boolean functions (logic equations):
F1(x,y,z) = x×y×z'
x y z F1 F2 F3 F4
F2(x,y,z) = x + y'×z 0 0 0 0
F3(x,y,z) = x'×y'×z + x'×y×z + x×y' 0 0 1 0
F4(x,y,z) = x×y' + x'×z 0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

±
 CS2100 Boolean Algebra 22

COMPLEMENT
• Given a Boolean function F, the complement of F, denoted
as F', is obtained by interchanging 1 with 0 in the
function’s output values.
• Example: F1 = x×y×z' x y z F1 F1'
0 0 0 0
• What is F1' ?
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

±
CS2100 Boolean Algebra 23

STANDARD FORMS (1/2)

• Certain types of Boolean expressions lead to circuits that
are desirable from implementation viewpoint.
• Two standard forms:
• Sum-of-Products
• Product-of-Sums

• Literals
• A Boolean variable on its own or in its complemented form
• Examples: x, x', y, y'

• Product term
• A single literal or a logical product (AND) of several literals
• Examples: x, x×y×z', A'×B, A×B, d×g'×v×w
CS2100 Boolean Algebra 24

STANDARD FORMS (2/2)

• Sum term
• A single literal or a logical sum (OR) of several literals
• Examples: x, x+y+z', A'+B, A+B, c+d+h'+j

• Sum-of-Products (SOP) expression

• A product term or a logical sum (OR) of several product terms
• Examples: x, x + y×z', x×y' + x'×y×z, A×B + A'×B',
A + B'×C + A×C' + C×D

• Product-of-Sums (POS) expression

• A sum term or a logical product (AND) of several sum terms
• Examples: x, x×(y+z'), (x+y')×(x'+y+z),
(A+B)×(A'+B'), (A+B+C)×D'×(B'+D+E')
• Every Boolean expression can be expressed in SOP or
POS.
 CS2100 Boolean Algebra 25

DO IT YOURSELF
SOP expr: A product term or a logical sum (OR) of several product terms.
POS expr: A sum term or a logical product (AND) of several sum terms.
• Put the right ticks in the following table.
Expression SOP? POS?

X'∙Y + X∙Y' + X∙Y∙Z

(X+Y')∙(X'+Y)∙(X'+Z')

X' + Y + Z

X∙(W' + Y∙Z)

X∙Y∙Z'

W∙X'∙Y + V∙(X∙Z + W')

±
CS2100 Boolean Algebra 26

MINTERMS & MAXTERMS (1/2)

• A minterm of n variables is a product term that
contains n literals from all the variables.
• Example: On 2 variables x and y, the minterms are:
x'∙y', x'∙y, x∙y' and x∙y
• A maxterm of n variables is a sum term that
contains n literals from all the variables.
• Example: On 2 variables x and y, the maxterms are:
x'+y', x'+y, x+y' and x+y
• In general, with n variables we have 2n minterms
and 2n maxterms.
CS2100 Boolean Algebra 27

MINTERMS & MAXTERMS (2/2)

• The minterms and maxterms on 2 variables are denoted
by m0 to m3 and M0 to M3 respectively.
Minterms Maxterms
x y
Term Notation Term Notation
0 0 x'∙y' m0 x+y M0
0 1 x'∙y m1 x+y' M1
1 0 x∙y' m2 x'+y M2
1 1 x∙y m3 x'+y' M3
n Each minterm is the complement of the corresponding
maxterm
q Example: m2 = x∙y'
m2' = ( x∙y' )' = x' + ( y' )' = x' + y = M2
CS2100 Boolean Algebra 28

CANONICAL FORMS
• Canonical/normal form: a unique form of
representation.
• Sum-of-minterms = Canonical sum-of-products
• Product-of-maxterms = Canonical product-of-sums
 CS2100 Boolean Algebra 29

SUM-OF-MINTERMS
• Given a truth table, example: x y z F1 F2 F3
0 0 0 0 0 0
0 0 1 0 1 1
n Obtain sum-of-minterms 0 1 0 0 0 0
expression by gathering the 0 1 1 0 0 1
minterms of the function 1 0 0 0 1 1
(where output is 1). 1 0 1 0 1 1
1 1 0 1 1 0
F1 = x∙y∙z' = m6
1 1 1 0 1 0
F2 =

F3 =

±
 CS2100 Boolean Algebra 30

PRODUCT-OF-MAXTERMS
• Given a truth table, example: x y z F1 F2 F3
0 0 0 0 0 0
0 0 1 0 1 1
n Obtain product-of-maxterms 0 1 0 0 0 0
expression by gathering the 0 1 1 0 0 1
maxterms of the function 1 0 0 0 1 1
(where output is 0). 1 0 1 0 1 1
1 1 0 1 1 0
1 1 1 0 1 0
F2 = (x+y+z) ∙ (x+y'+z) ∙ (x+y'+z')
= M0 ∙ M2 ∙ M3 = PM(0,2,3)

F3 =

±
CS2100 Boolean Algebra 31

CONVERSION
• We can convert between sum-of-minterms and x y z F2 F2'
product-of-maxterms easily 0 0 0 0 1
• Example: F2 = Sm(1,4,5,6,7) = PM(0,2,3)
0 0 1 1 0
• Why? See F2' in truth table.
0 1 0 0 1
0 1 1 0 1
n F2' = m0 + m2 + m3
Therefore, 1 0 0 1 0
F2 = (m0 + m2 + m3)' 1 0 1 1 0
= m0' ∙ m2' ∙ m3' (by DeMorgan’s)
1 1 0 1 0
= M0 ∙ M2 ∙ M3 (mx' =Mx)
1 1 1 1 0
CS2100 Boolean Algebra 32

READING ASSIGNMENT
• Conversion of Standard Forms
• Read up DLD section 3.4, pg 57 – 58.
© IT - TDT Number Systems Supplementary Notes 33

Q&A