Majority function

In Boolean logic, the majority function (also called the median operator) is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise. Alternatively, representing true values as 1 and false values as 0, we may use the formula

$\operatorname{Majority} \left ( p_1,\dots,p_n \right ) = \left \lfloor \frac{1}{2} + \frac{\sum_{i=1}^n p_i - 1/2}{n} \right \rfloor.$

The "−1/2" in the formula serves to break ties in favor of zeros when n is even; a similar formula can be used for a function that breaks ties in favor of ones.

A major result in circuit complexity asserts that this function cannot be computed by AC0 circuits of subexponential size.

A majority gate is a logical gate used in circuit complexity and other applications of Boolean circuits. A majority gate returns true if and only if more than 50% of its inputs are true.

Monotone formulae for majority

For n = 1 the median operator is just the unary identity operation x. 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.

For an arbitrary n there exists a monotone formula for majority of size O(n^5.3) (Valiant 1984). This is proved using probabilistic method. Thus, this formula is non-constructive. However, one can obtain an explicit formula for majority of polynomial size using a sorting network of Ajtai, Komlós, and Szemerédi.

Properties

Among the properties of the ternary median operator < x,y,z > are:

1. < x,y,y > = y
2. < x,y,z > = < z,x,y >
3. < x,y,z > = < x,z,y >
4. < < x,w,y > ,w,z > = < x,w, < y,w,z > >

An abstract system satisfying these as axioms is a median algebra.

References

• Valiant, L. (1984). "Short monotone formulae for the majority function". Journal of Algorithms 5 (3): 363–366. doi:10.1016/0196-6774(84)90016-6 .
• Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. 4.0. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 0-321-53496-4. 

See also

Media related to Majority functions at Wikimedia Commons

• Boolean algebra (structure)
• Boolean algebras canonically defined
• Majority problem (cellular automaton)