ECE275 - Digital Systems: September 2011

Friday, September 23, 2011

CONSENSUS THEOREM

Consensus theorem states:

XY + X’Z + YZ = XY + X’Z

The YZ term is called the consensus term and is redundant. The consensus term is formed from a PAIR OF TERMS in which a variable (X) and its complement (X’) are present; the consensus term is formed by multiplying the two terms and leaving out the selected variable and its complement.

The consensus of XY, X’Z is YZ .

Consensus Theorem 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

You could also use a truth table to prove this.

DUAL OF THE CONSENSUS THEOREM

(X + Y) (X’ + Z) (Y + Z) = (X + Y) (X’ + Z)

The consensus of (X + Y)(X’+ Z) is (Y + Z)

How do you use a consensus term? Use it to eliminate a redundant term from the original boolean expression

How to identify possible consensus forming terms?

1) Simply be suspicious anytime you have two terms that have a variable and its complement.

2) Form the consensus term and see if it is present in the original Boolean expression; if consensus term is present, just get rid of it.

EXAMPLE:

A’C’D + A’BD + BCD + ABC + CAD’ the term in red can be eliminated by consensus theorem.

A’C’D + A’BD + BCD + ABC + ACD’ start over -- this time eliminate two other terms

Now Consider:

F = ABCD + B’CDE + A’B’ + BCE’ cannot reduce by consensus thm.

F = ABCD + B’CDE + A’B’ + BCE’ + ACDE add the consensus term ACDE first

F = BCE’ + ABCD + ACDE + A’B’ +B’CDE + ACDE

Then the two underlined terms become redundant by consensus thm.

LOGIC EXPRESSION MINIMIZATION

Goal is to find an equivalent of an original logic expression that:

a) has fewer variables per term
b) has fewer terms
c) needs less logic to implement

There are three main manual methods
Algebraic minimization
Karnaugh Map minimization
Quine-McCluskey (tabular) minimization