Majority function

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1314507418 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.