1

DIGITAL LOGIC:
CHAPTER 4

Boolean Algebra and Logic

Simplification
 Boolean Operations &
2
Expressions
 Variable (Pembolehubah)
 A symbol that represents a logical quantity
 Usually italic uppercase (A, B, C, D)
 A single variable can have a 1 or 0 value

 Complement (Pelengkap)
 The inverse of a variable
 Indicated by an overbar (Ā) or prime (A’)
 If A = 1 , then Ā = 0

 Literal = both variable and its

complement in a term.
 Ā + B + C  3 literals
 Laws & Rules of Boolean
Algebra
3

 Basic laws of BA
 Commutative Laws (Hukum Tukar
Tertib)
 For addition and multiplication
 Associative Laws (Hukum Sekutuan)
 For addition and multiplication
 Distributive Laws (Hukum Taburan)
Commutative Laws
(Hukum Tukar Tertib)
 A+B=B+A
A B
A+B B+A
B A

Commutative law of addition

 AB = BA
A B
AB BA
B A

Commutative law of multiplication

4
Associative Laws (Hukum
Sekutuan)
 A + (B + C) = (A + B) + C
A A
A+B
A + (B + C)
B
B
(A + B) + C
B+C
C C
Associative law of addition

 A(BC) = (AB)C
A A
A(BC)
B

B
(AB)C
BC
C C

Associative law of multiplication

5
Distributive Law (Hukum
Taburan)
 A(B + C) = AB + AC

B A
B+C
C B
AB + AC
A(B + C)
A
A
C

6
 Rules of Boolean Algebra
7

1 A+0=A
2 A+1=1
3 A 0=0
4 A 1=A
5 A+A=A
6 A+A=1
7 A A=A
8 A A=0
9 A=A
10 A + AB = A
11 A + AB = A + B
12 (A + B)(A + C) = A + BC
 Rules of Boolean Algebra:
8
Proof
Rule 1:
A=1 A= 0
X=1 X=0
0 0

X=A+0=A

Rule 2:
A=1 A= 0
X=1 X=1
1 1

X=A+1=1
Rule 3:
A= 1 A= 0
X=0 X=0
0 0

X=A 0=0
Rule 4:
A= 0 A= 1
X=0 X=1
1 1

X=A 1=A

Rule 5:
A= 0 A= 1
X=0 X=1
A= 0 A= 1

X=A+A=A
9
Rule 6:
A= 0 A= 1
X=1 X=1
A= 1 A= 0

X=A+A=1

Rule 7:
A= 0 A= 1
X=0 X=1
A= 0 A= 1

X=A A=A

Rule 8:
A= 1 A= 0
X=0 X=0
A=0 A=1

X=A A=0
Rule 9:
A =0
A =1
A= 1 A=1
A= 0 A=0

A=A
10
 Rules 10, 11 and 12 can be proven using
BA laws.
Rule 10:
Refer proof
A + AB = A(1 + B) Factoring (distributive law)
=A.1 Rule 2: (1 + B) = 1 -next slide
=A Rule 4: A . 1 = A

Rule 11:
A + AB = (A + AB) + AB Rule 10: A = A + AB
= (AA + AB) + AB Rule 7: A = AA
= AA + AB + AA + AB Rule 8: adding AA = 0
= (A + A)(A + B) Factoring
= 1 . (A + B) Rule 6: A + A = 1
=A+B Rule 4: drop the 1

Rule 12:
(A + B)(A + C) = AA + AC + AB + BC Distributive law
= A + AC + AB + BC Rule 7: AA = A
= A(1 + C) + AB + BC Factoring (distributive law)
= A . 1 + AB + BC Rule 2: 1 + C = 1
= A(1 + B) + BC Factoring (distributive law)
= A . 1 + BC Rule 2: 1 + B = 1
= A + BC Rule 4: A . 1 = A
11
 Proof can also be shown by a truth table.

Rule 10
A B AB A + AB
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

equal

12
DeMorgan’s Theorems
 Provides mathematical verification for:
 NAND ≡ negative-OR

 NOR ≡ negative-AND

X X
XY X+Y
Y Y
NAND Negative-OR

X X
X+Y XY
Y Y

NOR Negative-AND

13
 DM theorem 1:
1
 The complement of a product of variables is
equal to the sum of the complements of the
variables
XY = X + Y

 DM theorem 2:
2
 The complement of a sum of variables is
equal to the product of the complements of
the variables
X + Y = XY

14
 DeMorgan’s Theorem
15
Application
DeMorgan's Theorems I

XYZ = X + Y + Z

WXYZ = W + X + Y + Z

DeMorgan's Theorem II

X + Y + Z = XYZ
** Note:
W + X + Y + Z = WXYZ
X = AB + C
Y = A + BC
 Examples for DeMorgan’s
Theorems
16

(AB +C)(A + BC) = (AB + C) + (A + BC)

(AB + C) + (A + BC) = (AB)C + A(BC)

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

Boolean expression for a Logic
Circuit
 To derive the Boolean expression for a given
circuit, follow left-2-right rule.
 Begin from the left-most inputs and work towards the
last.
1
4
C CD
Z Z(A(B + CD))
D 2
B + CD
B A(B + CD)
A 3

1 2 3 4

17
 Constructing a Truth Table for a
Logic Circuit
18

 A truth table shows the output for all

possible input values.
 From a Boolean expression, a truth table
can be developed.
 x = number of input variables
 Possible combinations of values, n = 2x
 E.g. A(B + CD)  x = 4; n = 24=16
 Steps in constructing a truth
19 table
 Step 1: Identify x and n from the Boolean
exp.
 Step 2: Find the values of the variables
that make the expression equal to 1.(Hint:
use the rules for Boolean addition and
multiplication)
 Step 3: List in a table
 all the n combinations of 1s and 0s (input)
 The values of variables from step 2 (output)
 All the other output values will be 0
 Example A(B + CD)
20
 Step 1: x = 4 ; n = 2x = 24 = 16
 Step 2:
 A(B + CD) = 1 • 1 = 1  A = 1
 What makes B + CD = 1?
 B + CD = 1 + 0 = 1
 B + CD = 0 + 1 = 1
 B + CD = 1 + 1 = 1  B = 1 or 0
 What makes CD = 1?
 CD = 1 . 1 = 1  C = 1; D = 1
 So for A(B + CD) = 1
 A = 1, B = 1, C = 0/1, D = 1/0
 A = 1, B = 1/0 , C = 1, D = 1
 Step 3 : Fill in the grid and results from
Step 2 INPUTS OUTPUT
A B C D A(B + CD)

0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
21
 Tips on ‘table-making’:
 For n possible combinations, the input part of
the table will register the binary value of 0 to
n-1. (e.g. n = 16; 0 to 15)

 Remember the sequence

24 22 21 20
8 4 2 1
0 0 0 0 (0)
0 0 0 1 (1)
0 0 1 0 (2)
0 0 1 1 (3)

22
 Simplification using Boolean
23
Algebra
 Simplification:
 To reduce an expression to its simplest form
 To change a form to a more convenient one
for efficient implementation
 We use:- basic laws, rules, theorems of
Boolean algebra
 Practice makes perfect
Simplify this expression
AB + A(B + C) + B(B + C)

AB + A(B + C) + B(B + C)
Step 1: Apply distributive law to the red terms
AB + AB + AC + BB + BC
Step 2: Apply rule 7 (BB = B) to the green term

AB + AB + AC + B + BC
Step 3: Apply rule 5 (AB + AB = AB) to the red terms

AB + AC + B + BC
Step 4: Apply rule 10 (B + BC = B) to the green terms

AB + AC + B
Step 5: Apply rule 10 (B + AB = B) to the red terms

24
AC + B
 Simplify this expression
ABC + ABC + ABC + ABC + ABC
ABC + ABC + ABC + ABC + ABC
Step 1: Factor BC for the red terms

BC(A + A) + ABC + ABC + ABC

Step 2: Apply rule 6 to the green term and factor the blue
term
BC . 1 + AB(C + C) + ABC
Step 3: Apply rule 4 to the red term and rule 6 to the blue
term
BC + AB . 1 + ABC
Step 4: Apply rule 4 to the green term
BC + AB + ABC
Step 5: Factor the red terms
BC + B(A + AC)
Step 6: Apply rule 11 to the blue term
BC + B(A + AC)
Step 7: Use the distributive and commutative laws to
get the following expression

BC + AB + BC
25
 Standard Form of Boolean
Expressions
26

 Boolean expression can be converted into

one of 2 standards forms:
 The sum-of-products (SOP) form
 The product-of-sums (POS) form
 Standardization makes the evaluation,
simplification, and implementation of
Boolean expressions more systematic and
easier
 Product term = a term with the product
(Boolean multiplication) of literals
 Sum term = a term with the sum (Boolean
addition) of literals
The Sum-of-Products (SOP)
Form
 SOP = when 2 or more product terms
are summed
 e.g ABP1 + ABCP2
ABCP1 + CDEP2 + BCDP3
 SOP can also contain a single variable
term
 In SOP a single overbar cannot extend
over more than 1 variable, but more
than 1ABC
variable
 can have
ABCan overbar.
27
 Domain = a set of variables contained in
an expression
 E.g. AB + ABC  domain = A, B, C
 ABC + CDE + BCD  domain = A, B, C, D, E

 Implementation of the SOP expression AB

+ BCD + AC
A
B
B
C X = AB + BCD + AC
D
A
C 28
 A logic expression can be changed to SOP form
using Boolean algebra techniques.
 A(B + CD) = AB + ACD
 AB + B(CD + EF) = AB + BCD + BEF

 Standard SOP form = where all the variables in

the domain appear in each product term in the
ABCD + A BC D + ABC D
expression.

 To convert product terms to standard SOP


A+ A =1
Multiply each of the nonstandard term with the missing
term using Boolean algebra rule 6 ( ).
 Repeat until all variables appear in each product term.
29
 Convert this Boolean expression to standard SOP form:
A BC + AB + ABC D
 Domain = A, B, C, D.
 What is missing?
 Term 1: missing D or D’
 Term 2: missing (C/C’) and (D/D’)
 Complete these terms by applying Boolean rule 6
Term 1 : ABC = A BC ( D + D) = A BCD + A BC D

Term 2 : A B = A BC + A BC
= ABC ( D + D ) + A BC ( D + D ) = ABCD + A BC D + ABC D + A BC D
 Now we have

ABC + A B + ABC D
= ABCD + A BC D + A BCD + ABC D + ABC D + ABC D + ABC D

30
Binary representation of a
standard product term
 A product = 1 only if
ALL variables in the
term is equal to 1. SOP

 Remember: product =
multiplication  1.1 = 1 Product1 Product2 Product3
 A sum = 1 when one
or all of the variables Var1 Var1 Var1

in the term is equal to

1.
 Remember: sum =
addition  1 + 0 = 1; 0
+ 1 = 1; 1 + 1 = 1
31
 Determine the binary value for which the following standard SOP
32 expression is equal to 1:

ABCD + ABCD + ABCD

The term ABCD is equal to 1 when A = 1, B = 1, C = 1, and D = 1

ABCD = 1.1.1.1 = 1
The term ABCD is equal to 1 when A = 1, B = 0, C = 0, and D = 1
ABCD = 1.0.0.1 = 1.1.1.1 = 1
The term ABCD is equal to 1 when A = 0, B = 0, C = 0, and D = 0
ABCD = 0.0.0.0 = 1.1.1.1 = 1
The SOP expression equals 1 when any or all of the three product
terms is 1.
Product-of-Sums (POS)
Form
 POS = when 2 or more sum terms are
multiplied.
 (A + B)S1(A + B + C)S2
 (A + B + C)S1(C + D + E)S2(B + C + D)S3
 Like SOP, POS
 can also contain a single variable term
 a single overbar cannot extend over more
than 1 variable, but more than 1 variable can
have an overbar.

A+ B+C  A+ B+C 
33
 Domain = a set of variables contained in
an expression
 (A + B + C)(A + B + D)(A + B + C + D) 
domain = A, B, C, D

 Implementation of the POS expression

(A + B)(B + C + D)(A + C)
A
B
B
C X = (A + B)(B + C + D)(A + C)
D
A
C
34
 Standard POS form = where all the
variables in the domain appear in each
sum term in the expression.
 To convert product terms to standard POS
 Multiply each of the nonstandard term with the
missing term using Boolean algebra rule 8:
A• A = 0
 Apply rule 12 : A + BC = (A + B)(A + C)
A + BC = ( A + B )( A + C )
 Repeat until all variables appear in each sum
term.

35
 Convert this Boolean expression to standard POS
form ( A + B + C )( B + C + D)( A + B + C + D)

 Domain = A, B, C, D.
 What is missing?
 Term 1: missing D or D’
 Term 2: missing A or A’
Apply
Term

1 : A +rules
B + C 8= and
A + B 12
+ C + D D = ( A + B + C + D)( A + B + C + D)
Term 2 : B + C + D = B + C + D + A A
= ( A + B + C + D)( A + B + C + D)

( A +
B + Cwe
Now )( B +have
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)
36
Binary representation of a
standard sum term
 A product = 0 only if
one or more of the
sum term is equal to POS

0.
 Remember: product = Sum1 Sum2 Sum3
multiplication  1.1 = 1
 A sum = 1 when one Var1 Var1 Var1

or all of the variables

in the term is equal to
1.
 Remember: sum =
addition  1 + 0 = 1; 0
+ 1 = 1; 1 + 1 = 1 37
Converting
Standard SOP to Standard POS
 Binary values in a
standard SOP
expression are not
present in the Standard Standard
equivalent SOP POS
Then x is
standard POS Binary
If x is here
not here
expression values (x) If x is not Then x is
here here

38
 Steps to follow : SOP to
39 POS
 Step 1: Evaluate each product term in the
SOP expression  i.e. determine the
binary numbers of the product terms.
 Step 2: Determine all the binary numbers
not included in Step 1.
 Step 3: Write equivalent sum term for
each binary number from Step 2 and
express in POS form.
 ** Using a similar procedure, to go from
POS to SOP
 Convert this SOP exp. to an equivalent
POS exp.
A B C + A B C + A BC + AB C + A B C

 Domain = A, B, C = 3. So, 23 = 8 possible

combinations.
A B C + A B C + A BC + A B C + A B C
000 010 011 101 111

 The SOP have 5 of 8, so POS have the

other 3 (001, 100, 110)  These 3 make
sum term
(A + B= 0 + B + C)(A + B +C)
+ C)(A
0 0 1 1 0 0 1 1 0

40
 Boolean Expressions and
41
Truth Tables
 Step 1: determine domain and
combinations of binary values  input
 Step 2: convert expression to Standard
SOP/POS.
 Step 3: find the binary values that make
the product = 1 (SOP) or sum = 0 (POS)
 Step 4: the remaining combination will be
 Equal to 0 (SOP)
 Equal to 1 (POS)
 Fill in the truth table
 Develop a truth table for the standard SOP
expression ABC + ABC + ABC
 Domain = A, B, C. combinations = 23 = 8
 What binary value makes the product term
= 1? ABC
001 =111=1
ABC INPUTS OUTPUT PRODUCT
100 =111=1 TERM
A B C X
ABC
111 =111=1
0 0 0 0
0 0 1 1 ABC
0 1 0 0
0 1 1 0
1 0 0 1 ABC
 Fill the truth table 1 0 1 0
1 1 0 0
1 1 1 1 ABC
42
 Develop a truth table for the standard POS
expression (A + B + C)(A + B + C)(A + B +C)(A + B + C)(A + B +C)
 Domain = A, B, C. combinations = 23 = 8
 What binary value makes the sum term =
0?
(A + B + C)(A + B + C)(A + B +C)(A + B + C)(A + B +C)
0 0 0 0 1 0 0 1 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0
INPUTS OUTPUT PRODUCT
TERM
A B C X
0 0 0 0 (A + B + C)
 Fill the truth table 0 0 1 1
0 1 0 0 (A + B + C)
0 1 1 0 (A + B + C)
1 0 0 1
1 0 1 0 (A + B + C)
1 1 0 0 (A + B + C)
1 1 1 1
43
Determining Standard expressions
from a truth table
 Replace each binary number with its
corresponding variable.
 SOP = 1→ var. & 0 → var. complement
 POS = 0→ var. & 1 → var. complement
SOP POS
1010 ABCD 1001 A+B+C+D
ABCD = 1 0 1 0 A+B+C+D= 1+0+0+1
=1111=1 =0+0+0+0=0

44
 Karnaugh Map (K-Map)
45
 K-Map is similar to the truth table, but it
presents all of the possible values of input
and output.
 This is shown in an array of cells.
 K-Maps can be used for expressions with 2,3,4 or
5 variables.
 The number of cells in a K-Map = total number of
possible input variable combinations  3 = 23 = 8
 Cells that differ by only one variable are adjacent
(bersebelahan)
 Cell 010 is adjacent to 000, 011 and 110
 Physically, cells that share their walls are
adjacent
 In a K-map with 4-variable or more, the top-most
& bottom-most cells of a column (and row) are
adjacent.
 C C
0 1 0 1
46 AB AB
00 00 ABC ABC

01 01 ABC ABC
3-Variable Karnaugh Map
11 11 ABC ABC

10 10 ABC ABC

CD CD
00 01 11 10 00 01 11 10
AB AB
00 00 ABCD ABCD ABCD ABCD

01 01 ABCD ABCD ABCD ABCD

11 11 ABCD ABCD ABCD ABCD

10 10 ABCD ABCD ABCD ABCD

4-Variable Karnaugh Map

47
K-Map SOP Minimization
 K-Map is used to simplify Boolean expressions to
their minimum form.
 A minimized SOP expression has the fewest
possible term with each term having fewest
possible variables.
 A minimized SOP expression needs fewer logic
gates than standard expression.
 To map an SOP expression to a map:
 Step 1: determine the binary value of each product term
 Step 2: Place a 1 in a cell that have the same value as
the product term
 Example: Mapping SOP
48 expression
ABC + ABC + ABC + ABC

C ABC + ABC + ABC + ABC

AB
0 1 000 001 110 100
00 1 1

01

11 1

10 1
 Map the following expression
ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD

ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD

0011 0100 1101 1111 1100 0001 1010
ABCD
CD
AB 00 01 11 10
00 1 1 ABCD

01 1
ABCD
11 1 1 1

ABCD 10 1 ABCD

ABCD ABCD
49
 To use K-maps, expressions must be in
standard form.
 For expressions that are not standard, it
must be converted to a standard form.
 Recall: AB + ABC
 AB(C/C’)  11(1/0)  ABC + ABC’
 So: ABC + ABC’ + ABC C
AB 0 1
 Map the following expression on a K-map:
00 1 1
A + AB + ABC
000 100 110 01 1 1
001 101
11 1
010
011 10 1 1

50
 K-Map Simplification of SOP
51
Expressions
 There are 3 steps to obtain a minimum
SOP expression from a K-map.
1. Grouping the 1s
2. Determine product term for each
group
3. Summing the resulting product terms
 Grouping the 1s
52

 Group must contain cells in 2x combination

(i.e. 1,2,4,8,16
 Each cell must be adjacent to at least 1 other
cell in the group, but all cells in a group need
not be adjacent
 Try to have the biggest possible group of
1s
 Each 1 must be in at least one group.
 The 1s already in a group may be included in
another group so long as the overlapping
group includes non-common 1s
 Here are some examples:
 (a) (b) (c) (d)
C C CD CD
AB 0 1 AB 0 1 00 01 11 10 AB 00 01 11 10
AB
00 1 00 1 1 00 1 1 00 1 1
01 1 01 1 01 1 1 1 1 01 1 1 1
11 1 1 11 1 11 11 1 1 1
10 10 1 1 10 1 1 10 1 1 1

C C
AB 0 1 0 1 CD CD
AB AB 00 01 11 10 AB 00 01 11 10
00 1 00 1 1
00 1 1 00 1 1
01 1 01 1
01 1 1 1 1 01 1 1 1
11 1 1 11 1 11 1 1 1
11
10 10 1 1 10 1 1 1
10 1 1

(a) (b) (c) (d)

53
 Link
www.allaboutcircuits.com/vol_4/chpt_7/5.html
wps.prenhall.com/chet_floyd_digitalfun_10/86/22258/5698226.cw/inde
x.html

54