Lecture six

BOOLEAN ALGEBRA AND LOGIC SIMPLIFICATION

1. BOOLEAN OPERATIONS AND EXPRESSIONS
o Variable, complement, and literal are terms used in Boolean algebra.
o A variable is a symbol used to represent a logical quantity.
⌂ Any single variable can have a 1 or a 0 value.
o The complement is the inverse of a variable and is indicated by a bar over
variable (overbar).
⌂ For example, the complement of the variable A is A ̅ . If A = 1, then A
̅
= 0. If A = 0, then A̅ = 1. The complement of the variable A is read as
"not A" or "A bar."
⌂ Sometimes a prime symbol rather than an overbar is used to denote
the complement of a variable; for example, B' indicates the
complement of B.
o A literal is a variable or the complement of a variable.

 Boolean Addition
o The Boolean addition is equivalent to the OR operation.
o In Boolean algebra, a sum term is a sum of literals.
o In logic circuits, a sum term is produced by an OR operation with no AND
operations involved.
o Some examples of sum terms are A + B, A + B ̅, A + B + C̅, and A
̅+B+C+
̅.
D
o A sum term is equal to 1 when one or more of the literals in the term are 1.
o A sum term is equal to 0 only if each of the literals is 0.

̅+
Example: Determine the values of A, B, C, and D that make the sum term A + B
C+D̅ equal to 0.

Solution:

A= 0, B= 1, C= 0, and D=1.

 Boolean Multiplication
o The Boolean multiplication is equivalent to the AND operation.
o In Boolean algebra, a product term is the product of literals.

Lecture 6 Digital Techniques lecturer: hayder sahib 1

 o In logic circuits, a product term is produced by an AND operation with no
OR operations involved.
o Some examples of product terms are AB, AB ̅, ABC, and A ̅ BCD̅.
o A product term is equal to 1 only if each of the literals in the term is 1.
o A product term is equal to 0 when one or more of the literals are 0.

Example: Determine the values of A, B, C, and D that make the product term
̅ BCD
A ̅ equal to 1.

Solution:

A= 0, B= 1, C= 1, and D= 0.

2. LAWS AND RULES OF BOOLEAN ALGEBRA

 Laws of Boolean Algebra
The basic laws of Boolean algebra (Commutative laws for addition and
multiplication, Associative laws for addition and multiplication, and
Distributive law) are the same as in ordinary algebra.

 Commutative Laws
If A and B ∈ S then:
(i) A+B=B+A (figure 1)
(ii) A . B = B . A (figure 2)

Fig.(1) Application of commutative law of addition.

Fig.(2) Application of commutative law of multiplication.

Lecture 6 Digital Techniques lecturer: hayder sahib 2

  Associative Laws
If A and B ∈ S then:
(i) A + (B + C) = (A + B) + C (figure 3)
(ii) A(BC) = (AB)C (figure 4)

Fig.(3) Application of associative law of addition.

Fig.(4) Application of associative law of multiplication.

 Distributive Law
If A and B ∈ S then:
(i) (B + C) . A = (A . B) + (A . C) (Figure 5-a)
(ii) (B . C) + A = (A + B) . (A + C) (Figure 5-b)

(a)

(b)

Fig.(5) Application of distributive law.

Lecture 6 Digital Techniques lecturer: hayder sahib 3

 Rules of Boolean Algebra
Table 1 lists 12 basic rules that are useful in manipulating and simplifying
Boolean expressions. Rules 1 through 9 will be viewed in terms of their
application to logic gates. Rules 10 through 12 will be derived in terms of the
simpler rules and the laws previously discussed.

Table 1: Basic rules of Boolean algebra.

1 A+0=A 7 A.A=A
2 A+1=1 8 ̅=0
A. A
3 A.0=0 9 ̿=A
A
4 A.1=A 10 A+AB=A
5 A+A=A 11 A+A̅ B=A+B
6 A+A̅ =1 12 (A+B).(A+C)=A+BC

Rule 1 (A+0=A):

For A = 0, LHS = 0 + 0 = 0 = RHS.

For A = 1, LHS = 1 + 0 = 1 = RHS.

This rule is illustrated in Fig.(6), where the lower input is fixed at 0.

Figure 6: Rule 1

Rule 2 (A+1=1):
For A = 0, LHS = 0 + 1 = 1 = RHS.

For A = 1, LHS = 1 + 1 = 1 = RHS.

This rule is illustrated in Fig.(7), where the lower input is fixed at 1.

Figure 7: Rule 2

Lecture 3 Digital Techniques lecturer: hayder sahib 4

Rule 3 (A.0=0):
For A = 0, LHS = 0.0 = 0 = RHS.
For A = 1, LHS = 1.0 = 0 = RHS.
This rule is illustrated in Fig.(8), where the lower input is fixed at .

Figure 8: Rule 3

Rule 4 (A.1=A):

For A = 0, LHS = 0.1 = 0 = RHS.

For A = 1, LHS = 1.1 = 1 = RHS.
This rule is illustrated in Fig.(9), where the lower input is fixed at .

Figure 9: Rule 4

Rule 5 (A+A=A):
For A = 0, LHS = 0+0 = 0 = RHS.
For A = 1, LHS = 1+1 = 1 = RHS.
This rule is illustrated in Fig.(10), where the lower input is fixed at .

Figure 10: Rule 5

Rule 6 (A+𝐀 ̅ =1):

For A = 0, A̅ =1, LHS = 0 + 1 = 1 = RHS.
For A = 1, A̅ =0, LHS = 1 + 0 = 1 = RHS.
This rule is illustrated in Fig.(11), where the lower input is fixed at .

Figure 11: Rule 6

Lecture 6 Digital Techniques lecturer: hayder sahib 5

Rule 7 (A.A=A):
For A = 0, LHS = 0.0 = 0 = RHS.
For A = 1, LHS = 1.1 = 1 = RHS.
This rule is illustrated in Fig.(12), where the lower input is fixed at .

Figure 12: Rule 7

Rule 8 (𝐀. 𝐀̅ = 𝟎):

For A = 0, A̅ =1, LHS = 0 . 1 = 0 = RHS.
For A = 1, A̅ =0, LHS = 1 . 0 = 0 = RHS.
This rule is illustrated in Fig.(13), where the lower input is fixed at .

Figure 13: Rule 8

Rule 9 (𝐀̿ = 𝐀):

This rule is shown in Fig.(14) using inverters.

Figure 14: Rule 9

Lecture 6 Digital Techniques lecturer: hayder sahib 6

Rule 10 (A+AB=A):
This rule can be proved by applying the distributive law, rule 2, and rule 4 as
follows:
A + AB = A( 1 + B) Factoring (distributive law)
=A.l Rule 2: (1 + B) = 1
=A Rule 4: A . 1 = A
The proof is shown in Table 2, which shows the truth table and the resulting logic
circuit simplification.

Table 2
A B AB A+AB
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Figure 15: Rule 10

Rule 11 (A+𝐀 ̅ B=A+B):

This rule can be proved as follows:
A+A ̅ B = (A + AB) + A ̅B 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) ̅=1
Rule 6: A + A
=A + B Rule 4: drop the 1
The proof is shown in Table 3, which shows the truth table and the resulting logic
circuit simplification.

Table 3
A B ̅ B A+A
A ̅ B A+B
0 0 0 0 0
0 1 1 1 1
1 0 0 1 1
1 1 0 1 1

Figure 16: Rule 11

Lecture 6 Digital Techniques lecturer: hayder sahib 7

Rule 12 ((A+B).(A+C)=A+BC):
This rule can be proved as follows:
(A + B)(A + C) = AA + AC + AB + BC Distributive law
= A + AC + AB + BC Rule 7: AA = A
= A( 1 + C) + AB + BC Rule 2: 1 + C = 1
= A. 1 + AB + BC Factoring (distributive law)
= A(1 + B) + BC Rule 2: 1 + B = 1
= A. 1 + BC Rule 4: A . 1 = A
= A + BC
The proof is shown in Table 4, which shows the truth table and the resulting logic
circuit simplification.

Table 4
A B C A+B A+C (A+B)(A+C) BC A+BC
0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 1 1 1 1
1 0 0 1 1 1 0 1
1 0 1 1 1 1 0 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1

Figure 17: Rule 12

Lecture 6 Digital Techniques lecturer: hayder sahib 8

3. DEMORGAN'S THEOREMS
o DeMorgan, a mathematician who knew Boole, proposed two theorems that
are an important part of Boolean algebra.
o In practical terms, DeMorgan's theorems provide mathematical verification
of the equivalency of the NAND and negative-OR gates and the
equivalency of the NOR and negative-AND gates.

⌂ DeMorgan's first theorems is stated as follows:

“The complement of two or more ANDed variables is equivalent to the OR of
the complements of the individual variables”.
̅̅̅̅ = X
o The formula for expressing this theorem for two variables is XY ̅+Y
̅
⌂ DeMorgan's second theorem is stated as follows:
“The complement of two or more ORed variables is equivalent to the AND of
the complements of the individual variables”,
̅̅̅̅̅̅̅̅̅
o The formula for expressing this theorem for two variables is X + Y=̅ X̅
Y
o Fig.(15) shows the gate equivalencies and truth tables for the two equations
above.

A B ̅̅̅̅
AB ̅ +B
A ̅
0 0 1 1
0 1 1 1
1 0 1 1
1 1 0 0
A ̅̅̅̅̅̅̅
B A +B ̅ .B
A ̅
0 0 1 1
0 1 0 0
1 0 0 0
1 1 0 0
Figure 18:Gate equivalencies and the corresponding truth tables that illustrate
DeMorgan's theorems.

Example: Apply DeMorgan's theorems to the expressions ̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅

XYZ and X + Y + Z.
Solution:

̅̅̅̅̅= X
XYZ ̅+Y ̅ + Z̅
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
X + Y + Z=̅ X ̅
Y Z̅

Lecture 6 Digital Techniques lecturer: hayder sahib 9

 ̅̅̅̅̅̅̅̅ and
Example: Apply DeMorgan's theorems to the expressions WXYZ
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
W + X + Y + Z.
Solution:
̅̅̅̅̅̅̅̅= W
WXYZ ̅ +X
̅+Y
̅ + Z̅
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
W + X + Y + Z=W ̅ ̅
X ̅
Y Z̅
Example: Apply DeMorgan's theorems to the following expressions:
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅
A + BC̅ + D(E + F̅)
Solution:
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
̅̅̅̅̅̅̅̅̅
A + BC̅ + D(E ̅̅̅̅̅̅̅
+ F̅) = A + BC̅ . ̅̅̅̅̅̅̅̅̅̅̅̅
̿̿̿̿̿̿̿̿̿ D(E ̅̅̅̅̅̅̅
+ F̅)
(A + BC̅). (D ̅ + (E ̿̿̿̿̿̿̿
+ F̅))
(A + BC̅). (D ̅ + E + F̅)

H.W: Apply DeMorgan's theorems to each of the following expressions:

(a) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(A + B + C)D
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(b) ABC + DEF
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(c) AB̅ + CD ̅ + EF

4. BOOLEAN ANALYSIS OF LOGIC CIRCUITS

o Boolean algebra provides a concise way to express the operation of a logic
circuit formed by a combination of logic gates so that the output can be
determined for various combinations of input values.
 Boolean Expression for a Logic Circuit
o To derive the Boolean expression for a given logic circuit, begin at the left-
most inputs and work toward the final output, writing the expression for
each gate.
o For the example circuit in Fig.(16), the Boolean expression is determined as
follows:

From the left-most inputs:

Out of AND1= CD
Out of OR= B + CD
Out of AND2= A.(B + CD)

Lecture 6 Digital Techniques lecturer: hayder sahib 10

 Figure 19: A logic circuit showing the development of the Boolean expression for
the output.
 Constructing a Truth Table for a Logic Circuit
o Once the Boolean expression for a given logic circuit has been determined,
a truth table that shows the output for all possible values of the input
variables can be developed.
o The procedure requires that you evaluate the Boolean expression for all
possible combinations of values for the input variables. In the case of the
circuit in Fig.(19), there are four input variables (A, B, C, and D) and
therefore sixteen (24 = 16) combinations of values are possible as follows.

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

Lecture 6 Digital Techniques lecturer: hayder sahib 11

5. SIMPLIFICATION USING BOOLEAN ALGEBRA
o A simplified Boolean expression uses the fewest gates possible to implement
a given expression.
Example: Using Boolean algebra techniques, simplify this expression:
AB + A(B + C) + B(B + C)
Solution:
Step 1: Apply the distributive law to the second and third terms in the expression,
as follows:
AB + AB + AC + BB + BC
Step 2: Apply rule 7 (BB = B) to the fourth term.
AB + AB + AC + B + BC
Step 3: Apply rule 5 (AB + AB = AB) to the first two terms.
AB + AC + B + BC
Step 4: Apply rule 10 (B + BC = B) to the last two terms.
AB + AC + B
Step 5: Apply rule 10 (AB + B = B) to the first and third terms.
B+AC
At this point the expression is simplified as much as possible. Fig.(4-17) Gate
circuits for example above.

Figure 20: Gate circuits for example above.

Lecture 6 Digital Techniques lecturer: hayder sahib 12

Example: Prove that: ABCD+ABC̅D ̅ + ABCD̅ + ABC̅D+ ABCDE
̅+ ABC̅D
̅ E+
ABC̅DE can be simplified to A.B
Solution:
̅D
ABCD + ABC ̅ + ABCD̅ + ABC̅D + ABCDE ̅ + ABC̅D ̅ DE
̅ E + ABC
 ABCD(1 + E̅) + ABC̅D ̅ + ABC̅D(1 + E)
̅ (1 + E) + ABCD
 ABCD + ABC̅D̅ + ABCD̅ + ABC̅D
 A. B(CD + C̅D
̅ + CD ̅ + C̅D)
 A. B(C(D + D̅ ) + C̅(D
̅ + D))
 A. B(C(1) + C̅(1))
 A. B(C + C̅)
 A. B

H.W: Simplify the Boolean expressions:

̅ + A(B
1- AB ̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅
+ C) + B(B + C).
2- [AB̅( C + BD) + A̅B̅]C
̅ BC + AB
3- A ̅C̅ + A
̅B̅C̅ + AB
̅C + ABC

Finish

Lecture 6 Digital Techniques lecturer: hayder sahi

sahib 13