Majority function

Majority function

In Boolean logic, the majority function (also called the median operator) is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise. Alternatively, representing true values as 1 and false values as 0, we may use the formula

\operatorname{Majority} \left ( p_1,\dots,p_n \right ) =  \left \lfloor \frac{1}{2} +  \frac{\sum_{i=1}^n  p_i - 1/2}{n} \right \rfloor.

The "−1/2" in the formula serves to break ties in favor of zeros when n is even; a similar formula can be used for a function that breaks ties in favor of ones.

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

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.

Contents

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(n5.3) (Valiant 1984). This is proved using probabilistic method. Thus, this formula is non-constructive. However, one can obtain an explicit formula for majority of polynomial size using a sorting network of Ajtai, Komlós, and Szemerédi.

Properties

Among the properties of the ternary median operator < x,y,z > are:

  1. < x,y,y > = y
  2. < x,y,z > = < z,x,y >
  3. < x,y,z > = < x,z,y >
  4. < < x,w,y > ,w,z > = < x,w, < y,w,z > >

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

References

See also

Media related to Majority functions at Wikimedia Commons


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Meijer G-function — In mathematics, the G function was introduced by Cornelis Simon Meijer (1936) as a very general function intended to include most of the known special functions as particular cases. This was not the only attempt of its kind: the generalized… …   Wikipedia

  • Smooth function — A bump function is a smooth function with compact support. In mathematical analysis, a differentiability class is a classification of functions according to the properties of their derivatives. Higher order differentiability classes correspond to …   Wikipedia

  • Tyranny of the majority — For the form of democracy, see Ochlocracy. For the Flesh Field album, see Tyranny of the Majority (album). The phrase tyranny of the majority (or tyranny of the masses ), used in discussing systems of democracy and majority rule, is a criticism… …   Wikipedia

  • God's utility function — is a phrase coined by Richard Dawkins in his book River Out of Eden. God s utility function is the third chapter in this book. Dawkins uses this phrase to expound the Gene centered view of evolution by equating the phrase to the meaning of life… …   Wikipedia

  • special function — ▪ mathematics       any of a class of mathematical functions (function) that arise in the solution of various classical problems of physics. These problems generally involve the flow of electromagnetic, acoustic, or thermal energy. Different… …   Universalium

  • Weighted Majority Algorithm — In machine learning, Weighted Majority Algorithm (WMA) is a meta learning algorithm used to construct a compound algorithm from a pool of prediction algorithms, which could be any type of learning algorithms, classifiers, or even real human… …   Wikipedia

  • Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

  • Post's lattice — In logic and universal algebra, Post s lattice denotes the lattice of all clones on a two element set {0, 1}, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941 [E. L. Post, The two valued …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”