Talk:Majority function

I have no idea what this is supposed to be for. The article was not written clearly at all. Maybe if it could be cleaned up a bit, it'd could be put back --Jzcool

Revision 4 seems to be more readable: we should have some stuff on its uses, such as reliable systems engineering -- The Anome

---

The Article states that
"The value of the operation is false when n/2 or fewer arguments are false, and true otherwise."
Shouldn't this be either
"is false when n/2 or fewer arguments are true, and true otherwise."
or
"is false when n/2 or more arguments are false, and true otherwise."
--79.210.246.99 (talk) 20:42, 15 March 2008 (UTC)

---

Is it true that the majority function can be evaluated by a boolean circuit of size O(n) with AND and OR gates ? If so, I think it should be written in the article. — Preceding unsigned comment added by Staskikotx (talk • contribs) 13:35, 15 February 2012 (UTC)

---

Reading the article it is stated that: "A majority gate returns true if and only if more than 50% of its inputs are true." However in 'Exploring the Limits of Efficient Algorithms', ISBN 3-540-21045-8, from 2005, on page 263 the author states that "The majority function has the value 1 if and only if the input contains at least as many 1's as 0's." Are there different types of the majority function or do I simply miss the point? ErnieFromV (talk) 23:09, 17 February 2012 (UTC)

---

Maybe add a sample circuit using basic gates(AND,OR,NAND etc) for a small value like 3 Lordvig (talk) 15:16, 9 August 2015 (UTC)

Dubious claim

"For n = 3 the ternary median operator can be expressed using conjunction and disjunction as xy + yz + zx. Remarkably this expression denotes the same operation independently of whether the symbol + is interpreted as inclusive or or exclusive or."

This really does not seem right. Unless I'm missing something big here, if the + is exclusive the resulting expression is an "exactly 2" operator which is not monotonic as it returns false if all three inputs are true; only if + is inclusive do we get the monotonic median operator, which returns true if all three inputs are true.

If I am missing something, a citation and some clarification would probably be nice. Since the statement is unsourced, I added a "citation needed". Starprizm (talk) 15:09, 20 July 2024 (UTC)

I removed this claim. I think you are correct that it is false. —David Eppstein (talk) 19:49, 20 July 2024 (UTC)

Hello,

The claim is true when using XOR for the operation for n = 3.

Here are the possibilities for all inputs:

- If all inputs are false (0) then the output will be zero (0 XOR 0 XOR 0 = 0).

- If only one input is true and the other two are false, then the output will be zero as none of the clauses are satisfied (0 XOR 0 XOR 0 = 0)

- If exactly 2 inputs are true and the third is false, then only one of the 3 clauses will be satisfied, and hence the output will be true (1 XOR 0 XOR 0 = 1 XOR 0 = 1).

- If all three inputs are true, then all 3 clauses will be true, and the output will be (1 XOR 1 XOR 1 = 1 XOR 0 = 1).

Hence using XOR results in the same truth table and therefore implements the same operation.

The counter-intuitive point is that it is impossible for exactly 2 clauses to be satisfied (let's say the first 2 are - xy and xz, this implies that x=y=z=1 and hence the third clause must also be satisfied).

For other n (n = 5 for example), this does not apply:

f(a,b,c,d,e) = abc + abd + abe + acd + ace + ade + bcd + bce + bde + cde

If all inputs are true (a=b=c=d=e=1), then all 10 clauses are true, but since there is an even number of clauses, using XOR would result in an output of false (0).

So, this is more of a special case for n=3. ~2026-19305-85 (talk) 14:41, 27 March 2026 (UTC)