In
Boolean logic
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
, the majority function (also called the
median
The median of a set of numbers is the value separating the higher half from the lower half of a Sample (statistics), data sample, a statistical population, population, or a probability distribution. For a data set, it may be thought of as the “ ...
operator) is the
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...
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

A ''majority gate'' is a
logical gate used in
circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
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
full adder
An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors, adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they ar ...
, 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
In computing, triple modular redundancy, sometimes called triple-mode redundancy, (TMR) is a fault-tolerant form of N-modular redundancy, in which three systems perform a process and that result is processed by a majority-voting system to produc ...
; they use the majority function for
majority logic decoding to implement
error correction
In information theory and coding theory with applications in computer science and telecommunications, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...
.
A major result in
circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
asserts that the majority function cannot be computed by
AC0 circuits 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.
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. In a few systems, the tie can be broken randomly.
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. 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.
See also
*
Boolean algebra (structure)
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a gen ...
*
Boolean algebras canonically defined
*
Boyer–Moore majority vote algorithm
*
Majority problem (cellular automaton)
Notes
References
*
External links
{{Commonscat-inline, Majority functions
Logic gates
Circuit complexity
Boolean algebra