Boolean Algebra

Chapter 12

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Chapter Summary Claude Shannon
Boolean Functions (1916 - 2001)
Representing Boolean Functions
Logic Gates
Minimization of Circuits
Boolean Functions
Section 12.1
Section Summary
Introduction to Boolean Algebra
Boolean Expressions and Boolean Functions
Identities of Boolean Algebra
The Abstract Definition of a Boolean Algebra
Introduction to Boolean Algebra
Boolean algebra has rules for working with elements from the
set {0, 1} together with the operators + (Boolean sum), 
(Boolean product), and .
These operators are defined by:
Boolean sum: 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0
Boolean product: 1  1 = 1, 1  0 = 0, 0  1 = 0, 0  0 = 0
complement: = 1, = 0
Example: Find the value of 1  0 +
Solution : 1  0 + = 0 +
=0+0
=0
Boolean Complement
The complement of a variable p is denoted by and has
this truth table:
p
1 0
0 1

6
Boolean Product
The Boolean product of variables p and q is denoted
by p . q and has this truth table:
p q p.q
0 1 1
0 0 0
1 1 0
1 0 0

7
Boolean Sum
The sum of variables p and q is denoted by p +q and
has this truth table:
p q p +q
1 1 1
1 0 1
0 1 1
0 0 0

8
Truth Tables
Construction of a truth table:
Rows
 Need a row for every possible combination of values for
the atomic variables.
Columns
Need a column for the compound statement (usually at
far right)
Need a column for the truth value of each expression
that occurs in the compound statement as it is built up.
 This includes the atomic variables

9
Example Truth Table
Construct a truth table for (x + y ) .
x y z x+y (x + y ) .
1 1 1 1 0 0
1 1 0 1 1 1
1 0 1 1 0 0
1 0 0 1 1 1
0 1 1 1 0 0
0 1 0 1 1 1
0 0 1 0 0 0
0 0 0 0 1 0

10
Problem
How many rows are there in a truth table with n
variables?

Solution: 2n.

Note that this means that with n variables, we can

construct 2n distinct (i.e., not equivalent) rows.

11
the rules of precedence
first, all complements are computed,
followed by all Boolean products,
followed by all Boolean sums.
Example:
Find the value of 1.0 +
1.0 + = 0 +
=0+0
=0
Boolean Expressions and Boolean Functions
Definition: Let B = {0, 1}. Then Bn = {(x1, x2, …, xn) | xi ∈ B
for 1 ≤ i ≤ n } is the set of all possible n-tuples of 0s and 1s.
The variable x is called a Boolean variable if it assumes values
only from B, that is, if its only possible values are 0 and 1. A
function from Bn to B is called a Boolean function of degree n.
Example: The function F(x, y) = x from the set of ordered
pairs of Boolean variables to the set {0, 1} is a Boolean
function of degree 2.
Boolean Expressions and Boolean Functions
(continued)
Example: Find the values of the Boolean function
represented by F(x, y, z) = xy +
Solution: We use a table with a row for each
combination of values of x, y, and z to compute the
values of F(x,y,z)
Boolean Expressions and Boolean Functions
(continued)
Definition: Boolean functions F and G of n variables are equal
if and only if F(b1, b2, …, bn)= G(b1, b2, …, bn) whenever b1, b2, …,
bn belong to B. Two different Boolean expressions that
represent the same function are equivalent.
Definition: The complement of the Boolean function F is the
function (x1, x2, …, xn) = .
Definition: Let F and G be Boolean functions of degree n. The
Boolean sum F + G and the Boolean product FG are defined by
(F + G)(x1, x2, …, xn) = (x1, x2, …, xn) + G(x1, x2, …, xn)
(FG)(x1, x2, …, xn) = (x1, x2, …, xn)G(x1, x2, …, xn)
 Boolean Functions
Example: How many different Boolean functions of
degree n are there?

Solution: By the product rule for counting, there are 2n

different n-tuples of 0s and 1s. Because a Boolean
function is an assignment of 0 or 1 to each of these
different n-tuples, by the product rule there are
different Boolean functions of degree n.

The example tells us that there are 16 different Boolean functions of degree two.
We display these in Table 3.
Equivalence of Boolean expressions
Two Boolean expressions e1 and e2 that represent
the exact same function are called equivalent.
Notation: e1  e2, or just e1 = e2.
Equivalence Example
Show that = .
To do this we represent the truth table for the two
expressions
x y x+y .
1 1 0 0 1 0 0
1 0 0 1 1 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 1

You can see that the last two columns are the same (Equivalent)
Identities of Boolean Algebra
Each identity can be proved using a
table.

All identities in Table 5, except for the

first and the last two come in pairs.
Each element of the pair is the dual of
the other (obtained by switching
Boolean sums and Boolean products
and 0’s and 1’s.

The Boolean identities correspond to the

identities of propositional logic (Section
1.3) and the set identities (Section 2.2).
Identities of Boolean Algebra
Example: Show that the distributive law
x(y + x) = xy + xz is valid.
Solution: We show that both sides of this identity
always take the same value by constructing this table.
De Morgan’s Laws
= +
= . Augustus De Morgan

This truth table shows that De Morgan’s First Law holds. 1806-1871

x y x.y +
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 0 1 1
0 0 1 1 0 1 1

21
Representing Boolean
Functions
Section 12.2
Section Summary
Sum-of-Products Expansions
Functional Completeness
Minterm
A minterm of Boolean variables x1,…,xn is a
Boolean product of n literals y1…yn, where yi is
either the literal, xi , or its complement, xi .
Sum-of-Products Expansions
Theorem: Any Boolean function can be represented
as a sum-of-products (SOP) of variables and their
complements

The Disjunctive Normal Form (DNF) of Boolean

function f, of a degree-n, is the unique sum of
minterms of the variables x1,…,xn that represents f.

A DNF is a sum-of-products representation

Sum-of-Products Expansion
Example: Find Boolean expressions that represent the
functions (i) F(x, y, z) and (ii) G(x, y, z) in Table 1.
Solution:
(i) To represent F, we need the one term x because this
expression has the value 1 when x = z = 1 and y = 0.
(ii) To represent the function G, we use the sum
xy + y because this expression has the value 1
when x = y = 1 and z = 0, or x = z = 0 and y = 1.
The general principle is that each combination of values of the variables
for which the function has the value 1 requires a term in the Boolean
sum that is the Boolean product of the variables or their complements.
Example
Find Boolean expressions that represent the functions
F(x,y,z) and G(x,y,z) in the following table
x y z F G
0 0 0 1 1
0 0 1 0 0
0 1 0 1 0
0 1 1 0 0
1 0 0 1 1
1 0 1 0 0
1 1 0 1 0
1 1 1 0 1
 Sum-of-Products Expansion (cont)
Definition:
 A literal is a Boolean variable or its complement.
 A minterm of the Boolean variables x1, x2, …, xn is a
Boolean product y1y2  yn , where yi = xi or yi = .
Hence, a minterm is a product of n literals, with one literal
for each variable.
The minterm y1, y2, …, yn has value 1 if and only if each xi is
1.This occurs if and only if xi = 1 when yi = xi and xi = 0 when
yi = .
Sum-of-Products Expansion (cont)
Example: Find a minterm that equals 1 if x1 = x3 = 0
and x2 = x4 = x5 = 1, and equals 0 otherwise.
Solution: The minterm x2 x4 x5 has the correct set of
values.
Examples
Find a Boolean product of the Boolean variables x and
y, or their complements, that has the value 1 if and
only if x=y=0
Solution:
Find a Boolean product of the Boolean variables x, y,
and z, or their complements, that has the value 1 if and
only if x=1,y=z=0
Solution: x
 Sum-of-Products Expansion (cont)
Example:
Find the sum-of-products expansion for the function F(x,y,z) = (x + y) .
Solution:
We use two methods, first using a table and second using Boolean identities.
(i) Form the sum of the minterms corresponding to each row of the table that has
the value 1. Including a term for each row of the table for which F(x,y,z) = 1 gives us
F(x, y, z) = xy + x + y
(ii) We now use Boolean identities to find the disjunctive normal form of F(x,y,z):
F(x,y,z) = (x + y)
= x + y distributive law
= x1 + 1y identity law
= x(y + ) + (x + )y unit property
= xy + x + xy + y distributive law
= xy + x + y idempotent law
Maxterm
A maxterm of Boolean variables x1,…,xn is a
Boolean sum of n literals y1…yn, where yi is either
the literal, xi , or its complement, xi .
Product-of-sums (POS) expansion
Conjunctive Normal Form (CNF)

The Conjunctive Normal Form (CNF) of Boolean

function f, of a degree-n, is the unique product of
maxterms of the variables x1,…,xn that represents f.

A CNF is a product-of-sums representation

product-of-sums expansion
A maxterm of Boolean variables x1, x2, …, xn is a Boolean sum of
n literals y1y2  yn where yi is either the literal, xi , or its
complement, xi .

Hence, a maxterm is a sum of n literals, with one literal for each

variable.
The maxterm y1, y2, …, yn has value 0 if and only if each xi is
0.This occurs if and only if xi = 0 when yi = xi and xi = 1 when yi =
.
product-of-sums expansion
To get the CNF representation for f:
Compute the DNF (SOP) representation for
complement f,
Then complementing the DNF of f yields the
CNF (POS) of   f=f
 Functional Completeness
Definition: Because every Boolean function can be represented using the
Boolean operators , +, and , we say that the set {, + , } is functionally
complete.
The set {, } is functionally complete since x + y = .
The set {+, } is functionally complete since xy = .
The nand operator, denoted by |, is defined by 1|1 = 0, and
1|0 = 0|1 = 0|0 = 1. The set consisting of just the one operator nand {|} is
functionally complete. Note that = x | x and xy = (x|y)|(x|y).

The nor operator, denoted by ↓, is defined by 0 ↓ 0 = 1, and

1 ↓ 0 = 0 ↓ 1 = 1 ↓ 1 = 0. The set consisting of just the one operator nor {↓} is
functionally complete. (see Exercises 15 and 16 for proof)
Logic Gates
Section 12.3
Section Summary
Logic Gates
Combinations of Gates
Examples of Circuits
Logic Gates
We construct circuits using gates, which take as input
the values of two or more Boolean variables and
produce one or more bits as output, and inverters,
which take the value of a Boolean variable as input and
produce the complement of this value as output.
Logic Gates symbols
Inverter
Corresponds to the logical Negation, or Boolean
complement

40
Logic Gates symbols
AND gate
Corresponds to the logical conjunction, or Boolean product

41
Logic Gates symbols
OR gate
Corresponds to the logical disjunction, or Boolean sum

42
Logic Gates symbols
XOR gate
Corresponds to the logical exclusive disjunction, or sum
mod 2

43
Logic Gates symbols
NAND gate
AND gate which output is complemented

44
Logic Gates symbols
NOR gate
OR gate which output is complemented

45
Logic Gates symbols
XNOR gate
XOR gate which output is complemented

46
Combinations of Gates
Combinatorial circuits can be constructed using a
combination of inverters, OR gates, and AND gates.
Gates may share input and the output of one or more
gates may be input to another.
We show two ways of
constructing a circuit
that produces the
output xy + y.
Combinations of Gates
Example: Construct
circuits that produce
these outputs
(a) (x + y)
(b)
(c) (x + y +z)()
Minimization of Circuits
Section 12.4
Goals of Circuit Minimization
(1) Minimize the number of primitive Boolean logic
gates needed to implement the circuit.
Ultimately, this also roughly minimizes the number of
transistors, the chip area, and the cost.
 Also roughly minimizes the energy expenditure.
This will be our focus.
(2) It is also often useful to minimize the number of
combinational stages or logical depth of the circuit.
This roughly minimizes the delay or latency through the
circuit, the time between input and output.
Minimizing Circuits
Karnaugh Maps
Gray code
Code that modifies only
one bit per line
Patented by Frank Gray in x y
1953 (submitted in 1947) 0 0
The code was known 0 1 Mirror
before 1 1
1 0
Gray code
x y z
0 0 0
0 0 1
0 1 1
0 1 0 Mirror
1 1 0
1 1 1
1 0 1
1 0 0
K-map for 2 variables

x\y 0 1
0 f(0, 0) f(0,1)

1 f(1, 0) f(1,1)
K-map for 2 variables
Example

x y f
x\y 0 1
0 0 1
0 1 0
0 1 0
1 1 1
1 1 1
1 0 1 K-Map
Truth table
K-map for 3 variables

x\yz 00 01 11 10
0 f(0,0,0) f(0,0,1) f(0,1,1) f(0,1,0)

1 f(1,0,0) f(1,0,1) f(1,1,1) f(1,1,0)

K-map for 3 variables
Example

x y z f
0 0 0 1
x\yz 00 01 11 10
0 0 1 1
0 1 1 1 1
0 1 1 1
0 1 0 1 1 0 0 1 0
1 1 0 0
1 1 1 1 K-Map
1 0 1 0
1 0 0 0
Truth table
Expression of f
Using truth table

x y z f
0 0 0 1 ++
0 0 1 1 +
0 1 1 1
0 1 0 1
1 1 0 0
x\yz 00 01 11 10
1 1 1 1
0 1 1 1 1
1 0 1 0
1 0 0 0 1 0 0 1 0
Truth table
Expression of f
Simplification using K-Map

x\yz 00 01 11 10
 Find rectangles of adjacent
0 1 1 1 1
1
1 0 0 1 0  Sideof the rectangle should
be a power of 2
Expression of f
Simplification using K-Map

x\yz 00 01 11 10
 Theborder of the map are
0 1 0 0 1 adjacent
1 1 0 0 1
Example
K-map for 4 variables
Example

F(w,x,y,z) = + + w x +

wx\yz 00 01 11 10
00 1

01 1 1

11 1 K-Map
10 1
Examples

Is this correct?
Examples

 Use K-maps to simplify these sum-of-products expansions