Editing Majority function

{{Short description|Boolean 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.

== Boolean circuits ==
[[File:Majority Logic.png|thumb|right|Three-bit majority circuit]]
[[File:Four-Bit Majority Circuit.png|thumb|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 [[Adder (electronics)|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|AC0 circuits]] of subexponential size.

== Properties ==

For any ''x'', ''y'', and ''z'', the ternary median operator &lang;''x'', ''y'', ''z''&rang; satisfies the following equations.
* &lang;''x'', ''y'', ''y''&rang; = ''y''
* &lang;''x'', ''y'', ''z''&rang; = &lang;''z'', ''x'', ''y''&rang;
* &lang;''x'', ''y'', ''z''&rang; = &lang;''x'', ''z'', ''y''&rang;
* &lang;&lang;''x'', ''w'', ''y''&rang;, ''w'', ''z''&rang; = &lang;''x'', ''w'', &lang;''y'', ''w'', ''z''&rang;&rang;

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

Other useful properties of the ternary median operator function include:
* given &lang;''x'', ''y'', ''z''&rang; = ''w'',  &lang;''x'', ''y'', ''w''&rang; = ''z''
* &lang;''¬x'', ''¬y'', ''¬z''&rang; = ¬&lang;''x'', ''y'', ''z''&rang;
* &lang;''x'', ''y'', ''x'' ⊕ ''y'' ⊕ ''z''&rang; = &lang;''x'', ''y'', ''¬z''&rang;
* &lang;''¬x'', ''y'', ''x'' ⊕ ''y'' ⊕ ''z''&rang; = &lang;''¬x'', ''y'', ''z''&rang;

== Ties ==
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.<ref>{{cite book |last1=Peterson |first1=William Wesley |url=https://archive.org/details/errorcorrectingc00pete |title=Error-correcting Codes |last2=Weldon |first2=E.J. |publisher=MIT Press |year=1972 |isbn=9780262160391 |url-access=registration}}</ref> In a few systems, the tie can be broken randomly.<ref>{{cite journal |last1=Chaouiya |first1=Claudine |last2=Ourrad |first2=Ouerdia |last3=Lima |first3=Ricardo |date=July 2013 |title=Majority Rules with Random Tie-Breaking in Boolean Gene Regulatory Networks |journal=PLOS ONE |publisher=Public Library of Science |volume=8 |pages=e69626 |doi=10.1371/journal.pone.0069626 |pmc=3724945 |doi-access=free |number=7|pmid=23922761 |bibcode=2013PLoSO...869626C }}</ref>

== 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''.

For an arbitrary ''n'' there exists a monotone formula for majority of size O(''n''<sup>5.3</sup>). This is proved using [[probabilistic method]]. Thus, this formula is non-constructive.<ref>{{Cite journal | first = Leslie | last = Valiant | author-link = Leslie Valiant | title = Short monotone formulae for the majority function | journal = Journal of Algorithms | volume = 5 | issue = 3 | year = 1984 | pages = 363–366 | doi = 10.1016/0196-6774(84)90016-6}}</ref>

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 [[Miklós Ajtai|Ajtai]]&ndash;[[János Komlós (mathematician)|Komlós]]&ndash;[[Endre Szemerédi|Szemerédi]] (AKS) construction is an example.
* Combine the outputs of smaller majority circuits.<ref>{{cite journal |last1=Amano |first1=Kazuyuki |title=Depth Two Majority Circuits for Majority and List Expanders |journal=43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |date=2018 |volume=117 |issue=81 |pages=1–13 |doi=10.4230/LIPIcs.MFCS.2018.81 |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik|doi-access=free }}</ref>
* Derandomize the Valiant proof of a monotone formula.<ref>{{cite book |last1=Hoory |first1=Shlomo |last2=Magen |first2=Avner |last3=Pitassi |first3=Toniann |title=Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |chapter=Monotone Circuits for the Majority Function |series=Lecture Notes in Computer Science |date=2006 |volume=4110 |pages=410–425 |doi=10.1007/11830924_38 |chapter-url=https://www.researchgate.net/publication/221462555 |publisher=Springer |isbn=978-3-540-38044-3 |language=en}}</ref>

== See also ==
* [[Boolean algebra (structure)]]
* [[Boolean algebras canonically defined]]
* [[Boyer–Moore majority vote algorithm]]
* [[Majority problem (cellular automaton)]]

== Notes ==
{{Reflist}}

== References ==
* {{cite book | last=Knuth | first=Donald E. | author-link=Donald Knuth | title=Introduction to combinatorial algorithms and Boolean functions | series=[[The Art of Computer Programming]] | volume=4a | year=2008 | isbn=978-0-321-53496-5 | pages=64–74 | publisher=Addison-Wesley | location=Upper Saddle River, NJ }}
==External links==
{{Commonscat-inline|Majority functions}}

[[Category:Logic gates]]
[[Category:Circuit complexity]]
[[Category:Boolean algebra]]