Simplification of majority function(boolean).

Question

I have a boolean expression $$ABC+AB\bar C +A\bar B C+\bar A BC$$ This gives the majority boolean operator. That is it returns true when two or more of $A,B,C$ are true. I simplify it as $$AB+C(A\bar B+\bar AB)$$

I cannot show that it is equivalent to $$AB+BC+CA$$ i.e standard representation of majority function.

Answer 1

It's been a while since I've done Boolean algebra, but I think this will work (using the fact that $A=A+A$):

$$ \begin{align} ABC + AB\bar C +A \bar B C + \bar ABC &= ABC + AB\bar C + ABC + \bar ABC + ABC +A\bar BC\\[0.5ex] &=AB(C+\bar C)+BC(A+\bar A)+CA(B+\bar B)\\[0.5ex] &=AB + BC + CA \end{align} $$

Answer 2

Because of:

Idempotence

$P+P=P$

, you can duplicate any terms.

So effectively, you can try and find any combination of terms to simplify.

That is, you got $AB$ by combining the first two terms $ABC$ and $AB\bar C$

This is actually an instance of:

Adjacency

$PQ+P\bar Q = P$

However, combining terms using Adjacency does not mean that those terms are now 'gone' and that you can't reuse them.

Indeed, we can also combine the first term $ABC$ with the third $A \bar B C$ into $AC$

And, the first can be combined with the last term to get $BC$

Once you understand this, you'll find that you can directly go from

$$ABC+AB\bar C +A\bar B C+\bar A BC$$

to

$$AB+BC+AC$$

in just one step using three instances of Adjacency