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. 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. ⟨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. 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⟩ 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. Thus, this formula is non-constructive. 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. Derandomize the Valiant proof of a monotone formula. ==External links== REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Majority function}, url = {https://encyclopegia.org/a/majority-function} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Majority function UR - https://encyclopegia.org/a/majority-function ER - CITE THIS ARTICLE ---------------- Cite this article: Majority function Derived from: https://en.wikipedia.org/w/index.php?oldid=1314507418 Licence: CC BY-SA 4.0 Snapshot: enwiki-001314507418 Permalink: /a/majority-function