Powerpoint - Choopan Rattanapoka

Report
CONSENSUS THEOREM
Choopan Rattanapoka
Introduction to The Consensus Theorem


The consensus theorem is very useful in simplifying
Boolean expressions.
Given an expression of the form
 XY
+ X’Z + YZ then term YZ is redundant and can be
eliminated to form the equivalent expression
 XY

+ X’Z
The eliminated term is referred to as the consensus
term.
Consensus Term



Given a pair of terms for which a variable appears
in one term and the complement of that variable
in another .
The consensus term is formed by multiplying the
two original terms together, leaving out the
selected variable and its complement.
Example :
 AB
and A’C , consensus is BC
 ABD and B’DE’, consensus is (AD)(DE’)  ADE’
The consensus theorem (1)


The consensus theorem can be stated as follows:
XY + X’Z + YZ = XY + X’Z
Proof
XY + X’Z + YZ  XY + X’Z + (X + X’)YZ
 XY + X’Z + XYZ + X’YZ
 (XY + XYZ) + (X’Z + X’YZ)
 XY(1 + Z) + X’Z(1 + Y)
 XY + X’Z
The consensus theorem (2)

Example : Simplify this expression
A’B’ + AC + BC’ + B’C + AB
A’B’ + AC + BC’ + B’C + AB
Ans : A’B’ + AC + BC
The consensus theorem (3)


The dual form of the consensus theorem is
(X + Y)(X’ + Z)(Y + Z) = (X + Y)(X’ + Z)
Example : (A + B + C’)(A + B + D’)(B + C + D’)
 The
Consensus of (A + B + C’) and (B + C + D’) is
(A + B + D’)
 Thus,
we can eliminate the consensus term
 Answer : (A + B + C’)(A + B + D’)
Consensus Term Eliminating Order (1)

Attention
 The
final result obtained by application of the
consensus theorem may depend on the order in which
terms are eliminated.

Example :
A’C’D + A’BD + BCD + ABC + ACD’
 Eliminate BCD terms (consensus of A’BD , ABC)
 A’C’D + A’BD + ABC + ACD’
(No more eliminated term.)
Consensus Term Eliminating Order (2)

Same Example :
A’C’D + A’BD + BCD + ABC + ACD’
 Eliminate A’BD terms (consensus of A’C’D , BCD)
 A’C’D + BCD + ABC + ACD’
 Eliminate ABC terms (consensus of BCD, ACD’)
 A’C’D + BCD + ACD’ (no more eliminated term)
Trick to use consensus theorem


Sometimes it is impossible to directly reduce an
expression to a minimum number of terms by simply
eliminating terms.
It may be necessary to first add a term using the
consensus theorem and then use the added term to
eliminate other terms.
Example

F = ABCD + B’CDE + A’B’ + BCE’
of ABCD and B’CDE  ACDE
 Consensus of A’B’ and BCE’  ACE’
 But none of them appear in the original expression.
 Consensus

However, if we first add the consensus ACDE to F
F
= ABCD + B’CDE + A’B’ + BCE’ + ACDE
 Consensus of ACDE and A’B’  B’CDE
 Consensus of ACDE and BCE’  ABCD
 Thus, F = A’B’ + BCE’ + ACDE
Exercise 1



Simplify each of the following expressions using
only the consensus theorem
BC’D’ + ABC’ + AC’D + AB’D + A’BD’ (reduce to 3 terms)
W’Y’ + WYZ + XY’Z + WX’Y (reduce to 3 terms)
Algebraic Simplification (1)

Combining terms
 XY
+ XY’ = X
 Example : abc’d’ + abcd’ = abd’ (X = abd’, Y = d)

Complex example :
+ abc + a’bc  (X + X = X)
 ab’c + abc + abc + a’bc
 ab’c

ac
+
bc
Algebraic Simplification (2)

Eliminating terms
X
+ XY = X
 Example
:
 a’b + a’bc = a’b (X = a’b, Y = c)
 XY
+ X’Z + YZ = XY + X’Z (consensus theorem)
 Example
:
 a’bc’ + bcd + a’bd = a’bc’ + bcd (X = c, Y = bd, Z = a’b)
Algebraic Simplification (3)

Eliminating literals
X
+ X’Y = X + Y
 Simply factoring may be necessary before the theorem
is applied
 Example :
 A’B
+ A’B’C’D’ + ABCD’ = A’(B + B’C’D’) + ABCD’
= A’(B + C’D’) + ABCD’
= A’B + AC’D’ + ABCD’
= B(A’ + ACD’) + AC’D’
= B(A’ + CD’) + AC’D’
= A’B + BCD’ + AC’D’
Algebraic Simplification (4)

Adding redundant terms.

Redundant terms can be introduced in several ways such as
adding xx’
 multiplying by (x + x’)
 Adding yz to xy+x’z
 Adding xy to x
 Example :
 WX + XY + X’Z’ + WY’Z’ = A’(B + B’C’D’) + ABCD’
= WX + XY + X’Z’ + WY’Z’ + WZ’ (add WZ’ by consensus term)
= WX + XY + X’Z’ + WZ’ (WZ’ + WY’Z’  WZ’)
= WX + XY + X’Z’ (eliminate WZ’ [consensus of WX and X’Z’])

TODO

1)
2)
Simplify to a sum of three terms:
A’C’D’ + AC’ + BCD + A’CD’ + A’BC + AB’C’
A’B’C’ + ABD + A’C + A’CD’ + AC’D + AB’C’

similar documents