Chapter 3

Boolean Algebra and Minimization

Section 1: Logical Gates
Section 2: Boolean Algebra and
Minimization
1

SECTION 1:
LOGICAL GATES

Logic Gates
The building blocks of any digital circuit
Have one input or more, with only one
output
Output is active for certain input
combinations
Truth table: list out the output for each
possible input combination
Boolean function: function of one or more
variables
3

Inversion bubble

NOT Gate ( Inverter )

X

F=X or

X
logic equation/function

The inverter performs the Boolean NOT operation.

Truth table
Input
X
0
1

Output
F
1
0

X
F

Binary number

A group of inverters can

be used to form the 1s
complement of a binary
number.

1s complement

AND Gate
X
Y

F= X .Y or F = XY.

The AND gate produces a

HIGH output when all inputs
are HIGH; otherwise, the
output is LOW.

Inputs

Output

X Y

0
0
1
1

0
0
0
1

0
1
0
1

Example waveforms:
X
Y
F

OR Gate
X
Y

Inputs

Example waveforms:

Output

0
0
1
1

0
1
0
1

0
1
1
1

F=X+Y

X
Y

The OR operation can be used in computer programming to set certain

bits of a binary number to 1.
6

NAND Gate
X
Y

Inputs

Output

0
0
1
1

0
1
0
1

1
1
1
0

F = (X .Y)

(or F = X+Y)

Example waveforms:
X
Y
F

The NAND gate is particularly useful because it is a

universal gate all other basic gates can be constructed
from NAND gates.
7

The NOR Gate

X
Y

Inputs

Output

0
0
1
1

0
1
0
1

1
0
0
0

F X Y or F X Y X Y

Example waveforms:
X
Y
F

The NOR operation will produce a LOW if any input is HIGH.

8

The XOR Gate

X
Y

Inputs

Output

0
0
1
1

0
1
0
1

0
1
1
0

F XY XY or F X Y

or F X Y XY

Example waveforms:
X
Y
F

Notice that the XOR gate will produce a HIGH only when exactly one
input is HIGH.
9

The XNOR Gate

X
Y

Inputs

Output

0
0
1
1

0
1
0
1

1
0
0
1

F A B AB
or F = X

or F X 'Y ' XY

Example waveforms:

X
Y
F

The XNOR gate will produce a HIGH when both inputs are the same.
This makes it useful for comparison functions.
10

Exercise
Given two inputs A = 11010112 and B =
00110012, compute
XOR(A, B)
NAND(A,B)
OR(A,B)

11

SECTION 2:
BOOLEAN ALGEBRA AND
MINIMIZATION

12

Boolean Expression
A large number of logical gates are used to implement
the Boolean expression.

A variable is a symbol used to represent an action, a

condition, or data. A single variable can only have a
logical value of 1 or 0.
The complement represents the inverse of a variable.
Thus, the complement of A is A or A
A literal is a variable or its complement.
Example: Expression abc + ab + abc has
3 variables and 6 literals.
13

Boolean Expression

To reduce the number of gates used in

implementing Boolean expression,
Boolean expression can be simplified by:
Algrebraic method
Karnaugh map (K map)
Quine-McCluskey method

14

Boolean Addition
Addition is equivalent to the OR operation.

The sum term is 1 if one or more literals are 1.

The sum term is zero only if each literal is 0.
Example: Determine the values of A, B, and C that
make the sum term of the expression A + B + C = 0?
Each literal must = 0; therefore A = 1, B = 0 and C = 1.

15

Boolean Multiplication
In Boolean algebra, multiplication is equivalent to the
AND operation.

The product of literals forms a product term.

The product term will be 1 only if all of the literals are 1.
Example: What are the values of the A, B and C if the
product term of A.B.C = 1?
Each literal must = 1; therefore A = 1, B = 0 and C = 0.
16

Commutative Laws
The commutative laws are applied to addition and
multiplication. (i.e., we can swap the literals and still get
the same answer/output)
A+B=B+A

AB = BA

Associative Laws

It doesnt matter how we group the literals (i.e., which

we calculate first)
A + (B +C) = (A + B) + C

A(BC) = (AB)C
17

Distributive Law
The distributive law is the factoring law. A common
variable can be factored from an expression just as in
ordinary algebra. (Inverse: A can be distributed to B+C)
AB + AC = A(B+ C)
The distributive law can be illustrated with equivalent
A
circuits:
AB
B
C

B+ C

X
X

A(B+ C)

A
C

AC

AB + AC
18

Rules of Boolean Algebra

3. A . 0 = 0

7. A . A = A
8. A . A = 0
=
9. A = A

4. A . 1 = A

10. A + AB = A

5. A + A = A

11. A + AB = A + B

6. A + A = 1

12. (A + B)(A + C) = A + BC

1. A + 0 = A
2. A + 1 = 1

19

Prove the distributive law

(A + B)(A + C) = A + BC

(A + B)(A + C) = AA + AC + AB + BC
= A + AC + AB + BC
= A(1 + C + B) + BC
= A . 1 + BC
= A + BC
Example: Prove the rule:

A+ AB

A + AB = A + B

= (A+A)(A+B)
= 1 (A+B)
= A+B
20

DeMorgans Theorem
DeMorgans 1st Theorem
The complement of a product of variables is
equal to the sum of the complemented variables.

AB = A + B
Applying DeMorgans first theorem to gates:
A

AB

B
NAND

Inputs

A+B

B
Negative-OR

A
0
0
1
1

B
0
1
0
1

Output
AB A + B
1
1
1
1
1
1
0
0
21

DeMorgans Theorem
DeMorgans 2nd Theorem
The complement of a sum of variables is equal to
the product of the complemented variables.

A+B=A.B
Applying DeMorgans second theorem to gates:
A

A+B

B
NOR

A
B
Negative-AND

Inputs

AB

A
0
0
1
1

B
0
1
0
1

Output
A + B AB
1
1
0
0
0
0
0
0
22

Generalized DeMorgans Theorem

(A1+A2+ +An) = A1A2An

(A1A2 An) = A1 + A2 + + An

23

Example
(a) Find the complement of (A+B)C
[(A+B)C] = (A+B) + C
= AB + C = AB + C
(b)

Note:

Complement the expression a + bc.

(a + bc)' = a'(bc)'
= a'(b' + c')
= a'b' + a'c
(a + bc)' a'b' + c'
24

Exercise: Reduce using De Morgans Theorem

Q1

Check the answer using truth table

Q2

A BC D( E F )
25

Boolean Analysis of Logic Circuits

Combinational logic circuits can be analyzed by writing
the expression for each gate and combining the
expressions according to the rules for Boolean algebra.
Example: Apply DeMorgans theorem to derive the expression for X.
Write the expression for each gate:
A
B

(A + B )

C (A + B )

X = C (A + B )+ D

X = C (A B) + D = A B C + D
26

Duality
Principle of duality: If an expression is valid in Boolean algebra,
the dual of the expression is also valid.
The dual of an expression is found by replacing
- all (+) operators with (),
- all () operators with (+),
- all ones with zeroes,
- all zeros with ones.
Note: Do not alter the location of parentheses when obtaining a
dual. Variables and complements are left unchanged.
Example:
Find the dual of the expression a + (bc) = (a + b)(a + c).
Dual of the above expression is

a(b + c) = (ab) + (ac)

27

Consensus Theorem
Given a pair of sum-of-product term (product-of-sum term) for
which a variable appears in one term and its complement in
the other, then the consensus term is formed by ANDing
(ORing) the original terms together, leaving out the selected
variable and its complements.
Example
redundant
The consensus of abc and ad is bcd.
The consensus of abd and abcd does not exist.
Why? abd+abcd+ bbcd= abd+abcd
The consensus of abc and bcd does not exist.

28

The Consensus Theorem:

ab + a'c + bc = ab + a'c
(a + b)(a' + c)(b + c) = (a + b)(a' + c)
Truth Table
Proofs:

ab + ac + bc
= ab + ac + bc(a+a)
= ab + ac + abc + abc
= ab (1 + c) + ac (1 + b)
= ab + ac
29

The Consensus Theorem:

ab + a'c + bc = ab + a'c
(a + b)(a' + c)(b + c) = (a + b)(a' + c)
Truth Table
Proofs:

ab + ac + bc = ab + ac
Duality:
(a+b)(a+c)(b+c) = (a+b)(ac)
30

Example: Simplify f = abc + abc + abc + abc

f

= ac (b + b) + abc + abc
= ac + abc +abc
= a(c+bc) + abc
= a ((c+b)(c+c)) + abc
= ac + ab + abc
= c(a+ab) + ab
= c ((a+a)(a+b)) + ab
= ac + bc + ab
= bc + ab

b + b =1
X+YZ=(X+Y)(X+Z)

Consensus term

31

Example: Simplify f = wy + wxz + wxy + wyz.

Note: There are no consensus terms that can be
eliminated.
f

= wy + wxz + wxy + wyz

= wy + wxz + wxy + wyz + xyz
= wy + wyz + xyz

[consensus of xyz and wyz is wxy and that of xyz

and wy is wxz]

32

Example

Simplify f = (a + b + c)(a + b + d)(b + c + d)

The consensus of (a+b+c) and (b+c+d) is (a+b+d)
So,

f = (a+b+c)(b+c+d)

33

Exercise:
- Simplify F = xyz + xyz + xyz + xyz

- Simplify F = xy + xz + yz + xz

34

Exercise:
F = xyz + xyz + xyz + xyz
= xy(z + z) + xz(y + y)
= xy + xz
F = xy + xz + yz + xz
= xy + xz + xz
= xy + x(z+z)
= xy + x
= (x + x)(x + y)
= (x + y)

35

Exercise:
- Simplify (A+B)(B+C)(A+D+C)(D+B+A)(B+C+D)(C+A)

- Verify your answer using truth table.

36

Answer
DUALITY:
AB + BC + ACD + ABD + BCD + AC
= AB + BC + ACD + ABD + BCD + AC
= AB (1+D) + BC + AC (1+D)
= AB + BC + AC
= AB + AC
Then,
(A+B)(B+C)(A+D+C)(D+B+A)(B+C+D)(C+A) =
(A+B)(A+C)

37

Answer
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

(A'+B)
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
TRUE

(B+C)
FALSE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE

(A+D+C)
FALSE
TRUE
TRUE
TRUE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE

(D+B+A')
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE

(B+C+D)
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE

(A+B)(B+C)(A+D+C)(D+B+A)(B+C+D)(C+A) = (A+B)(A+C)
(C+A)
LHS
RHS
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
FALSE
FALSE
TRUE
FALSE
FALSE
TRUE
FALSE
FALSE
TRUE
FALSE
FALSE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
TRUE
38

SOP and POS forms

Boolean expressions can be written in the

sum-of-products form (SOP) or in the

product-of-sums form (POS).
These forms can simplify the implementation of combinational
logic, particularly with PLDs. In both forms, an overbar cannot
extend over more than one variable.

These two forms of switching functions lead to

different circuit implementation
39

SOP form
An expression is said to be in sum of products
form if all products are products of only single
variables. Functions in SOP form are formed by
summing (ORing) product (ANDed) terms.
Examples:
AB + CDE + ACE
A + B + CD + EFG
Attention: (A+B)CD +E +FGH

(SOP form)
40

Example: Express the function in SOP forms

(A+BC)(A+D+E) = A + BC(D+E) = A + BCD + BCE
(Q+AB)(CD+Q) = QCD + ABQ
Any logic expression can be changed into SOP form by
applying the distributive laws to multiply out the expression
An SOP expression can be implemented by AND-OR logic

41

POS form
An expression is said to be in a product of sums form if
all sums are sums of single variables. Functions in POS
form are formed by taking product (ANDing) of sum (ORed)
terms.
Examples:

(A+B)(C+D+E)(A+C+F)
(A+B)(C+D+E)F
Attention: (A+B)(C+DE) POS form.

42

Example: Find POS forms:

(a)
A+BCD
A + BCD = (A+B)(A+CD) = (A+B)(A+C)(A+D)
(b)

AB+CD
AB + CD = (AB+C)(AB+D)
= (A+C)(B+C)(A+D)(B+D)

Useful laws to obtain POS forms:

(a) X(Y+Z) = XY + XZ

(b) X + YZ = (X+Y)(X+Z)

(c) (X + Y)(X+Z) = XZ + XY
43

Example:
Convert AC+ABD+ABE+ACDE to product of sums form.
XZ+XY = (X+Y)(X +Z)
AC+ABD+ABE+ACDE
= AC+A (BD+BE+CDE)
= [A + (BD+BE+CDE)][A+C]
X + YZ = (X+Y)(X+Z)
= [ (A+CDE) +B(D+E)] (A+C)
= (A+CDE+B) (A+CDE+D+E) (A+C)
E(1+ C D)=E
= (A+CDE+B) (A+D+E) (A+C)
= (A+C+B) (A+D+B) (A+E+B) (A+D+E) (A+C)

X + YZ = (X+Y)(X+Z)
X + YZ = (X+Y)(X+Z)

44

A POS expression can be implemented by OR-AND logic

45

Canonical or Standard form

All Boolean expressions, regardless of their form, can be
converted into either of the two canonical forms: SOP or POS.
Standardization makes the Boolean expressions much
more systematic and easier to compare with each other.

A Boolean expression with n variables is said to be in

canonical form if the SOP or POS expression has all
the n variables (or their complements) appearing exactly

once in each term.

46

SOP canonical (or standard) form

In SOP canonical form, every variable in the domain must
appear in each term. This form is useful for constructing
truth tables or for implementing logic in PLDs.
You can expand a nonstandard term to standard form by
multiplying the term by a term consisting of the sum of the
missing variable and its complement, i.e., (X+X).

Example: Convert X = A B+ A B C to canonical form.

X = A B (C + C) + A B C
=ABC+ABC+ABC
47

POS Canonical (or standard) form

In POS canonical form, every variable in the domain must
appear in each sum term of the expression.
You can expand a nonstandard POS expression to standard form
by adding the product of the missing variable and its complement
A . A and applying the rule which states that (A + B)(A + C) = A
+ BC.

Example: Convert X = (A + B)(A + B + C) to standard form.

X = (A + B + C C)(A + B + C)
= (A +B + C )(A + B + C)(A + B + C)
48

Example: canonical forms

f(A,B,C) = ABC+ABC+ABC+ABC

(canonical SOP)

f(A,B,C) = (A+B+C)(A+B+C)(A+B+C) (canonical POS)

f(A,B,C) = AB+ABC+B

(not in canonical SOP)

f(A,B,C) = (A+B+C)(A+B)(A+B+C) (not in canonical POS)

49

Minterm
Every term in a canonical SOP expression is called
a minterm.

A minterm is a product term.

E.g.: X= ABC+ ABC
minterm

minterm

A minterm is 1 for only one combination of variable values

and
0 for all other combinations
Example: a function of three variable, A, B, and C
Minterm ABC = 1 iff A = B = C = 0
Question:Is it possible for minterm ABC and minterm ABC
to be 1 at the same time?
50

Maxterm
Every term in a canonical POS expression is called a maxterm.
A maxterm is a sum term.
Eg: X = (A+B+C) (A+B+C)( A+B+C)
maxterm

maxterm

maxterm

A maxterm is 0 for only one combination of variable values and 1

for others.

Example: a function of three variable, A, B, and C

Maxterm (A+B+C+D) = 0 iff A = C = 0 and B = D = 1

51

Table: minterms for 3 variables, A, B and C.

Row No
i

ABC

Minterm

Minterm
numbers

0
1
2
3
4
5
6
7

000
001
010
011
100
101
110
111

ABC
ABC
ABC
ABC
ABC
ABC
ABC
ABC

m0
m1
m2
m3
m4
m5
m6
m7
C=0

A=1
52

Write canonical SOP form (minterm expansion) in

minterm list form
Example: f1(A, B, C) = ABC + ABC + ABC
= m2 + m3 + m6
Or f1(A, B, C) = m(2, 3, 6)
Note: the order of variables in the functional notation is important.

f1(A, B, C) = m(2, 3, 6)

(A is the MSB, C is the LSB)

f2(B, C, A) = m(2, 3, 6)

(B is the MSB, A is the LSB)

53

Construct truth table using canonical SOP form

f1(A, B, C) = ABC + ABC + ABC
Row
no.
i
0

Inputs
ABC

Outputs
f1(A, B, C)

000

Complemented
Outputs
f1(A, B, C)
1

1
2
3
4
5
6
7

001
010
011
100
101
110
111

0
1
1
0
0
1
0

1
0
0
1
1
0
1

f1(A, B, C) = m(2, 3, 6)

f1(A, B, C) = m(0, 1, 4, 5, 7)

A minterm

54

Table: maxterms for 3 variables, A, B and C.

Row
No i

ABC

Maxterm

Maxterm
numbers

0
1
2
3
4
5
6
7

000
001
010
011
100
101
110
111

A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C

M0
M1
M2
M3
M4
M5
M6
M7

A=1

C=0
55

Write canonical POS form (maxterm expansion) in

maxterm list form
fx(A, B, C) = (A+B+C)(A+B+C)(A+B+C)
=M4M1M0=M0M1M4
Or
fx(A, B, C) = (A+B+C)(A+B+C)(A+B+C)
= M(4, 1, 0) = M(0, 1, 4)
Note: the order of variables in the functional notation is important.

56

Construct truth table using canonical POS form

fx(A, B, C) = (A+B+C)(A+B+C)(A+B+C)
Row no.
i

Inputs
ABC

Outputs
fx(A, B, C)

Complemented
Output
fx(A, B, C)

000

001

010

011

100

101

110

111

fx(A, B, C) = M(4, 1, 0)

fx(A, B, C) = M(2, 3, 5, 6, 7)
A maxterm

57

Conversion between Canonical forms

Conversion can be done either using a truth table or
algebraically.
Example: Convert the following SOP expression,
f(A, B, C) = m(2, 6, 7), to an equivalent POS expression.
f(A, B, C) = m(2, 6, 7) = A'BC' + ABC' + ABC
f '(A, B, C)= m(0, 1, 3, 4, 5)
= A'B'C' + A'B'C + A'BC + AB'C' + AB'C

Taking complement of f '(A, B, C) gives

f(A, B, C)= f ''(A, B, C)= (A'B'C'+A'B'C+A'BC+AB'C'+AB'C)'
= (A+B+C)(A+B+C')(A+B'+C')(A'+B+C)(A'+B+C')
different form of f
= M(0, 1, 3, 4, 5)
So,

f(A, B, C) = m(2, 6, 7) = M(0, 1, 3, 4, 5)

58

Example: If
f(a, b, c) = m(2, 4, 6) = M(0,1,3,5,7) then
f (a, b, c) = m(0,1,3,5,7) = M(2, 4, 6)

Notes:
If mi is not present in a minterm expansion of f,
then Mi is present in the maxterm expansion.
Similarly, it applicable on f.

59

Example
Determine the canonical SOP and POS expressions from the
following truth table.
Inputs
ABC

Output
f(A, B, C)

000

001

010

011

100

101

110

111

SOP: Replace each 1 with

the corresponding variable and each 0
with the corresponding variable
complement.

f(A, B, C)

= m(3, 4, 6, 7)
= A'BC+AB'C'+ABC'+ABC

POS: Replace each 1 with the corresponding variable

complement and each 0 with the corresponding variable.
f(A, B, C)

= (A+B+C)(A+B+C')(A+B'+C)(A'+B+C')

60

SOP: Replace each 1 with the

corresponding variable and each 0 with
the corresponding variable Complement.

POS: Replace each 1 with the

corresponding variable complement and
each 0 with the corresponding variable.

ABC

SOP (Minterm)

POS (Maxterm)

000

ABC = m0

A + B + C = M0

001

ABC = m1

A + B + C = M1

010

ABC = m2

A + B + C = M2

011

ABC = m3

A + B + C = M3

100

ABC = m4

A + B + C = M4

101

ABC = m5

A + B + C = M5

110

ABC = m6

A + B + C = M6

111

ABC = m7

A + B + C = M7

f(A,B,C) = m3+m5 = m(3,5) = M0M1M2M4M6M7 = M(0,1,2,4,6,7)

Minterm Expansion

Maxterm Expansion

61

Derivation of Canonical Forms

Boolean algebra can be used to convert a non-canonical
function into canonical form.
To get canonical SOP form, multiply each non-standard product
term with a term containing the sum of a missing variable and its
complement. [A+A' = 1]
To get canonical POS form, add a term containing the product
of a missing variable and its complement to each non-standard
term. [AA' = 0]

62

Example
Convert the following function to canonical SOP form:
f(A,B,C) = AB + AC' + A'C
f(A,B,C)

= AB + AC' + A'C
= AB(C + C') + AC'(B + B') + A'C(B + B')
= ABC + ABC' + AB'C' + A'BC + A'B'C
= m7 + m6 + m4 + m3 + m1
= m(1, 3, 4, 6, 7)

63

Example
Convert the following function to canonical POS form:
f(A, B, C) = A(A + C')
A= A+BB'

f(A, B, C) = A(A + C')

A+BC = (A+B)(A+C)
= (A+BB')(A + C')
= (A+B')(A+B)(A + C')
= (A+B'+CC')(A+B+CC')(A+BB'+C')
= (A+B'+C')(A+B'+C)(A+B+C')(A+B+C)(A+B'+C')(A+B+C')
= M3 M2 M1 M0
= M(0, 1, 2, 3)

64

Example: Find the canonical SOP and POS expressions of

f (a,b,c) = a(b'+c) + bc

= ab' + ac + bc'

[write as SOP]

= ab' ( c + c') + ac ( b + b') + bc' (a + a')

= ab'c + ab'c' + abc + ab'c + abc' + a'bc
= m5 + m4 + m7 + m5 + m6 + m2
= m (2,4,5,6,7) = M (0,1,3)

65

Incompletely Specified Functions

A switching function may be incompletely specified.
This function has dont care terms.
Don't care arises when:
(a)The function has certain input combinations that
can never occur.
Example, BCD code has 6 dont-cares.

(b)All input combinations of a function occur but we dont care

whether the output is 1 or 0 for certain input combinations.
Dont care terms are included in logic design (assign a 1 to it)
if they help to simplify the logic circuit or otherwise omitted
(assign a 0 to it).
66

Example: An incompletely specified function. Dont care is

Notice: X=0 or 1.
represented by X.
A

1 1

Assign 0 to both X:
F = A'B'C' + A'BC + ABC
= A'B'C' + BC

Assign 1 to the first X and

0 to the second:
F = A'B'C' + A'B'C + A'BC + ABC
= A'B' + BC
Assign 1 to the second X and
0 to the first:
F = A'B'C' + A'BC + ABC + ABC
= A'BC + BC + AB

Minterm expansion:
F = m(0,3,7) + d(1,6) Assign 1 to both X:
F = A'B' + BC +AB

Maxterm expansion:
F = M(2,4,5) D(1,6)

The assignments that will produce the

67
simplest functions are preferred.

Example: A function f(A,B,C) has minterms m0, m3 and m7

and don't cares d4 and d5. Express the function and its
complement in both minterm and maxterm form and then reduce
the function to its simplest form.
f(A,B,C) = m(0, 3, 7) + d(4, 5)
f(A,B,C) = M(1, 2, 6) D(4, 5)

minterm form
maxterm form

f' (A,B,C) = m(1, 2, 6) + d(4, 5)= M(0, 3, 7) D(4, 5)

Logic simplification:
f(A,B,C)
= A'B'C' + A'BC + ABC + d(AB'C' + AB'C)
= A'B'C' + BC + d(AB'C' + AB'C)
Without the use of dont cares, there is no further simplification.
Assign 1 to d4 and 0 to d5

f(A,B,C) = A'B'C' + BC + AB'C' = B'C' + BC

68

Possible Input combinations of 3 variables

Row
No i
0
1
2
3
4
5
6
7

0
0

0
0

0
1

1
0

0
0
1

1
1
0

0
1
0

0
1
X

1
1
1

0
1
1

1
0
1

X
0
1
69

Exercise
Express (A+B)(A+C) using canonical POS
and canonical SOP forms. Notice that
there exists 4 variables, A, B, C and D.
Given f(a,b,c) = ab + ac + bc
Write f as a minterm expansion and maxterm
expansion
Write f as a minterm expansion and maxterm
expansion
70

Exercise
(A+B)(A+C)
= (A+B+CC+DD)(A+BB+C+DD)
= (A+B+C+D) (A+B+C+D) (A+B+C+D) (A+B+C+D)
(A+B+C+D) (A+B+C+D) (A+B+C+D) (A+B+C+D)
(A+B)(A+C)
= AC + AB + BC
= AC(D+D)(B+B) + AB(C+C)(D+D)
= ABCD + ABCD + ABCD + ABCD +
ABCD + ABCD + ABCD + ABCD

71

Exercise
f(a,b,c)
= ab + ac + bc
= ab + ac
= abc + abc + abc + abc
= m 3 + m2 + m 6 + m4
= m(2,3,4,6) = M(0,1, 5, 7)
f(a,b,c)
= m(0,1, 5, 7) = (2,3,4,6)
72

Exercise
A

Find the simplest expression for f in both SOP and POS

forms. Specify clearly the values assigned for the dont care
terms that lead to the expression.
73

Exercise
f(A,B,C)
= ABC + ABC + ABC + d(ABC + ABC)
= ABC + ABC + ABC + BC + d(ABC + ABC)
= ABC + BC + d(ABC + ABC)
Assign 1 to ABC and 0 to ABC
f(A,B,C)
= ABC + BC + ABC
= BC + BC(A + A)
= BC + BC
= C(B+B) = C
74