The iterative consensus non-optimal as it will return terms that is covered by prime implicants. An example of this is that cannot be absorbed. Here is a modified algorithm that adds polynomial complexity:
- Let and be two disjoint list. The induction assumption is that contain only essential terms.
- For all pairs , calculate . Place the resulting term in:
- . Then perform absorption on .
- For all pairs , perform absorption. If any absorbent is in , then the result is in .
- If .
- If no new terms appear in step 2 or 3, stop and output . Otherwise go to 2.
The proof of this being correct goes as follows:
If all terms in iteration are essential, then all terms in iteration are essential.
Proof. Consider the following steps:
- We first show that no non-essential terms can be in in after the th iteration. Assume that we add a term that is non-essential to . By 2.a, at least one of the consensus terms, let this be (wlog), yielding z′ must be essential. If , then must cover . Now, is absorbed into . is non-essential by assumption, but it is the only one covering the value that made essential. Contradiction.
- We now show that no essential terms are in . We proceed in the same manner by assuming that is essential. Since , two cases appear: (a) it is a consensus of two non-essential terms, which clearly not is essential or (b) one term is essential and one term is not . If , can only cover a subset of and cannot be essential.
The algorithm presented above returns an optimal expression of any essential terms.
Proof. By the Induction axiom in conjunction with the assumption that all initial terms were essential and Proposition 1, we see that contains all essential terms at all iterations. Thus, it will contain all essential term at the end of the execution algorithm.
If you find a counterexample or an error in the steps of the proof, please report it!