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. If the term "−1/2" is omitted, the formula can be used for a function that breaks ties in favor of ones.
For instance, in a full adder, the carry output is found by applying a majority function to the three inputs, although frequently this part of the adder is broken down into several simpler logical gates.
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). 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.
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.
- 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 4a. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 0-321-53496-4.
Media related to Majority functions at Wikimedia Commons