LOGIC SIMPLIFICATION USING ALGEBRAIC METHODS
Example
1: Prove that AB + AB′ = A.
Proof: LHS = A(B + B′) = A = RHS
Example
2: Prove that (A + B′) B = AB.
Proof: LHS = (A + B′)
B = AB +BB′ = AB = RHS
Example 3: Prove
that (A + B′) A = A,
Proof: LHS = (AA + AB′) = A (1+B′) = A = RHS
Example 4: Prove that A + A′B = A + B
Proof: LHS = A(1+B) + A′B
= A + AB + A′B = A+ B(1+ A′) = A + B
In the above proof, we have used the relation= A(1+B) = A.
Example 5: Prove that A⊕B⊕AB = A + B.
Proof: We first expand the term
where we have used B′B = 0. Now we expand using De Morgan the relation
B(AB)′ = B(A′+B′) = BA′
Then we find that A⊕ BA′ = A′BA′+ A(BA′)= A′B +
A(B′ + A)
Further reducing, we find that A′B +
A + AB′ = A′B + A(1+ B′)
which reduces to A′B + A(1+ B′) = A′B + A = A + B = RHS
Example 6: Prove that B
+ A′ B′C
= B + A′C
Proof: We have LHS = B + A′ B′C = B + B′ (A′C)
= B + A′C = RHS
where we
have used a relation similar to B + B′C = B + C.
Example 7: Prove that A + A′ B
+ A′ B′C + A′ B′
C′D + … = A + B + C +…
Proof: We know that A + A′ B
= A + B
Extending the above
relation, we find
A + B + A′ B′C
= A + (B + A′ B′C) = A + B + A′ C
where we have used the relation (B + A′ B′C)
= B + A′ C
But, we know that A + A′ C = A + C. Thus we obtain the relation
A + B + A′ B′C = A + (B + A′ B′C) = A + B + C
Carrying out this operation and mathematical induction, we
obtain the final relation: A
+ A′ B +
A′ B′C
+ A′ B′C′D
+ … = A + B + C + D +…
Hint: As stated earlier, logic simplification through algebraic methods is very tedious and
requires the knowledge of many fundamental theorems and laws, especially when
the RHS part is not given. To keep these theorems in memory is not that easy
since there exist several of them.
To simplify the procedure, we suggest that the student (especially
one who is writing an examination) first find the correct solution using an
appropriate Kmap. Once we have the answer with us, we can proceed to solve the
problem algebraically. As an example, we solve Example 6 (assuming the RHS part
is not given) using this method. For this, let us assume that the given problem
is stated as
A + A′ B + A′ B′C + A′ B′C′D + … = ?
In the above problem, since the RHS is not given, we are not
sure what the answer (RHS) would be. To find the answer (i.e., RHS), we first
draw the threevariable map M_{1}
as shown in Fig. E6a and enter the implicants A, A’B,
and A’B′C in it as shown.
Next we draw Kmap M_{2} as shown in Fig. E5b and remove the first
encirclements. Then we regroup them as shown in M_{2} to find what A + A′ B
+ A′ B′C would be.
From map M,
we get the answer as:
A + A′ B + A′ B′C = A + B + C
Now we are sure what the RHS would be in this case.
Knowing the answer in advance, we can prepare our strategy accordingly to solve
the problem.
Example 8: Prove that (i) A ⊕ A ⊕ A ⊕… = 0, if the number of A’s
is even
(ii) A ⊕ A ⊕ A ⊕… = A, if the number of A’s is odd
Proof: We know that
(i) A
⊕ A = A′ A + A A′ = 0
This means that if the number of A’s is even, then the sum will be 0. Now, if the number is odd
(say, three), we get
(ii) A ⊕ A ⊕ A = 0 + A = 0. A′ + 1. A =
A
Extending the above two results, using mathematical induction,
we get the desired results.
Example 9: Prove that AB ⊕
AB′ = A
Proof: LHS = AB ⊕
AB′ = AB(AB′)′ + (AB)′ AB′
= AB(A′+B) + (A′+B′) AB′
= AB + AB′ = A =RHS
Example
10: Prove that A′
+ B′ + ABC′ = A′ + B′ + C′
Proof: We know that A′ + ABC′ = A′ + BC′
Using the above relation we find LHS = A′ + B′ + BC′ = A′ + B′ + C′ = RHS
Example 11: Prove that x′y′z +yz + xz = ?
Proof: LHS = z(y + y′x′) + xz = z(y + x′) + xz
= zy + zx′ + xz = zy + z = z = RHS
Example 12: Reduce the expression
Proof: Applying De Morgan on the barred term
in square brackets yields
Example 13: Prove that: xy + x′y′ + yz = xy + x′y′ + x′z
Proof: LHS
= xy + x′y′ + yz (1 + x′) = xy + x′y′ + yz +yzx′
= xy + x′(y′ + yz) + yz = xy + x′y′ + x′z + yz
= (xy + yz
+ x′z) + x′y′ = xy + x′z +x′y′ = RHS
where we have applied the consensus theorem on the
bracketed terms.
Example 14: Prove that: A′C′ + ABD + AB′D′ + ABCD′ = ?
Proof: Since the
RHS is not given, we use a Kmap and find the RHS
Example 15: Prove the De Morgan’s laws, viz.,(A + B)′ = A′B′ and (AB)′ = A′ + B′.
Proof: These laws were enunciated by Augustus De
Morgan (to be pronounced as da morgan),
a nineteenth century British mathematician. To prove these laws, we make use of
truth tables: Table E14a is used to prove the first law. It can be observed
that the entries in the rightmost two columns are the same; this proves the
first law.
Truth Table
E14a Proof
of (A + B)′ = A′B′
A

A′

B

B′

A+B

(A+B)′

A′ B′

0
1

1
0

0
1

1
0

0
1

1
0

1
0

Table E14b proves the second law. The entries related to the
second law are as shown in the table. As in the first case, in this case also
the entries in the rightmost two columns are the same, which proves the second
law.
Example
16:
Prove the transposition theorem,
which states that
AB + A′C = (A′ + B)(A + C)
Solution: Consider the RHS. We find
RHS = (A′ + B)(A + C) = A′A + A′C + BA + BC = A′C + BA + BC
where we have used the basic law A′A = 0. Now, the remaining expression A′C+BA+BC can
be seen
to be a statement of the
consensus theorem, which reduces to A′C+BA. That is,
AB + BC + A′C = AB +A′C = LHS
Example
17: Involution law: This
law states that (A′)′ = A
Proof: Involution law becomes highly useful in
solving problems applying De Morgan’s laws. The
law can be proved using the truth table E16. We find that the first and last
columns agree with each other, which proves the law.
Truth Table E16 Involution Law
Truth Table E16 Involution Law
A

A’

(A′)′= A

0
1

1
0

0
1

Solution: The logic function Z = AB′ + A′B is called the EXCLUSIVEOR
(EXOR or XOR) function. This
relation can be derived from Table E17a, the truth table for the OR function.
Truth Table E17a The OR function
Truth Table E17a The OR function
A

B

Z = A+B

0
0
1
1

0
1
0
1

0
1
1
1

In Table E17a, if we change the last row as shown in
Table E17b, we get the XOR function.
Truth Table E17b The XOR function
Truth Table E17b The XOR function
A

B

Z = A ⊕ B 
0
0
1
1

0
1
0
1

0
1
1
0

From Table E17b, we get the XOR relation, A ⊕ B
= AB′ + A′B
where the symbol ‘⊕’ represents the XOR operation. It is to be noted that it is
the XOR operation (and not the OR operation) that really represents the
algebraic addition of two bits.
Example
19: Define
the EXNOR
function.
Solution: The logic statement (A′B+AB′)′ is
called the EXCLUSIVENOR (EXNOR or XNOR) function.
This relation is derived from the truth table for the OR function as shown
below. EXNOR represents the complementary operation of the algebraic addition
of two bits. The EXNOR operation in the last column may be read as “NOT of
either A OR B”.
Truth Table E18 The XNOR function
Truth Table E18 The XNOR function
A

B

A ⊕ B

(AB′ +
A′B)′

0
0
1
1

0
1
0
1

0
1
1
0

1
0
0
1

From Table E18, we get the EXNOR relation as (A ⊕ B)′
= A′B′ + AB
Example 20:
Use De Morgan’s laws
to expand the XNOR relation.
Solution: The
XOR operation given
by
Z = (AB′ +
A′B)′
Since XNOR operation is the complement of , by applying De Morgan
on the RHS, we get
Z = (AB′)′.(A′B)′
Applying De Morgan on the two RHS terms individually
yields
Z = [A′ + (B′)′][(A′)′+ B′]
= AB + A′B′
Thus we get
Example 21: Explain the principle of duality.
Solution:
Consider the
function
f(x) = x_{1
}+ x_{2}∙x_{3} + x_{4}∙x_{5}∙x_{6} (1)
Replacing the pluses with dots and dots with pluses in the
RHS of Eq. (1), we get a new function
_{ }F(x) = x_{1 }∙ (x_{2} + x_{3}) ∙ (x_{4 }+ x_{5} + x_{6}) (2)
The function F(x) defined in Eq. (2) is called the dual of the function f(x). We find that f(x)
and F(x) are equally valid functions and duality is a special property of
Boolean (binary) algebra. The property of duality exists in every stage of
Boolean algebra. For example, positive and negative logic schemes are dual
schemes. Similarly, AND is the dual of OR, NAND is the dual of NOR, and so on.
To illustrate further, consider the De Morgan’s law
(A
+ B)′ =
A′.B′ (1)
Now, in Eq. (1), replace the plus with a dot and the dot with
a plus; this action yields the expression
(A.B)′ =
A′ + B′ (2)
We find that Eq. (2) is the complementary De Morgan’s
law. This suggests that the De Morgan’s laws form a dual pair.
We now state that every rule and law applicable to a
positivelogic scheme is applicable to its corresponding_{ }negative
(or, complementary) logic scheme also. We now formally define the dual of a
given function as follows:_{
}
A function F(x) is said to be
the dual of another function f(x), provided that F(x) is obtained from f(x) by replacing the multiplication signs
(∙) and summation signs (+) in f(x) with summation signs and multiplication signs, respectively, and with no
change in the variables of f(x).
The definition given above may also be
considered as the duality theorem. In this context, we may define duality as the state of being dual.
Example 22: Find (ABC′)+(ABC′)′
Solution: Let
us assume that ABC′ = P. Then we find that (ABC′)′
= P′. Now the given function can be written as:
(ABC′) + (ABC′)′ = P + P′ = 1
Example 23: Find (ABC′)+(ABC′)′ using a different method.
Solution:
Applying De Morgan
on the bracketed term yields
(ABC′) + (ABC′)′ = ABC′+A′+B′+C
But we know that ABC′+A′ = BC′+A′
and
A′+BC′+B′ = C′+B′+A′
Finally,
C′+B′+C + A′= (C′+ C)
+B′ + A′ = 1
Example 24: Find w(x +
y′z) + x + y′z.
Solution: Expanding the
given expression yields
wx + wy′z + x + y′z = wx + x + wy′z
+ y′z
= x + y′z
Example 25: Find (w + x′ +
yz)(w′ + x′ + yz).
Solution: Expanding the
given expression yields
(w + x′ +
yz)(w′ + x′ + yz) = wx′ + wyz +
x′ w′ + x′ + x′yz + yzw′ + yzx′ + yz
= wx′ + wyz + x′ w′ + x′ +
x′yz + yzw′ + yzx′ + yz
= x′ (w +w′)+
yz (w +w′)+ x′ (1 + yz) + yz (x′ + 1)
= x′ + yz + x′ + yz
= x′ + yz
Example 26: Find (a + b′)(a
+ c + d)(a + c + d′).
Solution: Performing
the first multiplication in the given expression yields
(a + b′) (a + c + d)
= (a + ac + ad) + b′c + b′d
=a + b′c + b′d
Now, we perform the second multiplication, which gives
(a + b′c
+ b′d) (a + c + d′) = (aa + ac+ ad′ + ab′c + ab′d) +
(b′c + b′cd′ + b′cd)
= a + b′c
Example 27: Find ab′(c + d)
+ (c + d)′.
Solution: Performing
the first multiplication and applying De Morgan to the complemented (third)
term in the given expression yields
(ab′)(c + d)
+ (c + d)′ = ab′c + ab′d + c′d′
Now, we are in confusion regarding the route through
which we have to move to reach the destiny. As the first step, we try expanding
the term c′d′. This is because the term c′d′ contains four 4variable terms, given within
brackets below, and contains components related to ab′c and ab′d. Thus we find
RHS = ab′c + ab′d + (a′b′c′d′ + a′bc′d′ + abc′d′ + ab′c′d′)
Now, we find that terms
ab′d + ab′c′d′ = ab′(d + c′d′)
= ab′d + ab′c′
Using the above two factors, the RHS may be expressed as
RHS = ab′c + ab′d + ab′c′ + a′b′c′d′ + a′b c′d′ + ab c′d′
Combining factors ab′c
and ab′c yields
RHS = ab′ +
ab′d + a′b′c′d′ + a′bc′d′ + abc′d′
Combining factors ab′ and ab′d, we get
RHS
= ab′ + a′b′c′d′ + a′bc′d′ + abc′d′
Combining factors a′b′c′d′ and
a′bc′d′
RHS = ab′ + a′c′d′ + abc′d′
Finally, combining factors a′c′d′
and a′bc′d′, we obtain the reduced expression as
RHS = ab′ +
c′d′
It
can be seen that the reduction process is quite laborious and lengthy. Further,
the reduction has been performed based on hunches and previous experience. Experiences and difficulties of this kind
led to the development of the Kmap and QM methods of Boolean reduction.
Example 28: Find a + b + c′d(a + b)′.
Solution: Performing
the first multiplication and applying De Morgan to the complemented (third)
term in the given expression yields
a + b + c′d
(a + b)′ = a + b
+ c′d (a′b′) = a + b + a′b′c′d
= (a
+ a′b′c′d) + b = a + b′c′d + b
Example 29: Find [(ab)′ + a′
+ ab]′.
Solution: Applying De
Morgan to the terms within the square brackets yields
[(ab)′ + a′
+ ab]′ = [(ab)′]′
∙ a ∙ (ab)′
Applying De Morgan to RHS terms, we get
[(ab)′]′
∙ a ∙ (ab)′ = ab ∙ a
∙ (a′ + b′) = ab (a′ + b′)
= 0
[Note: This may also be reduced at the second stage itself
(without second the demorganization. For this observe that
[(ab)′]′ ∙ a ∙ (ab)′ = (ab) ∙ (ab)′ = 0
Example 30: Prove that (a + b′)(b + c′)(c + d′)(d + a′) = (a′ + b)(b′ + c)(c′ + d)(d′ + a)
Solution: Multiplying
the individual terms in LHS yields
LHS
= (ab + ac′ + b′c′)(cd
+
ca′ + d′a′) =
abcd + b′c′d′a′ (1)
Similarly, multiplying the RHS terms yields
RHS = (a′b′ + a′c + bc)(c′d′ + c′a + da) = a′b′c′d′ + bcda (2)
We find that
Equation (1) = Equation (2)
which is the desired result.
No comments:
Post a Comment