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
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 at least 50% +1 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(n5.3) (Valiant 1984).
Properties
Among the properties of the ternary median operator < x,y,z > are:
- < x,y,y > = y
- < x,y,z > = < z,x,y >
- < x,y,z > = < x,z,y >
- < < 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: 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. Vol. 4.0. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 0-321-53496-4.