Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Majority Function is

1: A.B.¬C + A.¬B.C + ¬A.B.C + A.B.C

I can see intuitively that it can be simplified to

2: A.B + A.C + B.C

and thus A.(B + C) + B.C

but how can I use boolean algebra to get from one to the other?

This is where I get too so far

A.B.¬C + A.¬B.C + ¬A.B.C + A.B.C

= A.B.¬C + A.¬B.C + B.C.(¬A + A)

= A.B.¬C + A.¬B.C + B.C

= A(B.¬C + ¬B.C) + B.C

but I can't figure out how to rearrange the B.¬C + ¬B.C part to get the B + C that I need. Can anyone help?

share|improve this question
Closing as "too localized". I think for our target audience this question is uninteresting. –  Scott Morrison Dec 18 '09 at 19:59
add comment

closed as too localized by Scott Morrison Dec 18 '09 at 19:58

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 7 down vote accepted

Your argument has the right idea. If you do the same thing that you did for the pair of $A$ and $\neg A$ for $B$ and $C$ too, you get $$\neg A . B . C + A . B . C = B . C$$ $$A . \neg B . C + A . B . C = A . C$$ $$A . B . \neg C + A . B . C = A . B$$ Sum the three equations and use that $X + X = X$ for all $X$ in your Boolean algebra. Voilá!

share|improve this answer
Ah, I see then the three (A.B.C) terms simplify to one and I'm left with my #1 version. Thanks very much for your help! –  Martin Dec 18 '09 at 19:03
add comment

All such problems are trivial when expressed in a suitable formal system for propositional calculus.

For example, you might try expressing your problem in logical graphs — see here or here and here — then checking the required equation by using the four axioms of that system.


The lack of LaTeX in the comment boxes is a major headache, so I'll add my comments and elaborations here.

Comment 1

I'm guessing that you're using "+" for inclusive disjunction "$\lor$". This has turned out to be a bad practice, leading to major breaches of communication among mathematicians, computer scientists, and engineers. It is best to save "+" for the field operation, in this case corresponding to the operation of exclusive disjunction and the relation of logical inequality. Besides, we already have the symbol "$\lor$", so we might as vel use it.

Comment 2

Proceeding on the maxim, "Act Locally, Think Globally", let us take this very simple example as a paradigmatic case and use it to explore several themes involving the variety of formal systems that afford interpretation as propositional calculi.

One theme worth developing has to do with the choice among various "proof styles". Two dimensions of proof style that come to mind are these:

  • Equational Proofs vs. Implicational Proofs
  • Insight Proofs vs. Routine Proofs

Equational Proofs are those that use only 2-way inference rules. There is no loss of information in applying an equational rule of inference, and so the corresponding syntactic transformation is fully reversible.

Implicational Proofs are those that use 1-way inference rules like modus ponens. There is in general a loss of information in applying an implicational rule of inference.

Insight Proofs are those that require a modicum of cleverness or strategy on the part of the prover.

Routine Proofs are those that can be applied in a lock-step form of procedure or a straightforwardly methodical manner, suitable for automation by a mechanical prover.

Comment 3

The required equation between two expressions of the 3-majority function $f : \mathbb{B}^3 \to \mathbb{B}$ is proven below by means of equational inference steps in the syntax of logical graphs. I don't know if this is the best possible proof — it's simply the one that came to me first. The only bit of cleverness or "insight" required comes at the very beginning, where a step of "Reflection" or Double Negation is needed to prepare the ground. Everything after that is pretty much like rolling off a log. The axioms, theorems, and familiar names for the inference rules are given in this PlanetMath entry, also here if that doesn't work.

Majority Function Example Proof 1 Title Majority Function Example Proof 1 Frame 1 Equational Inference Reflect ab, ac, bc Majority Function Example Proof 1 Frame 2 Equational Inference Distribute (abc) Majority Function Example Proof 1 Frame 3 Equational Inference Collect ab, ac, bc Majority Function Example Proof 1 Frame 4 Equational Inference Quit (a), (b), (c) Majority Function Example Proof 1 Frame 5 Equational Inference Cancel (( )) Majority Function Example Proof 1 Frame 6 Equational Inference Weed ab, ac, bc Majority Function Example Proof 1 Frame 7 Equational Inference Delete a, b, c Majority Function Example Proof 1 Frame 8 Image:Equational Inference Cancel (( )) Majority Function Example Proof 1 Frame 9 Equational Inference QED

Here's an animated recap of the graphical transformations that occur in the above proof:

Majority Function Example 2.0 Animation

Further explanation of Proof 1 can be found here.

share|improve this answer
Your last edit message said "testing images 1 by 1", which is really something that is best done on faketestsite.stackexchange.com –  Anton Geraschenko Dec 24 '09 at 22:44
Got it. I made the mistake of trying to squeeze in a last minute bit of over-rushed work. I think they should be okay now. –  Jon Awbrey Dec 25 '09 at 1:15
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.