# Majority function > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Majority_function > Markdown URL: https://mediated.wiki/source/Majority_function.md > Source: https://en.wikipedia.org/wiki/Majority_function > Source revision: 1314507418 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Boolean function}} In [Boolean logic](/source/Boolean_logic), the '''majority function''' (also called the '''[median](/source/median)''' '''operator''') is the [Boolean function](/source/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 == thumb|right|Three-bit majority circuit thumb|Four-bit majority circuit A ''majority gate'' is a [logical gate](/source/logical_gate) used in [circuit complexity](/source/circuit_complexity) and other applications of [Boolean circuits](/source/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](/source/Adder_(electronics)), 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](/source/triple_modular_redundancy); they use the majority function for [majority logic decoding](/source/majority_logic_decoding) to implement [error correction](/source/error_correction). A major result in [circuit complexity](/source/circuit_complexity) asserts that the majority function cannot be computed by [AC0 circuits](/source/AC0) 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](/source/median_algebra). Other useful properties of the ternary median operator function include: * given ⟨''x'', ''y'', ''z''⟩ = ''w'', ⟨''x'', ''y'', ''w''⟩ = ''z'' * ⟨''¬x'', ''¬y'', ''¬z''⟩ = ¬⟨''x'', ''y'', ''z''⟩ * ⟨''x'', ''y'', ''x'' ⊕ ''y'' ⊕ ''z''⟩ = ⟨''x'', ''y'', ''¬z''⟩ * ⟨''¬x'', ''y'', ''x'' ⊕ ''y'' ⊕ ''z''⟩ = ⟨''¬x'', ''y'', ''z''⟩ == 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.{{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=978-0-262-16039-1 |url-access=registration}} In a few systems, the tie can be broken randomly.{{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 |article-number=e69626 |doi=10.1371/journal.pone.0069626 |pmc=3724945 |doi-access=free |number=7|pmid=23922761 |bibcode=2013PLoSO...869626C }} == 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''5.3). This is proved using [probabilistic method](/source/probabilistic_method). Thus, this formula is non-constructive.{{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}} Approaches exist for an explicit formula for majority of polynomial size: * Take the median from a [sorting network](/source/sorting_network), where each compare-and-swap "wire" is simply an OR gate and an AND gate. The [Ajtai](/source/Mikl%C3%B3s_Ajtai)–[Komlós](/source/J%C3%A1nos_Koml%C3%B3s_(mathematician))–[Szemerédi](/source/Endre_Szemer%C3%A9di) (AKS) construction is an example. * Combine the outputs of smaller majority circuits.{{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 }} * Derandomize the Valiant proof of a monotone formula.{{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}} == See also == * [Boolean algebra (structure)](/source/Boolean_algebra_(structure)) * [Boolean algebras canonically defined](/source/Boolean_algebras_canonically_defined) * [Boyer–Moore majority vote algorithm](/source/Boyer%E2%80%93Moore_majority_vote_algorithm) * [Majority problem (cellular automaton)](/source/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](/source/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 --- Adapted from the Wikipedia article [Majority function](https://en.wikipedia.org/wiki/Majority_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Majority_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.