Boolean Logic - Working with Consensus Terms

In this blog entry we'll be looking at consensus terms in Boolean logic. What they are, what they tell us, why they are useful, and how to work with them. Although some of these concepts lend themselves very nicely to dipictions using Karnaugh Maps, we will work in strictly algebraic terms, if for no other reason that to show how something that most people only know how to deal with using K-maps can be done algebraically.

First, don't let fancy terminology confuse you. The name 'consensus term' was coined by Willard Van Orman Quine in 1955, although the concept had been introduced by Archie Blake in 1937. If it helps, realize that he could have called them "poodle terms" after his favorite type of dog. Having said that, he did choose the name with the intent of conveying meaning, so it is worth touching on that. The notion of a "consensus" generally means several viewpoints coming together and, between them, arriving at a solution that no single viewpoint captured individually. In the case of Boolean logic, the notion is remarkably similar -- two terms, when considered together, permit a third term to be identified that would not be true except for the contribution of both original terms.

This is best demonstrated by a simple example. Consider the following logic expression:

Y = A'B + AC

What is far from obvious, is that this is equal to

Y = A'B + AC + BC

To see that this is indeed the case, let's enumerate the truth table and each of these terms:


A|B|C| Y |A'B|AC|BC
0|0|0| 0 | 0 | 0| 0
0|0|1| 0 | 0 | 0| 0
0|1|0| 1 | 1 | 0| 0
0|1|1| 1 | 1 | 0| 1
1|0|0| 0 | 0 | 0| 0
1|0|1| 1 | 0 | 1| 0
1|1|0| 0 | 0 | 0| 0
1|1|1| 1 | 0 | 1| 1

As you can see, the rows that are covered by the term BC are completely covered by the original two terms -- but that it requires BOTH of the original terms to cover them. Hence the term BC is produced by the 'consensus' of the other two terms.

So why bother? What utility does this have?

There are actually two very practical uses for this property. If you are attempting to minimize a Boolean expression and were given the second form above having three terms, you could eliminate the final term as being redundant and get the first expression having just two terms. But, of course, you could only do that if you could identify that the term BC is truly redundant. But it turns out that, in designing real-world logic systems that are reliable, we often want to start with an expression such as the first one and add any consensus terms explicitly to it. In doing so, we eliminate so-called "static-1 hazards" from our design.
To see what a static-1 hazard is, consider the first equation under the conditions that all three inputs are True:

Y = A'B + AC = (0)(1) + (1)(1) = 1

Now let A go from True to False. The end result is

Y = A'B + AC = (1)(1) + (0)(1) = 1

So our system will put out a logic True both before and after the change. In other words, the output should remain 'static' at a '1' level, or 'static-1', throughout this transition. But think of the mechanics involved. We have two AND gates (or however the logic is ultimately implemented) whose outputs are OR'ed together and during this transition an input to each of them is changing. Since nothing changes instantaneously or simultaneously, one of those AND gates will output its new level before the other. If the first one changes first, then we go through the follwing sequence:

Y = A'B + AC = (0)(1) + (1)(1) = 1
Y = A'B + AC = (1)(1) + (1)(1) = 1
Y = A'B + AC = (1)(1) + (0)(1) = 1

And everything is fine. But if the second one changes first, we get the following:

Y = A'B + AC = (0)(1) + (1)(1) = 1
Y = A'B + AC = (0)(1) + (0)(1) = 0
Y = A'B + AC = (1)(1) + (0)(1) = 1

And we will have a momentary False that is output when it shouldn't have been. This is known as a 'glitch' and the fact that the design is susceptible to producing it is denoted by saying that it posesses a static-1 hazard. In case you are wondering, there are also "static-0 hazards" which simply means that a circuit that should output an unchanging False level when one of the inputs is changed has the potential to "glitch HI" and briefly output a logic True during the transition.

These glitches do not last long, perhaps only a fraction of a nanosecond. But this is long enough for some logic, particularly edge-triggered logic such as flip flops, to respond.

With this practical view of what a consensus term is, we are actually in a good position to see how to either identify them or to generate them as needed. The key is to consider what has to be true of the two terms that produce a consensus term. As we have seen, it must be possible for the OR of both terms to remain true when only a single signal changes state as a result of one term going from True to False while the other goes from False to True. In order for this to happen, there must be exactly one variable that appears uncomplemented in one term and complemented in the other. As for the rest of the variables in the two terms, the situation we are looking for will arise only when ALL of them are True (as used in the terms, meaning that a variable might need to be False because it appears in complemented form within the two terms). The two terms may share other variables, but they don't have to. But, if they do share a variable, then that variable must appear the same way, complemented or uncomplemented, in BOTH terms.

So let's look at the simpler task of producing consensus terms based on what we have learned. In the following expression, there are two consensus terms that can be generated. What are they?

Y = ACD' + BC + B'C' + C'D

The terms are

ACD' + B'C' = AB'D'
BC + C'D = BD

Note that ACD'+C'D is NOT a consensus pair because both C and D appear complemented and uncomplemented. Similarly, BC+B'C' is not a consensus pair.

So our equation, augmented with the consensus terms, becomes:

Y = AB'D' + ACD' + BC + B'C' + BD + C'D

How might we generate these terms through purely Boolean algrebraic manipulations? The technique is probably best see by looking at the simplest non-trivial case:

Y = AB + A'C
Y = AB(1+C) + A'C(1+B)
Y = AB + ABC + A'C + A'BC
Y = AB + A'C + (ABC + A'BC)
Y = AB + A'C + (A + A')BC
Y = AB + A'C + BC

It might be worth noting that a very brute force approach could be taken to producing consensus terms. Namely, go through every pair of terms and, if there exists a variable that is complemented in one and uncomplemented in the other, remove that variable and perform a logical AND on all of the remaining variables from both terms. So for the above example:

ACD' + BC => False (No complemented/uncomplemented variable)
A(C)D' + B'(C') => AB'D'
A(C)D' + (C')D => A(DD') = False
AC(D') + C'(D) => A(CC') = False
(B)C + (B')C' => (CC') = False
B(C) + B'(C') => (BB') = False
B(C) + (C')D => BD
B'C' + C'D => False (No complemented/uncomplemented variable)

Notice how terms that violate the requirement that there be only a single complemented/uncomplemented variable amongst the pair of terms take care of themselves since any other such variables force the consensus term to False.

Now that we know how to generate the consensus terms, let's examine how to identify consensus terms so that we can eliminate them, if that is our desire. We could apply the brute force approach and generate all of the consensus terms there are and then, having generated them, we would know that any existing terms that match them are, therefore, consensus terms themselves and can be eliminated. In practice, the easiest way to identify existing consensus terms is not far removed from this. Just as a little bit of practice allows you to quickly generate missing consensus terms, so too will that same practice allow you to generate all of the consensus terms and match them up against existing terms.

While this might be the practical way, it is worth understanding the rigorous Boolean algebraic way that a consensus term can be eliminated. This is basically done by reversing the steps shown in generating it and the concept is pretty simple -- a consensus terms is nothing but a term in which all of the combinations that it covers are also covered by other terms. So just break it up and then absorb the individual combinations into those other terms.

Y = AB + A'C + BC

Let's assume that we don't recognize that the BC term is actually a concensus term. We do know that if it IS a consensus term, that we must have at least two other terms, one that includes A and the other A'. So we can expand our potential consensus term as follows:

Y = AB + A'C + (A + A')BC
Y = AB + A'C + ABC + A'BC

Now we can see if we can simplify things by factoring out common combinations:

Y = (AB + ABC) + (A'C + A'BC)
Y = AB(1+C) + A'C(1+B)
Y = AB + A'C

It would not be too difficult to simply apply this technique to every term that MIGHT be a consensus term, requiring only that at least one pair of others terms exist having the needed complemented/uncomplemented variable that is missing in the candidate consensus term.

Blog entry information

Author
WBahn
Views
3,176
Last update

More entries in General

More entries from WBahn

Share this entry

Top