Majority function

In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of the inputs. Representing true values as 1 and false values as 0, we may use the (real-valued) formula:

${\displaystyle \langle p_{1},\dots ,p_{n}\rangle =\operatorname {Majority} \left(p_{1},\dots ,p_{n}\right)=\left\lfloor {\frac {1}{2}}+{\frac {\left(\sum _{i=1}^{n}p_{i}\right)-1/2}{n}}\right\rfloor .}$

The "−1/2" in the formula serves to break ties in favor of zeros when the number of arguments 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.

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. ^[1] In a few systems, the tie can be broken randomly. ^[2]

Boolean circuits

Three-bit majority circuit

Four-bit majority circuit

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.

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.

Many systems have triple modular redundancy; they use the majority function for majority logic decoding to implement error correction.

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

Properties

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.

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). This is proved using probabilistic method. Thus, this formula is non-constructive. ^[3]

Approaches exist for an explicit formula for majority of polynomial size:

• Take the median from a sorting network, where each compare-and-swap "wire" is simply an OR gate and an AND gate. The Ajtai – Komlós – Szemerédi (AKS) construction is an example.
• Combine the outputs of smaller majority circuits. ^[4]
• Derandomize the Valiant proof of a monotone formula. ^[5]

See also

• Boolean algebra (structure)
• Boolean algebras canonically defined
• Boyer–Moore majority vote algorithm
• Majority problem (cellular automaton)

Notes

1. Peterson, William Wesley; Weldon, E.J. (1972). Error-correcting Codes . MIT Press. ISBN   9780262160391.
2. Chaouiya, Claudine; Ourrad, Ouerdia; Lima, Ricardo (July 2013). "Majority Rules with Random Tie-Breaking in Boolean Gene Regulatory Networks". PLOS ONE. Public Library of Science. 8 (7): e69626. doi: 10.1371/journal.pone.0069626 . PMC   3724945 .
3. 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.
4. Amano, Kazuyuki (2018). "Depth Two Majority Circuits for Majority and List Expanders". 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 117 (81): 1–13. doi:10.4230/LIPIcs.MFCS.2018.81.
5. Hoory, Shlomo; Magen, Avner; Pitassi, Toniann (2006). "Monotone Circuits for the Majority Function". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 4110. Springer. pp. 410–425. doi:10.1007/11830924_38. ISBN   978-3-540-38044-3.

References

• Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. Vol. 4a. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN   978-0-321-53496-5.

External links

Media related to Majority functions at Wikimedia Commons