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). 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.
The majority function produces "1" when more than half of the inputs are 1; it produces "0" when more than half the inputs are 0. Most applications deliberately force an odd number of inputs so they don't have to deal with the question of what happens when exactly half the inputs are 0 and exactly half the inputs are 1. The few systems that calculate the majority function on an even number of inputs are often biased towards "0"—they produce "0" when exactly half the inputs are 0 -- for example, a 4-input majority gate has a 0 output only when two or more 0's appear at its inputs. In a few systems, a 4-input majority network randomly chooses "1" or "0" when exactly two 0's appear at its inputs.
For any x, y, and z, the ternary median operator 〈x, y, z〉 satisfies the following equations.
- 〈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, Leslie (1984). "Short monotone formulae for the majority function". Journal of Algorithms 5 (3): 363–366. doi:10.1016/0196-6774(84)90016-6.
- Peterson, William Wesley; Weldon, E.J. (1972). Error-correcting Codes. MIT Press. ISBN 9780262160391.
- Chaouiya, Claudine; Ourrad, Ouerdia; Lima, Ricardo (July 2013). "Majority Rules with Random Tie-Breaking in Boolean Gene Regulatory Networks". PLoS ONE 8 (7) (Public Library of Science). doi:10.1371/journal.pone.0069626.
- 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