Digital Logic Design

Chapter 2

Boolean functions

Digital Logic Design

 2.5 Boolean Functions
 Binary variables can take two values, either 0 or 1.
 A Boolean function is an algebraic expression consists of
 Binary variables
 Binary operators OR and AND

 Unary operator NOT

 Parentheses and Equal sign

 Examples
 F1= x y z'

 F2 = x + y'z
 F3 = x' y' z + x' y z + x y'
 F4 = x y' + x' z

Digital Logic Design

2
 Boolean Functions represented in a
truth trable
 The truth table of 2n entries (n=number of variables)

x y z F1 F2 F3 F4
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 0 0 0 0
0 1 1 0 0 1 1
1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 0
 Two Boolean expressions may specify the same function
 F3 = F4

Digital Logic Design

3
 Boolean Functions
 Implementation with logic gates
 F4 is more economical

F2 = x + y'z

F3 = x' y' z + x' y z + x y'

F4 = x y' + x' z

Digital Logic Design

4
 Algebraic Manipulation
 When a Boolean expression is implemented with logic gates, each
term requires a gate and each variable within the term designates
an input to the gate.
 To minimize Boolean expressions, minimize the number of
variables and the number of terms → results in a circuit with less
equipment
 It is a hard problem (no specific rules to follow)

 Example 2.1
1. x(x'+y) =
2. x+x'y =
3. (x+y)(x+y') =
4. xy + x'z + yz =
5. (x+y)(x'+z)(y+z) =

Digital Logic Design

5
 Algebraic Manipulation
 Example 2.1
1. x(x'+y) = xx' + xy = 0+xy = xy
2. x+x'y = (x+x')(x+y) = 1 (x+y) = x+y
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 + yzx + yzx' = xy(1+z) +
x'z(1+y) = xy +x'z
5. (x+y)(x'+z)(y+z) = (x+y)(x'+z), by duality from function 4.

 Function 1 and 2 are duals of each other and function 2 can be derived
from the dual of the steps of function 1.
 Function 4 and 5 are duals of each other and function 5 can be derived
from the dual of the steps of function 4.

Digital Logic Design

6
 Complement of a Function
 Complement of a function F is F'
 Obtained from an interchange of 0's for 1's and 1's for 0's
in the value of F from the truth table.
 Algebraically complement is obtained by De Morgan's
theorem
 Ex:(A+B+C)' = (A+X)' let B+C = X
= A'X' by theorem 5(a) (DeMorgan's)
= A'(B+C)' substitute B+C = X
= A'(B'C') by theorem 5(a)
(DeMorgan's)
= A'B'C' by theorem 4(b) (associative)

Digital Logic Design

7
 Complement of a Function
 Generalization: a function is obtained by interchanging
AND and OR operators and complementing each literal.
 (A+B+C+D+ ... +F)' = A'B'C'D'... F'
 (ABCD ... F)' = A'+ B'+C'+D' ... +F'

Digital Logic Design

8
 Examples
 Example 2.2
 F1' = (x'yz' + x'y'z)' = (x'yz')' (x'y'z)' = (x+y'+z) (x+y+z')
 F2' = [x(y'z'+yz)]' = x' + (y'z'+yz)' = x' + (y'z')' (yz)‘
= x' + (y+z) (y'+z')
= x' + yz‘+y'z
 Example 2.3: a simpler procedure
 Take the dual of the function and complement each literal
1. F1 = x'yz' + x'y'z.
The dual of F1 is (x'+y+z') (x'+y'+z).
Complement each literal: (x+y'+z)(x+y+z') = F1'
2. F2 = x(y' z' + yz).
The dual of F2 is x+(y'+z') (y+z).
Complement each literal: x'+(y+z)(y' +z') = F2'

Digital Logic Design

9
 2.6 Canonical and Standard Forms
Minterms and Maxterms
 A minterm (standard product): A product term containing all n variables
of the function in either true or complemented form is called the
minterm.
 For example, two binary variables x and y, has 4 minterms
» xy, xy', x'y, x'y'
 It is also called a standard product.

 n variables can be combined to form 2n minterms.

 A maxterm (standard sums): A sum term containing all n variables of the

function in either true or complemented form is called the maxterm.
 It is also call a standard sum.

 2n maxterms.

 For example, two binary variables x and y, has 4 minterms

» x+y, x+y', x'+y, x'+y'
Digital Logic Design
10
 Minterms and Maxterms
 Each maxterm is the complement of its corresponding
minterm, and vice versa.

Digital Logic Design

11
 Minterms and Maxterms
 An Boolean function can be expressed
 From a truth table

 By forming Sum of minterms for each combination of

variables that produces a (1) in the function.
 f1 = x'y'z + xy'z' + xyz = m1 + m4 +m7 (Minterms)

 f2 = x'yz+ xy'z + xyz'+xyz = m3 + m5 +m6 + m7 (Minterms)

Digital Logic Design

12
 Minterms and Maxterms
 The complement of a Boolean function
 The minterms that produce a 0

 f1' = m0 + m2 +m3 + m5 + m6 = x'y'z'+x'yz'+x'yz+xy'z+xyz'

 f1 = (f1')'

 f1=(x+y+z)(x+y'+z) (x+y'+z') (x'+y+z')(x'+y'+z) = M0 M2 M3

M5 M6
 f2 = (x+y+z)(x+y+z')(x+y'+z)(x'+y+z)=M0M1M2M4

Digital Logic Design

13
 Minterms and Maxterms

 Any Boolean function can be expressed as a product of

maxterms (“product” meaning the ANDing of terms).
 Any Boolean function can be expressed as a sum of minterms
(“sum” meaning the ORing of terms)
 Boolean functions expressed as sum of minterms or product of
maxterms are said to be in Canonical form.

Digital Logic Design

14
 Minterms Expansion

 If the given expression is not in its sum of minterms, it can be

made so by first expanding the expression into a sum of AND
terms.
 Each term is then inspected to see if it contains all the variables.
 If it misses one or more variables, it is ANDed with an
expression such as x+xʹ, where x is one of the missing variable

Digital Logic Design

15
 Minterms Expansion
 Example 2.4: Express F = A+B’C as a sum of minterms.
 F = A+B'C = A (B+B') + B'C
 =AB +AB' + B'C
 = AB(C+C') + AB'(C+C') + (A+A')B'C
 = ABC+ABC'+AB'C+AB'C'+A'B'C
 F = A'B'C +AB'C' +AB'C+ABC'+ ABC = m1 + m4 +m5 + m6 + m7
 F(A, B, C) = (1, 4, 5, 6, 7)
 or, built the truth table first

Digital Logic Design

16
 Maxterm Expansion

 If the given expression is not in its product of maxterms, it must

first be brought into a form of product of OR terms.
 This is done by using the distributive law :
x + (yz) = (x + y).(x + z)

 Then any missing variable x in each OR term is ORed with xxʹ.

Digital Logic Design

17
 Product of Maxterms
 Product of maxterms: using distributive law to expand.
 x + yz = (x + y)(x + z)
 = (x+y+zz')(x+z+yy')
 = (x+y+z)(x+y+z')(x+y'+z)

 Example 2.5: express F = xy + x'z as a product of maxterms.

 F = xy + x'z = (xy + x')(xy +z)
 = (x+x')(y+x')(x+z)(y+z) = (x'+y)(x+z)(y+z)
 x'+y = x' + y + zz' = (x'+y+z)(x'+y+z')
 x+z=x+z+yy’=(x+z+y)(x+z+y’)
 y+z= y+z+xx’=(y+z+x)(y+z+x’)

 F = (x+y+z)(x+y'+z)(x'+y+z)(x'+y+z') = M M M M
0 2 4 5
 F(x, y, z) = (0, 2, 4, 5)

Digital Logic Design

18
 Conversion between Canonical Forms
 The complement of a function expressed as the sum of minterms
equals the sum of minterms missing from the original function.
 F(A, B, C) = (1, 4, 5, 6, 7)

 Thus, F‘ (A, B, C) = (0, 2, 3)=m0+m2+m3

 Take complement of F‘ (A, B, C), by De Morgan's theorem

F=(F')'
= (m0+m2+m3 )' = m’0+m’2+m’3 =M0M2 M3 = (0, 2, 3)
mj' = Mj
 To convert from one canonical form to another: interchange the
symbols  and and list those numbers missing from the original
form
»  of 1's
»  of 0's

Digital Logic Design

19
 Example
 F = xy + xz

 F(x, y, z) = (1, 3, 6, 7)

 F(x, y, z) =  (0, 2, 4,
6)

Digital Logic Design

20
 Standard Forms
 In canonical forms each minterm or maxterm must contain
all the variables either complemented or uncomplemented,
thus these forms are very seldom the ones with the least
number of literals.
 Standard forms: the terms that form the function may obtain
one, two, or any number of literals, .There are two types of
standard forms:
 Sum of products(SOP)
 Product of sums(POS)

Digital Logic Design

21
Sum of Products: SOP is a Boolean expression containing AND terms, called
product terms. Each term may have any number of literals. The sum denotes the
ORing of these terms.

Ex: F1 = y' + xy+ x'yz'

Product of Sums: POS is a Boolean expression containing OR terms, called

sum terms. Each term may have any number of literals. The product denotes the
ANDing of these terms.

Ex: F2 = x(y'+z)(x'+y+z')

Digital Logic Design

 Standard Forms
 A Boolean function may be expressed in a nonstandard form
 F3 = AB + C(D + E)
 But it can be changed to a standard form by using The
. .

distributive law
 F3 = AB + C(D + E) = AB + CD + CE

Digital Logic Design

23
 2.7 Other Logic Operations
 2n rows in the truth table of n binary variables.
 22n functions for n binary variables.
 16 functions of two binary variables.

 All the new symbols except for the exclusive-OR symbol are
not in common use by digital designers.

Digital Logic Design

24
Boolean Expressions

Digital Logic Design

25
 2.8 Digital Logic Gates

 Consider the 16 functions in Table 2.8

 Two functions produce a constant : (F0 and F15).

 Four functions with unary operations: complement and

transfer(equal to input variable): (F3, F5, F10 and F12).
 The other ten functions with binary operators that define
Eight different operations AND, OR, NAND,
NOR, Exclusive-OR, equivalence, inhibition and
implication.

Digital Logic Design

26
 Standard Gates

 Of the 16 functions defined in Table 2.8

 Two are equal to constant

 Inhibition and implication are not commutative or

associative and thus are impractical to use as standard
logic gates.
 The other eight are used as standard gates in digital
design : complement (F12), transfer (F3), AND (F1), OR
(F7), NAND (F14), NOR (F8), XOR (F6), and
equivalence (XNOR) (F9).
 Complement: inverter.
 Transfer: buffer (increasing drive strength).

 Equivalence: XNOR.

Digital Logic Design

27
 Boolean Functions with logic gates
 The main logic gates A B F
0 0 0
AND Gate A F=A.B 0 1 0
1 0 0
B 1 1 1
A B F
OR Gate A F=A+B 0 0 0
0 1 1
B
1 0 1
1 1 1
Buffer A F=A A F
0 0
1 1
A F
Inverter A
0 1
1 0

Digital Logic Design

Summary of Logic Gates

Figure 2.5 Digital logic gate

Digital
Digital Logic
Logic Design
Design 50
Summary of Logic Gates

Figure 2.5 Digital logic gates

Digital Logic Design 51 Digital Logic Design
 Multiple Inputs
 Extension to multiple inputs
 A gate can be extended to have multiple inputs(more
than two inputs) except for inverter and buffer.
» A gate can be extended if its binary operation is
commutative and associative.
 AND and OR are commutative and associative.
» OR
o x+y = y+x
o (x+y)+z = x+(y+z) = x+y+z
» AND
− xy = yx
− (x y)z = x(y z) = x y z

Digital Logic Design

31
 Multiple Inputs
 Multiple NOR = a complement of OR gate, Multiple NAND
= a complement of AND.
 The cascaded NAND operations = sum of products.
 The cascaded NOR operations = product of sums.

Figure 2.7 Multiple-input and cascated NOR and

NAND gates Digital Logic Design
32
 Multiple Inputs
 The XOR and XNOR gates are commutative and associative.
 XOR is an odd function: it is equal to 1 if the inputs variables
have an odd number of 1's.

Figure 2.8 3-input XOR gate

Digital Logic Design
33
 Problems (imp)
1.Express the Boolean function F=A+BC in a sum of minterms.
2.Express F= xy+x’z in a product of maxterms.

Digital Logic Design