1

When using the Consensus Theorem in Boolean algebra to minimize an expression, is it a legal move to find and add a redundant term to the expression and then use that term to find more redundant terms and then eliminate all of them?

For instance:
F = A'B + AC + B'A
 If XY = AC and X'Z = A'B, then YZ = BC, so:
F = A'B + AC + B'A + BC
 Then if XY = BC and X'Z = B'A, then YZ = AC
AC and BC are (possibly?) redundant terms, so drop them both:
F = A'B + B'A

Is this legal, or is it an odd hack/mathematical abomination?

NDro
  • 13

1 Answers1

1

There's something off, since the Venn diagrams don't match. You can legally do your first step. At that point, you may replace BC+B'A by BC+B'A+AC using consensus. There are now five terms, A'B+AC+BC+B'A+AC. Of course the two copies of AC may be combined, so at this point you just have four terms A'B+B'A+AC+BC. This time the Venns do match with the original A'B+AC+BA. [You now have four terms instead of the starting three, so perhaps not much was gained.] However there can't be a way to express the set in question without mentioning C somehow, as the Venn shows that C goes along a border of the final region and cuts it.

Note: In this example in a way the final +BC in A'B+AB'+AC+BC is redundant, since dropping it happens not to affect the resulting set. But I don't (immediately) see an "automatic" way to drop it using a simple rule. [I'm no expert on this consensus topic though.]

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • Thanks for your answer! So if I'm understanding you correctly, the problem is not that you can't use redundant terms to find more redundant terms, it's that you can't completely eliminate one of the terms (C in this case)? If there was an extra C term in the expression ("+ CD", maybe?) and one took the exact same steps, would it be a valid move then? – NDro Mar 17 '15 at 21:50
  • I think the consensus theorem only says XY+X'Z=XY+X'Z+YZ. So one can remove a term only if it is a product YZ for which there is some X for which (along with the term YZ one wants to remove) each of XY and X'Z are in the expression being worked on at that point. I don't think a single term C can be removed, C itself would have to be a product XY as above with the extra terms mentioned being present. – coffeemath Mar 17 '15 at 22:35
  • Issue has more to do with breaking boolean algebra rules. In the first step, he adds BC, which is redundant. Second step, he adds AC, which is Not redundant. It exists in original equation. X + X = X. It becomes a non-step. In general, it's better to expand all terms with missing terms and look for common terms to find a minterm solution. You can add a redundant term via consensus, but if you can't use the redundant term to minimize another unique term in the next step, it's probably a waste of energy. – StainlessSteelRat Apr 06 '15 at 10:48
  • @StainlessSteelRat I only see two steps here. From the first bold statement to the next is OK (using consensus rule). But from the second bold statement to the third, OP has simply dropped each of AC and BC at once, which is not justified via consensus. The way I see consensus is that one must use it carefully, only dropping a single term on any one step, and then only if two other terms are present (see my previous comment). – coffeemath Apr 06 '15 at 20:52
  • I agree. In the second step, consensus creates BC. The third step creates a second AC via consensus. AC is not redundant since it exists in the original equation. The 4th step is invalid. I'm not a big fan of expanding via consensus to minimize. But the approach would be valid if the BC created in step 2 was used to minimize the unused term (AC), but if it was possible there may be easier ways to minimize. – StainlessSteelRat Apr 07 '15 at 01:17
  • @StainlessSteelRat I thought of the AC as just "brought down" from the first bold statement, If we count that as another step, then the "third" step is the one from the second to third bold statement, at that step both terms AC, BC have been simultaneously dropped. It is true that consensus at that point allows one to drop either one of them individually, however after doing that there isn't a legal move to drop the other. So we can legally get back to the original A'B+AB'+AC, or to A'B+AB+BC. However from neither of these is there a legal consensus move to shorten it. – coffeemath Apr 07 '15 at 01:39
  • 1
    Agreed. It is minimal. – StainlessSteelRat Apr 07 '15 at 01:49